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

Introduction to [CPP] STL

2021-01-23 20:36:54 sinkinben

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 .

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

随机推荐