关于c++:C容器unorderedmap

#include <unordered_map>

template <
    class Key,                                              // unordered_map::key_type
    class T,                                                // unordered_map::mapped_type
    class Hash = std::hash<Key>,                            // unordered_map::hasher
    class Pred = std::equal_to<Key>,                        // unordered_map::key_equal
    class Alloc = std::allocator<std::pair<const Key, T>>   // unordered_map::allocator_type
> class unordered_map;

unordered_map 具备如下性质：

唯一性：键是惟一的；
无序性：键值对是无序存储的，元素被存储在桶中，如果两个元素领有雷同哈希值的键，则它们会被存储于同一桶中；
具备常数工夫复杂度（均匀来说）的搜寻、插入、删除操作。

如果键是自定义类型，则须要提供相应的哈希函数，来计算键的哈希值。

办法 1：显式提供相应的模板参数

#include <iostream>
#include <unordered_map>
#include <string>

struct Key
{
    std::string first;
    std::string second;
};

struct KeyHash
{std::size_t operator()(const Key& k) const
    {return std::hash<std::string>()(k.first) ^
               (std::hash<std::string>()(k.second) << 1);
    }
};

struct KeyEqual
{bool operator()(const Key& lhs, const Key& rhs) const
    {return lhs.first == rhs.first && lhs.second == rhs.second;}
};

int main()
{Key k1{ "John", "Doe"}, k2{"Mary", "Sue"};

    std::unordered_map<Key, std::string, KeyHash, KeyEqual> m =
    {{ k1, "example"},
        {k2, "another"}
    };

    std::cout << m[k1] << '\n';        // example
}

办法 2：显式特化 std::hash<> 模板

template<class Key>
struct hash;

#include <iostream>
#include <unordered_map>
#include <string>

struct Foo
{Foo(int val_) : val(val_) {}
    int val;

    // unordered_map::key_equal
    bool operator==(const Foo& rhs) const
    {return val == rhs.val;}
};

namespace std
{
    template<>
    struct hash<Foo>
    {std::size_t operator()(const Foo& f) const
        {return std::hash<int>{}(f.val);
        }
    };
}

int main()
{
    std::unordered_map<Foo, std::string> m =
    {{ Foo(1), "One"}, {2, "Two"}, {3, "Three"}
    };

    std::cout << m[Foo(1)] << '\n';            // One
}

std::unordered_map<int, char> m;

bool isEmpty = m.empty();    // Test whether container is empty
size_t n = m.size();         // Return container size
size_t limit = m.max_size(); // Return maximum size

/*
Sets the number of buckets in the container (bucket_count) 
to the most appropriate to contain at least 30 elements.
*/
m.reserve(30);

std::unordered_map<std::string, std::string> m;

m["Bakery"] = "Barbara";        // 存在时更新值；不存在时插入键值对
std::string v = m["Bakery"];    // 存在时返回对应的值；不存在时插入键值对（应用值类型的默认构造函数来创立值）m.at("Hello") = "World";        // 存在时更新值；不存在时抛出 out_of_range 异样
std::string v = m.at("Hello");  // 存在时返回对应的值；不存在时抛出 out_of_range 异样

std::unordered_map<std::string, double> m = 
{{"mom", 5.4},
    {"dad", 6.1},
    {"bro", 5.9}
};

auto it = m.find("mom");
if (it == m.end())
{std::cout << "not found";}
else
{std::cout << "key=" << it->first << ", value=" << it->second;}

bool exists = m.contains("mom");        // 是否存在（C++20）

emplace：应用给定的实参原地结构元素，能够防止不必要的拷贝。只有不存在相应的键才会插入。

struct Person
{
    std::string m_name;
    double m_salary;

    Person() = default;
    Person(const std::string& name, double salary)
        : m_name(name), m_salary(salary)
    {}};

int main()
{
    std::unordered_map<int, Person> m;

    /*
    返回值类型为 pair<iterator, bool>
    其中，迭代器执行新插入的元素，或已存在的元素
    bool 示意是否插入胜利
    */
    auto p = m.emplace(1, Person(std::string("Mike"), 12345.6));
    if (p.second)
    {std::cout << "插入胜利 \n";}
    else
    {std::cout << "已存在，原值为：" << p.first->second.m_salary;}
}

insert：只有不存在相应的键才会插入。

std::unordered_map<std::string, double> m;

/*
返回值类型为 pair<iterator, bool>
其中，迭代器执行新插入的元素，或已存在的元素
bool 示意是否插入胜利
*/
auto p = m.insert({"sugar", 0.8});
if (p.second)
{std::cout << "插入胜利 \n";}
else
{std::cout << "已存在，原值为：" << p.first->second;}

std::unordered_map<std::string, std::string> m;

m.erase("France");        // 删除指定键的元素，不存在时也没事

auto it = m.find("France");
if (it != m.end())
{m.erase(it);         // 删除指定地位的元素
}

m.clear();               // 清空容器

遍历元素

std::unordered_map<std::string, std::string> m
{{ "Australia", "Canberra"},
    {"U.S.", "Washington"},
    {"France", "Paris"} 
};

for (auto it = m.begin(); it != m.end(); it++)
{if (it->first[0] == 'U')
    {std::cout << it->first << "->" << it->second << '\n';}
}

遍历桶

std::unordered_map<std::string, std::string> m
{{"house","maison"},
    {"apple","pomme"},
    {"tree","arbre"},
    {"book","livre"},
    {"door","porte"},
    {"grapefruit","pamplemousse"}
};

size_t bucketCount = m.bucket_count();
std::cout << "bucket count:" << bucketCount << '\n';

for (size_t i = 0; i < bucketCount; i++)
{std::cout << "bucket #" << i << "has" << m.bucket_size(i) << "elements.\n";
}
std::cout << '\n';

for (size_t i = 0; i < bucketCount; i++)
{
    std::cout << "bucket #" << i << "contains:";

    for (auto it = m.begin(i); it != m.end(i); it++)
    {std::cout << "[" << it->first << ":" << it->second << "]";
    }
    std::cout << '\n';
}

bucket count: 8
bucket #0 has 1 elements.
bucket #1 has 1 elements.
bucket #2 has 1 elements.
bucket #3 has 1 elements.
bucket #4 has 0 elements.
bucket #5 has 1 elements.
bucket #6 has 0 elements.
bucket #7 has 1 elements.

bucket #0 contains: [book:livre]
bucket #1 contains: [door:porte]
bucket #2 contains: [grapefruit:pamplemousse]
bucket #3 contains: [house:maison]
bucket #4 contains:
bucket #5 contains: [tree:arbre]
bucket #6 contains:
bucket #7 contains: [apple:pomme]

关于c++:C容器unorderedmap

1. 简介

2. 自定义键类型

3. 容器大小

4. 拜访元素

5. 查找元素

6. 插入元素

7. 删除元素

8. 遍历容器