在 C++ 的標準庫中，std::unordered_set?是基于哈希表實現的哈希集合。下面介紹這種語言里哈希集合的常用函數。

C++?std::unordered_set

1. 元素操作

• insert
  • 功能：向哈希集合中插入元素。如果元素已經存在，則不會重復插入。
  • 示例代碼：

#include <iostream>
#include <unordered_set>int main() {std::unordered_set<int> uset;uset.insert(1);uset.insert(2);for (auto num : uset) {std::cout << num << " ";}return 0;
}

• erase
  • 功能：從哈希集合中移除指定元素。可以通過元素值或者迭代器來指定要移除的元素。
  • 示例代碼：

#include <iostream>
#include <unordered_set>int main() {std::unordered_set<int> uset = {1, 2, 3};uset.erase(2);for (auto num : uset) {std::cout << num << " ";}return 0;
}

• find
  • 功能：查找指定元素。如果找到，返回指向該元素的迭代器；如果未找到，返回?end()?迭代器。
  • 示例代碼：

#include <iostream>
#include <unordered_set>int main() {std::unordered_set<int> uset = {1, 2, 3};auto it = uset.find(2);if (it != uset.end()) {std::cout << "Found: " << *it << std::endl;} else {std::cout << "Not found" << std::endl;}return 0;
}

• count
  • 功能：統計指定元素在哈希集合中的數量。由于哈希集合中元素唯一，返回值要么是 0（元素不存在），要么是 1（元素存在）。
  • 示例代碼：

#include <iostream>
#include <unordered_set>int main() {std::unordered_set<int> uset = {1, 2, 3};std::cout << "Count of 2: " << uset.count(2) << std::endl;return 0;
}

2. 容量相關

• empty
  • 功能：檢查哈希集合是否為空。如果為空，返回?true；否則返回?false。
  • 示例代碼：

#include <iostream>
#include <unordered_set>int main() {std::unordered_set<int> uset;std::cout << "Is empty: " << (uset.empty() ? "Yes" : "No") << std::endl;uset.insert(1);std::cout << "Is empty: " << (uset.empty() ? "Yes" : "No") << std::endl;return 0;
}

• size
  • 功能：返回哈希集合中元素的數量。
  • 示例代碼：

#include <iostream>
#include <unordered_set>int main() {std::unordered_set<int> uset = {1, 2, 3};std::cout << "Size: " << uset.size() << std::endl;return 0;
}

• max_size
  • 功能：返回哈希集合所能容納的最大元素數量，這取決于系統和庫的實現。
  • 示例代碼：

#include <iostream>
#include <unordered_set>int main() {std::unordered_set<int> uset;std::cout << "Max size: " << uset.max_size() << std::endl;return 0;
}

3. 迭代器相關

• begin?和?end
  • 功能：begin()?返回指向哈希集合首元素的迭代器，end()?返回指向哈希集合尾后位置的迭代器，可用于遍歷哈希集合。
  • 示例代碼：

#include <iostream>
#include <unordered_set>int main() {std::unordered_set<int> uset = {1, 2, 3};for (auto it = uset.begin(); it != uset.end(); ++it) {std::cout << *it << " ";}return 0;
}

• cbegin?和?cend
  • 功能：與?begin()?和?end()?類似，但返回的是常量迭代器，不能用于修改元素。
  • 示例代碼：

#include <iostream>
#include <unordered_set>int main() {const std::unordered_set<int> uset = {1, 2, 3};for (auto it = uset.cbegin(); it != uset.cend(); ++it) {std::cout << *it << " ";}return 0;
}

在 C++ 中，標準庫提供了基于哈希表實現的容器?std::unordered_map（存儲鍵值對）和?std::unordered_set（存儲單一元素），下面詳細介紹它們除了前面提到之外的常見函數和用法。

std::unordered_map

元素操作類

• emplace
  • 功能：原位構造元素并插入到?unordered_map?中。與?insert?不同，emplace?可以直接使用構造函數的參數來構造元素，避免了臨時對象的創建和拷貝。
  • 示例代碼：

#include <iostream>
#include <unordered_map>
#include <string>int main() {std::unordered_map<int, std::string> umap;umap.emplace(1, "one");for (const auto& pair : umap) {std::cout << pair.first << ": " << pair.second << std::endl;}return 0;
}

• emplace_hint
  • 功能：與?emplace?類似，但可以提供一個迭代器作為插入位置的提示，幫助提高插入效率。不過，這只是一個提示，插入位置不一定就是該迭代器所指的位置。
  • 示例代碼：

#include <iostream>
#include <unordered_map>
#include <string>int main() {std::unordered_map<int, std::string> umap = {{1, "one"}, {2, "two"}};auto hint = umap.begin();umap.emplace_hint(hint, 3, "three");for (const auto& pair : umap) {std::cout << pair.first << ": " << pair.second << std::endl;}return 0;
}

• extract
  • 功能：從?unordered_map?中提取一個元素，將其從容器中移除，但保留其資源，可用于后續的插入操作。
  • 示例代碼：

#include <iostream>
#include <unordered_map>
#include <string>int main() {std::unordered_map<int, std::string> umap = {{1, "one"}, {2, "two"}};auto node = umap.extract(1);if (node) {node.key() = 3;umap.insert(std::move(node));}for (const auto& pair : umap) {std::cout << pair.first << ": " << pair.second << std::endl;}return 0;
}

容量相關類

• reserve
  • 功能：為?unordered_map?預留一定數量的桶（bucket），避免在插入元素時頻繁進行哈希表的擴容操作，從而提高插入效率。
  • 示例代碼：

#include <iostream>
#include <unordered_map>
#include <string>int main() {std::unordered_map<int, std::string> umap;umap.reserve(100);for (int i = 0; i < 50; ++i) {umap[i] = std::to_string(i);}return 0;
}

• rehash
  • 功能：設置?unordered_map?的桶數量。如果指定的桶數量小于當前元素數量，可能會導致哈希表重新哈希以適應新的桶數量。
  • 示例代碼：

#include <iostream>
#include <unordered_map>
#include <string>int main() {std::unordered_map<int, std::string> umap = {{1, "one"}, {2, "two"}};umap.rehash(10);return 0;
}

哈希策略相關類

• load_factor
  • 功能：返回?unordered_map?當前的負載因子，即元素數量與桶數量的比值。負載因子過高可能會導致哈希沖突增加，影響性能。
  • 示例代碼：

#include <iostream>
#include <unordered_map>
#include <string>int main() {std::unordered_map<int, std::string> umap = {{1, "one"}, {2, "two"}};std::cout << "Load factor: " << umap.load_factor() << std::endl;return 0;
}

• max_load_factor
  • 功能：可以設置或獲取?unordered_map?的最大負載因子。當負載因子超過最大負載因子時，哈希表會自動進行擴容。
  • 示例代碼：

#include <iostream>
#include <unordered_map>
#include <string>int main() {std::unordered_map<int, std::string> umap;umap.max_load_factor(0.5);std::cout << "Max load factor: " << umap.max_load_factor() << std::endl;return 0;
}

std::unordered_set

std::unordered_set?的很多函數和用法與?std::unordered_map?類似，以下是一些額外的特點和示例：

元素操作類

• emplace?和?emplace_hint
  • 功能：與?unordered_map?中的?emplace?和?emplace_hint?類似，用于原位構造元素并插入到?unordered_set?中。
  • 示例代碼：

#include <iostream>
#include <unordered_set>int main() {std::unordered_set<int> uset;uset.emplace(1);auto hint = uset.begin();uset.emplace_hint(hint, 2);for (const auto& num : uset) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

容量和哈希策略相關類

unordered_set?同樣支持?reserve、rehash、load_factor?和?max_load_factor?等函數，用法與?unordered_map?一致，用于管理容量和哈希策略。

?