演演算法競賽向 C++ Standard Library 使用速查

2.1 pair

• operator= ：過載了賦值運運算元用於拷貝。
• first / second ：存取第一項或第二項。
• std::make_pair(a,b) ：新建元素對，自動檢測型別。
• operator<=> ：過載了各種比較運運算元，按第一關鍵字、第二關鍵字順序比較。

2.2 tuple

• operator= ：過載了賦值運運算元用於拷貝。
• std::get<i>(tp) ：獲取元組的第 i 項。
• std::get<T>(tp) ：獲取元組中型別為 T 的項。
• std::make_tuple(a,b,c,...)：新建元組，自動檢測型別。
• operator<=> ：過載比較運運算元，同樣是順序關鍵字比較。 …

2.3 string

與 vector 類似。其餘重要特性如下：

• c_str() ：生成一個 C 風格字串（尾部置 0）並返回其頭部指標。
• length() ：size() 的同義函數。
• append(str) ：後方追加字串，返回 *this。
• append(first, last) ：區間插入版本。
• operator+ ：連線兩個字串。
• compare(str) ：字典序比較。返回一個 int，用 <0 / ==0 / >0 判斷該字串小於 / 等於 / 大於引數字串。
• operator<=> ：字典序比較的運運算元過載。
• substr(pos=0, count)：返回 [pos, min(pos+count, size())) 的子串。時間複雜度與 count 成線性。
• pop_back() (C++11)
• find(str) / rfind(str) / find_first_of(c) / find_first_not_of(c) / find_last_of(c) / find_last_not_of(c)：找字串或字元，返回位置。若無，返回 npos=-1。無時間複雜度保證，不建議使用。

2.4 bitset

bitset<N> bs(val / str)：宣告一個長度為 N 的 bitset 並設定初值。

• & / ! / ^ / ~ / >> / << ：支援 AND / OR / XOR / NOT / 右移 / 左移等位運算系列。
• operator== ：判斷兩個 bitset 是否相同。
• test(idx) / operator[idx] ：前者會做越界檢查，丟擲異常。
• size()
• count() ：返回 1 的個數。
• all() (C++11) ：檢查是否全為 1。
• any() / none() ：檢查是否存在 1 / 沒有 1。
• set() / reset() ：所有位賦 1 / 0。
• flip() ：翻轉 0 / 1。

3.1 迭代器

宣告：形如 vector<int>::iterator iter = xxx.begin()。C++11 後可用 auto 代替型別宣告。

*iter 取值，iter++ 後繼。

雙向迭代器可 iter--，隨機存取迭代器支援加減、比較運算。

• begin(), end() ：返回迭代器。end() 常作為 NULL 使用。
• cbegin(), cend() (C++11) ：部分容器支援，返回唯讀迭代器。
• rbegin(), rend() ：部分容器支援，返回反向迭代器。
• crbegin(), crend() ：部分容器支援，返回唯讀反向迭代器。

3.2 公共性質

• operator= ：過載了賦值運運算元用於拷貝。
• empty() ：返回容器是否為空，即 v.begin() == v.end()。
• size() ：返回容器內元素個數。
• clear() ：清空容器。

4.1 vector

Find:

• crbegin()
• at(idx) / operator[idx] ：前者會做越界檢查，丟擲異常。
• front(), back() ：返回首尾元素參照。

Modify:

• push_back(x) / pop_back() ：均攤常數複雜度。
• insert(iter, val) ：於迭代器 iter 處插入，返回指向被插入元素的迭代器。 insert(iter, first, last) ：左閉右開區間插入，返回指向首個被插入元素的迭代器。 注意，此操作非常數時間複雜度。
• erase(iter) ：於迭代器 iter 處刪除，返回指向被刪除元素的後一個元素的迭代器。 erase(first, last) ：左閉右開區間刪除，返回指向被刪除元素的後一個元素的迭代器。 注意，此操作非常數時間複雜度。

Size:

• resize(n) ：改變長度，可指定補充元素預設值。
• shrink_to_fit() ：調整為恰好長度。

4.2 deque

• push_front(x), pop_front()

其餘與 vector 類似。

4.3 list

• 無隨機存取介面。
• insert(iter, val) / erase(iter) ：插入與刪除變為常數時間複雜度，參見 vector。
• sort(cmp) ：為連結串列特殊設計的 $O(n\log n)$ 穩定排序演演算法。

其餘與 deque 類似。

5.1 set / multiset

set<Key, Compare>：類似 priority_queue，可自定義比較方式。

Find：

• crbegin()
• count(x) ：返回值為 x 的元素數量。
• lower_bound(x) / upper_bound(x) ：為 set 特殊客製化的對數時間複雜度 lower_bound 和 upper_bound。

Modify:

• insert(x) ：插入元素 x。返回 pair<iterator, bool>，表示插入元素的迭代器與插入是否成功。 對於 multiset，由於插入不會失敗，insert 只返回迭代器。
• erase(x) ：刪除所有值為 x 的元素，返回刪除元素的個數。 erase(iter) ：刪除迭代器指向的元素，(C++11) 返回指向被刪除元素的後一個元素的迭代器。 erase(first, last)：左閉右開區間刪除，(C++11) 返回指向被刪除元素的後一個元素的迭代器。

auto it = s.find(x);
s.erase(it);

5.2 map / multimap

map<Key, T, Compare>：可自定義比較方式。

• 對迭代器解除參照得到 pair<Key, T>。
• insert(pair<Key, T>)
• at[key] / operator[key]：前者會做越界檢查，丟擲異常。

其餘與 set 類似。