【C++ STL】unordered_set/multiset的概念和其成员方法具体使用

发布时间:2024年01月18日

unordered_set

unordered_set 是 C++ 标准库中的无序集合容器,它基于哈希表实现,提供了高效的查找、插入和删除操作。由于是无序集合,元素的存储顺序不是按照插入顺序或者元素大小排序的。

1. 概念:

无序集合(Unordered Set)是一个不按照元素顺序存储的容器。在 unordered_set 中,元素的存储位置由哈希函数决定,因此无序集合具有快速的查找特性。

2. 成员方法:

2.1. 插入元素:

  1. insert(val):向无序集合中插入元素 val。
  2. emplace(args…):使用传递给 args… 的参数在无序集合中构造一个新元素。相比 insert 方法,emplace 可以直接在集合中构造元素,而不需要创建一个临时对象。
  3. emplace_hint(hint, args…):使用传递给 args… 的参数在无序集合中构造一个新元素,并将其插入到 hint 指向的位置之前。hint 是一个迭代器,用于提供插入的位置的提示。
#include <unordered_set>
#include <iostream>

struct MyStruct {
    int a;
    double b;

    MyStruct(int x, double y) : a(x), b(y) {}
};

int main() {
    std::unordered_set<int> mySet;
    mySet.insert(1);
    mySet.insert(2);
    mySet.insert(3);

	for (int num : mySet) {
        std::cout << num << " ";
    }
    
	std::unordered_set<MyStruct> mySet2;
	// 使用 emplace 插入元素
    mySet2.emplace(1, 2.5);
    mySet2.emplace(2, 3.7);
    mySet2.emplace(3, 4.9);
	
	// 遍历集合并输出元素
    for (const auto& elem : mySet2) {
        std::cout << "a: " << elem.a << ", b: " << elem.b << std::endl;
    }

	std::unordered_set<MyStruct> mySet3;
    // 使用 emplace_hint 插入元素
    auto hint = mySet3.begin();
    hint = mySet3.emplace_hint(hint, 1, 2.5);
    hint = mySet3.emplace_hint(hint, 2, 3.7);
    hint = mySet3.emplace_hint(hint, 3, 4.9);

    // 遍历集合并输出元素
    for (const auto& elem : mySet3) {
        std::cout << "a: " << elem.a << ", b: " << elem.b << std::endl;
    }

    return 0;
}

2.2. 删除元素:

erase(val):从无序集合中删除值为 val 的元素。

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> mySet = {1, 2, 3};
    mySet.erase(2);

    for (int num : mySet) {
        std::cout << num << " ";
    }

    return 0;
}

2.3. 查找元素:

  1. count(val):返回值为 val 的元素在集合中的数量,由于是无序集合,返回值只能是 0 或 1。
  2. find(val):返回指向值为 val 的元素的迭代器,如果找不到则返回 end()。
#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> mySet = {1, 2, 3};
    
    if (mySet.count(2) > 0) {
        std::cout << "2 exists in the set." << std::endl;
    }

    auto it = mySet.find(3);
    if (it != mySet.end()) {
        std::cout << "3 found in the set." << std::endl;
    }

    return 0;
}

2.4. 大小和清空:

  1. size():返回无序集合中元素的数量。
  2. empty():检查无序集合是否为空。
  3. clear():清空无序集合中的所有元素。
#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> mySet = {1, 2, 3};

    std::cout << "Size: " << mySet.size() << std::endl;
    std::cout << "Is empty: " << (mySet.empty() ? "true" : "false") << std::endl;

    mySet.clear();

    std::cout << "Size after clear: " << mySet.size() << std::endl;
    std::cout << "Is empty after clear: " << (mySet.empty() ? "true" : "false") << std::endl;

    return 0;
}

2.5. 桶操作:

  1. bucket_count():返回无序集合底层桶的数量。
  2. max_bucket_count():返回无序集合可能具有的最大桶数。
  3. bucket_size():返回无序集合中所有桶的平均元素数量。
  4. bucket(key):返回包含给定键 key 的桶的索引。
#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> mySet = {1, 2, 3};
    
    std::cout << "Bucket count: " << mySet.bucket_count() << std::endl;
    std::cout << "Max bucket count: " << mySet.max_bucket_count() << std::endl;
    for (const int& element : mySet) {
        std::cout << "Element " << element << " is in bucket " << mySet.bucket(element) << std::endl;
    }
    std::cout << "Average bucket size: " << mySet.bucket_size() << std::endl;

    return 0;
}

2.6. 哈希策略:

  1. load_factor():返回无序集合的当前负载因子。
  2. max_load_factor():返回或设置无序集合的最大负载因子。
#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> mySet = {1, 2, 3};
    
    std::cout << "Load factor: " << mySet.load_factor() << std::endl;

    mySet.max_load_factor(0.7); // 设置最大负载因子
    std::cout << "Max load factor: " << mySet.max_load_factor() << std::endl;

    return 0;
}

2.7. 桶迭代器:

  1. begin(n) 和 end(n):返回第 n 个桶的起始和结束迭代器。
#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> mySet = {1, 2, 3};
    
    for (size_t i = 0; i < mySet.bucket_count(); ++i) {
        std::cout << "Bucket " << i << ": ";
        for (auto it = mySet.begin(i); it != mySet.end(i); ++it) {
            std::cout << *it << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

3. 总结:

  1. unordered_set 特点和优势:
    (1) 无序性: 无序集合中的元素不按照插入顺序或者元素大小排序,而是根据哈希函数确定存储位置。
    (2) 快速查找: 由于底层使用哈希表,查找元素的时间复杂度为平均 O(1)。
    (3) 唯一性: 无序集合中的元素是唯一的,不允许重复。

  2. unordered_map 相较于 unordered_set:
    (1)元素允许重复,可以存储相同的元素多次。
    其他操作都是类似的。

在算法题中去掉重复元素,快速查找这两个特点可以有效利用起来,帮助快速解决复杂问题。


希望能更好掌握 unordered_set/multiset 的特性和使用方法。
欢迎关注🔎点赞👍收藏??留言📝

文章来源:https://blog.csdn.net/qq_46403377/article/details/135641580
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。