元素在順序容器中的順序與其加入容器時的位置相對應。關聯容器中元素的位置由元素相關聯的關鍵字值決定。所有容器類都共用公共的介面，不同容器按不同方式對其進行擴展。

　　一個容器就是一些特定類型對象的集合。順序容器為程式員提供了控制元素存儲和訪問順序的能力。

1. 順序容器概述

容器的兩種性能：

• 向容器中添加或刪除元素的代價
• 非順序訪問容器中元素的代價

順序容器類型：

如何確定使用哪種順序容器

NOTE：通常情況下，使用vector是最好的選擇。根據使用的需求對容器的哪種性能更加看重來選擇合適的容器。

2. 容器庫概覽

 容器類型上的操作有三個層次：

• 某些操作是所有容器類型都提供的
• 另外一些操作僅針對順序容器、關聯容器或無序容器
• 還有一些操作只適用於一小部分容器

每個容器都定義在一個頭文件中，文件名與類型名相同。容器均定義為模板類。

以下容器操作是所有容器類型所共有的操作

2.1 迭代器

迭代器範圍

一個迭代器範圍由一對迭代器表示，begin指向容器的首元素，end指向容器的尾元素之後的位置。

迭代器範圍是一個左閉合區間，[begin, end)。

begin可以和end指向同一個位置，但是end不能指向begin之前的位置。

2.2 容器類型成員

處理迭代器之外還有反向迭代器，對反向迭代器進行++操作，會得到上一個元素。

通過value_type得到元素類型，通過reference或const_reference得到元素類型的一個引用。

2.3 標準庫array具有固定大小

與內置數組一樣，array的大小也是類型的一部分。定義array時，除了指定元素類型，還要指定容器大小。

array<int, 42>  arr;

其構造函數和數組差不多，列表初始化時，列表元素不要超過array的大小，可以少，array剩下的元素就進行值初始化。

array<int, 10> a={1,2,3};

剩下的7個元素值初始化為0；

此外還可以對array進行拷貝或對象賦值操作，但內置數組是不支持的

int a1[3]={0,1,2};
int a2[3]=a1;    //錯誤
array<int, 3> a3={0,1,2};
array<int, 3> a4=a3;    //正確

 拷貝或賦值要保證類型相同。

2.4 賦值和swap

註意array在初始化的時候可以進行列表初始化，但是賦值的時候不能將一個花括弧列表賦值給它。

NOTE：array賦值的時候，兩邊的運算對象必須具有相同的類型。

array<int, 3> a1 = { 0, 1, 2 };
array<int, 3> a2 = { 0 };
array<int, 3> a3 = { 2, 3, 4 };
a1 = a2;
a3 = { 0 };    //錯誤

對a3賦值的時候，a3的類型是array<int,3>，而右邊是先把{0}轉換成臨時變數array<int,1> tmp,然後再將tmp賦值給a3，這是tmp和a3類型不一致。

由於可能因為大小不一致導致類型不一致，array不支持容器的賦值運算assign。

NOTE：assign操作僅適合順序容器

賦值運算符要求左右兩邊的運算對象具有相同的類型，將右邊運算對象所有元素拷貝到左邊運算對象中。

swap

swap交換兩個相同類型容器的內容。swap操作並不會交換元素本身，知識交換兩個容器的內部數據結構（除array外）。這就意味著，指向容器的迭代器、引用和指針在swap操作之後都不會失效，仍指向swap操作之前的那些元素，只是這些元素屬於不同容器了。

swap兩個array會真正交換他們的元素。

有兩個版本的swap：成員函數版本以及非成員版本，統一使用非成員版本的swap。

2.5 容器大小操作

• size：forward_list不支持size
• empty
• max_size

 2.6 關係運算符

每個容器類型都支持相等運算符（=和！=），除了無序容器外都支持關係運算符。關係運算符兩邊的運算對象必須是相同類型的容器，且必須保存相同類型的元素。

關係比較規則：

對元素進行逐對比較。大小相同、對應元素相等則相等；元素相等，大小不等，小的小於大的；都不相等，則比較第一個不相等的元素。

NOTE：只有當容器的元素定義了相應的比較運算符操作時，才可以使用關係運算符。

3. 順序容器操作

 順序容器和關聯容器的不同之處在於兩者組織元素的方式。這些不同之處直接關係到了元素如何存儲、訪問、添加以及刪除。接下來的操作都是順序容器所獨有的操作。

3.1 向順序容器中添加元素

新標準引入了三個新成員：emplace_front 、emplace和emplace_back，這些操作構造而不是拷貝元素。

當調用push或insert成員函數時，我們將元素類型的對象傳遞給它們，這些對象被拷貝到容器中。而當我們調用emplace成員函數時，則是將參數傳遞給元素類型的構造函數。

empalce函數的參數根據元素類型而變化，參數必須與元素類型的構造函數相匹配。

c.empalce("978-001",25,15.99);    //用三個參數直接構造對象
c.push_back("978-001",25,15.99);    //錯誤，沒有接受三個參數的push_back版本
c.push_back(Sales_data("978-001",25,15.99));    //正確

NOTE：emplace函數在容器中直接構造元素，而push_back則是創建臨時對象。

3.2 訪問元素

訪問成員函數返回的是引用

front、back、下標和at，其返回的都是引用。

如果我們使用auto變數來保存這些函數的返回值，並且希望使用此變數來改變元素的值，必須記得將變數定義為引用類型。

auto &v=c.back();    //獲得指向最後一個元素的引用
auto v=c.back();    //v不是一個引用，是c.back()的一個拷貝

 下標操作必須保證在範圍內操作

3.3 刪除元素

3.4 特殊的forward_list操作

forward_list並未定義insert、emplace和erase，而是定義了名為insert_after、emplace_after和erase_after的操作。

3.5 改變容器大小

list<int> ls(10,45);    //10個int，都是45
ls.resize(15);    //將5個值為0的元素添加到ls的末尾
ls.resize(25,-1);    //將10個值為-1的元素添加到ls的末尾
ls.resize(5);    //從ls末尾刪除20個元素

 3.6 容器操作可能使迭代器失效

由於向迭代器添加元素和從迭代器刪除元素的代碼可能會使迭代器失效，因此必須保證每次改變容器的操作之後都正確地重新定位迭代器。

4. vector對象是如何增長的

 每次都比實際所需空間多分配點空間，而不是每次都把所有元素移動到新空間。

管理容量的成員函數

capacity和size

size是指已經保存的元素的數目；而capacity則是在不分配新的記憶體空間的前提下它最多可以保存多少元素。

NOTE：只有當迫不得已時才可以分配新的記憶體空間。

5. 額外的string操作

 5.1 構造string的其他方法

string定義的這些額外操作要麼是提供string類和C風格字元數組之間的相互轉換，要麼是增加了允許我們用下標代替迭代器的版本。

substr操作

substr返回一個string，它是原始string的一部分或全部的拷貝，可以傳遞給substr一個可選的開始位置和計數值。

5.2 改變string的其他方法

string類型支持順序容器的賦值運算符以及assign、insert和erase操作。除此之外，還定義了額外的insert和erase版本。

s.insert(s.size(),5,'!');    //在s末尾插入5個感嘆號
s.erase(s.size()-5,5);    //從s刪除最後5個字元

const char *cp="Stately, plump Buck";
s.assign(cp,7);    //s=="Stately"
s.insrt(s.size(),cp+7);    //s=="Stately, plump Buck"

string s="some string", s2="some other string";
s.insert(0,s2);    //在s中位置0之前插入s2的拷貝
s.insert(0,s2,0,s2.size());

 5.3 string搜索操作

搜索是大小寫敏感的

逆向搜索

rfind成員函數搜索最後一個匹配，即子字元串最靠右的出現位置。

5.4 compare函數

5.5 數值轉換

6. 容器適配器

 除了順序容器外，標準庫還定義了三個順序容器適配器：stack、queue和priority_queue。容器、迭代器和函數都有適配器。

本質上，一個適配器是一種機制，能使某種事物的行為看起來像另一種事物一樣。

一個容器適配器接受一種已有的容器類型，使其行為看起來像一種不同的類型。