參考：

C語言：

C語言實現類似C++的容器vector

1. 容器概述

1.1. 順序容器、關聯容器 ----區分

可以用下標存取的容器有（既可以插入也可以賦值）：vector、deque、map；
特別要注意一下，vector和deque如果沒有預先指定大小，是不能用下標法插入元素的！、
序列式容器纔可以在容器初始化的時候指定大小，關聯式容器不行；
注意，關聯容器的迭代器不支援it+n操作，僅支援it++操作。

1.2. 特點分析

特點

標準容器適配器	特點
順序性容器
vector	從後面快速的插入與刪除，直接存取任何元素
deque	從前面或後面快速的插入與刪除，直接存取任何元素
list	雙鏈表，從任何地方快速插入與刪除
關聯容器
set	快速查詢，不允許重複值
multiset	快速查詢，允許重複值
map	一對多對映，基於關鍵字快速查詢，不允許重複值
multimap	一對多對映，基於關鍵字快速查詢，允許重複值
容器適配器
stack	後進先出
queue	先進先出
priority_queue	最高優先順序元素總是第一個出列

2. 順序容器

2.1. 概述

分類
1. vector
2. string (它不是類別範本）
3. list (雙向鏈表)
4. forward_list (單向鏈表)
5. deque (double-end queue,雙端佇列)
6. queue
7. priority_queue
8. stack

2.2. Vector 容器

常用操作

1. 屬性操作
    v1.size()　　　　　//v1內已經存放的元素的數目
    v1.capacity()　　　// v1現有的在儲存容量（不再一次進行擴張記憶體空間的前提下）
    v1.empty()　　　　 // 判斷v1是否爲空
    v1.max_size()　　　// 返回vector可以存放的最大元素個數，一般這個數很大，
                       //因爲vector可以不斷調整容量大小。
    v1.shrink_to_fit()　　// 該函數會把v1的capacity()的大小壓縮到size()大小，即釋放多餘的記憶體空間。

2. 存取操作：存取操作都會返回參照，通過它，我們可以修改vector中的值。
    v1[n]　　　　　　// 通過下標進行存取vector中的元素的參照
                    //（下標一定要存在 ，否則未定義，軟體直接崩了）
    v1.at(n)　　　　// 與上面類似，返回下標爲n的元素的參照，不同的是，如果下標不存在，
                        //它會拋出out_of_range的異常。它是安全的，建議使用它。
    v1.front()　　　// 返回vector中頭部的元素的參照（使用時，一定要進行非空判斷）
    v1.back()　　　 // 返回vector中尾部的元素 參照（使用時，一定要進行非空判斷）

3. 新增操作：
    v1.push_back(a)　　　　　　 //在迭代器的尾部新增一個元素
    v1.push_front(a)　　　　　　// vector不支援這個操作--------------------
    v1.insert(iter, a)　　　　　// 將元素a 插入到迭代器指定的位置的前面，
                        //返回新插入元素的迭代器（在c++11標準之前的版本，返回void)
    v1.insert(iter, iter1, iter2)　　　
        //把迭代器[iterator1, iterator2]範圍內的元素插入到迭代器iterator之前的位置，
        //返回新插入的第一個元素的迭代器（在c++11標準之前的版本， 返回空）。

標準與效率 問題：
    在c++11標準中，引入了emplac_front()、 emplace()、emplace_back(),
    它們分別與push_front()、insert()、 push_back()相對應，
    用法與完成的動作作完全相同，但是實現不一樣。
    push_front()、insert()各push_back()是對元素使用copy操作來完成的，
    而emplac_front()、 emplace()和emplace_back()是對元素使用構造來完成的，
    後者的效率更高，避免了不必要的操作。因此，在以後更後推薦使用它們。

4. 刪除操作：
    v1.erase(iterator)　　　　
        // 刪除人人迭代器指定的元素，
        //返回被刪除元素之後的元素的迭代器。（效率很低，最好別用）
    v1.pop_front() 　　　　　　//vector不支援這個操作-------------
    v1.pop_back()　　　　　　  //刪除vector尾部的元素 ， 返回void型別 (使用前，一定要記得非空判斷）
    v1.clear()　　　　　　　　 //清空所有元素

5. 替換操作：
    v1.assign({初始化列表})　　// 它相當於賦值操作，
    v1.assign(n, T)　　　　　　// 此操作與初始化時的操作類似，用n個 T型別的元素對v1進行賦值
    v1.assign(iter1, iter2)　　　
        // 使用迭代器[iter1, iter2]區間內的元素進行賦值（該迭代器別指向自身就可以），
        //另外，只要迭代器指的元素型別相同即可（存放元素的容器不同，
        //例如：可以用list容器內的值對vector容器進行assign操作，而用 "=" 絕對做不到的。
    v1.swap(v2)　　　　　　
        // 交換v1與v2中的元素;
        //swap操作速度很快，因爲它是通過改變v1與v2兩個容器內的數據結構
        //（可能是類似指針之類的與v1和v2的系結）完成的，不會對容器內的每一個元素進行交換。
        //這樣做，不僅速度快，並且指向原容器的迭代器、參照以及指針等仍然有效，
        //因爲原始的數據沒有變。在c++ primer 中建議大家使用==非成員版本的swap()函數==，它在範型程式設計中很重要。
----註釋寫在後面；

2.3. string 容器

概述

string與vector類似，但是string不是一種類別範本，而就是一種型別，因爲它專門用於存放字元的（存放的元素型別已經明確），所以沒有設計爲類別範本。它的所有特性與vector相同，包括儲存在連續的空間／快速隨機存取／高效在尾部插入與刪除／低效在中間插入與刪除等， string的迭代器也支援算術運算。實際上，就可以把string型別看作爲vector型別， vector的所有特性都適合與string型別。當然，因爲string型別比vector模板更特例化一些，因此它肯定具有一些自己特有而vector沒有的特性，下面下麪總結一下。

在陳述之前，首先說明：

在string中(有一些也適用於C風格的字串），我們可以使用一組迭代器／單個迭代器（從此迭代器開始到字串末）／位置＋長度表示範圍／單個位置（從此位置到字串末）來表示字串中的範圍，這樣的參數記作range.
可以使用列表初始化的字串／使用字串＋range的組合形式表示的子字串 / 字面值常數（如「china」）來表示字串。這裏的字串包括string型別的字串和C風格的char* 字串。字串使用字元args 表示。

正因爲pos和args的樣式可以隨意組合，所以string的操作函數的參數是多種的，因此它的過載函數數目很多，由於對於insert(pos, args)／append(args)／erase(pos,args)／replace(pos, args)等操作。

a. string的初始化
相對於vector型別來說， string 增加一個使用字面值型別進行初始化，即：

string a("xiaoming")
string a = "xiaoming"

b. string中包含的專有的操作（相對於vector來說）

string的新增與替換

在string中，增加了append(）與 replace()函數

str.append(args)　　　　// 在尾部新增一個字元或一個字元

str.replace(pos, args)　　　　// 在尾部新增一個字元或一個字元 ,它的過載函數很多,共16個。

string的存取子字串：

str.substr(_pos, n)　　//該函數可以獲得原字串中的部分字元, 從pos開始的n個字元，當_pos超過範圍時，會拋出out_of_range的異常。

str的搜尋操作：

str.find(args)　　//查詢args 第一次出現的位置

str.rfind(args)　　//查詢args最後一次出現的位置

str.find_first_of(args)　　　//搜尋的是字元，第一個是args裡的字元的位置

str.find_last_of(args)　　　// 搜尋的是字元，最後一個是args裡的字元的位置

str.find_first_not_of()　　// 搜尋的是字元，第一個不是args裡的字元的位置

str.find_last_not_of()　　// 搜尋的是字元，最後一個不是args裡的字元的位置

str的大小操作：

str.length()　　　// 該函數與str.size()函數完成一樣，只是名字不同而已罷了。只所以這樣搞的原因，可能開發人員感覺length更適合字串符，size更適合容器吧。

c字串的轉換函數

由數值轉換爲字串：

to_string(val):

由字串轉換爲數值：（要轉換的string的第一個非空白符必須是數值中可能出現的字元，處理直到不可能轉換爲數值的字元爲止，以下內容來自：c++primer）

stoi(str, pos, base) 　　// 字串轉換爲整型，其中str表示字串， pos用於表示第一個非數值字元的下標(意思就是我給函數傳入一個地址，它會對它進行賦第一個非數值字元的位置）, base表數值的基數，預設爲10，即10進位制數。
stol(str, pos, base)　　　　// 轉換爲long
stoul(str, pos, base)　　　　// 轉換爲 unsigned long
stoll(str, pos, base)　　　　// 轉換爲 long long
stoull(str, pos, base)　　　// 轉換爲unsigned long long
stof(str, pos)　　　　　　// 轉換爲float
stod(str, pos,)　　　　　// 轉換爲double
stold(str, pos,)　　　　　// 轉換爲long double

d 對字元的操作（在cctype標頭檔案中，並不屬於string標頭檔案的範圍，但是關係很緊密的）
以下內容來自:c++ primer 第五版p82, 只寫出部分常用來的(字母：alpha, 數位：number或digit)

isalnum©　　// 當爲字母或數位時爲真

isalpha©　　// 當爲字母時爲真

isdigit©　　// 當爲數位時真

islower©　　// 當爲小寫字母時爲真

issupper©　　// 當爲大寫字母時爲真

2.4. List 容器

概述
1. 與vector和string相比，list內部的實現爲一個雙向鏈表，元素儲存在非連續的記憶體空間，
2. 這就決定了它不能在常數時間內完成對元素的隨機存取，只能從頭到尾的遍歷一遍。
3. 因爲是用雙向鏈表實現的，所以，它的一大特性就是它的迭代器永遠不會變爲無效；
  （除非這段空間不存在了），即無論增加、刪除操作，都不會破壞迭代器。
大多數對vector的操作也適合於list，由於底層實現不同，有也差異：
list與vector的差別：
1. list支援push_front()、pop_front()操作；
2. list不支援vector中的隨機存取操作，即使用v1.at( )和v1[ ] 操作。
3. list的刪除與增加元素的操作不會破壞迭代器，而 vector與string 會使迭代器失效。
4. list 內部增加了一個sort()的方法，用於實現排序，不過呢，反正我感覺基本不用它，直接用裡的範型sort(）更好啊啊。
5. list增加了一個類似insert()的函數，爲splice( ) ：該函數可以實現在常數時間內把一個list 插入到另一個list內，與insert()的區別在於insert是進行copy, 而splice()直接操作的鏈表的指針指向。它有好幾個過載函數。
6. list的去重複函數： unique()；該函數的作用是去除連續重複的元素，參數即可以爲空，也可以傳入一個二元謂詞，用於確定相等的比較演算法。因爲unique()函數可能去除連續重複的元素，因此，很依賴配合上sort()函數使用啊。
7. list的合併函數merge(): 該函數就是合併兩個list，它在合併過程中會在兩個鏈表之間進行來回的比較，如果原來的兩個list是有順序的，合併之後的結果也是有序的，如果合併之前是無序的，合併之後也是無序的。反正吧，這個比較就這樣。

3. 關聯容器

3.1. 概述

分類
1. 有序關聯容器
  1. map
  2. multimap
  3. set
  4. multiset
2. 無序關聯容器
  1. unordered_map
  2. unordered_multimap
  3. unordered_set
  4. unordered_multiset
關聯容器與順序容器最大的區別：
1. 在於關聯容器沒有下標，都過鍵值或值本身進行索引。
2. 有序關聯容器內部通過紅黑樹實現的，當搜尋一個元素時，具有O(logn）的平均複雜度，
3. 而無序的關聯容器在底層是通過雜湊表（雜湊函數對映）實現的，當搜尋一個元素時，通常O(1)的平均複雜度，最壞爲O(logn)。

3.2. 有序關聯–map

map 容器
在介紹map之前，必須先介紹pair 型別。

pair型別：

pair型別定義在標頭檔案utility中。
pair型別爲一個結構體型別的模板，（在c++中結構體與類，除了預設的存取符不同，沒有其它任何區別）
pair 有兩個public的數據成員，分別爲first與second.
pair的初始化與大多數結構體或類的初始化相同：

pair<int, string> sb //初始化一個預設值的pair物件sb, 它的first是預設初始化的（0,內建型別預設初始化大多數應該是未定義的啊，它這是爲0）， second也是採用預設初始化（空字串）
pair<int, string> sb(1, 「japan」); //很常見的初始化方法
pair<int, string> sb = (1, 「japan」);
pair<int, string> sb{1,「japan」} //c++11中的列表初始化方法
pair<int, string> sb = {1, 「japan」}
可以呼叫make_pair()模板函數，返回一個pair物件：

1. map是用於存放鍵-值對的容器，它使用pair的first數據成員表示鍵（key)，second數據成員表示對應的值(value),所以呢，map是存放pair型別物件的容器。在map中，key都是固定的，一旦使用就不可以改變，而value是可以改變的， 因此會把pair型別的first數據成員的型別宣告爲const。

2. map的特性之一是：按value的大小進行有序存放（unordered_map是無序的）， 因此，構造mqp容器時，要求它的key型別必須能夠比較大小，當使用自定義的類型別時，

應該把過載的 operator< 運算子傳遞給map, 例如：

1 // 新增相關程式碼
2
3
4
5 …
3.在map中:

::value_type表示"鍵-值對"型別
::key_type表示鍵型別,vlue型別
::mapped_type 表示值的型別
例如： map<int, string>, 則 map<int, string>::value_type 與pair<int, string>等價， map<int, string>::key_type與int等價， map<int, string>::mapped_type與string等價;

4. map的存取操作：

map同樣支援使用迭代器，它會返回指向 pair型別的物件的迭代器
map 使用[]運算子通過key來存取對應的 value ，如果存取的key不存在，則會自動新增一個對應的pair 物件，其中它的value採用預設值。因此，當通過key來存取map時，
map不能是const型別。
map 使用at()成員函數通過key來存取對應的value, 如果存取的key不存在，則會拋出一個out_of_range的異常;
5. map的新增與刪除操作:

insert()或emplace()操作：當向map中插入不存在的元素（指key值不同）時,可以插入成功，當插入一個已經存在key值的pair物件時，ma不會作任何改變。因此，當對map進行插入操作時，需要知道有沒有插入成功。insert()與emplace()函數的返回值也是一個pair型別，first爲一個迭代器，指向插入時的鍵值對應的pair物件(可能是新插入的，也可能是已經存在的), second是一個bool型別，它表示是否插入成功(例如：當map中已經存在待插入的值時，爲false)
erase()操作：它有三個版本，前兩個版本與順序容器相同，使用迭代器指定一個位置或一對迭代器指定一個範圍，這時返回值爲一個迭代器，指向刪除之後的下一個元素；第三個版本的erase()很不錯，我很喜歡，它的參數爲key值，刪除對應key值的pair()物件, 返回值爲成功刪除的個數（可能爲0或1，在multimap中可能爲n)
6.查詢操作

find(key): 查詢一個特定key值的pair物件，如果找到就返回對應的迭代器，如果找不到，就返回.end()迭代器。
count(key)：統計在map容器中特徵key值的pair物件的個數.(在multimap與multiset中很有用的）
equal_range(key) // 返回一個pair型別，first表示low_bound, second表示upper_bound;
lower_bound(key) //返回迭代器，對應第一個大於等於key的元素
upper_bound(key) //返回迭代器，對應第一個大於key的元素（說明：其實，最後這四個函數，在multimap與multiset中是非常有用的）

C++ STL標準模板庫----容器