c++ 疑难杂症(12) unordered_map

std::unordered_map c++11引入，还没有实践过， 学习学习

1. 概念

这个自然是问AI了.

1.1 std::unordered_map是什么

std::unordered_map是C++标准库（STL）中的一个关联容器。它基于哈希表实现，可以存储一组键值对，并且支持快速的查找、插入和删除操作。这个容器的主要特点是它内部是无序的，元素的存储和检索不依赖于它们在容器中插入的顺序。相反，元素是通过键的哈希值来组织和检索的。

std::unordered_map中的元素是键值对（key-value pairs），每个键在容器中都是唯一的。键和值通过std::pair类型来表示，其中pair.first对应键（key），pair.second对应值（value）。

由于std::unordered_map是基于哈希表的，因此它的查找、插入和删除操作的平均时间复杂度都是O(1)，这在处理大量数据时非常高效。然而，需要注意的是，在最坏情况下，当哈希函数产生大量冲突时，这些操作的时间复杂度可能会增加。

此外，std::unordered_map还满足容器（Container）、具分配器容器（AllocatorAwareContainer）和无序关联容器（
UnorderedAssociativeContainer）的要求，这使得它在C++编程中具有广泛的应用。

1.2 它有什么特性

std::unordered_map具有以下特性：

• 无序性：std::unordered_map内部使用哈希表来存储数据，因此它不保证元素的顺序与插入顺序一致。这意味着每次遍历容器时，元素的顺序可能会有所不同。
• 键的唯一性：在std::unordered_map中，每个键都是唯一的。如果尝试插入一个已经存在的键，则新的键值对不会替换旧的键值对，而是插入操作无效。这保证了容器中不会出现重复的键。
• 常数时间复杂度：std::unordered_map的查找、插入和删除操作的平均时间复杂度都是O(1)，这意味着这些操作的速度非常快，即使在处理大量数据时也能保持高效。然而，需要注意的是，在最坏情况下，当哈希函数产生大量冲突时，这些操作的时间复杂度可能会增加。
• 基于哈希表实现：std::unordered_map底层使用哈希表来存储数据，哈希表是一种根据键的哈希值来组织数据的数据结构。这使得std::unordered_map能够快速地查找、插入和删除元素。
• 满足多种容器要求：std::unordered_map满足容器（Container）、具分配器容器（AllocatorAwareContainer）和无序关联容器（UnorderedAssociativeContainer）的要求，这使得它在C++编程中具有广泛的应用。

总之，std::unordered_map是一种高效、灵活且易于使用的关联容器，适用于需要快速查找、插入和删除键值对的场景。

1.3 实现原理是什么：

std::unordered_map的实现原理主要基于哈希表（hash table）数据结构。哈希表是一种通过计算键（key）的哈希值来快速定位存储位置的数据结构。以下是std::unordered_map的实现原理的简要说明：

0. 哈希函数：std::unordered_map使用一个哈希函数（hash function）将键转换为哈希值。哈希函数是一个将输入（键）映射到固定大小输出（哈希值）的函数。这个哈希值通常用于确定键在哈希表中的存储位置。
1. 桶数组（Bucket Array）：哈希表通常由一个桶数组组成，每个桶用于存储具有相同哈希值的键值对。std::unordered_map使用桶数组来组织这些键值对。桶数组的大小通常是固定的，但可以根据需要进行调整。
2. 链表或其他数据结构：在每个桶中，std::unordered_map使用一个链表（或其他数据结构，如双向链表）来存储具有相同哈希值的键值对。这是因为在哈希表中，不同的键可能会产生相同的哈希值，这种情况称为哈希冲突。链表用于解决这种冲突，确保每个键都能唯一地映射到一个位置。
3. 查找操作：当查找一个键时，std::unordered_map首先使用哈希函数计算键的哈希值，然后使用该哈希值定位到相应的桶。然后，它遍历该桶中的链表，直到找到匹配的键或遍历完整个链表。
4. 插入和删除操作：插入和删除操作也类似。首先，使用哈希函数计算键的哈希值以定位到相应的桶。然后，在桶的链表中执行插入或删除操作。

需要注意的是，std::unordered_map的性能高度依赖于哈希函数的选择和实现。一个好的哈希函数应该能够将键均匀地映射到桶数组中，以减少哈希冲突的发生。此外，std::unordered_map还使用了一种称为再哈希（rehashing）的技术来处理哈希冲突和动态调整桶数组的大小，以确保容器的性能。

2. 标准文档

std::unordered_map - cppreference.com

//在标头 `` 定义

template<
    class Key,
    class T,
    class Hash = std::hash,
    class KeyEqual = std::equal_to,
    class Allocator = std::allocator>
> class unordered_map;//(c++ 11 起)

namespace pmr {
    template<
        class Key,
        class T,
        class Hash = std::hash,
        class KeyEqual = std::equal_to
    > using unordered_map =
          std::unordered_map>>;
}//(c++17 起)
/*
Hash      - 散列函数（哈希）
KeyEqual  - 用于进行此容器所有的键比较的比较函数
Allocator - 用于此容器所有内存分配器的分配器
*/

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

元素在内部不以任何特定顺序排序，而是组织进桶中。元素放进哪个桶完全依赖于对应键的散列。具有相同散列码的键出现于同一个桶。这允许对单独元素的快速访问，因为一旦计算其散列，它即代表元素所放进的确切的桶。

如果映射的键相等性谓词在传递两个键时返回 true，则它们被认为 等价。如果两个键等价，则散列函数必须对它们返回相同的值。

std::unordered_map 满足容器 (Container) 、知分配器容器 (AllocatorAwareContainer) 和无序关联容器 (
UnorderedAssociativeContainer) 的要求。

迭代器失效

注解

• swap 函数不会使容器内的任何迭代器失效，但它们会使标记交换区域结尾的迭代器失效。
• 指向在容器中存储的键或数据的引用和指针只会因为擦除该元素而失效，即使对应迭代器失效也是如此。

成员类型

成员函数

非成员函数

示例

#include 
#include 
#include 
 
int main()
{
    // 创建包含三个字符串的（映射到字符串的）unordered_map
    std::unordered_map u =
    {
        {"红色", "#FF0000"},
        {"绿色", "#00FF00"},
        {"蓝色", "#0000FF"}
    };
 
    // 用于打印键值对的辅助 lambda 函数
    auto print_key_value = [](const auto& key, const auto& value)
    {
        std::cout << "键：[" << key << "] 值：[" << value << "]\n";
    };
 
    std::cout << "遍历并打印 unordered_map 的键值对，显式指定类型：\n";
    for (const std::pair& n : u)
        print_key_value(n.first, n.second);
 
    std::cout << "\n通过 C++17 的结构化绑定来遍历并打印 unordered_map 的键值对：\n";
    for (const auto& [key, value] : u)
        print_key_value(key, value);
 
    // 向 unordered_map 中添加两项
    u["黑色"] = "#000000";
    u["白色"] = "#FFFFFF";
 
    std::cout << "\n通过键输出值：\n"
                 "红色的十六进制表示：[" << u["红色"] << "]\n"
                 "黑色的十六进制表示：[" << u["黑色"] << "]\n\n";
 
    std::cout << "通过以先前不存在的键使用 operator[] 来插入新的键值对：\n";
    print_key_value("新键", u["新键"]);
 
    std::cout << "\n通过使用 auto 来遍历并打印键值对；\n"
                 "现在`新键`是映射中的一个键：\n";
    for (const auto& n : u)
        print_key_value(n.first, n.second);
}

可能的输出：

遍历并打印 unordered_map 的键值对，显式指定类型：
键：[蓝色] 值：[#0000FF]
键：[绿色] 值：[#00FF00]
键：[红色] 值：[#FF0000]
 
通过 C++17 的结构化绑定来遍历并打印 unordered_map 的键值对：
键：[蓝色] 值：[#0000FF]
键：[绿色] 值：[#00FF00]
键：[红色] 值：[#FF0000]
 
通过键输出值：
红色的十六进制表示：[#FF0000]
黑色的十六进制表示：[#000000]
 
通过以先前不存在的键使用 operator[] 来插入新的键值对：
键：[新键] 值：[]
 
通过使用 auto 来遍历并打印键值对；
现在`新键`是映射中的一个键：
键：[新键] 值：[]
键：[白色] 值：[#FFFFFF]
键：[黑色] 值：[#000000]
键：[蓝色] 值：[#0000FF]
键：[绿色] 值：[#00FF00]
键：[红色] 值：[#FF0000]

3. 探索

3.1 构造函数

std::unordered_map::unordered_map - cppreference.com

从各种数据源构造新容器。可选的以用户提供的 bucket_count 为用于创建的最小桶数，以 hash 为散列函数，以 equal 为比较键的函数，并以 alloc 为分配器。

1-5) 构造空容器。设置 max_load_factor() 为 1.0。对于默认构造函数，桶数是实现定义的。

6-8) 构造具有范围 [first,last) 的内容的容器。设置 max_load_factor() 为 1.0。如果范围中的多个元素的键比较相等，那么未指定哪个元素会被插入（参考待决的 LWG2844）。

9,10) 复制构造函数。构造拥有 other 内容副本的容器，一同复制加载因子、谓词和散列函数。若不提供 alloc，则通过调用 std::allocator_traits
::select_on_container_copy_construction(other.get_allocator()) 获得分配器。

11,12) 移动构造函数。用移动语义构造拥有 other 的内容的容器。若不提供 alloc，则通过从属于 other 的分配器进行移动构造来获得分配器。

13-15) 初始化式列表构造函数。构造拥有 initializer_list init 的内容的容器，同 unordered_map(init.begin(), init.end())。

参数

复杂度

1-5) 常数。

6-8) 平均情况为线性（即 O(N)，其中 N 为 std::distance(first, last)），最坏情况成平方，即 O(N2)。

9,10) 与 other 的大小成线性。

11,12) 常数。若给定 alloc 且 alloc != other.get_allocator() 则为线性。

13-15) 平均情况为 O(N)（N 为 std::size(init)），最坏情况为 O(N2)。

示例

#include 
#include 
#include 
#include 
#include 
 
struct Key
{
    std::string first;
    std::string second;
};
 
struct KeyHash
{
    std::size_t operator()(const Key& k) const
    {
        return std::hash()(k.first) ^
            (std::hash()(k.second) << 1);
    }
};
 
struct KeyEqual
{
    bool operator()(const Key& lhs, const Key& rhs) const
    {
        return lhs.first == rhs.first && lhs.second == rhs.second;
    }
};
 
struct Foo
{
    Foo(int val_) : val(val_) {}
    int val;
    bool operator==(const Foo &rhs) const { return val == rhs.val; }
};
 
template<> struct std::hash
{
    std::size_t operator()(const Foo &f) const
    {
        return std::hash{}(f.val);
    }
};
 
int main()
{
    // 默认构造函数：空映射
    std::unordered_map m1;
 
    // 列表构造函数
    std::unordered_map m2 =
    {
        {1, "foo"},
        {3, "bar"},
        {2, "baz"}
    };
 
    // 复制构造函数
    std::unordered_map m3 = m2;
 
    // 移动构造函数
    std::unordered_map m4 = std::move(m2);
 
    // 范围构造函数
    std::vector, int>> v = {{0x12, 1}, {0x01,-1}};
    std::unordered_map, double> m5(v.begin(), v.end());
 
    // 带自定义 Key 类型的构造函数的选项 1
    // 定义 KeyHash 与 KeyEqual 结构体并在模板中使用它们
    std::unordered_map m6 =
    {
        {{"John", "Doe"}, "example"},
        {{"Mary", "Sue"}, "another"}
    };
 
    // 带自定义 Key 类型的构造函数的选项 2
    // 为 class/struct 定义 const == 运算符并于 std 命名空间特化 std::hash 结构体
    std::unordered_map m7 =
    {
        {Foo(1), "One"}, {2, "Two"}, {3, "Three"}
    };
 
    // 选项 3：用 lambda
    // 注意必须将初始桶数传递给构造函数
    struct Goo { int val; };
    auto hash = [](const Goo &g){ return std::hash{}(g.val); };
    auto comp = [](const Goo &l, const Goo &r){ return l.val == r.val; };
    std::unordered_map m8(10, hash, comp);
}

3.2 自定义KEY

在上面示例中已经有演示， 这里强调一下。

• 自定义的KEY 要满足二个条件:

a. 提供 对应的Hash函数

b. 提供 对应的 KeyEqual函数 或 重载operator==

注: 支持lambda

#include 
#include 

class Key {
    std::string val;
public:
    Key(const char* str) : val(str) {}
    operator const char* () const {
        return val.c_str();
    }
    bool Equal(const Key& other) const {
        return val == other.val;
    }
    std::size_t Calc() const {
        std::size_t t = 0;
        for (auto& i : val) {
            t += i;
        }
        return t;
    }
};

//提供Key的特化std::hash
template<> struct std::hash {
    std::size_t operator()(const Key& f) const
    {
        return std::hash{}((const char*)f);
    }
};

//提供Key的特化 std::equal_to
template<> struct std::equal_to {
    bool operator()(const Key& k1, const Key& k2) const {
        return k1.Equal(k2);
    }
};

int main() {

    //打印map
    auto show = [](const char* str, auto& m) {
        std::cout << str << " : ";
        //for (const auto& [k, v] : m) {//c++17 结构化绑定
        for (const auto& pair : m) {
            std::cout << "(" << pair.first << " , " << pair.second << ") ";
        }
        std::cout << std::endl;
    };
    
    std::unordered_map m1{
  //std::unordered_map, std::equal_to>
        {Key("one"), 1},
        {Key("two"), 2},
        {Key("three"), 3},
    };
    //调用std::equal_to
    auto x_m1 = m1.find(Key("two"));
    show("Key", m1);


    //提供自定义的hash
    auto key_hash = [](const Key& k) {
        //return std::hash{}((const char*)k);
        return k.Calc();
    };

    std::unordered_map m2({
        {Key("one"), 1},
        {Key("two"), 2},
        {Key("three"), 3},
    }, 2, key_hash);
    auto x_m2 = m2.find(Key("two"));
    show("key_hash", m2);


    //提供自定义的 equal_to
    auto key_equal_to = [](const Key& k1, const Key& k2) {
        return k1.Equal(k2);
    };

    std::unordered_map, decltype(key_equal_to)> 
        m3(10, std::hash(), key_equal_to); 
    m3 = {
        {Key("one"), 1},
        {Key("two"), 2},
        {Key("three"), 3},
    };
    show("key_equal_to", m3);
    

    //自定义的hash 与 equal_to
    std::unordered_map
        m4(10, key_hash, key_equal_to);
    m4 = {
        {Key("one"), 1},
        {Key("two"), 2},
        {Key("three"), 3},
    };
    show("key_hash and key_equal_to", m4);
}

3.3 常规操作

#include 
#include 
#include 

int main() {

    //打印map
    auto show = [](const char* str, auto& m) {
        std::cout << str << " : ";
        //for (const auto& [k, v] : m) {//c++17 结构化绑定
        for (const auto& pair : m) {
            std::cout << "(" << pair.first << " , " << pair.second << ") ";
        }
        std::cout << std::endl;
    };
    
    //buckets 信息
    auto info = [](const char* str, std::unordered_map& m) {
        std::cout << "\n" << str << " : \n";
        std::cout << "size=" << m.size() << "\n";
        std::cout << "buckets=" << m.bucket_count() << "\n";

        //获取容纳元素最多的bucket
        int elem = 0;
        int id = 0;
        for (int i = 0; i < m.bucket_count(); i++) {
            if (m.bucket_size(i) > elem) {
                id = i;
                elem = m.bucket_size(i);
            }
        }
        std::cout << "max_bucket=(" << id << " " << elem << ")"<first << " " << iter->second << ") ";
        }
        std::cout << std::endl;

    };
  
    std::unordered_map m;
    info("初始化", m);

    //插入1000
    m = { {1, .1}, {2,.2}, {3,.3}, {4,.4},{5, .5} };
    m.emplace(6, 0.6);
    m.insert({ 7, .7 });
    m.insert({ { 9, .9 }, {8, .8} });
    m.try_emplace(10, .02);
    m.insert_or_assign(10, .10);
    info("插入10", m);

    std::unordered_map m1{
        {11, .11}, {12,.12}, 
        {13,.13}, {14,.14},{15, .15},
    };
    m.insert(m1.begin(), m1.end());
    m.merge(m1);
    info("插入15", m);

    for (int k = 16; k <= 50000; k++) {

        double v = k;
        for (int t = k; t > 0; t /= 10) {
            v /= 10.0;
        }
        m.emplace(k, v);

        if (k % 5000 == 0) {
            std::string str("插入" + std::to_string(k));
            info(str.c_str(), m);
        }
    }

    //删除
    for (int k = 11; k <= 50000; k++) {
        m.erase(k);
        if (k % 5000 == 0) {
            std::string str("删除" + std::to_string(k));
            info(str.c_str(), m);
        }
    }

    show("删除前", m);
    for (auto iter = m.begin(); iter != m.end(); iter++) {
        if (iter->first == 2) {
            m.erase(iter--);
            continue;
        }
        //....
    }
    show("删除后", m);

    try {
        m.at(1000);
    }
    catch (...) {
        std::cout << "越界了" << std::endl;
    }

    std::cout << (m.end() == m.find(4)) << std::endl;;
    std::cout << m.count(4) << std::endl;
    auto rit = m.equal_range(3);
    std::cout << rit.first->first << " " << rit.first->second << std::endl;
    std::cout << rit.second->first << " " << rit.second->second << std::endl;
}

4. 结论

至此， std::unordered_map的使用上应该没有什么问题了。

大概了解了哈希表、桶的概念。