緒論

在復雜算法實現過程中我們經常會需要一個高效的集合數據結構，支持常數級別的增、刪、查，以及隨機返回、遍歷，最好還能夠支持交集、并集、子集操作

哈希集合實現

大家可能很快想到unordered_set，unordered_set由于底層是哈希表，所以自身就支持常數級別的增、刪、查，雖然不支持常數級別的隨機返回，但是可以很簡單地實現一個O(n)的隨機返回。于是我們可以很快實現一個好用的Set數據結構：

---

頭文件Set.h

// Copyright(C), Edward-Elric233
// Author: Edward-Elric233
// Version: 1.0
// Date: 2022/6/27
// Description: 封裝unordered_set實現支持交集、并集的set
#ifndef P_CENTER_SET_H
#define P_CENTER_SET_H#include <unordered_set>
#include <vector>
#include <iostream>namespace edward {class Set {std::unordered_set<int> set_;
public:Set() = default;~Set() = default;explicit Set(const std::vector<int> &arr):set_(arr.begin(), arr.end()) {}void insert(int x) {set_.insert(x);}void erase(int x) {set_.erase(x);}int size() const {return set_.size(); //size_t -> int}bool empty() const {return set_.empty();}bool exist(int x) const {return set_.count(x) > 0;}const std::unordered_set<int>& getSet() const {return set_;}int getRandom() const;const Set& operator&= (const Set& rhs);const Set& operator|= (const Set& rhs);bool operator<= (const Set& rhs) const;   //check if it's a subset of the right-hand side.friend Set operator& (const Set& lhs, const Set& rhs);friend Set operator| (const Set& lhs, const Set& rhs);friend std::ostream& operator<< (std::ostream &os, const Set& rhs);
};Set operator& (const Set& lhs, const Set& rhs);
Set operator| (const Set& lhs, const Set& rhs);
std::ostream& operator<< (std::ostream &os, const Set& rhs);}#endif //P_CENTER_SET_H

實現文件Set.cpp

// Copyright(C), Edward-Elric233
// Author: Edward-Elric233
// Version: 1.0
// Date: 2022/6/27
// Description: 
#include "Set.h"
#include "utils.h"namespace edward {const Set& Set::operator&=(const Set &rhs) {for (auto iter = set_.begin(); iter != set_.end(); ) {if (rhs.set_.count(*iter) == 0) {set_.erase(iter++);} else {++iter;}}return *this;
}const Set& Set::operator|=(const Set &rhs) {for (auto x : rhs.set_) {insert(x);}return *this;
}bool Set::operator<=(const Set &rhs) const {//check if it's a subset of the right-hand side.for (auto x : set_) {if (!rhs.exist(x)) return false;}return true;
}Set operator& (const Set& lhs, const Set& rhs) {if (lhs.size() > rhs.size()) {return operator&(rhs, lhs);} else {//lhs.size() <= rhs.size()Set ans;for (auto x : lhs.set_) {if (rhs.set_.count(x) > 0) {ans.insert(x);}}return ans;}
}
Set operator| (const Set& lhs, const Set& rhs) {//按秩合并if (lhs.size() > rhs.size()) {return operator|(rhs, lhs);} else {//lhs.size() <= rhs.size()Set ans = rhs;return ans |= lhs;}
}std::ostream& operator<< (std::ostream &os, const Set& rhs) {for (auto x : rhs.set_) {os << x << " ";}return os;
}int Set::getRandom() const {int idx = Random::rand(size());auto iter = set_.begin();while (idx--) ++iter;return *iter;
}}

標記數組實現

使用哈希表其實幫助我們解決了常數插入刪除的問題，但是當我們尤其要求集合的高效時使用哈希表仍然有比較高的復雜度常數。這就要求我們使用空間換時間的思想：直接用數組進行哈希，每個元素值本身就是自己在數組中的下標（值到下標的哈希映射為：$x?x$）。這種哈希毋庸置疑是最快的，因為根本不需要進行運算，但是我們存在無法遍歷和隨機返回的問題，為了解決這個問題，我們再用一個輔助的數組存儲值，而標記數組中則存儲的是值在輔助數組中的下標，只要我們能夠保證元素在輔助數組中是緊湊的，那么就可以實現遍歷和隨機返回，并且隨機返回是O(1)的。
這種實現能夠滿足我們絕大多數需求，但是缺點也是顯而易見的：空間復雜度太高，每個集合的空間復雜度固定地為集合元素的值域的大小，當我們元素的值域不是太大的時候，我們就可以使用這種集合實現，否則就只能使用上面的哈希集合。

---

頭文件RandomSet.h

// Copyright(C), Edward-Elric233
// Author: Edward-Elric233
// Version: 1.0
// Date: 2022/7/4
// Description: 
#ifndef P_CENTER_RANDOMSET_H
#define P_CENTER_RANDOMSET_H#include <vector>
#include "utils.h"namespace edward {class RandomSet {std::vector<int> pos_, nums_;
public:explicit RandomSet(int n): pos_(n, -1) {nums_.reserve(n);}void insert(int x) {pos_[x] = nums_.size();nums_.push_back(x);}void erase(int x) {nums_[pos_[x]] = nums_.back();pos_[nums_.back()] = pos_[x];pos_[x] = -1;nums_.pop_back();}int size() const {return nums_.size(); //size_t -> int}bool empty() const {return nums_.empty();}bool exist(int x) const {return pos_[x] != -1;}const std::vector<int>& getSet() const {return nums_;}int getRandom() const {return nums_[Random::rand(nums_.size())];}friend std::ostream& operator<< (std::ostream& os, const RandomSet& randomSet);
};std::ostream& operator<< (std::ostream& os, const RandomSet& randomSet);}#endif //P_CENTER_RANDOMSET_H

實現文件RandomSet.cpp

// Copyright(C), Edward-Elric233
// Author: Edward-Elric233
// Version: 1.0
// Date: 2022/7/4
// Description: 
#include "RandomSet.h"namespace edward {std::ostream& operator<< (std::ostream& os, const RandomSet& randomSet) {for (auto x : randomSet.nums_) {os << x << " ";}return os;
}}

測試文件test.cpp

// Copyright(C), Edward-Elric233
// Author: Edward-Elric233
// Version: 1.0
// Date: 2022/6/27
// Description: 
#include "test.h"
#include "Set.h"
#include "utils.h"
#include "RandomSet.h"namespace edward {void test_Set() {/*edward::Set a({1,2}), b({3,4,5});//a.insert(4);print("a.size():", a.size());print("a & b:", a & b);print("a | b:", a | b);//print("a &= b:", a &= b);print("a |= b:", a |= b);*/
}void test_RandomSet() {RandomSet randomSet(10);randomSet.insert(0);randomSet.insert(1);randomSet.insert(2);print(randomSet);randomSet.erase(1);print(randomSet);print(randomSet.size());randomSet.erase(2);randomSet.erase(0);randomSet.insert(9);print(randomSet);
}void test_Set_efficiency() {constexpr int MAXN = 1000000;Timer timer_Set;edward::Set set;for (int i = 0; i < MAXN; ++i) {set.insert(i);}for (int i = 0; i < MAXN; i += 2) {set.erase(i);}for (int i = 0; i < MAXN; i += 2) {set.insert(i);}print("Set.size() =", set.size());timer_Set("Set:");Timer timer_RandomSet;edward::RandomSet randomSet(MAXN);for (int i = 0; i < MAXN; ++i) {randomSet.insert(i);}for (int i = 0; i < MAXN; i += 2) {randomSet.erase(i);}for (int i = 0; i < MAXN; i += 2) {randomSet.insert(i);}print("RandomSet.size() =", randomSet.size());timer_RandomSet("RandomSet:");
}}

其中print是我自己實現的打印可變參模板函數，Timer類是計時器，實現文件放在文章末尾。
測試結果如下：

Set.size() = 1000000
Set: 0.522428 s
RandomSet.size() = 1000000
RandomSet: 0.0637485 s

我們可以看出，使用數組實現的集合雖然存在大小的限制，但是操作平均快一個量級。對于我們需要設計高效算法的場合，我們可以使用后者。大家可能注意到我沒有在第二種實現RandomSet中重載集合操作，這是因為如果已經需要考慮優化常數的話，那么往往也不允許實現一個完整的集合操作（交集、并集、子集），而是要求用戶具體地手動實現，并根據實際情況進行優化。

代碼中的utils頭文件實現了print、Timer等工具函數和類，詳見博客：C++ 工具函數庫