一、種類

1. vector：變長數組，倍增的思想。給數組申請空間所耗費的時間取決于申請次數，而不是申請空間的大小，即a[1]和a[10000]兩個數組的申請時間是基本一致的。
2. pair<int, string>：存儲一個二元組，前后兩個變量類型任意。也可以存儲多個類型，如pair<int, pair<int, string>>。
3. string：字符串。操作：substr(), c_str()
4. queue：隊列。操作：push(), front(), pop()
5. priority_queue：優先隊列。操作：push(), top(), pop()
6. stack：棧。操作：push(), top(), pop()
7. deque：雙端隊列。
8. set, map, multiset, multimap：基于平衡二叉樹（紅黑樹），動態維護有序序列。
9. unordered_set, unordered_map, unordered_multiset, unordered_multimap：哈希表。
10. bitset：壓位。

二、具體操作

• 所有STL中的對象均具備：

a.size()
a.empty()

• ?vector：

size()           // 返回元素個數
empty()          // 返回是否為空
clear()          // 清空
front()          // 返回數組的第一個數
back()           // 返回數組的最后一個數
push_back()      // 在數組的末尾插入一個數
pop_back()       // 彈出數組末尾的最后一個數
begin()          // vector的第0個數
end()            // vector最后一個數的后一位數
支持比較運算，如vector<int> a(4, 3), b(3, 4);其中, a < b。
當比較兩個vector對象時，實際上是在比較它們的字典序。
vector容器的比較操作符按照元素的順序進行比較。
它首先比較第一個元素，如果它們相等，則比較第二個元素，以此類推。

• pair：

first()         // 返回第一個元素
second()        // 返回第二個元素
支持比較運算，以first為第一個關鍵字，second為第二個關鍵字，按字典序。

• string

size()        
empty()
clear()
substr(a, b)        // 返回子串，a表示子串下標，b表示長度；
c_str()             
/*c_str()是C++中的一個字符串成員函數，用于返回一個指向以空字符結尾的字符數組（C風格字符串）的指針。
在C++中，字符串常常使用std::string類來表示。
c_str()函數允許我們將std::string對象轉換為C風格字符串的形式，即以const char*的形式表示。*/

• queue：

size()
empty()
push()            // 向隊尾插入一個元素
front()           // 返回隊頭元素
back()            // 返回隊尾元素
pop()             // 彈出隊頭元素
q = queue<int>()  // 清空queue

值得注意的是，queue沒有clear()操作。

• priority_queue:

push()    // 插入一個元素
top()     // 返回堆頂元素
pop()     // 彈出堆頂元素

默認是大根堆，小根堆定義如下：

priority_queue<int, vector<int>, great<int>> heap;

• stack：

size()
empty()
push()        // 向棧頂插入一個元素
top()         // 返回棧頂元素
pop()         // 彈出棧頂元素

• deque（效率較低，用的較少）：

size()
empty()
clear()
front()        // 返回第一個元素
back()         // 返回最后一個元素
push_back()    // 在末尾插入一個元素
pop_back()     // 彈出末尾一個元素
push_front()   // 在隊首插入一個元素
pop_front()    // 彈出隊首一個元素
begin()
end()

• set（不能有重復元素）/ multiset（可以有重復元素）：

size()
empty()
clear()
begin()    // 可++，--
end()insert()
find()
count()        // 返回某一個數的個數
erase()(1) 輸入一個數x，刪除所有x，時間復雜度：O(k + logn);(2) 輸入一個迭代器，刪除這個迭代器.
lower_bound(x)    // 返回大于等于x的最小數的迭代器
upper_bound(x)    // 返回大于x的最小數的迭代器
[]              // 時間復雜度是 O(logn)

• map / multimap

size()
empty()
clear()
begin()
end()insert()        // 插入的數是一個pair
erase()         // 輸入的參數是pair或者迭代器
find()
[]              // 時間復雜度是 O(logn)
lower_bound()
upper_bound()

• unordered_set,?unordered_map,?unordered_multiset,?unordered_multimap, 哈希表

和上面類似，增刪改查的時間復雜度是 O(1)，而除此之外上面的增刪改查的時間復雜度是 O(logn)，但支持和排序有關的操作。

不支持 lower_bound() / upper_bound()、迭代器的++和--

• bitset（壓位）：

bitset<10000> s;
~ & | ^
>>, <<
==, !=
[]count()    // 返回有多少個1
any()      // 判斷是否至少有一個1
none()     // 判斷是否全為0
set()      // 把所有位置變成1
reset()    // 把所有位置變成0
flip()     // 等價于~
flip(k)    // 把第k位取反