工作准备-01（C++STL---容器部分总结）

学习内容

C++中的STL分为以下几个大的部分：容器、迭代器、算法、仿函数、适配器、分配器，这篇文章总结了容器部分的内容。

C++ STL容器部分

C++中有容器，容器大多都是以泛型编程的方式出现（就是模板方法），这样做的好处就是同意容器支持多种类型的数据，C++中的容器按照存储的内容可以分为两个部分：序列式容器、关联式容器；

序列式容器

序列式容器有以下几种容器：array(C++11新增)、vector、list、forward_list(C++11新增)、heap、stack、deque、queue、slist…

1. array与vector可以分为一类，都是数组型容器，不同的是array的大小在创建之后就固定了，而vector可以根据所装入容器中的元素数量进行动态扩展，一般是以当前容量的两倍进行扩展，而且是重新在内存中找到这么大的地方直接复制过去。
2. list、forward_list、slist容器可以归为一类，都是链表型容器，list底层是双向型链表，而slist和forward_list底层是单向型链表。

3. deque、stack、queue可以归为一类，deque是双向都能存取数据的一个容器（打个比方：deque相当与一个管道，两边都能注水或者出水），deque俗称断而连续，意思是表面上看它内部元素的存储是连续的，但是它的内部其实上是通过一个个指针来将分布在内存中不同区间的存储地址连起来（我个人觉得这就像是下面说的以hash table为底层实现的构成形式一样）；而stack和queue可以通过deque转换而来：stack就是所谓的“栈”，因为一般stack就是先进后出，即只有一端可以进行数据的压入和弹出（将管道的一段堵住，只留另一端可以出水和进水）；queue就是所谓的队列（限制管道的一端（尾端）只能注水，另一端（头部）只能出水；也可以看成打饭的队伍，队头元素打完饭出队，从队尾插入元素进行打饭）；因为以上stack、queue能够通过deque实现（其实他们底层也是通过deque进行实现的），所以他们一般不称为容器，而叫做容器适配器

   deque中插入和弹出元素的成员函数有：push_front、push_back、pop_front、pop_back；

   stack、queue中的插入和弹出元素的成员函数有：push、pop

4. heap严格意义上讲不属于STL容器组件，它作为priority queue的底层机制出现，一般使用vector容器和一些heap常见的算法（插入元素、删除元素、取极值…）其中用到heap的算法有：push_heap、pop_heap、sort_heap、make_heap。

   以上容器需要注意：

5. 容器本身自带的sort()、find()函数速度要比全局的::sort()、::find()函数的速度快。
6. stack、queue没有迭代器，也没有find函数 ，因为他们对于元素的存取顺序不能改变。

序列式容器中存入的元素之间没有什么顺序关系（即没有从大到小或者从小到大的一定自然关系，你存入的顺序决定了它的顺序），而下面介绍的关联式容器却可以将你存入的元素按照一定的顺序进行排列，而且是一种动态的过程，就是根据你当前存入的元素进行重新排列已有的元素。

关联式容器

关联式容器按照底层实现的不同可以分为以RB-tree构成的：set、multiset、map、multimap，以及以hash-table为底层的hash_set、hash_mutiset、hash_map、hash_mutimap。

** 以RB-tree为底层**

map容器存放的是一个pair类型的元素，即存入的元素可以分为key、value；key作为map容器中元素排列（从大到小还是从小打大排列，默认为从小到大排列）的对象，即按照key值的大小对存入其中的元素进行排序，value就是所谓的实值，但是map容器只允许key值不同的元素存入，这和它insert()底层使用insert_unique()实现有关。

multimap容器与map容器类似，所不同的是其insert()底层使用insert_equal()实现，所以它可以存入key值相同的元素。

这里需要注意三点：

1. map和mutimap容器的insert函数可以插入元素进入容器中，这个函数会返回插入元素的信息，即它返回的是一个pair对象，这个pair对象的first是正确插入那个元素之后得到指向它所在位置的该容器的迭代器，而second是一个bool类型的值，表示是否插入成功，插入成功返回true，插入失败返回false。
2. map、multimap对象可以通过“[]”进行访问，比如定义一个

map<string, int> myMap,
	myMap.insert(make_pair("张三", 45));
	myMap.insert(make_pair("李四", 25));
	myMap.insert(make_pair("王五", 35));
	cout << "张三年龄：" << myMap["张三"] << endl;
           

以上通过[first]去访问second。

3. multimap不能通过下标操作符[]来进行插入、访问操作，因为mltimap中的key值是可以重复的，如果使用[]来进行插入的话会发生歧义，但是map中的key是不会重复的，所以可以使用[]来进行元素的插入。

set、multiset容器存入的元素可以看成是将map、mutimap容器中的元素的key、value值合并为一个值的情况，所以set、multiset可以直接按照存入的值对其中的元素进行排列。其它特性与map、multimap类似，但是没有[]访问，因为它只有一个值，不是pair。

总结：用户不能通过set和multiset容器的迭代器更改里面元素，但是map和multimap可以通过其迭代器修改里面的实值，记住是实值不是键值。

以hash-table实现底层

以前叫作hash_map/hash_set/hash_multimap/hash_multiset，现在叫作unordered_map/unordered_set/unordered_multimap/unordered_multiset，但是现在以hash开头的定义名仍然是可以使用的，但是要包含头文件例如：<hash_map>他们底层实现都是通过hash_table（散列表），其中hash_table，是以basket（俗称篮子）上面挂链表来实现的，其中的链表是用来存储元素的；

basket的数量一定大于元素的数量，因为设计的原则就是当basket的数量等于元素的个数的时候就会重新扩充篮子的数量（一般是以两倍扩充的），原因是因为当一个篮子所挂的链表较长的时候查找的时候需要的时间较长。