[STL source code analysis] summary notes (1): Opening

00 Write it at the front

STL As C++ An important part of the standard library , I'm learning C++ The process is very important . This reusable component library is more like an all inclusive “ frame ”.

Mr. Houjie is interested in STL I have benefited a lot from my deep understanding of . and 《STL Source analysis 》 This book is also a collection of essence , Explored in depth for STL Every part of . It is very good to eat with the teacher's video .

From here on , I want to sort out the main contents of videos and books and record some understanding parts . Because the video part does not coincide with the book part , Each has its own essence , So it's worth integrating to understand and learn .

Study STL Readers need to have a certain C++ Basic ability , And there are some uses STL Experience , In this way, we can better see the essence through the phenomenon in the learning process , understand STL Local operation mechanism .（STL The user guide recommends cppreference.com）

I'm sorry for STL The reading ability of the source code is not very high , Therefore, in the summary, we will try to focus on the understanding of the concept after analysis as easily as possible , Do not focus on a large number of source code analysis . Students interested in the source code can read deeply SGI STL Source code .

01 STL summary

meaning

STL Is a reusable Standard Template Library , A conceptual structure set up on the basis of universal thinking , Make abstract concepts the subject , And make it systematic .

Six components

STL There are six components , It can be combined and applied to each other , Cooperation .

Containers （containers）： The most common structure we usually have , For storing data , It includes all kinds of such as vector,list,deque,set,map And so on .

distributor （allocators）： We may not use it often, but it exists in every container , Realize dynamic space configuration 、 Space management 、 Space release .

Algorithm （algorithms）： A lot of features （ How to operate data ） Being independent , Become an algorithm .

iterator （iterators）： The algorithm needs to process the data in the container , Iterators are bridges between algorithms and data . It can be understood as a generalized pointer .

functor （functors）： Custom type calculations , Some strategy of the algorithm , Internal is overloaded .

Adapter （Adapter）： Used to convert , Modify the interface , Can convert containers 、 functor 、 iterator . such as stack and queue The bottom layer of is with the help of deque Accomplished , Belongs to container adapter .

Simple and vivid examples

An example can well show the use of all components .

#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>

using namespace std;

int main()
{
    int ia[6]={27,210,12,47,109,83};
    vector<int,alloctor<int>>vi(ia,ia+6);//1
    cout << cout_if(vi.begin(),vi.end().not1(bind2nd(less<int>(),40)));//2
    return 0;
}

explain ：

1. A container is defined here vector, hinder <> Pass on the reference . The first parameter is the data type , Allocator for the second template parameter （ It is generally ignored and not written , The source code has default values ）

The allocator itself is a template , Pass it on alloctor, To match the former .

2.count_if() It's an algorithm , Calculate the number of elements that meet the conditions under the conditions .

The range of operations required is vi Of begin() and end(), Here is the generalized pointer , That is to say iteraotr, Used to point to the head and tail （ Note that the interval here is left closed and right open ,begin() Point to the first one ,end() Point to the next position of the last ）

less() It's an affine function , Judge a Is less than b.

bind2nd and not1 It's a function adapter ,bind2nd You can bind the second parameter , take a Less than b Convert to a Less than 40.not1 Is the result of inversion , Become greater than or equal to 40.

In this way, the six components are reflected in a small program .

02 Note structure

stay 《STL Source analysis 》 in , Mr. Houjie uses the space configurator （alloctor） As the beginning , Then I will explain iterators and containers one by one . This is because alloctor Is hidden in the container , With STL From the perspective of implementation, this is the first content to be introduced .

In our daily use , Containers should be the most used . We can start with the classification of containers , With vector As an example, the analysis of containers , Then go deep into the... Used in each container alloctor, Again from list The angle of extends the use of iterators . Then start to analyze the following contents one by one .

03 Something to watch out for

edition

Reference resources SGI STL Implementation version , This version is highly readable in terms of naming symbols and reading style .

SGT STL The header files of are distributed as follows ：

1. STL Standard header file （ Part without extension ）
2. C++ Specification before finalization of the standard STL The header file （ extension .h Part of ）
3. SGI STL Internal documents （stl_ start , It's also STL The real implementation part ）
4. 
   

Front closing back opening section

STL Algorithms need to be obtained by a pair of iterators （iterator） The space indicated . The range represented in practice is [first,last), it is to be noted that last It refers to the next position of the last element .

auto keyword

auto Keywords are C++11 New features . The principle is to infer the type of the front according to the following values .

for instance ：

list <string >c;

// It was written in the original way 
list<string>::iterator ite;
ite=::find(c.begin(),c.end(),target);

//auto keyword 
auto ite=::find(c.begin,c.end(),target);

operators overloading

When we use some algorithms, we will also find , Algorithms generally provide multiple versions . For example, the sorting algorithm has the general default ascending sorting , You can also specify relationships to sort .

stay c In language , You want to pass a function as a parameter , You need to use function pointers to implement .

stay STL in , these “ A whole set of operations ” All of them are realized in the form of imitative function . Simply put, it means overloading the operators . For example, left and right parentheses .

for instance ：

template <class T>
   struct plus{// functor plus
       T operator()(const T& x,const T& y) const {return x + y}
   };

int main()
{
    // Generate a functor object 
    plus<T> plusobj;
    
    // Use the functor 
    cout<<plusobj(2,3);
    
    // Generate a functor temporary object 
    cout<<plus<int>(2,3);
}

04 summary

Summary notes are intended to help understand the content , Maybe it's more about the explanation of the key code , The rest can be used in conjunction with the original book , better . If you have any shortcomings, please give me more advice . New ideas and solutions to some key problems are also expected to be discussed and improved by everyone .

I hope everyone can learn STL On the road to gain .