11. 关联容器

1. 有序关联容器

1.1 定义关联容器

有序关联容器的关键字有序，默认升序，如 string 类型的关键字默认按照字母顺序升序排列。有序关联容器包含：map、set、multimap 和 multiset，其中 map 和 set 的关键字不能重复，multi 前缀的关键字可以重复，代表一对多的映射关系。

有序容器的底层采用红黑树实现，与 vector 等容器不同之处在于，关联容器的元素是根据关键字进行存储的，不支持 push_back 等与位置相关的操作。

例如，如下操作，存在错误：

// v是vector， m是set
copy(v.begin(), v.end(), back_insert(set); // 错误，set没有push_back操作
copy(v.begin(), v.end(), insert(set)); // 正确，set可以使用insert操作

map 的定义与赋值，实现了 key 和 value 的一对一映射关系。

#include <map>

map<string, int> words_count; // 定义了一个map类型，其关键字是string类型，值是int类型
words_count = {{"Hello", 1}, {"World", 2}}; // 赋值

// 非默认排序，指定排序规则：
// 自定义比较函数
bool compare(const int& lhs, const int& rhs){
    return lhs > rhs; // 降序排序
}
std::map<int, std::string, decltype(&compare)> descendingMap(compare);

关于第三个参数，自定义比较函数，其写法还有以下方式：

#include <iostream>
#include <map>
#include <string>

// 1. 使用 decltype 和 lambda 对象
auto compareLambda = [](const int& lhs, const int& rhs) -> bool {
    return lhs > rhs;
};
std::map<int, std::string, decltype(compareLambda)> descendingMap1(compareLambda);

// 2. 使用 decltype 和函数指针（无捕获 lambda）
decltype(&compareLambda) compareFuncPtr = &compareLambda;
std::map<int, std::string, decltype(compareFuncPtr)> descendingMap2(compareFuncPtr);

// 3. 使用 std::function
#include <functional>
std::function<bool(const int&, const int&)> compareFunc = [](const int& lhs, const int& rhs) -> bool {
    return lhs > rhs;
};
std::map<int, std::string, std::function<bool(const int&, const int&)>> descendingMap3(compareFunc);

// 4. 使用 typedef 定义函数指针
typedef bool (*CompareFunc)(const int&, const int&);
CompareFunc comparePtr = [](const int& lhs, const int& rhs) -> bool {
    return lhs > rhs;
};
std::map<int, std::string, CompareFunc> descendingMap4(comparePtr);

// 5. 使用 using 定义函数指针（C++11 引入）
using CompareFuncUsing = bool (*)(const int&, const int&);
CompareFuncUsing comparePtrUsing = [](const int& lhs, const int& rhs) -> bool {
    return lhs > rhs;
};
std::map<int, std::string, CompareFuncUsing> descendingMap5(comparePtrUsing);

// 6. 使用仿函数 (Functor)
struct CompareFunctor {
    bool operator()(const int& lhs, const int& rhs) const {
        return lhs > rhs;
    }
};
std::map<int, std::string, CompareFunctor> descendingMap6;

set 的定义与赋值，set 只有关键字，没有值，其作用主要用来检测元素是否位于容器。set容器也可以指定第二个参数用于自定义排序规则。

#include <set>
set<string> words;
set = {"Hello", "World"};

std::set<int, decltype(compare)> mySet(compare); //自定义比较函数

multimap 与 multiset 定义与赋值方式同上。

有序关联容器对关键字类型要求：支持比较操作，默认情况下使用 < 符号。 当使用关联容器存储自定义的类型，需要指定 “比较操作”，比较操作是一种函数指针。

如下代码所示，我们使用了自定义类型定义了 myMap，使用下标的方式进行赋值。可以注意到，MyValue 类包含了一个默认构造器，原因在于 map 类型的关联容器使用数组下标时，会首先调用值的默认构造器 MyValue("")，生成一个默认对象，然后再使用 MyValue("value1") 进行赋值，所以自定义对象作为 map 的值时，必须包含默认构造器。

class MyKey {
public:
    int id;
    std::string name;

    MyKey(int id, const std::string &name) : id(id), name(name) {}
};

class MyValue {
public:
    std::string description;

    MyValue(const std::string &description) : description(description) {};
    MyValue() = default; // 默认构造器
};

bool compareMyKey(const MyKey &a, const MyKey &b) {
    if (a.id != b.id) {
        return a.id < b.id;
    } else {
        return a.name < b.name;
    }
}

multimap<mykey, int, decltype(compareMyKey)*> myMap(compareMyKey); // 定义自定义比较

myMap[MyKey(1, "key1")] = MyValue("value1");
myMap[MyKey(2, "key2")] = MyValue("value2");

1.2 pair

map 类的关联容器的每一个元素都是由 pair 类型组成，pair 类型的定义如下：

pair<string, int> my_pair("Hello", 1);
pair<string, int> my_pair;
pair<string, int> my_pair = {"hello", 1}; // 旧版本的构造器也许不支持列表初始化，会检测类型是否匹配，禁止缩窄转换

其支持以下操作：

make_pair(arg1, arg2); // 返回一个使用arg1和arg2初始化的pair，其类型与参数类型有关
p.first; // 访问关键字
p.second; // 访问值
p1 relop p2; // p1和p2支持的关系运算符：(<, >, ==, >=, <=, !=)，当p1.first<p2.first则p1 < p2，或者(p1.first >= p2.first && p1.second < p2.second)，则p1 < p2

1.3 关联容器的类型

key_type // 关联容器的关键字类型
mapped_type // 关联容器的值类型，只适用于map
value_type // 关联容器的元素类型，对于set，与key_type相同；对于map，为pair<const key_type, mapped_type>

由于set只有关键字，所以其key_type与value_type是相同的。map拥有关键字到值的映射，value_type为pair<const key_type, mapped_type>。set的关键字是readonly，而map的关键字是const类型，所以我们无法修改关键字，只能读取、删除。

2. 无序关联容器

C++ 11 定义了4个无序关联容器，使用哈希表作为底层数据结构。红黑树结构的关联容器，其访问、插入、删除的时间复杂度是o(log n)，而哈希表结构的无序容器，其时间复杂度从o(1)-o(n)变化，当一直发生hash碰撞，则其从哈希表退化为链表。

无序关联容器的关键字需满足：支持==操作符，

unordered_map;
unordered_multimap;
unordered_set;
unordered_multiset;

无序关联容器在存储自定义对象时，需要指定hash模版和比较函数。

std::size_t my_hash(const MyObject& obj){
    return std::hash<int>()(obj.id); // 仅使用 id 进行哈希
}

bool my_equal(const MyObject& lhs, const MyObject& rhs) const {
    return lhs.id == rhs.id; // 比较 id 是否相等
}
std::unordered_map<MyObject, std::string, decltype(&my_hash), decltype(&my_equal)> unorderedMap(10, my_hash, my_equal); // 10代表桶的数量

3. 关联容器的操作

3.1 遍历关联容器

与其他容器采用迭代器遍历容器一样，关联容器也是通过迭代器进行遍历。关联容器包括4个迭代器，是否是const类型，则需要关注容器被定义时，是否是const。

const::iterator;
iterator;
reverse_iterator;
const_reverse_iterator;

非const的map容器，通过：begin()和end()返回首元素迭代器和尾后迭代器。

auto it = my_map.begin();
while(it != my_map.end())
{
    cout << "first is: " << it->first << " second is: " << it->second;
}

//c++ 11 基于range-based的方式遍历，&代表不拷贝
for (const auto &pair : word_count) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}

set容器：

auto it = my_map.begin();
while(it != my_map.end())
{
    cout << "item is: " << *it;
}

3.2 添加元素

// v是value_type类型的对象，args用于构造一个元素，只有当元素不在时，才会插入成功。返回pair<iterator,bool>，iterator指向关键字所在的元素，bool表示是否插入成功。
insert(v);
emplace(args); 

//b和e是迭代器，表示c::value_type类型的一个范围内的元素，而il包含了一系列可以使用默认构造器的对象。返回void。
insert(b, e);
emplace(il);

//指出从位置p开始搜索插入的位置，如果元素已经存在，则会覆盖，返回插入元素的迭代器。
insert(p, t);
emplace(p, args);

3.3 删除元素

c.erase(k); // 删除关键字为k的元素，返回删除的数量，类型为size_type
c.erase(b, e); // 删除迭代器范围内的元素，返回e
c.erase(p); // 删除迭代器位置的元素，如果p是c.end()，则会报错。返回p之后的一个元素的迭代器。

对于非multi类型的容器来说，c.erase(k)，永远返回0或者1。

3.4 访问元素

3.4.1 下标方式

map类型的容器支持下标访问操作，而set类型的容器不支持，原因在于set没有关键字对应的值。下标访问可以使用两种方式：

c[k]; // 数组下标的方式，会默认先使用mapped_type的构造函数，生成一个默认的value，其返回的是一个左值对象。
c.at(k); // 如果k不在c中，则会返回out_of_range

3.4.2 查找方式

c.find(k); //返回指向k元素的迭代器，如果k不在c中，则返回c.end()。

由于find函数会返回迭代器，所以也可以使用find访问c的元素。如果只是统计c中有多少个k，或者判断k是否在c中，还可以使用：

c.count(k); // 对于非multi类型容器，返回0或者1。对于multi类型容器则返回元素的数量。

由于有序关联容器默认升序，还可以使用bound后缀的函数进行查找元素：

c.lower_bound(k); //返回迭代器，指向第一个大于等于k的元素
c.upper_bound(k); // 返回迭代器，指向第一个大于k的元素
c.equal_bound(k); // 返回一个pair，first是lower_bound，second是upper_bound，如果k不存在，则返回c.end();

比如在multi类型中的元素寻找关键字等于k的元素：

auto range = my_map.equal_range(k);

// 使用 for 循环访问键 k 的元素
for (auto it = range.first; it != range.second; ++it) {
    std::cout << "Key " << k << " has value: " << it->second << "\n";
}

auto it_low = mmap.lower_bound(k);
auto it_up = mmap.upper_bound(k);

// 使用 for 循环访问键 k 的所有元素
for (auto it = it_low; it != it_up; ++it) {
    std::cout << "Key " << k << " has value: " << it->second << "\n";
}

4. 无序关联容器的特定操作

特定操作是关于桶的操作：

桶相关的函数

• bucket_count(): 返回当前桶的数量。
• max_bucket_count(): 返回容器能容纳的最多的桶的数量。
• bucket_size(n): 返回第 n 个桶中的元素数量。
• bucket(k): 返回关键字为 k 的元素所在的桶。

桶迭代器

• local_iterator: 用来访问桶中元素的迭代器类型。
• const_local_iterator: 桶迭代器的 const 版本。
• begin(n): 返回桶 n 的首元素迭代器。
• end(n): 返回桶 n 的尾后迭代器。
• cbegin(n): 返回桶 n 的 const 首元素迭代器。
• cend(n): 返回桶 n 的 const 尾后迭代器。

哈希策略

• load_factor(): 返回每个桶的平均元素数量，返回 float 值。
• max_load_factor(): 返回容器试图维护的平均桶大小，返回 float 值。容器会在需要时添加新的桶，以使得 load_factor <= max_load_factor。
• rehash(n): 重新分配存储，使得 bucket_count >= n 且 bucket_count > size / max_load_factor。
• reserve(n): 重新分配存储，使得容器可以保存 n 个元素且不必 rehash。