Statistics
| Branch: | Revision:

root / latex / STL_book_note.tex @ d1ed66aa

History | View | Annotate | Download (8.06 KB)

1
\documentclass[12pt]{article}
2
\usepackage{booktabs}
3
\usepackage{listings}
4
\usepackage{color}
5
\definecolor{codegreen}{rgb}{0,0.6,0}
6
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
7
\definecolor{codepurple}{rgb}{0.58,0,0.82}
8
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}
9
\lstdefinestyle{mystyle}{
10
    language=C++,
11
    backgroundcolor=\color{backcolour},
12
    commentstyle=\color{codegreen},
13
    keywordstyle=\color{magenta},
14
    numberstyle=\tiny\color{codegray},
15
    stringstyle=\color{codepurple},
16
    % basicstyle=\footnotesize,
17
    % basicstyle=\scriptsize,
18
    basicstyle=\ttfamily\footnotesize,
19
    breakatwhitespace=false,
20
    breaklines=true,
21
    captionpos=b,
22
    keepspaces=true,
23
    numbers=left,
24
    numbersep=5pt,
25
    showspaces=false,
26
    showstringspaces=false,
27
    showtabs=false,
28
    tabsize=2
29
}
30
\lstset{style=mystyle}
31

    
32

    
33
\usepackage[colorlinks]{hyperref}       % from http://tex.stackexchange.com/questions/3568/how-does-one-typeset-a-url
34
\hypersetup{citecolor=pink}
35
\hypersetup{linkcolor=red}
36
\hypersetup{urlcolor=blue}
37
\usepackage{cleveref}
38

    
39
\begin{document}
40

    
41
\title{
42
    Book Note
43
    STL Tutorial and Reference Guide (1996)
44
    David R. Musser, Atul Saini.
45
}
46

    
47
\author{Quynh PX Nguyen  quynh.xq@gmail.com}
48

    
49
\maketitle
50

    
51
\clearpage
52

    
53

    
54
\section{Chapter 1}
55
    \subsection{Template}
56
        \subsubsection{Template Functions}
57
            \begin{lstlisting}
58
template <class T>
59
const T& custom_max(const T& x, const T& y)
60
{
61
    return x < y ? y : x;
62
}
63
            \end{lstlisting}
64

    
65
        \subsubsection{Template Member Functions}
66

    
67

    
68
\section{Chapter 2 - Overview of STL Components}
69
    \subsection{From the official documentation}
70
        \href{http://www.sgi.com/tech/stl/doc_introduction.html}{Introduction from the Official Documentation}
71

    
72
         The STL documentation classifies components in two ways.
73

    
74
        \textbf{Categories} are a classification by functionality. The categories are:
75
        \begin{itemize}
76
            \item Container
77
            \item Iterator
78
            \item Algorithm
79
            \item Function Object
80
            \item Utility
81
            \item Adaptor
82
            \item Allocator
83
        \end{itemize}
84

    
85
        \textbf{Component types} are a structural classification: one based on what kind of C++ entity (if any) a component is. The component types are:
86
        \begin{itemize}
87
            \item Type (i.e. a \lstinline{struct} or \lstinline{class}).
88

    
89
            Ex: \lstinline{vector<T, Alloc>}. Read more \href{http://www.sgi.com/tech/stl/Vector.html}{here}
90

    
91
            Ex: \lstinline{input_iterator<T, Distance>}.
92

    
93
            \item Function. Ex: \lstinline{find} function
94
            \item Concept. Ex: \lstinline{Container}. Read more \href{http://www.sgi.com/tech/stl/Container.html}{here}
95
        \end{itemize}
96

    
97
        \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.
98

    
99
        It is misleading to think that the component type of one specific \emph{function objects}, such as \lstinline{plus<T>} belongs to \emph{Function}. Actually, \lstinline{plus<T>} is a \emph{Type}
100

    
101
        \begin{table}[h]
102
        \centering
103
            \begin{tabular}{|l|l|l|}
104
            \toprule
105
                Name & Category & Component Types \\
106
            \midrule
107
                Sequence & Container & Concept \\
108
                vector & Container & Type \\
109
                Input Iterator & Iterators & Concept \\
110
                input\_iterator & Iterators & Type \\
111
                distance & Algorithms, Iterators & Function \\
112
                find, find\_if & Algorithms & Function \\
113
                Binary Function & Functors & Concept \\
114
                Adaptable Generator & Functors & Concept \\
115
                Predicate & Functors & Concept \\
116
                plus<T> (predefined function objects) & Functors & Type \\
117
            \bottomrule
118
            \end{tabular}
119
        \end{table}
120

    
121
        \subsubsection{Function Objects}
122
            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.
123

    
124
            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.
125

    
126
        \subsubsection{More about \emph{Concepts}}
127
            \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.
128

    
129
            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}.
130

    
131
            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.
132

    
133
    \subsection{From the book}
134
        \subsubsection{Containers}
135
            Sequence Containers
136

    
137
            Sorted Associative Containers
138

    
139
        \subsubsection{Generic Algorithms}
140

    
141
        \subsubsection{Iterators}
142

    
143
        \subsubsection{Function Objects}
144

    
145
            This one is also known as \emph{functors}
146

    
147
            passing a \emph{function object}
148

    
149
            \textbf{function object} can carry with them additional information that an ordinary function cannot.
150

    
151
        \subsubsection{Adaptors}
152
            \lstinline{1 << 26} = $2^{26}$
153

    
154
            I don't really get why defining the \lstinline{reverse_iterator} has to be that difficult
155

    
156
            And what is the difference between \lstinline{vector<float>::reverse_iterator} and \lstinline{reverse_iterator<vector<float>::iterator, ... >}
157

    
158
            \begin{lstlisting}
159
reverse_iterator<vector<float>::iterator, float,
160
                float&, ptrdiff_t> first(vector1.end()), last(vector1.begin());
161

    
162
// Meaning
163
vector<float>::iterator // this is the container type's iterator TYPE
164
float // corresponding value type
165
float& // reference type for the value type
166
ptrdiff_t // distance type for the iterator type = differences between iterator values
167
first // variable of type reverse_iterator<vector<float>::iterator, float,
168
                float&, ptrdiff_t>
169
            \end{lstlisting}
170

    
171

    
172
\section{Chapter 3 - How STL Differs from Other Libraries}
173
    each container provides some category of iterators.
174
    each algorithm works with some category of iterators.
175

    
176
    So the data structure is separated from the algorithm.
177

    
178

    
179
\section{Chapter 4 - Iterators}
180

    
181
\section{Chapter 5 - Generic Algorithms}
182
    Nonmutating Sequence Algorithms: \lstinline{find, adjacent_find, count, for_each, mismatch, equal, search}
183

    
184
    Mutating Sequence Algorithms:
185
    \begin{itemize}
186
        \item \lstinline{copy, copy_backward}
187
        \item \lstinline{fill, fill_n}
188
        \item \lstinline{generate}
189
    \end{itemize}
190

    
191
    [pg. 86] I don't understand why the \lstinline{operator()} in class \lstinline{calc_square} can be invoked
192

    
193
\end{document}