STL source code analysis (Hou Jie) notes -- Classification and testing of stl containers

1、 Structure and classification of containers

Sequential containers ： Elements have order relations , Include array、vector、deque、list、forward-list(stack,queue It's the adapter )

Associative containers ：key-value type , Include set/Multiset、map/Multimap、unordered_map/Multimap、unordered_set/Multiset.（set Can be regarded as key=value）

• array： Fixed size arrays
• vector： Single extended vector （ Array ）
• deque： Bidirectional arrays , It can be extended at both ends
• list： Double linked list ,SGI STL The source code is implemented as a circular linked list
• forward-list： One way linked list
• set/multiset: Red and black trees , Balanced binary search tree at the expense of balanced properties , Insert and delete faster than balanced binary tree , After inserting elements, they will be sorted automatically, such as set s = {4,3,2,1}; for(auto num) cout << num; Output ：1,2,3,4
• map/multimap： Same as set/multiset,key-value
• unordered_set/Multiset/unordered_map/Multimap, disorder , Using hash structure , Here's the picture
• 

2、 Using a container array

Several points that can be learned in the above figure ：
Get the timestamp ：

clock_t timeStart = clock(); // clock() The function returns clock_t

array Some member functions of ：

size(), Calculate container size 
front(), Starting element value 
back(), Final prime value 
data(), The starting position of the array 

qsort、qsearch function , Quick sort 、 Two points search , In the header file cstdlib in

//qsort Source code 
void qsort(void* base, size_t num, size_t size, int(*compare)(const void*, const void*));
params:
base: The first address of the container to sort , That is, the first address of the array 
num: Number of elements , That is, the first... In the array num Elements 
size: The size of the element type to sort , If yes int Element ordering , Then for sizeof(int)
int(*)(void*,void*): Sort function pointer , Custom such as ：
int compareMyType (const void * a, const void * b)
{
    
  if ( *(MyType*)a <  *(MyType*)b ) return -1;//  First the void* Convert to a specific type pointer and compare ,void* Can't compare 
  if ( *(MyType*)a == *(MyType*)b ) return 0;
  if ( *(MyType*)a >  *(MyType*)b ) return 1;
}

// qsearch Source code 
void* bsearch(const void* key, const void* base, size_t num, size_t size, int(*compare)(const void*, const void*));
params：
key： Pointer to the search object 
 Other parameters are the same as qsort

3、 Using a container vector

Learn something ：
vector Member function of ：

size(): The actual number of elements 
data(): First element address 
capacity():vector In the capacity ,1.5 or 2 Times the growth , Always greater than or equal to size.

find Algorithm

 overall situation find function std::find(), When using, add ::, Is a template function 
template<class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value)
{
    
	while (first != last){
    
		if (*first == value) return first;
		++first;
	}
	return last;
}

c++11 New characteristics ：auto keyword

 Type inference ,  There must be an initial value 
//（1） Common type inference 
auto x = 10; // infer x by int
auto y; // error , No initial value 
//(2) Reference type inference 
int a = 10, &b = a;
auto c = b;//  Deduce b by int&
//(3)const Type inference , There are changes 
const int a = 10;
auto b = a;// b Infer as int, Discard the top layer const
auto &c = a;//c by const int, Keep the top floor const
//(4) Inference of arrays and functions 
const char arr[] = "helloworld";
auto l = arr;// The array address is inferred as a pointer type , namely const char*;
auto &r = arr;// r For array reference type , namely const char(&)[];

int add(int a,int b);
auto r = add; // r Infer as int(*)(int,int);
auto &r1 = add; r Infer as int(&)(int,int);

auto Do not apply to ：

• Function arguments cannot be auto type , Such as int add(auto a, auto b);
• A member variable of a class cannot be auto type , Static member variables can , But need cosnt modification , And you need to initialize in the class

4、 Using a container list( Double linked list )

list<int> c;
c.push_back(), Additive elements 
c.max_size(), The maximum capacity , It should be related to memory capacity .
c.sort(),list Inborn sort function , Than the standard library std::sort() More suitable for list The order of elements .( When the container comes with sort when , Be sure to use your own )

5、 Using a container forward_list( One way linked list )

push_front(),pop_front(), No, push_back();
forward_list<int> myList = {
    1,2,3};
myList.push_front(4); //myList The content of :4,1,2,3
myList.push_front(5); //myList The content of :5,4,1,2,3

6、slist( Single chain list gnu c++ Non template library content )

Same as forward_list

7、 Using a container deque

The bidirectional queue , It can be expanded on both sides , Piecewise continuity

dque The iterator of will put several buffer Connect , namely ++ It can realize shift and jump , involve ++ heavy load

map Each pointer in points to a buffer The first address ,buffer The size of is determined by the allocator ( Guess the ) decision , It's not fixed

8、 Use adapter stack、queue

stack<int> st;
st.push(); Additive elements 
st.top(); Get stack top element 
st.size();

queue<int> que;
que.size();
que.front();
que.back();
que.push();//  Add elements to the end 

9、 Using a container multiset、multimap

multiset<string> c;
c.insert();//  Additive elements , No, push_back,push
c.find();  The container's own lookup function , Than std::find() faster , The following relational containers are also self-contained find function 

multimap<long, string> c;
c.insert(pair<long,string>(1,"hello"));//  Unavailable [] Do the index , That is not to say c[i] = value; Otherwise, it directly covers and map You can use index assignment 

10、 Using a container unordered_multiset、unordered_multimap

unordered_multiset<string> c;
c.insert();
c.bucket_count();//  The size of the edge array , More than the number of elements , If the number of elements is greater than the number of baskets , The basket will expand ,2 About times 
c.load_factor();//  Loading factor , The proportion of non empty baskets in all baskets 
c.max_load_factor();
c.max_bucket_count();

11、set、map

And multiset and multimap The difference is simply not repeatable .

Documents and video resources github Address ( Not in person )：https://github.com/ZachL1/Bilibili-plus