Statistics
| Branch: | Revision:

## root / latex / STL_book_note.tex @ d1ed66aa

1 2 3 d1ed66aa Quynh PX Nguyen \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}