顺序容器 Sequential Containers
类库中定义了3种顺序容器：vector, list, deque。
对应3种适配器：stack, queue, priority_queue。
什么是适配器？
每种适配器都会对应一种容器，根据原始数据类型的操作重新定义了接口。
9.1 定义顺序容器
容器初始化的方法有：
1. Intializing a Container as a Copy of Another Container
将一个容器初始化为另一个容器的副本
|
vector<int> ivec;
vector<int> ivec2(ivec); // ok: ivec is vector<int>
|
2. 初始化为指定范围的元素的副本
这种方式和方式一的不同，就是不会限制容器的类型，只要元素element的类型能够匹配或者能够转换就可以。因此可以把vector中的元素copy给list。
下面这个例子把vector<char>拷贝给list<int>。
|
vector<char> cvec(10,'a');
list<int> ilist(cvec.begin(), cvec.end() );
|
|
// 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());
|
容器单元类型的限制条件
1. 单元类型必须支持赋值assignment
2. 单元类型必须可以拷贝
根据这两个限制条件得出：
引用
IO对象
是不能作为单元类型的。
但是单元类型也可以是容器。
这和Java有些不一样的地方：Java是不允许如int,double这样的基本数据类型作为单元对象。
9.2迭代器和迭代器范围
iterator的通用操作包括：
*iter
iter->mem
++iter iter++
--iter iter--
iter1 == iter2
iter1 != iter2
vector，deque支持额外的操作，包括：
iter + n
iter - n
iter1 += iter2
iter1 -= iter2
iter1 - iter2
>, >=, <, <=
迭代器范围
迭代器范围由一对迭代器来标记。这两个迭代器分别指向同一个容器中的两个元素或超出末端的下一位置，通常将它们命名为 first 和 last，或 beg 和 end，用于标记容器中的一段元素范围。
last和end的区别是last是指向迭代器范围内的最后一个元素，而end指向的是最后一个元素后的那个位置。
l [ first, last )
这里所描述的迭代器范围更多是用在例如erase,insert等容器的操作都会用到迭代器范围的概念：
|
void insert ( iterator position, InputIterator first, InputIterator last );
iterator erase ( iterator first, iterator last );
|
这些操作的迭代器范围都是不包含last的。
l 一些操作能够使得迭代器失效，这类操作主要是添加和删除操作，例如erase(),insert()。
9.3 Sequence Container Operations顺序容器操作
有四类：
1. Add elements to the container
在容器中添加元素。
2. Delete elements from the container
在容器中删除元素。
3. Determine the size of the container
设置容器大小。
4. Fetch the first and last elements from the container, if any
（如果有的话）获取容器内的第一个和最后一个元素。
Container Typedefs容器定义的类型别名
每种容器都要定义一下的类型（type）：
|
size_type
iterator
const_iterator
reverse_iterator
const_reverse_iterator
difference_type
value_type
reference
const_reference
|
咔咔，目前为止我不明白这些东东（value_type，reference，const_reference）是干嘛用的。大师说到16章就会豁然大悟的。期待…
在顺序容器中添加元素
|
iterator insert ( iterator position, const T& x );
void insert ( iterator position, size_type n, const T& x );
template <class InputIterator>
void insert ( iterator position, InputIterator first, InputIterator last );
|
container elements are copies.当我们向一个容器中追加一个element时，我们实际是把单元的值拷贝到容器里。这意味着后续的对容器内的element改变是不会影响被拷贝的值的，反之亦然。
这点就和Java有很大的不同，在Java中你可以把一个对象追加到Vector中，在后续的操作中修改Vector中每个element的值。也会导致最初被拷贝的对象值发生改变。
以下是java代码，
|
{
Vector a = new Vector();
StringBuffer sb1= new StringBuffer();
sb1.append("123");
a.add(sb1);
System.out.println( "<1> " + ((StringBuffer)a.elementAt(0)).toString());
sb1.append("123");
System.out.println( "<2> " + ((StringBuffer)a.elementAt(0)).toString());
}
|
输出：
Java的容器中追加的应该是对象的引用。
任何的添加操作都会导致迭代器失效
Relational Operators 关系操作符
前提是相同的容器类型和相同的元素（element）类型要相同。
容器的比较是使用和元素类型相同的关系操作符：就是说使用!=关系运算符比较两个容器，也就是使用!=关系运算符比较元素类型。这样如果元素类型并不支持这种比较操作，那么容器就不能进行这样的比较。
C++ 语言只允许两个容器做其元素类型定义的关系运算。We can compare two containers only if the same relational operator defined for the element types.
容器大小操作
有四种关于大小的操作：
|
size()
empty()
resize()
max_size()
|
resize()会导致迭代器失效（invalidate all iterators）。
访问元素
有4类操作，返回值是引用。
|
back()
front()
at //如果越界，会抛出异常out_of_range exception
operator[] //只会产生run-time error
|
不要和以下的操作混淆：
前一组操作返回的是引用，后一组begin，end返回值是迭代器。但是二者还是有关系的：
这组代码真是简明扼要啊：（欣赏）
|
// check that there are elements before dereferencing an iterator
// or calling front or back
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();
}
|
删除元素 Erasing Elements
删除操作有4类：
|
erase()
clear()
pop_back()
pop_front()
|
注意：
l erase操作是不检查参数的有效性的。因此要程序员来保证迭代器和迭代器范围是有效的。As usual, the erase operations don't check their argument(s). It is up to the programmer to ensure that the iterator or iterator range is valid.
l 删除操作和添加操作一样都会使得迭代器失效。
赋值和交换 Assignment and swap
9.5 决定使用哪种容器
插入操作如何影响容器的选择
vector和deque提供快速的随机访问容器中元素，但是这是以在非结尾处添加或删除元素开销很大为代价的。而list恰好相反。
list：当追加或删除元素时，不需要移动其它的元素。因此随机访问也就不支持。访问一个元素需要遍历所有的元素。
vector：当追加一个元素时，这个元素右边的所有元素都要移动。因此在vector开始的位置插入或者删除的开销最大。
deque：提供了vector和list的特性。
关于选择使用哪一种容器的提示
除非有其它更好的理由来使用其它的容器，否则vector是最好的选择。
容器选择法则：
1. If the program requires random access to elements, use a vector or a deque.
如果程序要求随机访问元素，则应使用 vector 或 deque 容器。
2. If the program needs to insert or delete elements in the middle of the container, use a list.
如果程序必须在容器的中间位置插入或删除元素，则应采用 list 容器。
3. If the program needs to insert or delete elements at the front and the back, but not in the middle, of the container, use a deque.
如果程序不是在容器的中间位置，而是在容器首部或尾部插入或删除元素，则应采用 deque 容器。
4. If we need to insert elements in the middle of the container only while reading input and then need random access to the elements, consider reading them into a list and then reordering the list as appropriate for subsequent access and copying the reordered list into a vector.
如果只需在读取输入时在容器的中间位置插入元素，然后需要随机访问元素，则可考虑在输入时将元素读入到一个 list 容器，接着对此容器重新排序，使其适合顺序访问，然后将排序后的 list 容器复制到一个 vector 容器。
起支配作用的操作决定容器的类型。In general, the predominant operation of the application should determine the choice of container type.
9.6 重新来看string string Revisited
把string看做容器
string支持大多数的顺序的容器操作。
为什么要在这章里又单独把string拎出来？因为可以把string看做是char的容器。string只是不支持堆栈操作，例如：front, back, pop_back。
string和vector一样，元素是按顺序保存的。
所以可以用迭代器来访问一个string哦。
|
string s("Hiya!");
string::iterator iter = s.begin(); //这样的代码很奇特。
while (iter != s.end())
cout << *iter++ << endl; // postfix increment: print old value
|
其它方式来创建string Other Ways to Construct strings
继承于vector的构造函数
|
string s1; // s1 is the empty string
string s2(5, 'a'); // s2 == "aaaaa"
string s3(s2); // s3 is a copy of s2
string s4(s3.begin(), s3.begin() + s3.size() / 2); // s4 == "aa"
|
string特有的构造函数：
|
string s(cp, n)
|
创建一个 string 对象，它被初始化为 cp 所指向数组的前 n 个元素的副本
|
|
string s(s2, pos2)
|
创建一个 string 对象，它被初始化为一个已存在的 string 对象 s2 中从下标 pos2 开始的字符的副本
|
|
string s(s2, pos2, len2)
|
创建一个 string 对象，它被初始化为 s2 中从下标 pos2 开始的 len2 个字符的副本。
|
Example:
|
char *cp = "Hiya"; // null-terminated array
char c_array[] = "World!!!!"; // null-terminated
char no_null[] = {'H', 'i'}; // not null-terminated
string s1(cp); // s1 == "Hiya"
string s2(c_array, 5); // s2 == "World"
string s3(c_array + 5, 4); // s3 == "!!!!"
string s4(no_null); // runtime error: no_null not null-terminated
string s5(no_null, 2); // ok: s5 == "Hi"
|
其它方式来修改string
string独有的操作
string的查找操作
比较操作
9.7 容器适配器