Statistics
| Branch: | Revision:

## root / latex / STL_book_note.tex @ d1ed66aa

 1 \documentclass[12pt]{article} \usepackage{booktabs} \usepackage{listings} \usepackage{color} \definecolor{codegreen}{rgb}{0,0.6,0} \definecolor{codegray}{rgb}{0.5,0.5,0.5} \definecolor{codepurple}{rgb}{0.58,0,0.82} \definecolor{backcolour}{rgb}{0.95,0.95,0.92} \lstdefinestyle{mystyle}{ language=C++, backgroundcolor=\color{backcolour}, commentstyle=\color{codegreen}, keywordstyle=\color{magenta}, numberstyle=\tiny\color{codegray}, stringstyle=\color{codepurple}, % basicstyle=\footnotesize, % basicstyle=\scriptsize, basicstyle=\ttfamily\footnotesize, breakatwhitespace=false, breaklines=true, captionpos=b, keepspaces=true, numbers=left, numbersep=5pt, showspaces=false, showstringspaces=false, showtabs=false, tabsize=2 } \lstset{style=mystyle} \usepackage[colorlinks]{hyperref} % from http://tex.stackexchange.com/questions/3568/how-does-one-typeset-a-url \hypersetup{citecolor=pink} \hypersetup{linkcolor=red} \hypersetup{urlcolor=blue} \usepackage{cleveref} \begin{document} \title{ Book Note STL Tutorial and Reference Guide (1996) David R. Musser, Atul Saini. } \author{Quynh PX Nguyen quynh.xq@gmail.com} \maketitle \clearpage \section{Chapter 1} \subsection{Template} \subsubsection{Template Functions} \begin{lstlisting} template const T& custom_max(const T& x, const T& y) { return x < y ? y : x; } \end{lstlisting} \subsubsection{Template Member Functions} \section{Chapter 2 - Overview of STL Components} \subsection{From the official documentation} \href{http://www.sgi.com/tech/stl/doc_introduction.html}{Introduction from the Official Documentation} The STL documentation classifies components in two ways. \textbf{Categories} are a classification by functionality. The categories are: \begin{itemize} \item Container \item Iterator \item Algorithm \item Function Object \item Utility \item Adaptor \item Allocator \end{itemize} \textbf{Component types} are a structural classification: one based on what kind of C++ entity (if any) a component is. The component types are: \begin{itemize} \item Type (i.e. a \lstinline{struct} or \lstinline{class}). Ex: \lstinline{vector}. Read more \href{http://www.sgi.com/tech/stl/Vector.html}{here} Ex: \lstinline{input_iterator}. \item Function. Ex: \lstinline{find} function \item Concept. Ex: \lstinline{Container}. Read more \href{http://www.sgi.com/tech/stl/Container.html}{here} \end{itemize} \lstinline{Concept} is kind of the definition. And then \lstinline{Type} is the ???materialized version of each concept. \lstinline{Function} is the implementation that receives some input, and returns some output. It is misleading to think that the component type of one specific \emph{function objects}, such as \lstinline{plus} belongs to \emph{Function}. Actually, \lstinline{plus} is a \emph{Type} \begin{table}[h] \centering \begin{tabular}{|l|l|l|} \toprule Name & Category & Component Types \\ \midrule Sequence & Container & Concept \\ vector & Container & Type \\ Input Iterator & Iterators & Concept \\ input\_iterator & Iterators & Type \\ distance & Algorithms, Iterators & Function \\ find, find\_if & Algorithms & Function \\ Binary Function & Functors & Concept \\ Adaptable Generator & Functors & Concept \\ Predicate & Functors & Concept \\ plus (predefined function objects) & Functors & Type \\ \bottomrule \end{tabular} \end{table} \subsubsection{Function Objects} Just as iterators are a generalization of pointers, function objects are a generalization of functions: a function object is anything that you can call using the ordinary function call syntax. There are several different concepts relating to function objects, including \texttt{Unary Function} (a function object that takes a single argument, i.e. one that is called as f(x)) and \texttt{Binary Function} (a function object that takes two arguments, i.e. one that is called as f(x, y)). Function objects are an important part of generic programming because they \textbf{allow abstraction} not only over the types of objects, but also \textbf{over the operations} that are being performed. \subsubsection{More about \emph{Concepts}} \lstinline{Find} isn't the only STL algorithm that has such a set of requirements; the arguments to \lstinline{for_each} and \lstinline{count}, and other algorithms, must satisfy the same requirements. These requirements are sufficiently important that we give them a name: we call such a set of type requirements a concept, and we call this particular concept \texttt{Input Iterator}. We say that a type conforms to a concept, or that it is a model of a concept, if it satisfies all of those requirements. We say that \lstinline{int*} is a model of Input Iterator because \lstinline{int*} provides all of the operations that are specified by the \texttt{Input Iterator} requirements. the author of \lstinline{find} only has to consider the interface specified by the concept \texttt{Input Iterator}, rather than the implementation of every possible type that conforms to that concept. Similarly, if you want to use \lstinline{find}, you need only to ensure that the arguments you pass to it are models of \texttt{Input Iterator}. Container classes, like iterators, are organized into a hierarchy of concepts. All containers are models of the concept \texttt{Container}; more refined concepts, such as \texttt{Sequence} and \texttt{Associative Container}, describe specific types of containers. \subsection{From the book} \subsubsection{Containers} Sequence Containers Sorted Associative Containers \subsubsection{Generic Algorithms} \subsubsection{Iterators} \subsubsection{Function Objects} This one is also known as \emph{functors} passing a \emph{function object} \textbf{function object} can carry with them additional information that an ordinary function cannot. \subsubsection{Adaptors} \lstinline{1 << 26} = $2^{26}$ I don't really get why defining the \lstinline{reverse_iterator} has to be that difficult And what is the difference between \lstinline{vector::reverse_iterator} and \lstinline{reverse_iterator::iterator, ... >} \begin{lstlisting} reverse_iterator::iterator, float, float&, ptrdiff_t> first(vector1.end()), last(vector1.begin()); // Meaning vector::iterator // this is the container type's iterator TYPE float // corresponding value type float& // reference type for the value type ptrdiff_t // distance type for the iterator type = differences between iterator values first // variable of type reverse_iterator::iterator, float, float&, ptrdiff_t> \end{lstlisting} \section{Chapter 3 - How STL Differs from Other Libraries} each container provides some category of iterators. each algorithm works with some category of iterators. So the data structure is separated from the algorithm. \section{Chapter 4 - Iterators} \section{Chapter 5 - Generic Algorithms} Nonmutating Sequence Algorithms: \lstinline{find, adjacent_find, count, for_each, mismatch, equal, search} Mutating Sequence Algorithms: \begin{itemize} \item \lstinline{copy, copy_backward} \item \lstinline{fill, fill_n} \item \lstinline{generate} \end{itemize} [pg. 86] I don't understand why the \lstinline{operator()} in class \lstinline{calc_square} can be invoked \end{document}