|
本文主要讨论C++标准库中的顺序容器及相应的容器适配器，这些内容主要涉及顺序容器类型：vector、list、deque，顺序容器适配器类型：stack、queue、priority_queue。 标准库中的容器分为顺序容器和关联容器。顺序容器(sequential container)内的元素按其位置存储和访问，顾名思义，这些内部元素是顺序存放的；顺序容器内的元素排列次序与元素值无关，而是由元素添加到容器里的次序决定。而关联容器的元素按键(key)排序。 容器类共享部分公共接口。标准库定义的三种顺序容器类型：vector、list、deque（double-ended queue的缩写，发音为“deck”），它们的差别仅在访问元素的方式，以及添加或删除元素相关操作的代价。顺序容器适配器包括：stack、queue和priority_queue。容器只定义了少量操作，大多数操作由算法库提供。如果两个容器提供了相同的操作，则它们的接口（函数名和参数个数）应该相同。
容器类型
顺序容器的定义
顺序容器的构造和初始化
下表为迭代器为所有容器类型所提供的运算：
(责任编辑：admin)
vector和deque容器的迭代器提供了额外的运算：迭代器的算术运算和另一些关系运算，如下表所示：
关系操作符只适用于vector和deque容器，这是因为只有这两种容器为其元素提供快速、随机的访问。它们确保可根据元素位置直接有效地访问指定的容器元素。这两种容器都支持通过元素位置实现的随机访问，因此它们的迭代器可以有效地实现算术和关系运算。
迭代器范围：[first, last)是一个左闭合区间，表示范围从first开始，到last结束，但不包括last。注意：如果first不等于last，则对first反复做自增运算必须能够到达last；否则，即last位于first之前，则将发生未定义行为。
迭代器范围使用左闭合的意义：因为这样可以统一表示空集，就无需特别处理。
另外，使用迭代器时，要特别留意迭代器的可能的失效问题。
访问元素
删除元素
赋值与swap
注意：assign操作首先删除容器内所有的元素，再将参数所指定的新元素插入到容器中。
swap操作不会删除或插入任何元素，而且保证在常量时间内实现交换。由于容器内没有移动任何元素，因此迭代器不会失效。但要注意这些迭代器指向了另一个容器中的元素。
容器的选用：
vector和deque容器提供了对元素的快速访问，但付出的代价是，在容器的任意位置插入或删除元素，比在容器尾部插入和删除的开销更大，因为要保证其连续存储，需要移动元素；list类型在任何位置都能快速插入和删除，因为不需要保证连续存储，但付出的代价是元素的随机访问开销较大。特征如下：
1）与vector容器一样，在deque容器的中间insert或erase元素效率比较低；
2）不同于vector容器，deque容器提供高效地在其首部实现insert和erase的操作，就像在尾部一样；
3）与vector容器一样而不同于list容器的是，deque容器支持对所有元素的随机访问。
4）在deque容器首部或尾部删除元素则只会使指向被删除元素的迭代器失效。在deque容器的任何其他位置的插入和删除操作将使指向该容器元素的所有迭代器都失效。
容器的比较：
vector （连续的空间存储,可以使用[]操作符）快速的访问随机的元素，快速的在末尾插入元素，但是在序列中间岁间的插入，删除元素要慢，而且如果一开始分配的空间不够的话，有一个重新分配更大空间，然后拷贝的性能开销。
stack ：适配器，必须结合其他的容器使用，stl中默认的内部容器是deque。先进后出，只有一个出口，不允许遍历。 一些容器选用法则：
1）如果程序要求随机访问元素，则应使用vector或deque容器；
2）如果程序必须在容器的中间位置插入或删除元素，则应采用list容器；
3）如果程序不是在容器的中间位置，而是在容器首部或尾部插入或删除元素，则应采用deque容器；
4）如果只需要在读取输入时在容器的中间位置插入元素，然后需要随机访问元素，则可以在输入时将元素读入到一个list容器中，然后对容器排序，再将排序后的list容器复制到vector容器中。
5）如果程序既需要随机访问，又需要在容器的中间位置插入或删除元素，此时应当权衡哪种操作的影响较大，从而决定选择list容器还是vector或deque容器。注：此时若选择使用vector或deque容器，可以考虑只使用它们和list容器所共有的操作，比如使用迭代器而不是下标，避免随机访问元素等，这样在必要时，可以很方便地将程序改写为使用list容器。
容器适配器
适配器（adaptor）是标准库中通用的概念，包括容器适配器、迭代器适配器和函数适配器。本质上，适配器是使一事物的行为类似于另一事物的行为的一种机制。容器适配器让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现，只是发生了接口转换而已。
标准库提供了三种顺序容器适配器：queue, priority_queue和stack。
所有适配器都定义了两个构造函数：默认构造函数用于创建空对象，而带一个容器参数的构造函数将参数容器的副本作为其基础值。
默认的stack和queue都基于deque容器实现，而priority_queue则在vector容器上实现。在创建适配器时，通过将一个顺序容器指定为适配器的第二个类型参数，可覆盖其关联的基础容器类型。例如：
stack<int, vector<int> > int_stack; // 此时，int-stack栈是基于vector实现
对于给定的适配器，其关联的容器必须满足一定的约束条件。stack适配器所关联的基本容器可以是任意一种顺序容器类型，因为这些容器类型都提供了push_back、pop_back和back操作；queue适配器要求其关联的基础容器必须提供pop_front操作，因此其不能建立在vector容器上；priority_queue适配器要求提供随机访问功能，因此不能建立在list容器上。
两个相同类型的适配器可以做==, !=, <, >, <=, >=这些关系运算，只要其基本元素类型支持==和<两个操作即可。这与容器大小比较原则一致。
这与容器大小比较原则一致。
栈
队列和优先级队列
标准库队列使用了先进先出（FIFO）的存储和检索策略，进入队列的元素被放置在尾部，下一个被取出的元素则取自队列的首部。
priority_queue默认使用元素类型的 < 操作符来确定它们之间的优先级关系，用户也可以定义自己的优先级关系。在优先级队列中，新元素被放置在比它优先级低的元素的前面。
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||