[STL source code analysis] summary note (2): overview of containers

00 Write it at the front

Containers （containers） yes STL An important part of , It is also a part worthy of our in-depth study . Various vector、map、set The use of has greatly improved our efficiency in solving problems .

Each container has its own unique implementation and some key points that we need to understand , These will be the focus of the article .

01 Structure and classification of containers

summary

Containers can be roughly divided into sequential containers （Sequence）, Associative containers （Associative） And unordered containers （Unordered）, Unordered containers can also be classified as associative containers .

classification

Sequential containers （Sequence）

1. array： Array , Is a fixed size structure , Static space , The size cannot be changed after configuration .
2. vector： The dynamic array , Linear continuous space with unidirectional openings , Dynamically configurable space , The principle is to double the capacity each time , Then copy the original spatial data to the new space .
3. deque： It is a linear continuous space with two-way openings , You can insert and delete at the beginning and end .
4. list： Chain table structure , Not a linear continuous space , Use pointer addressing , Here refers to a two-way linked list .
5. forward-list： One way linked list
6. stack/queue： Stacks and queues , The bottom layer is made of two-way openings deque Realized after packaging .

Associative containers （Associative）

1. set/multiset： A structure based on red and black trees , It can store key. about set Come on key Not to be repeated ,multiset Of key Can be repeated .
2. map/multimap： A structure based on red and black trees , It can store key and value, about map Come on key Not to be repeated ,multimap Of key Can be repeated .
3. unordered set/multiset： A structure based on a hash table , It can store key. about set Come on key Not to be repeated ,multiset Of key Can be repeated .
4. unordered map/multimap： A structure based on a hash table , It can store key and value, about map Come on key Not to be repeated ,multimap Of key Can be repeated .

Contrast relationship ：

aggregate	Underlying implementation	Is it orderly	Whether the value can be repeated	Can I change the value	The query efficiency	Efficiency of addition and deletion
std::set	Red and black trees	Orderly	no	no	O(logn)	O(logn)
std::multiset	Red and black trees	Orderly	yes	no	O(logn)	O(logn)
std::unordered_set	Hashtable	disorder	no	no	O(1)	O(1)

mapping	Underlying implementation	Is it orderly	Whether the value can be repeated	Can I change the value	The query efficiency	Efficiency of addition and deletion
std::map	Red and black trees	key Orderly	key Do not repeat	key Do not modify the	O(logn)	O(logn)
std::multimap	Red and black trees	key Orderly	key repeatable	key Do not modify the	O(logn)	O(logn)
std::unordered_map	Hashtable	key disorder	key Do not repeat	key Do not modify the	O(1)	O(1)

02 The relationship between containers

Let's first look at a diagram ：

The indented display here represents the relationship between the base layer and the derived layer , Derivation is not inheritance , But compound .

such as heap and priority There are vector As the base .set、map There are red and black trees as the base .

There are also some non-standard containers inside , such as slist,hash At the beginning, wait . stay C++ 11 in slist Renamed as forward-list,hash All the beginning should be changed to unordered start .

notes ： there sizeof() Bury a small foreshadowing , There will be specific size comparison later . in addition GNU4.9 There are many designs that have become complicated , For example, a lot of inheritance is used , But the actual function is not very different .

03 summary

After knowing the general contents of the container , We can learn from the most familiar vector Let's take a look at the internal implementation details .

There are many things worth learning in other containers , such as list The iterator will be reflected in （iterators） The subtlety of design , stay set and map The implementation of red and black trees will be reflected in , Follow up with a separate summary .