当前位置:网站首页>Introduction to [CPP] STL

Introduction to [CPP] STL

2021-01-24 02:11:41 itread01

STL Standard template library (Standard Template Library), yes C++ Part of the standard library , It contains some templated general data structures and algorithms .STL Based on the implementation of template , 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 interface card (container adapter) References :+ [1] https://oi-wiki.org/lang/csl/container/+ [2] https://en.cppreference.com/w/cpp/container+ [3] http://c.biancheng.net/view/409.html## Affine, affine (Functor) The essence of ** Overload in the structure `()` Operators **. for example :```cppstruct 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 terms of intelligence indicators `unique_ptr` Customize deleter You'll also use ).## 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** The underlying implementation :`vector` yes ** Memory is continuous 、 Automatic expansion of the array **, The essence is the fixed length array . Features :- Random access : Overload `[]` Operators - Dynamic expansion : Before inserting a new element , If `size == capacity` When , Then expand to the current capacity of 2 times , And copy the original information - Support `==, !=, <, <=, >, >=` Comparative operation - C++20 front , Through the above 6 An overload operator is implemented ;C++20 in , Unify 「 Package 」 For one `<=>` Operators (aka, [three-way comparsion](https://en.cppreference.com/w/cpp/language/operator_comparison#Three-way_comparison) ). - It's not hard to understand , Time complexity is $O(n)$ .PS:`string` The underlying implementation and `vector` It's similar , It's also memory continuity 、 Automatic expansion of the array ( But the expansion strategy is different ).-----**array (C++11)** The underlying implementation :`array` yes ** Memory is continuous ** 、 ** Fixed length ** Array of , Its essence is the direct encapsulation of the native array . Features ( Mainly with `vector` Compare ):- Support 6 Compare operators , Support `[]` Random access - Discard auto expansion , To achieve the same performance as native arrays - No support `pop_front/back, erase, insert` These operations . - The length is determined at compile time .`vector` The initialization method of is function argument ( Such as `vector v(10, -1)`, The length can be determined dynamically ), but `array` The length of needs to be determined at compile time , Such as `array 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 you just need to exchange the indicators .----**deque** Also known as “ Double ended queue ”. The underlying implementation :** Multiple discrete buffers , And the memory in the buffer is contiguous **. And each buffer also records the first indicator and the last indicator , 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 . Features :- Support `[]` Random access - Insertion and deletion of linear complexity , And random access to constant complexity .-----**list** The underlying implementation : Two way concatenation . Features :- No support `[]` Random access - Insertion and deletion of constant complexity **forwar_list (C++11)** The underlying implementation : One way concatenation . Features :- comparison `list` Reduced space overhead - No support `[]` Random access - Reverse iteration is not supported `rbegin(), rend()`### Relational containers relational containers include :`set/multiset`,`map/multimap`.`multi` Indicates that the key value can be repeatedly inserted into the container . The underlying implementation : Red and black trees . Features :- 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 operators `<` - If it is `int` Etc. built in type , By imitating function ```cppstruct cmp { bool operator()(int a, int b) { return a > b; } };set s;```### Unordered container (Unorderde Containers) Include :`unordered_set/unordered_multiset`,`unordered_map/unordered_multimap` . The underlying implementation : Hash table . In the standard library implementation , The hash value of each element is a pair of values ** A prime number ** Take the module to get , Features :- The internal elements are out of order - In the worst case , Insert unordered associative containers 、 Delete 、 The time complexity of queries and other operations will be ** Linear with container size ** . This often happens in containers ** A lot of clutter and conflict ** When it comes to . In practical application scenarios , Suppose we know the distribution of key values , To avoid a lot of clutter , We can customize hash functions ( Or in the form of a functor ).```cppstruct my_hash { size_t operator()(int x) const { return x; } };unordered_map my_map;unordered_map , int, my_hash> my_pair_map;```### Summarize four operations ** Average time complexity of ** Compare :- increase : Inserts an element at the specified location - Delete : Delete the element at the specified location - Change : Modify the element at the specified location - check : Query an element | Containers | The underlying structure | increase | Delete | Change | check || :--------------------------------------------------------: | :--------------------------------------------: | :----------: | :----------: | :----------: | :----------: || `vector/deque` | vector: Dynamic continuous memory
deque: Continuous memory + Link string | $O(n)$ | $O(n)$ | $O(1)$ | $O(n)$ || `list` | Two way concatenation | $O(1)$ | $O(1)$ | $O(1)$ | $O(n)$ || `forward_list` | One way concatenation | $O(1)$ | $O(n)$ | $O(1)$ | $O(n)$ || `array` | Continuous memory | No support | No support | $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}` | Hash table | $O(1)$ | $O(1)$ | $O(1)$ | $O(1)$ |## Container interface card container interface card (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 interface cards :`stack`,`queue`,`priority_queue`. For interface cards , 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 0 $O(1)$ . Specify the container as the underlying data structure :```cppstack 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 0 $O(1)$ . Specify the container :```cppqueue > q;```**priority_queue** Also known as “ Priority queue ” .- Default container :`vector`- $O(1)$:`top, empty, size`- $O(\log{n})$ : `push, pop` Template argument parsing :```cpppriority_queue , Compare = less > q;// Through Container Specify the underlying container , The default is vector// Through Compare Custom comparison function , The default is less, The highest priority of elements is at the top of the heap , The big top pile priority_queue , greater > q;// Incoming greater Then a small top pile will be constructed // Similar , And greater_equal, less_equal```## Iterators iterators (Iterator) It's actually GOF A design pattern in :** Provides a way to sequentially access the elements in a polymer part , 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 iterators corresponding to the interface card are shown in the following table .| Container | Iterator || :-----------------------: | :------------: || array | Random access iterators || vector | Random access iterators || deque | Random access iterators || 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 an iterator failure is caused by the insertion or deletion of elements into a container, resulting in a change in the space or order of the container , Make the original iterator unavailable . So in the face of 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 ~~):```cppint main(){ vector 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 you write 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) Test on , There's no problem with this code , And can output the correct results . The compilation options are :```g++ test.cpp -std=c++11 -O0``` Actually, it's not hard to understand , Because it's continuous memory ,`i` Point to the memory location , stay `erase` And then it was covered by other data ( The behavior here is the same as we use ordinary arrays ), But the position is still `vector` Within the effective range of . In the above code , When `i = v.begin()` When , Execute `erase` After , Yes `i` Perform auto reduction operation , This is already an undefined behavior . I guess it should be C++11 After ( Or later compiler updates ), The problem of iterator failure is optimized . Although it can perform 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 , Recommended `i = erase(i)` Get the next valid iterator . - Memory reallocation : When `vector` When expanding capacity automatically ,** Probably ** Will apply for a new memory and copy the original data ( It could also be based on the current memory , Add another contiguous memory ), So all iterators will fail .- Concatenation 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 ( Entering `erase` Auto increment has been completed before operation ).- Tree type (`set/map`): Same as concatenation .- Hash type (`unodered_{set_map}`): And linked tandem type

版权声明
本文为[itread01]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/01/20210124021047735u.html

随机推荐