- 注意,STL头文件没有扩展名.h
- STL中默认是采用小于号来排序的
1.容器概论
- 容器,置物之所也。像桶可装水,碗可盛汤,C++的容器,可以存储对象。容器有多种,用来处理不同的元素操作诉求。按照元素存储到容器中以及访问方式的差异,容器分为顺序容器与关联容器。
- 顺序容器也称为序列式容器。序列式容器按元素插入的顺序存储元素,这些元素可以进行排序,但未必是有序的。C++本身内置了一个序列式容器array(数组),STL另外提供了vector,list,forward_list,deque,stack,queue,priority-queue,string等等序列式容器。
- 所有的容器都是基于模板实现的,因为容器必须保证能装得下各种各样的类型。其中,stack,queue都是基于deque来实现的,priority-queue基于heap来实现,从技术上来说它们属于容器适配器(adapter)。其中array与forward_list是C++11添加的新容器类型。
2.序列式容器(顺序容器)
向量(vector) 连续存储的元素
<vector>
列表(list) 由节点组成的双向链表,每个结点包含着一个元素
<list>
双端队列(deque) 连续存储的指向不同元素的指针所组成的数组
<deque>
3.适配器容器
栈(stack) 后进先出的值的排列
<stack>
队列(queue) 先进先出的值的排列
<queue>
优先队列(priority_queue) 元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列
<queue>
4.关联式容器
- 关联容器内的元素是排序的。插入元素时,容器会按一定的排序规则将元素放到适当的位置上,因此插入元素时不能指定位置。
集合(set) 由节点组成的红黑树,每个节点都包含着一个元素,节点之间以某种作用于元素对的谓词排列,没有两个不同的元素能够拥有相同的次序
<set>
多重集合(multiset) 允许存在两个次序相等的元素的集合
<set>
映射(map) 由{键,值}对组成的集合,以某种作用于键对上的谓词排列
<map>
多重映射(multimap) 允许键对有相等的次序的映射
<map>
5.容器适配器
- stack,也称为栈,是一种先进后出的数据结构。STL中的statck是一种容器适配器。所谓的容器适配器,是以某种容器作为底部容器,在底部容器之上修改接口,形成另一种风貌。stack默认以双端队列deque作为底部容器。stack没有提供迭代器,通过push/pop接口对栈顶元素进行操作。
- queue,也称为队列,是一种先进先出的数据结构,它同样也是一种容器适配器。它的底部容器默认为deque。同样,queue也没有提供迭代器,通过push向队尾压入元素,pop从队首弹出元素。
- priority-queue,优先队列,是一种拥有权值观念的队列,例如在以整数大小作为衡量的权值定义下,priority-queue总是弹出最大的数。priority-queue的底部数据结构默认是max-heap,大顶堆。
6.基础总结
注意:
- “尾部可高效插入/删除元素”,意味着在除了尾部之外的其他位置插入/删除元素是较低效的。
- “顺序访问”意味着要访问某一个元素,必须遍历其他元素。
- 迭代器失效意味着指针、引用在同样的情况下也会失效。
所有容器都有以下两个成员函数:
- int size():返回容器对象中元素的个数。
- bool empty():判断容器对象是否为空。
顺序容器和关联容器还有以下成员函数:
- begin():返回指向容器中第一个元素的迭代器。
- end():返回指向容器中最后一个元素后面的位置的迭代器。
- rbegin():返回指向容器中最后一个元素的反向迭代器。
- rend():返回指向容器中第一个元素前面的位置的反向迭代器。
- erase(…):从容器中删除一个或几个元素。该函数参数较复杂,此处省略。
- clear():从容器中删除所有元素。
如果一个容器是空的,则 begin() 和 end() 的返回值相等,rbegin() 和 rend() 的返回值也相等。
顺序容器还有以下常用成员函数:
- front():返回容器中第一个元素的引用。
- back():返回容器中最后一个元素的引用。
- push_back():在容器末尾增加新元素。
- pop_back():删除容器末尾的元素。
- insert(…):插入一个或多个元素。该函数参数较复杂,此处省略。
stl注意点
- size 是当前容器真实占用的大小,也就是容器当前拥有多少个容器。
- 因为是实时的大小,所以在对容器进行操作后size大小会变化,特别注意在循环用size作循环条件时,如果在循环语句中对容器进行了操作,那么size会不断发生变化
- 对容器进行读取,删除,弹出等操作时一定要先判空,如对
stack.top()
使用时必须先判空,否侧可能程序不会报错但无法运行 - 如果需要对deque进行排序的话,最好是先复制到vector中,然后再进行排序,最后在把元素拷贝回来,这样效率会提高一点。
v1.5.2