C++基础与技巧【顺序容器】 (三大顺序容器~vector, list, deque)_顺序寻址 vector list

C++基础与技巧【顺序容器】

标准库定义了三种顺序容器类型：vector、list 和 deque（是双端队列“double-ended queue”的简写，发音为“deck”）。它们的差别在于访问元素的方式，以及添加或删除元素相关操作的运行代价。

顺序容器：
vector 支持快速随机访问
list 支持快速插入/删除
deque 双端队列
顺序容器适配器：
stack 后进先出（LIFO）堆栈
queue 先进先出（FIFO）队列
priority_queue 有优先级管理的队列

为了定义一个容器类型的对象，必须先包含相关的头文件，即下列头文件之一：
#include <vector>
#include <list>
#include <deque>
所有的容器都是类模板。要定义某种特殊的容器，必须在容器名后加一对尖括号，尖括号里面提供容器中存放的元素的类型：
vector<string> svec; // empty vector that can hold strings
list<int> ilist; // empty list that can hold ints
deque<Sales_item> items; // empty deque that holds Sales_items

容器构造函数：
C<T> c; 创建一个名为 c 的空容器。C 是容器类型名，如 vector，T 是元素类型，如 int 或 string 适用于所有容器。
C c(c2); 创建容器 c2 的副本 c；c 和 c2 必须具有相同的容器类型，并存放相同类型的元素。适用于所有容器。
C c(b,e);创建 c，其元素是迭代器 b 和 e 标示的范围内元素的副本。适用于所有容器。
C c(n,t);用 n 个值为 t 的元素创建容器 c，其中值 t 必须是容器类型 C 的元素类型的值，或者是可转换为该类型的值。只适用于顺序容器。
C c(n); 创建有 n 个值初始化（value-initialized）元素的容器 c。只适用于顺序容器。

同时指定元素个数和初值的一个方法是将新创建的容器初始化为一个同类型的已存在容器的副本：
vector<int> ivec;
vector<int> ivec2(ivec); // ok: ivec is vector<int>
list<int> ilist(ivec); // error: ivec is not list<int>
vector<double> dvec(ivec); // error: ivec holds int not double
将一个容器复制给另一个容器时，类型必须匹配：容器类型和元素类型都必须相同。

使用迭代器时，不要求容器类型相同。容器内的元素类型也可以不相同，只要它们相互兼容，能够将要复制
的元素转换为所构建的新容器的元素类型，即可实现复制：

// initialize slist with copy of each element of svec
list<string> slist(svec.begin(), svec.end());
// find midpoint in the vector
vector<string>::iterator mid = svec.begin() + svec.size()/2;
// initialize front with first half of svec: The elements up to but not including *mid
deque<string> front(svec.begin(), mid);
// initialize back with second half of svec: The elements *mid through end of svec
deque<string> back(mid, svec.end());
允许通过使用内置数组中的对指针初始化容器：
char *words[] = {"stately", "plump", "buck", "mulligan"};
// calculate how many elements in words
size_t words_size = sizeof(words)/sizeof(char *);
// use entire array to initialize words2
list<string> words2(words, words + words_size);
其中第二个指针提供停止复制的条件，其所指向的位置上存放的元素并没有复制。

const list<int>::size_type list_size = 64;
list<string> slist(list_size, "eh?"); // 64 strings, each is eh?
这段代码表示 slist 含有 64 个元素，每个元素都被初始化为“eh?”字符串。

接受容器大小做形参的构造函数只适用于顺序容器，而关联容器不支持这种初始化。

C++ 语言中，大多数类型都可用作容器的元素类型。容器元素类型必须满足以下两个约束：
• 元素类型必须支持赋值运算。
• 元素类型的对象必须可以复制

引用不支持一般意义的赋值运算，因此没有元素是引用类型的容器。IO 库类型不支持复制或赋值。因此，不能创建存放 IO 类型对象的容器。

可以定义 vector 类型的容器 lines，其元素为 string 类型的 vector 对象：
// note spacing: use ">>" not ">>" when specifying a container element type
vector< vector<string> > lines; // vector of vectors
注意，在指定容器元素为容器类型时，必须如下使用空格：
vector< vector<string> > lines; // ok: space required between close>
vector< vector<string>> lines; // error: >> treated as shift operator

迭代器为所有标准库容器类型所提供的运算：

*iter 返回迭代器 iter 所指向的元素的引用
iter->mem 对 iter 进行解引用，获取指定元素中名为 mem 的成员。等效于(*iter).mem
*iter 返回迭代器 iter 所指向的元素的引用
++iter iter++ 给 iter 加 1，使其指向容器里的下一个元素
--iter iter-- 给 iter 减 1，使其指向容器里的前一个元素
iter1 ==iter2
iter1 !=iter2 比较两个迭代器是否相等（或不等）。当两个迭代器指向同一个容器中的同一个元素，或者当它们都指向同一个容器的超出末端的下一位置时，两个迭代器相等。

vector 和 deque 类型迭代器支持的操作：
iter + n
iter - n
在迭代器上加（减）整数值 n，将产生指向容器中前面（后面）第 n个元素的迭代器。新计算出来的迭代器必须指向容器中的元素或超出容器末端的下一位置。
iter1 +=iter2
iter1 -=iter2
这里迭代器加减法的复合赋值运算：将 iter1 加上或减去 iter2 的运算结果赋给 iter1。
iter1 -iter2
两个迭代器的减法，其运算结果加上右边的迭代器即得左边的迭代器。这两个迭代器必须指向同一个容器中的元素或超出容器末端的下一位置，只适用于 vector 和 deque 容器。
>, >=,<, <=
迭代器的关系操作符。当一个迭代器指向的元素在容器中位于另一个迭代器指向的元素之前，则前一个迭代器小于后一个迭代器。关系操作符的两个迭代器必须指向同一个容器中的元素或超出容器末端的下一位置，只适用于 vector 和 deque 容器。

我们已经使用过三种由容器定义的类型：size_type、iterator 和 const_iterator。所有容器都提供这三种类型。

容器定义的类型别名：
size_type 无符号整型，足以存储此容器类型的最大可能容器长度。
iterator 此容器类型的迭代器类型。
const_iterator 元素的只读迭代器类型。
reverse_iterator 按逆序寻址元素的迭代器。
const_reverse_iterator 元素的只读（不能写）逆序迭代器。
difference_type 足够存储两个迭代器差值的有符号整型，可为负数。
value_type 元素类型。
reference 元素的左值类型，是 value_type& 的同义词。
const_reference 元素的常量左值类型，等效于 const value_type&。

最后三种类型使程序员无须直接知道容器元素的真正类型，就能使用它。需要使用元素类型时，只要用 value_type 即可。如果要引用该类型，则通过 reference 和 const_reference 类型实现。

容器的begin 和 end 操作：
c.begin() 返回一个迭代器，它指向容器 c 的第一个元素
c.end() 返回一个迭代器，它指向容器 c 的最后一个元素的下一位置
c.rbegin() 返回一个逆序迭代器，它指向容器 c 的最后一个元素
c.rend() 返回一个逆序迭代器，它指向容器 c 的第一个元素前面的位置

除了 push_back 运算，list 和 deque 容器类型还提供了类似的操作：push_front。这个操作实现在容器首部插入新元素的功能。

在顺序容器中添加元素的操作：
c.push_back(t) 在容器 c 的尾部添加值为 t 的元素。

c.push_front(t) 在容器 c 的前端添加值为 t 的元素。只适用于 list 和 deque 容器类型。

c.insert(p,t) 在迭代器 p 所指向的元素前面插入值为 t 的新元素。返回指向新添加元素的迭代器。
c.insert(p,n,t) 在迭代器 p 所指向的元素前面插入 n 个值为 t 的新元素。返回 void 类型
c.insert(p,b,e) 在迭代器 p 所指向的元素前面插入由迭代器b和e标记的范围内的元素。返回 void 类型。

例子：string sarray[4] = {"quasi", "simba", "frollo", "scar"};
可将该数组中所有的或其中一部分元素插入到 string 类型的 list 容器中：
// insert all the elements in sarray at end of slist
slist.insert(slist.end(), sarray, sarray+4);
list<string>::iterator slist_iter = slist.begin();
// insert last two elements of sarray before slist_iter
slist.insert(slist_iter, sarray+2, sarray+4);

顺序容器的大小操作：
c.size() 返回容器 c 中的元素个数。返回类型为 c::size_type。
c.max_size() 返回容器 c 可容纳的最多元素个数，返回类型为c::size_type。
c.empty() 返回标记容器大小是否为 0 的布尔值。
c.resize(n) 调整容器 c 的长度大小，使其能容纳 n 个元素，如果 n <c.size()，则删除多出来的元素；否则，添加采用值初始化的新元素。
c.resize(n,t) 调整容器 c 的长度大小，使其能容纳 n 个元素。所有新添加的元素值都为 t。
访问顺序容器内元素的操作：
c.back() 返回容器 c 的最后一个元素的引用。如果 c 为空，则该操作未定义。
c.front() 返回容器 c 的第一个元素的引用。如果 c 为空，则该操作未定义。
c[n] 返回下标为 n 的元素的引用如果 n <0 或 n >= c.size()，则该操作未定义，只适用于 vector 和 deque 容器。
c.at(n) 返回下标为 n 的元素的引用。如果下标越界，则该操作未定义，只适用于 vector 和 deque 容器。

例程：if (!ilist.empty()) {
// val and val2 refer to the same element
list<int>::reference val = *ilist.begin();
list<int>::reference val2 = ilist.front();
// last and last2 refer to the same element
list<int>::reference last = *--ilist.end();
list<int>::reference last2 = ilist.back();

}

删除顺序容器内元素的操作：
c.erase(p) 删除迭代器 p 所指向的元素返回一个迭代器，它指向被删除元素后面的元素。

c.erase(b,e) 删除迭代器b和e所标记的范围内所有的元素，返回一个迭代器，它指向被删除元素段后面的元素。如果 e 本身就是指向超出末端的下一位置的迭代器，则返回的迭代器也指向容器的超出末端的下一位置。
c.clear() 删除容器 c 内的所有元素。返回 void。
c.pop_back() 删除容器 c 的最后一个元素。返回 void。如果 c 为空容器，则该函数未定义。
c.pop_front() 删除容器 c 的第一个元素。返回 void。如果 c 为空容器，则该函数未定义，只适用于 list 或 deque 容器。

使用find函数：

string searchValue("Quasimodo");
list<string>::iterator iter =find(slist.begin(), slist.end(), searchValue);
if (iter != slist.end())
slist.erase(iter);

顺序容器的赋值操作：
c1 = c2 删除容器 c1 的所有元素，然后将 c2 的元素复制给 c1。c2 的类型必须相同。
c1.swap(c2) 交换内容：调用完该函数后，c1 中存放的是 c2 原来的元素，c2 中存放的则是 c1 原来的元素。c.assign(b,e) 重新设置 c 的元素：将迭代器 b 和 e 标记的范围内所有的元素复制到 c 中。b 和 e 必须不是指向 c 中元素的迭代器。
c.assign(n,t) 将容器 c 重新设置为存储 n 个值为 t 的元素。

如果在不同（或相同）类型的容器内，元素类型不相同但是相互兼容，则其赋值运算必须使用 assign 函数。

swap 操作实现交换两个容器内所有元素的功能。

###################关于 swap 的一个重要问题在于：该操作不会删除或插入任何元素，而且保证在常量时间内实现交换。由于容器内没有移动任何元素，因此迭代器不会失效。##################################

例如：在做 swap 运算之前，有一个迭代器 iter 指向 svec1[3] 字符串；实现 swap 运算后，该迭代器则指向 svec2[3] 字符串（这是同一个字符串，只是存储在不同的容器之中而已）。

vector 和 deque容器提供了对元素的快速随机访问，但付出的代价是，在容器的任意位置插入或删除元素，比在容器尾部插入和删除的开销更大。list 类型在任何位置都能快速插入和删除，但付出的代价是元素的随机访问开销较大。

选择容器类型的法则：
1. 如果程序要求随机访问元素，则应使用 vector 或 deque 容器。
2. 如果程序必须在容器的中间位置插入或删除元素，则应采用 list 容器。
3. 如果程序不是在容器的中间位置，而是在容器首部或尾部插入或删除元素，则应采用 deque 容器。
4. 如果只需在读取输入时在容器的中间位置插入元素，然后需要随机访问元素，则可考虑在输入时将元素读入到一个 list 容器，接着对此容器重新排序，使其适合顺序访问，然后将排序后的 list 容器复制到一个vector
容器。

除了一些特殊操作，string 类型提供与 vector 容器相同的操作。

只适用于 string 类型的操作：
• substr 函数，返回当前 string 对象的子串。
• append 和 replace 函数，用于修改 string 对象。
• 一系列 find 函数，用于查找 string 对象。

适配器通用的操作和类型：
size_type 一种类型，足以存储此适配器类型最大对象的长度。
value_type 元素类型。
container_type 基础容器的类型，适配器在此容器类型上实现。
A a; 创建一个新空适配器，命名为 a。
A a(c); 创建一个名为 a 的新适配器，初始化为容器 c 的副本。
关系操作符 所有适配器都支持全部关系操作符：==、 !=、 <、 <=、 >、>=。

使用适配器时，必须包含相关的头文件：
#include <stack> // stack adaptor
#include <queue> // both queue and priority_queue adaptors

所有适配器都定义了两个构造函数：默认构造函数用于创建空对象，而带一个容器参数的构造函数将参数容器的副本作为其基础值。例如，假设 deq 是deque<int> 类型的容器，则可用 deq 初始化一个新的栈，如下所示：
stack<int> stk(deq); // copies elements from deq into stk

默认的 stack 和 queue 都基于 deque 容器实现，而 priority_queue 则在 vector 容器上实现。在创建适配器时，通过将一个顺序容器指定为适配器的第二个类型实参，可覆盖其关联的基础容器类型：
// empty stack implemented on top of vector
stack< string, vector<string> > str_stk;
// str_stk2 is implemented on top of vector and holds a copy of svec
stack<string, vector<string> > str_stk2(svec);

。stack 适配器
所关联的基础容器可以是任意一种顺序容器类型。因此，stack 栈可以建立在vector、list 或者 deque 容器之上。而 queue 适配器要求其关联的基础容器必须提供 push_front 运算，因此只能建立在 list 容器上，而不能建立在vector 容器上。priority_queue 适配器要求提供随机访问功能，因此可建立在vector 或 deque 容器上，但不能建立在 list 容器上。

栈容器适配器支持的操作：
s.empty() 如果栈为空，则返回 true，否则返回 stack。
s.size() 返回栈中元素的个数。
s.pop() 删除栈顶元素的值，但不返回其值。
s.top() 返回栈顶元素的值，但不删除该元素。
s.push(item) 在栈顶压入新元素。

标准库队列使用了先进先出（FIFO）的存储和检索策略。进入队列的对象被放置在尾部，下一个被取出的元素则取自队列的首部。标准库提供了两种风格的队列：FIFO 队列（FIFO queue，简称 queue），以及优先级队列（priority queue）。

队列和优先级队列支持的操作：
q.empty() 如果队列为空，则返回 true，否则返回 false。
q.size() 返回队列中元素的个数。
q.pop() 删除队首元素，但不返回其值。
q.front() 返回队首元素的值，但不删除该元素，该操作只适用于队列。
q.back() 返回队尾元素的值，但不删除该元素，该操作只适用于队列。
q.top() 返回具有最高优先级的元素值，但不删除该元素，该操作只适用于优先级队列。
q.push(item) 对于 queue，在队尾压入一个新元素，对于 priority_quue，在基于优先级的适当位置插入新元素。