unordered_set 的常用函数

在 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 一致，用于管理容量和哈希策略。