C++11无序关联容器有哪几种

C++11标准引入了无序关联容器（Unordered Associative Containers），这些容器基于哈希表实现，提供了平均常数时间复杂度的插入、删除和查找操作。与有序关联容器（如std::map和std::set）不同，无序关联容器不维护元素的顺序，而是通过哈希函数将元素映射到桶中。C++11标准中定义了四种无序关联容器，分别是std::unordered_set、std::unordered_multiset、std::unordered_map和std::unordered_multimap。

1. std::unordered_set

std::unordered_set是一个无序集合，它存储唯一的元素。与std::set不同，std::unordered_set不保证元素的顺序，而是通过哈希函数将元素映射到桶中。std::unordered_set的主要特点包括：

• 唯一性：std::unordered_set中的元素是唯一的，不允许重复。
• 哈希函数：元素通过哈希函数映射到桶中，哈希函数可以通过模板参数自定义。
• 平均常数时间复杂度：插入、删除和查找操作的平均时间复杂度为O(1)。

示例代码

#include <unordered_set>
#include <iostream>

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

    uset.insert(6);
    uset.erase(3);

    for (const auto& elem : uset) {
        std::cout << elem << " ";
    }
    return 0;
}

2. std::unordered_multiset

std::unordered_multiset是一个无序多重集合，它允许存储重复的元素。与std::unordered_set类似，std::unordered_multiset也不保证元素的顺序，而是通过哈希函数将元素映射到桶中。std::unordered_multiset的主要特点包括：

• 允许重复：std::unordered_multiset中的元素可以重复。
• 哈希函数：元素通过哈希函数映射到桶中，哈希函数可以通过模板参数自定义。
• 平均常数时间复杂度：插入、删除和查找操作的平均时间复杂度为O(1)。

示例代码

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_multiset<int> umset = {1, 2, 2, 3, 4, 4, 5};

    umset.insert(6);
    umset.erase(2);

    for (const auto& elem : umset) {
        std::cout << elem << " ";
    }
    return 0;
}

3. std::unordered_map

std::unordered_map是一个无序映射容器，它存储键值对。与std::map不同，std::unordered_map不保证键值对的顺序，而是通过哈希函数将键映射到桶中。std::unordered_map的主要特点包括：

• 键值对：std::unordered_map存储键值对，键是唯一的。
• 哈希函数：键通过哈希函数映射到桶中，哈希函数可以通过模板参数自定义。
• 平均常数时间复杂度：插入、删除和查找操作的平均时间复杂度为O(1)。

示例代码

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> umap = {{"apple", 1}, {"banana", 2}, {"cherry", 3}};

    umap.insert({"date", 4});
    umap.erase("banana");

    for (const auto& pair : umap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

4. std::unordered_multimap

std::unordered_multimap是一个无序多重映射容器，它允许存储多个具有相同键的键值对。与std::unordered_map类似，std::unordered_multimap也不保证键值对的顺序，而是通过哈希函数将键映射到桶中。std::unordered_multimap的主要特点包括：

• 允许重复键：std::unordered_multimap中的键可以重复，允许多个键值对具有相同的键。
• 哈希函数：键通过哈希函数映射到桶中，哈希函数可以通过模板参数自定义。
• 平均常数时间复杂度：插入、删除和查找操作的平均时间复杂度为O(1)。

示例代码

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_multimap<std::string, int> ummap = {{"apple", 1}, {"apple", 2}, {"banana", 3}};

    ummap.insert({"banana", 4});
    ummap.erase("apple");

    for (const auto& pair : ummap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

总结

C++11标准引入了四种无序关联容器：std::unordered_set、std::unordered_multiset、std::unordered_map和std::unordered_multimap。这些容器基于哈希表实现，提供了平均常数时间复杂度的插入、删除和查找操作。与有序关联容器不同，无序关联容器不维护元素的顺序，而是通过哈希函数将元素映射到桶中。根据具体需求，可以选择合适的无序关联容器来存储和操作数据。