STL(Standard Template Library)

It's very convenient for us to use library functions , And it's very efficient ( Relative to your own implementation ). What's the inside of such a good template library ? What did it do behind our backs “ magic ” Well ? I decided to check it out , Believe you too . I will choose some important codes for analysis , To improve oneself , I hope you can have your own harvest in my humble opinion later .


vector

Data storage mode : Linear storage ( A piece of continuous memory ), similar array.

Compared to built-in arrays ( No array Oh ) The advantages of : Dynamic capacity .( In fact, it's not an advantage , The array can also do , It just encapsulates the expansion process efficiently and safely .)

Compared with array, The advantage is even greater ,array In the beginning, the capacity of is dead , Can't expand .

Usage method

 #include <iostream>
#include <vector>
#include <algorithm>
using namespace std; // unique_ptr::get vs unique_ptr::release
int main()
{
// initialization
vector<int> vec;// Statement , uninitialized
vector<int> vec1(, );//2 individual 5
vector<int> vec2 = { , , , , };// Direct initialization
// Read elements
cout << " The first 2 Elements : " << vec2[] << endl;
cout << " First element : " << vec2.front() << endl;
cout << " The tail element : " << vec2.back() << endl;
// Insert elements
vec1.insert(vec1.begin(), );//para1- Insertion position , To iterator is a pointer ,para2- Insert content
vec2.push_back();// Tail insertion
vec2.pop_back();// Delete tail , Be similar to stack, So sometimes you can also put vector When stack use
// Remove elements
vec2.erase(vec2.end()-);// Parameters are also iterator types , So use insert and erase when , It is best to iterator To traverse
// Sort
sort(vec2.begin(), vec2.end());// Give the first pointer
sort(vec2.begin(), vec2.begin()+);// Even this can , because iterator It's a type pointer // Traverse -- Subscript index access
cout << "vec1 : " ;
for (int i = ; i < vec1.size(); ++i)
{
cout << vec1[i] << " ";
} // Traverse -- Iterator pointer access
cout << "\nvec2 : ";
vector<int>::iterator it;
for (it=vec2.begin(); it != vec2.end(); ++it)
{
cout << *it << " ";
}
41   // Use pointer traversal vector
    auto vec = new vector<int>(10, 8);
    for(int i=0; i<vec->size(); i++)
      cout << (*vec)[i] << " ";
return ;
}

Okay , This is the basic usage .


How is the bottom layer implemented ?

stay STL Source code ,vector Class maintenance has three iterators ( Three type pointers )start, finish, end_of_storage, Each represents the head , tail ( Actually used ), vector Storage tail ( The amount of , Usually greater than the actual use ).

When we vector<TYPE>::iterator it; when ,it Namely TYPE* Type a pointer , So are the three iterators .

The implementation of library function ?

We can see that , Through the three pointers above , Almost all operations can be carried out . It is worth mentioning that vector Reload the [ ], Easy access to values .

We need to pay attention to Yes. , When we visit Wei Yuansu , Iterators are not *.end(), It is *.end()-1.


So let's talk about , Something interesting .

When inserting elements , Preset end_of_storage What to do if it's not enough ? How to expand .

Look at the source code !

The whole process is :

1. Apply twice the memory first , Judge if it's enough , Enough to get into 2; otherwise , Allocate the required size ;

2. Copy the content before the insertion point

3. Construct the insertion elements to be added to the back in sequence

4. Then copy the content behind the previous insertion point into the new space

5. Free up space

Take a look at GCC Of vector Expansion process , Probably , If it's not enough, expand to the original 2 times , Expand to the original 2 Times is not enough , Then expand to the required size .

 int main()
{
vector<int> vec;
for(int i=; i<; i++)
{
cout << "vector size= " << vec.size() << endl;
cout << "vector capacity= " << vec.capacity() << endl;
//cout << "vector max_size= " << vec.max_size() << endl;
vec.push_back(i);
}
cout << " The last time , Insert 100 Elements " << endl;
vec.insert(vec.begin(), , );
cout << "vector size= " << vec.size() << endl;
cout << "vector capacity= " << vec.capacity() << endl;
//cout << "vector max_size= " << vec.max_size() << endl; return ;
}

however ,vector The maximum space is fixed .

I test it with the same piece of code vector The biggest space of  , There is a question , What if it exceeds the rated maximum space ? Finally, there is an attempt .

 int main()
{
vector<int> vec;
for(int i=; i<; i++)
{
cout << "Max_size = " << vec.max_size() << endl;
cout << "size = " << vec.size() << endl;
vec.push_back(i);
cout << " Insert " << i << endl;
}
return ;
}

(1)GCC 1019

(2)MSVC 109

Beyond the above max_size after , Rejected by the system insert 了 , I think that's the limit , Can't break through .

thus , We are right. STL vector The realization of is almost understood , It's enough to go out and have a chat .


Code from 《STL The source code parsing 》, The source code is shining !

STL Source analysis -vector More articles about

  1. STL Source code analysis of reading notes vector

    STL Source code analysis of reading notes vector 1.vector summary vector It's a sequential container , My understanding is that vector It's like arrays . But the big problem with arrays is when we assign When an array of a certain size , At first maybe we ...

  2. STL&quot; Source code &quot; analyse - Summary of key knowledge

    STL yes C++ One of the important components , I saw it in college <STL Source analysis > This book , I have reviewed these days , Here's a summary LZ The more important point is that , It's a little bit more :) 1.STL summary STL There are six components , They can be combined with each other ...

  3. 【 Reprint 】STL&quot; Source code &quot; analyse - Summary of key knowledge

    original text :STL" Source code " analyse - Summary of key knowledge STL yes C++ One of the important components , I saw it in college <STL Source analysis > This book , I have reviewed these days , Here's a summary LZ The more important point is that , The content is a little bit ...

  4. STL Source analysis iterator (iterator) Concepts and programming techniques ( 3、 ... and )

    1 STL Principle of iterator 1.1  iterator (iterator) It's a way to check the elements in the container and traverse the data types of the elements ,STL The essence of design is , Put the container (Containers) Sum algorithm (Algorithms) Separate , And iterators (i ...

  5. STL&quot; Source code &quot; analyse

    STL" Source code " analyse - Summary of key knowledge   STL yes C++ One of the important components , I saw it in college <STL Source analysis > This book , I have reviewed these days , Here's a summary LZ The more important point is that , The content is a bit sketchy ...

  6. 《STL Source analysis 》 Summary of related interview questions

    Link to the original text :http://www.cnblogs.com/raichen/p/5817158.html One .STL brief introduction STL There are six components , They can be combined with each other : Containers are all kinds of data structures , I won't say much about , have a look ...

  7. STL Source code analysis of the sequential container

    Recently, due to the need to find a job , I'm going to learn more about it STL Source code , I'm looking at what Hou Jie wrote <STL Source analysis >. The reason why I read this book is mainly because I have contacted some Taiwanese in the past , I always think Taiwanese are very good ( There's no politics involved here , Limited to ...

  8. STL Source analysis — Space configurator (allocator)

    Preface With STL In terms of implementation , The first thing we need to introduce is the space configurator , Because the entire STL All the operation objects are stored in the container . You can achieve a direct access to hardware space allocator. What follows is SGI STL What's provided is ...

  9. c++ stl Source code analysis study notes ( One )uninitialized_copy() function

    template <class InputIterator, class ForwardIterator>inline ForwardIterator uninitialized_copy ...

Random recommendation

  1. Pramp mock interview (4th practice): Matrix Spiral Print

    March 16, 2016 Problem statement:Given a 2D array (matrix) named M, print all items of M in a spiral ...

  2. HTML Call in servlet The problem of (?)

    Studying recently servlet. At the beginning , Knock the code line by line according to the case . however , Something is wrong. . hello1.html <!DOCTYPE html> <html> <head> ...

  3. make[1]: *** [pcrecpp.lo] error 1

    In the installation :pcre-8.30 when , Report the following error : [root@localhost pcre-8.30]# make && make installmake  all-ammake[1]: ...

  4. vector Of resize And reserve

    Recently I came across a pit , In a nutshell resize And reserve It's confusing . as follows : If the resize Transformation of , Compilation error , If Text Provide a default constructor , Can be compiled , The final output is 10. If the re ...

  5. Linux The server is set to support Chinese

    Linux The server is set to support Chinese Because the server does not support Chinese by default . So you need to set it separately . Check the existing language pack on this machine locale -a The default is no Chinese , So it shows : C C.UTF-8 POSIX e ...

  6. [C#] Design patterns - Abstract factory - Create pattern

    After introducing the simple factory and factory method , Now let's take a look at the last of the three brothers in the factory -- Abstract factory . So what is an abstract factory ? Abstract factory pattern (Abstract Factory Pattern): Provides a way to create a series of related or related ...

  7. [unity3d] Character controller components don't collide with each other

    RPG The game will have this demand . Between teammates , Between players . Between players and monsters , It's possible that they can't collide . How to achieve ? It's been a problem for a while , I saw the solution on the Internet yesterday : Here's an example of the relationship between players and monsters : 1, Fill in 2 There are two different levels mon ...

  8. Oracle IMPDP Notes for importing data cases (undo/temp)

    in the light of Oracle Data migration , We may use expdp/impdp The way , Sometimes you need a big watch .lob Fields may consume too much temporary table space and undo Table space , So we usually export logs according to , Adjust the table space size before importing . otherwise ...

  9. Linux Character device driver --No.1

    platform :tiny210SOC:s5pv210 kernel :Linux 3.0.8 Character driven : Key interrupt driver source code : /************************************************* ...

  10. 【 Search for 】 The magic board problem (BFS)

    [ Search for ] The magic board problem The time limit : 1 Sec   Memory limit : 64 MB Submit : 5   solve : 3[ Submit ][ state ][ Discussion board ] Title Description It is said that the ancient artifact that can make the holder the master of the world is hidden in the magic board space , Magic board by 8 Two of the same size ...