容器小记
-
1.容器种类
下面来看7种容器类型：
- vector:简单地说，vector是数组的一种类表示，它提供了自动内存管理功能，可以动态地改变vector对象的长度，可以动态地改变vector对象的长度，并随着元素的添加和删除而增大或缩小。它提供了对元素的随机访问。vector还是可反转容器概念的模型
- deque：在deque头文件中声明，表示双端队列，在STL中类似于vector，也支持随机访问。主要区别是从deque对象的开始位置插入和删除元素的时间是固定的，而不像vector中那样是线性的
- list:表示双向链表，与vector之间关键的区别在于，list在链表中任一位置进行插入和删除的时间都是固定的。所以list强调的是通过随机访问进行快速访问，而list强调的是元素的快速插入与删除。list也可以是反转容器，而且与vector不同的是，list不支持数组表示法和随机访问。还有list成员函数详见P699
- forward_list(c++11)：c++11新增的容器类forward_list，它实现了单链表。在这种链表中每个节点都只链接到下一个节点，而没有链接到前一个节点。forward_list是不可反转容器
- queue:这是一个适配器类。queue模板让底层类(默认为queue)展示典型的队列接口。详细操作详见P701
- priority_queue:这是另一个适配器类，它支持的操作与queue相同
- stack:与queue相似，stack也是一个适配器类，它给底层类(默认为vector)提供了典型的栈接口，操作详见P701
- array(c++11):它并非STL容器，因为其长度是固定的，所以array没有定义调整容器大小的操作
2.关联容器
-
关联容器是对容器概念的另一个改进。关联容器将值与键关联在一起，并使用键来查找值。优点在于提供对元素的快速访问。与序列相似，关联容器也允许插入新元素，但不能指定容器的插入位置。关联容器通常是使用某种树实现的
-
STL提供了4种关联容器：set,multiset,map和multimap。前两种在头文件set中定义，后2种在map中定义的，要注意键必须是唯一的
-
set模拟了多个概念，它是关联集合，可反转，可排序，且键是唯一的，所以不能存储多个相同的值 set<string> A; //第二个模板参数是可选的，可用于指定用来对键进行排序的比较函数或对象，默认情况下，将使用模板less<> const int N = 6; string s1[N] = {"a","b","c","d","e","f"}; set<string> A(s1, s1+N); //set也有一个将迭代器区间作为参数的构造函数 详细示例见P704 -
multimap与set相似，但键和值得类型不同，且同一个键可能与多个值关联 multimap<int, string> codes;//第3个参数是可选的，指出用于对键进行排序的比较函数或对象 详细示例和pair见P706 -
无序关联容器(c++11)：与关联容器底层的差别在于，关联容器是基于树结构的，而无序关联容器是基于数据结构哈希表的，这旨在提高添加和删除元素的速度以及提高查找算法的效率
