STL Standard template library (Standard Template Library), yes C++ Part of the standard library , It contains some templated general data structures and algorithms .STL Implementation of template based software , So it can support custom data structure .

STL There's a total of 6 Big components :

  • Containers (container)
  • iterator (iterator)
  • Algorithm (algorithm)
  • distributor (allocator)
  • functor (functor)
  • Container adapter (container adapter)

Reference material :

functor

functor (Functor) The essence of Overload... In a structure () Operator .

for example :

struct Print
{ void operator()(const char *s) const { cout << s << endl; } };
int main()
{
Print p;
p("hello");
}

This concept will be in priority_queue Use in ( In the field of smart pointer unique_ptr Customize deleter It also uses ).

Containers

Containers (Container) stay STL It is also divided into sequential containers (Sequence Containers) , Associative containers (Associative Containers) And unordered containers (Unorderde Containers) .

Sequential containers

Common sequential containers include :vector, string, array, deque, list, forward_list .

vector/string

Underlying implementation :vector yes Memory is continuous 、 Automatically expanded array , In essence, it's a fixed length array .

characteristic :

  • Random access : heavy load [] Operator
  • Dynamic capacity : Before inserting a new element , If size == capacity when , Then expand to the current capacity of 2 times , And copy the original data
  • Support ==, !=, <, <=, >, >= Comparison operations
    • C++20 front , Through the above 6 An overloaded operator implementation ;C++20 in , Unified 「 encapsulation 」 For one <=> Operator (aka, three-way comparsion ).
    • It's not difficult to understand. , The time complexity is \(O(n)\) .

PS:string The underlying implementation and vector It's similar , The same is memory continuity 、 Automatically expanded array ( But the expansion strategy is different ).


array (C++11)

Underlying implementation :array yes Memory is continuous Fixed length Array of , Its essence is to encapsulate the original array directly .

characteristic ( Mainly with vector Compare ):

  • Support 6 Two comparison operators , Support [] Random access
  • Discard auto expansion , To get the same performance as native arrays
  • I won't support it pop_front/back, erase, insert These operations .
  • The length is determined at compile time .vector The initialization method of is function parameter ( Such as vector<int> v(10, -1), The length can be determined dynamically ), but array The length of needs to be determined at compile time , Such as array<int, 10> a = {1, 2, 3} .

It should be noted that ,array Of swap The method complexity is \(\Theta(n)\) , Others STL Container of swap yes \(O(1)\), Because it's just a pointer swap .


deque

Also known as “ deque ”.

Underlying implementation : Multiple discrete buffers , And the memory in the buffer is continuous . And each buffer also records the first pointer and the last pointer , The interval used to mark valid data . When a buffer is full, a new buffer will be allocated before or after it to store more data .

characteristic :

  • Support [] Random access
  • Insertion and deletion of linear complexity , And random access to constant complexity .

list

Underlying implementation : Double linked list .

characteristic :

  • I won't support it [] Random access
  • Insertion and deletion of constant complexity

forwar_list (C++11)

Underlying implementation : One way linked list .

characteristic :

  • comparison list Reduced space overhead
  • I won't support it [] Random access
  • Reverse iteration is not supported rbegin(), rend()

Associative containers

Relational containers include :set/multiset,map/multimap.multi Indicates that the key value can be repeatedly inserted into the container .

Underlying implementation : Red and black trees .

characteristic :

  • Internal self ordering , Search for 、 Removal and insertion have logarithmic complexity .
  • For any associative container , The time complexity of traversing containers with iterators is \(O(n)\) .

Custom comparison method :

  • If it's a custom data type , Overload operator <
  • If it is int Etc , Through the functor
struct cmp { bool operator()(int a, int b) { return a > b; } };
set<int, cmp> s;

Unordered container

Unordered container (Unorderde Containers) Include :unordered_set/unordered_multiset,unordered_map/unordered_multimap .

Underlying implementation : Hashtable . In the standard library implementation , The hash value of each element is a pair of values A prime number Take the module to get ,

characteristic :

  • The internal elements are out of order
  • In the worst case , Insert unordered associative containers 、 Delete 、 The time complexity of operations such as lookup will decrease Linear with container size . This often happens in containers A lot of hash conflicts Time production .

In the actual application scenario , Suppose we know the distribution of key values , To avoid a lot of hash conflicts , We can customize the hash function ( Or in the form of functor ).

struct my_hash { size_t operator()(int x) const { return x; } };
unordered_map<int, int, my_hash> my_map;
unordered_map<pair<int, int>, int, my_hash> my_pair_map;

Summary

Four operations Average time complexity of Compare :

  • increase : Inserts an element at the specified location
  • Delete : Deletes the element at the specified location
  • Change : Modify the element at the specified location
  • check : Find an element
Containers The underlying structure increase Delete Change check
vector/deque vector: Dynamic continuous memory
deque: Continuous memory + Linked list
\(O(n)\) \(O(n)\) \(O(1)\) \(O(n)\)
list Double linked list \(O(1)\) \(O(1)\) \(O(1)\) \(O(n)\)
forward_list One way linked list \(O(1)\) \(O(n)\) \(O(1)\) \(O(n)\)
array Continuous memory I won't support it I won't support it \(O(1)\) \(O(n)\)
set/map/multiset/multimap Red and black trees \(O(\log{n})\) \(O(\log{n})\) \(O(\log{n})\) \(O(\log{n})\)
unordered_{set,multiset}
unordered_{map,multimap}
Hashtable \(O(1)\) \(O(1)\) \(O(1)\) \(O(1)\)

Container adapter

Container adapter (Container Adapter) It's not really a container ( Personal understanding is an encapsulation of a container ), They don't have some of the characteristics of containers ( Such as : There are iterators 、 Yes clear() function ……).

Common adapters :stack,queue,priority_queue.

For the adapter , You can specify a container as its underlying data structure .

stack

  • Default container :deque
  • Random access is not supported , Iterators are not supported
  • top, pop, push, size, empty The time complexity of the operation is \(O(1)\) .

Specify the container as the underlying data structure :

stack<TypeName, Container> s;  //  Use  Container  As the bottom container 

queue

  • Default container :deque
  • Random access is not supported , Iterators are not supported
  • front, push, pop, size, empty The time complexity of the operation is \(O(1)\) .

Specify the container :

queue<int, vector<int>> q;

priority_queue

Also known as “ Priority queue ” .

  • Default container :vector
  • \(O(1)\):top, empty, size
  • \(O(\log{n})\) : push, pop

Template parameter analysis :

priority_queue<T, Container = vector<T>, Compare = less<T>> q;
// adopt Container Specify the underlying container , The default is vector
// adopt Compare Custom comparison function , The default is less, The elements with high priority are at the top of the heap , The big top pile
priority_queue<int, vector<int>, greater<int>> q;
// Pass in greater<int> So we're going to build a little top pile
// Allied , also greater_equal, less_equal

iterator

iterator (Iterator) In fact GOF A design pattern in : Provides a way to access elements of an aggregate object in sequence , Without exposing the internal representation of the object .

The classification of iterators is shown in the figure below .

Iterators for each container

STL Each container in the container / The corresponding iterators used by the adapter are shown in the following table .

Container Iterator
array Random access iterator
vector Random access iterator
deque Random access iterator
list Bidirectional iterator
set / multiset Bidirectional iterator
map / multimap Bidirectional iterator
forward_list Forward iterator
unordered_{set, multiset} Forward iterator
unordered_{map, multimap} Forward iterator
stack Iterators are not supported
queue Iterators are not supported
priority_queue Iterators are not supported

Iterator failure

Iterator failure is due to the insertion or deletion of elements into the container, resulting in a change in the space or order of the container , Make the original iterator unavailable . So in the right STL When the iterator is adding or deleting , Pay special attention to whether iterators fail .

Search on the Internet 「 Iterator failure 」, There are many examples of this , In a vector Remove all of the 2 and 3, Deliberately scanning with iterators ( We all know that subscripts can be used ):

int main()
{
vector<int> v = {2, 3, 4, 6, 7, 8, 9, 3, 2, 2, 2, 2, 3, 3, 3, 4, 5, 6};
for (auto i = v.begin(); i != v.end(); i++)
{
if (*i==2 || *i==3) v.erase(i), i--;
// correct code should be
// if (*i==2 || *i==3) i=v.erase(i), i--;
}
for (auto i = v.begin(); i != v.end(); i++)
cout << *i << ' ';
}

I used it a long time ago Dev C++ ( It should be built in very old MinGW) When writing code , I have experienced this situation in my impression ,v.erase(i), i-- This kind of operation is problematic . erase(i) Will make i And the iterator after it fails , So a segment error occurs .

But now MacOS (clang++ 12), Ubuntu16 (g++ 5.4), Windows (mingw 9.2) Up test , There's no problem with this code , And can output the correct results . Compile options are :

g++ test.cpp -std=c++11 -O0

Actually, it's not hard to understand , Because it's continuous memory ,i Point to memory location , stay erase And then it's covered by other data ( The behavior here is the same as when we use normal arrays ), But the position is still vector Within the effective range of . In the above code , When i = v.begin() when , perform erase after , Yes i Perform auto reduction operation , This is already an undefined behavior .

I guess so C++11 after ( Or later compiler updates ), The problem of iterator failure is optimized .

Although it can run normally , But I think it's better to be rigorous , Follow the rules of iterators more strictly :if (*i==2 || *i==3) i=v.erase(i), i--; .

Here are the situations where iterator failures may occur for various containers :

  • Array type (vector, deque)

    • insert(i) and erase(i) There will be data movement , bring i After the iterator failure , It is recommended to use i = erase(i) Get the next valid iterator .
    • Memory reallocation : When vector Automatic expansion , Probably Will apply for a new memory and copy the original data ( It may also be based on the current memory , Add another piece of continuous memory ), So all iterators will fail .
  • List type (list, forward_list):insert(i) and erase(i) The operation does not affect iterators in other locations ,erase(i) Make the iterator i invalid , Invalid pointing data ,i = erase(i) Get the next valid iterator , Or use erase(i++) Can also be ( When entering erase Auto increment has been completed before operation ).
  • Tree shape (set/map): Same as linked list type .
  • Hash type (unodered_{set_map}): Same as linked list type .

[CPP] STL More related articles in the introduction

  1. C++STL brief introduction

    This article is just a personal learning process combined with online blog , Yes STL Sort it out , It's just a brief introduction . Just for personal study notes . One .STL brief introduction ( Excerpt from : dawn (Morning)) STL(Standard Template Library), ...

  2. C++ Generic programming and STL Template library (1)--- Introduction to generic programming and STL Introduction and structure

    Basic concepts of generic programming Write programs that don't depend on specific data types Abstracting algorithms from specific data structures , Become universal C++ The template for generic programming lays a key foundation The term : Concept It is used to define the data types with certain functions . for example : take ...

  3. STL brief introduction , Standard template library

    This article is about C++ A new extension of language -- Standard template library (Standard Template Library), Also called STL.  When I first planned to write an article about STL When , I have to admit that I underestimated that ...

  4. C++ Standard template library Stand Template Library(STL) Introduction and STL string class

    Reference resources <21 Tian Xue Tong C++> The first 15 and 16 chapter , After learning about macros and templates , Open to C++ Implementation of the standard template class STL Brief introduction , At the same time, introduce the simple string class . Although the front for vector.deque.list Wait for progress ...

  5. STL brief introduction

    Due to different books and translation problems, it is necessary for STL There may be some differences in terms in this article <STL Source analysis > Terms in STL The components of contain 6 A component , They are containers . Algorithm . iterator . functor ( Function object ). adapter ( Adapter ). Configurator ( ...

  6. C++ Standard template library of (STL) brief introduction

    STL(Standard Template Library, Standard template library ) yes C++ The realization of the idea of generic programming , It was first developed by HP Labs . In being introduced C++ The technology has been around for a long time . later STL Become ANSI ...

  7. C++ Basic knowledge of :STL brief introduction

    1. Standard template library STL ― STL , namely : Standard Template Library , yes C++ Part of ― STL Is a collection of commonly used data structures and algorithms ― STL The goal is to standardize components , Improve development efficiency ...

  8. STL Learning notes ---STL brief introduction

    1. summary STL Is a collection of generic class templates and algorithms , It provides programmers with some standard data structure and algorithm implementation .STL Three key components : Containers (Containers), A collection used to manage class objects iterator (Iterators), Used in a ...

  9. [CPP - STL] functor Ask the bottom

    As STL One of the six components , stay STL Source code and its application , A lot of places use affine functions (functor), Especially in associative containers ( Such as set.map) as well as algorithm( Such as find_if.count_if etc. ) in . Although already ...

  10. [CPP - STL] swap skill

    Recently in to see <Effective STL>,[ Clause 17: Use “ Exchange skills ” Trimming excess capacity ] The function of the container is mentioned in void swap(container& from), That is to implement container object and from Yes ...

Random recommendation

  1. IO Stream exception handling

    stay IO We should pay attention to the following points when handling stream exception : 1. Create references outside , stay Try Initialization is performed in (FileWriter fw = null;) 2. The path to the file must be double slash , escape (fw = new FileWrit ...

  2. ( One )boost The date of the library 、 Time

    ( One )boost The date of the library . Time One . timer   timer , It is very practical to count the execution time of a function in a project .   #include <boost/timer.hpp> void PrintU ...

  3. Vue.js The method of parameter transfer of components in - be based on webpack Templates

    stay Vuejs in , This is the first contact between components today , The components written before are independent of each other , I dare to be expert , There must be a division of people Environmental Science : node.js npm vue-cli Please install the above by yourself One . Project creation $ vue ...

  4. solve vmware workstations 14 Turn on the virtual machine black screen

    Some friends are using vmware workstations 14 Black screen found when creating or opening virtual machine , But in fact, the normal startup of the system is , It's just that there's no screen . 1. Start the command line as an administrator 2. Repair LSP stay CMD Input in netsh ...

  5. A way of leading to emwin in EDIT Control is not displayed

    @2018-12-11 [ Notes ] The design interface uses EDIT Control , But it is misused in its initialization statement text-color attribute API, Results in the control EDIT Medium Text Unable to display , As follows hItem ...

  6. linux Driving engineering interview must ask knowledge points

    linux The core principle interview must ask ( From easy to difficult ) Simple type 1:linux The difference between kernel space and user space in ? What are the communication modes between user space and kernel ? 2:linux Memory partition and how to use ? The concept of virtual address and physical address and the transformation between them , ...

  7. L242

    They provide a means of keeping track of the thousands of journal papers that are published monthly ...

  8. Additive Attribute animation

    Additive Attribute animation Reference resources http://ronnqvi.st/multiple-animations/ effect Source code https://github.com/YouXianMing/Animatio ...

  9. 【 Nebula test 】 Developer testing (2)- Use precision testing tools to J2EE Guns Develop a framework for testing

    Configuration testing Guns Guns brief introduction Guns It's based on SpringBoot Open source, convenient and relatively new JavaEE Project development framework , It integrated. springmvc + shiro + mybatis-plus + ...

  10. select2 multi-select Sort ( edition 3.4.6)

    Use select2 multi-select , The order of the page selection values is the same as that of the page selection values control The values of are not in the same order , For convenience , It didn't change js file , On the page through change Method change . 1. Page code ( Add and modify using the same page ) <li ...