跳转至

關聯式容器

set

set 是關聯容器，含有鍵值類型對象的已排序集，搜索、移除和插入擁有對數複雜度。set 內部通常採用 紅黑樹 實現。平衡二叉樹 的特性使得 set 非常適合處理需要同時兼顧查找、插入與刪除的情況。

和數學中的集合相似，set 中不會出現值相同的元素。如果需要有相同元素的集合，需要使用 multiset。multiset 的使用方法與 set 的使用方法基本相同。

插入與刪除操作

  • insert(x) 當容器中沒有等價元素的時候，將元素 x 插入到 set 中。
  • erase(x) 刪除值為 x 的 所有 元素，返回刪除元素的個數。
  • erase(pos) 刪除迭代器為 pos 的元素，要求迭代器必須合法。
  • erase(first,last) 刪除迭代器在 \([first,last)\) 範圍內的所有元素。
  • clear() 清空 set。
insert 函數的返回值

insert 函數的返回值類型為 pair<iterator, bool>，其中 iterator 是一個指向所插入元素（或者是指向等於所插入值的原本就在容器中的元素）的迭代器，而 bool 則代表元素是否插入成功，由於 set 中的元素具有唯一性質，所以如果在 set 中已有等值元素，則插入會失敗，返回 false，否則插入成功，返回 true；map 中的 insert 也是如此。

迭代器

set 提供了以下幾種迭代器：

  1. begin()/cbegin()
    返回指向首元素的迭代器，其中 *begin = front。
  2. end()/cend()
    返回指向數組尾端佔位符的迭代器，注意是沒有元素的。
  3. rbegin()/crbegin()
    返回指向逆向數組的首元素的逆向迭代器，可以理解為正向容器的末元素。
  4. rend()/crend()
    返回指向逆向數組末元素後一位置的迭代器，對應容器首的前一個位置，沒有元素。

以上列出的迭代器中，含有字符 c 的為只讀迭代器，你不能通過只讀迭代器去修改 set 中的元素的值。如果一個 set 本身就是隻讀的，那麼它的一般迭代器和只讀迭代器完全等價。只讀迭代器自 C++11 開始支持。

查找操作

  • count(x) 返回 set 內鍵為 x 的元素數量。
  • find(x) 在 set 內存在鍵為 x 的元素時會返回該元素的迭代器，否則返回 end()。
  • lower_bound(x) 返回指向首個不小於給定鍵的元素的迭代器。如果不存在這樣的元素，返回 end()。
  • upper_bound(x) 返回指向首個大於給定鍵的元素的迭代器。如果不存在這樣的元素，返回 end()。
  • empty() 返回容器是否為空。
  • size() 返回容器內元素個數。
lower_bound 和 upper_bound 的時間複雜度

set 自帶的 lower_bound 和 upper_bound 的時間複雜度為 \(O(\log n)\)。

但使用 algorithm 庫中的 lower_bound 和 upper_bound 函數對 set 中的元素進行查詢，時間複雜度為 \(O(n)\)。

nth_element 的時間複雜度

set 沒有提供自帶的 nth_element。使用 algorithm 庫中的 nth_element 查找第 \(k\) 大的元素時間複雜度為 \(O(n)\)。

如果需要實現平衡二叉樹所具備的 \(O(\log n)\) 查找第 \(k\) 大元素的功能，需要自己手寫平衡二叉樹或權值線段樹，或者選擇使用 pb_ds 庫中的平衡二叉樹。

使用樣例

set 在貪心中的使用

在貪心算法中經常會需要出現類似 找出並刪除最小的大於等於某個值的元素。這種操作能輕鬆地通過 set 來完成。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// 現存可用的元素
set<int> available;
// 需要大於等於的值
int x;

// 查找最小的大於等於x的元素
set<int>::iterator it = available.lower_bound(x);
if (it == available.end()) {
  // 不存在這樣的元素，則進行相應操作……
} else {
  // 找到了這樣的元素，將其從現存可用元素中移除
  available.erase(it);
  // 進行相應操作……
}

map

map 是有序鍵值對容器，它的元素的鍵是唯一的。搜索、移除和插入操作擁有對數複雜度。map 通常實現為 紅黑樹。

設想如下場景：現在需要存儲一些鍵值對，例如存儲學生姓名對應的分數：Tom 0，Bob 100，Alan 100。但是由於數組下標只能為非負整數，所以無法用姓名作為下標來存儲，這個時候最簡單的辦法就是使用 STL 中的 map。

map 重載了 operator[]，可以用任意定義了 operator < 的類型作為下標（在 map 中叫做 key，也就是索引）：

1
map<Key, T> yourMap;

其中，Key 是鍵的類型，T 是值的類型，下面是使用 map 的實例：

1
map<string, int> mp;

map 中不會存在鍵相同的元素，multimap 中允許多個元素擁有同一鍵。multimap 的使用方法與 map 的使用方法基本相同。

Warning

正是因為 multimap 允許多個元素擁有同一鍵的特點，multimap 並沒有提供給出鍵訪問其對應值的方法。

插入與刪除操作

  • 可以直接通過下標訪問來進行查詢或插入操作。例如 mp["Alan"]=100。
  • 通過向 map 中插入一個類型為 pair<Key, T> 的值可以達到插入元素的目的，例如 mp.insert(pair<string,int>("Alan",100));；
  • erase(key) 函數會刪除鍵為 key 的 所有 元素。返回值為刪除元素的數量。
  • erase(pos): 刪除迭代器為 pos 的元素，要求迭代器必須合法。
  • erase(first,last): 刪除迭代器在 \([first,last)\) 範圍內的所有元素。
  • clear() 函數會清空整個容器。
下標訪問中的注意事項

在利用下標訪問 map 中的某個元素時，如果 map 中不存在相應鍵的元素，會自動在 map 中插入一個新元素，並將其值設置為默認值（對於整數，值為零；對於有默認構造函數的類型，會調用默認構造函數進行初始化）。

當下標訪問操作過於頻繁時，容器中會出現大量無意義元素，影響 map 的效率。因此一般情況下推薦使用 find() 函數來尋找特定鍵的元素。

查詢操作

  • count(x): 返回容器內鍵為 x 的元素數量。複雜度為 \(O(\log(size)+ans)\)（關於容器大小對數複雜度，加上匹配個數）。
  • find(x): 若容器內存在鍵為 x 的元素，會返回該元素的迭代器；否則返回 end()。
  • lower_bound(x): 返回指向首個不小於給定鍵的元素的迭代器。
  • upper_bound(x): 返回指向首個大於給定鍵的元素的迭代器。若容器內所有元素均小於或等於給定鍵，返回 end()。
  • empty(): 返回容器是否為空。
  • size(): 返回容器內元素個數。

使用樣例

map 用於存儲複雜狀態

在搜索中，我們有時需要存儲一些較為複雜的狀態（如座標，無法離散化的數值，字符串等）以及與之有關的答案（如到達此狀態的最小步數）。map 可以用來實現此功能。其中的鍵是狀態，而值是與之相關的答案。下面的示例展示瞭如何使用 map 存儲以 string 表示的狀態。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// 存儲狀態與對應的答案
map<string, int> record;

// 新搜索到的狀態與對應答案
string status;
int ans;
// 查找對應的狀態是否出現過
map<string, int>::iterator it = record.find(status);
if (it == record.end()) {
  // 尚未搜索過該狀態，將其加入狀態記錄中
  record[status] = ans;
  // 進行相應操作……
} else {
  // 已經搜索過該狀態，進行相應操作……
}

遍歷容器

可以利用迭代器來遍歷關聯式容器的所有元素。

1
2
3
set<int> s;
typedef set<int>::iterator si;
for (si it = s.begin(); it != s.end(); it++) cout << *it << endl;

需要注意的是，對 map 的迭代器解引用後，得到的是類型為 pair<Key, T> 的鍵值對。

在 C++11 中，使用範圍 for 循環會讓代碼簡潔很多：

1
2
set<int> s;
for (auto x : s) cout << x << endl;

對於任意關聯式容器，使用迭代器遍歷容器的時間複雜度均為 \(O(n)\)。

自定義比較方式

set 在默認情況下的比較函數為 <（如果是非內置類型需要 重載 < 運算符）。然而在某些特殊情況下，我們希望能自定義 set 內部的比較方式。

這時候可以通過傳入自定義比較器來解決問題。

具體來説，我們需要定義一個類，並在這個類中 重載 () 運算符。

例如，我們想要維護一個存儲整數，且較大值靠前的 set，可以這樣實現：

1
2
3
4
5
struct cmp {
  bool operator()(int a, int b) { return a > b; }
};

set<int, cmp> s;

對於其他關聯式容器，可以用類似的方式實現自定義比較，這裏不再贅述。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用