順序容器 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 容器適配器