C++无序容器

• 1. std::unordered_set
• 2. std::unordered_map
• 3. std::unordered_multiset
• 4. std::unordered_multimap

此文来自👉容器库 - cppreference.com

容器库是类模板与算法的汇集，允许程序员简单地访问常见数据结构，例如队列、链表和栈。有三类容器——顺序容器、关联容器和无序关联容器——每种都被设计为支持不同组的操作

无序关联容器提供能快速查找（均摊 O(1) ，最坏情况 O(n) 的复杂度）的无序（哈希）数据结构。

1. #

唯一键的集合，按照键生成散列

• unordered_set 是含有 Key 类型唯一对象集合的关联容器。搜索、插入和移除拥有平均常数时间复杂度。

• 在内部，元素并 不以任何特别顺序排序，而是组织进桶中。元素被放进哪个桶完全依赖其值的哈希。这允许对单独元素的快速访问，因为哈希一旦确定，就准确指代元素被放入的桶。

• 不可修改容器元素（即使通过非 const 迭代器），因为修改可能 更改元素的哈希，并破坏容器。

例子#

#include <iostream>
#include <string>
#include <unordered_set>

int main()
{
    // 创建三个 string 的 unordered_set（映射到 string ）
    std::unordered_set<std::string> u = {
        "RED",
        "GREEN",
        "BLUE"
        };

    // 迭代并打印 unordered_set 的关键和值
    for (const auto &n : u)
    {
        std::cout << "Key:" << n << "\n";
    }

    // // 添加新入口到 unordered_set
    // "BLACK";
    // "WHITE";
    u.emplace("BLACK");
    u.emplace("WHITE");

    std::cout << "-----------------------------------------------\n";

    for (const auto &n : u) {
        std::cout << "Key:" << n << "\n";
    }

    // 用关键输出值
    for (const auto &n : {"BLACK", "WHITE"}) {
        if (u.find(n) != u.end()) 
        {
            std::cout << n << ": Found\n";
        }
        else {
            std::cout << n << "NOT found\n"; 
        }
        
    }
   
    return 0;
}

2. std::unordered_map#

键值对的集合，按照键生成散列，键是唯一的

• unordered_map 是关联容器，含有带唯一键的键-值 pair 。搜索、插入和元素移除拥有平均常数时间复杂度。

• 元素在内部不以任何特定顺序排序，而是组织进桶中。元素放进哪个桶完全依赖于其键的哈希。这允许对单独元素的快速访问，因为一旦计算哈希，则它准确指代元素所放进的桶。

例子#

#include <iostream>
#include <string>
#include <unordered_map>
 
int main()
{
    // 创建三个 string 的 unordered_map （映射到 string ）
    std::unordered_map<std::string, std::string> u = {
        {"RED","#FF0000"},
        {"GREEN","#00FF00"},
        {"BLUE","#0000FF"}
    };
 
    // 迭代并打印 unordered_map 的关键和值
    for( const auto& n : u ) {
        std::cout << "Key:[" << n.first << "] Value:[" << n.second << "]\n";
    }
 
    // 添加新入口到 unordered_map
    u["BLACK"] = "#000000";
    u["WHITE"] = "#FFFFFF";
 
    // 用关键输出值
    std::cout << "The HEX of color RED is:[" << u["RED"] << "]\n";
    std::cout << "The HEX of color BLACK is:[" << u["BLACK"] << "]\n";
 
    return 0;
}

3. std::unordered_multiset#

键的集合，按照键生成散列

• unordered_multiset 是关联容器，含有可能非唯一 Key 类型对象的集合。搜索、插入和移除拥有平均常数时间复杂度。

• 元素在内部并不以任何顺序排序，只是被组织到桶中。元素被放入哪个桶完全依赖其值的哈希。这允许快速访问单独的元素，因为一旦计算哈希，它就指代放置该元素的准确的桶。

例子#

#include <iostream>
#include <unordered_set>
 
int main()
{  
// 简单比较演示
    std::unordered_multiset<int> example = {1, 2, 3, 4};
 
    auto search = example.find(2);
    if (search != example.end()) {
        std::cout << "Found " << (*search) << '\n';
    } else {
        std::cout << "Not found\n";
    }
 
 	return 0;
 
}

4. std::unordered_multimap#

键值对的集合，按照键生成散列

• unordered_multimap 是无序关联容器，支持等价的关键（一个 unordered_multimap 可含有每个关键值的多个副本）和将关键与另一类型的值关联。 unordered_multimap 类支持向前迭代器。搜索、插入和移除拥有平均常数时间复杂度。

• 元素在内部不以任何特定顺序排序，而是组织到桶中。元素被放进哪个桶完全依赖于其关键的哈希。这允许到单独元素的快速访问，因为哈希一旦计算，则它指代元素被放进的准确的桶。

例子#

#include <iostream>
#include <unordered_map>
 
int main()
{  
// 简单比较演示
    std::unordered_multimap<int,char> example = {{1,'a'},{2,'b'}};
 
    auto search = example.find(2);
    if (search != example.end()) {
        std::cout << "Found " << search->first << " " << search->second << '\n';
    } else {
        std::cout << "Not found\n";
    }
 
 
 	return 0;
}