di-11-zhang-guan-lian-rong-qi

与顺序容器不同的是，关联容器中的元素是按关键字来保存和访问的，而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的，那么典型的就是我们常见的 map 与 set 数据结构

关联容器类型

使用 map

//example1.cpp
#include <iostream>
#include <map>
using namespace std;
int main(int argc, char **argv)
{
    map<string, size_t> m_map;
    m_map["a"] = 4;
    m_map["b"] = 5;
    cout << m_map["a"] << endl; // 4
    cout << m_map["b"] << endl; // 5
    return 0;
}

使用 set

//example2.cpp
map<string, size_t> m_map;
vector<string> vec = {"aaa", "bbb", "ccc", "aaa"};
set<string> m_set;
for (auto &item : vec)
{
    m_set.insert(item);
    cout << item << endl; // aaa bbb ccc aaa
    if (m_map.find(item) != m_map.end())
    {
        m_map[item]++;
    }
    else
    {
        m_map[item] = 1;
    }
}
for (auto &item : m_map)
{
    // aaa 1 bbb 1 ccc 1
     cout << item.first << " " << item.second << endl;
}
//遍历set
for (auto &item : m_set)
{
    cout << item << endl; // aaa bbb ccc
}

定义关联容器

当定义一个 map 时，必须指明关键字类型与值类型，而定义 set 只需指明关键字类型

初始化 map 与 set

//example3.cpp
//空容器
 map<string, size_t> map_1;
//列表初始化
set<string> set_1 = {"aaa", "bbb", "ccc", "aaa", "bbbb"};
// map列表初始化
 map<string, string> map_2 = {
    {"aaa", "vfvdf"},
    {"bbb", "adfdsfs"},
     {"ccc", "vfdvdf"}};

初始化 multimap 与 multiset

multi 的意义就是，map 一个关键词可以存储多个值，set 也可以存储多个相同的值

//example4.cpp
// multiset
vector<string> vec = {"aaa", "aaa", "bbb", "bbb", "ccc"};
multiset<string> m_set(vec.begin(), vec.end());
for (auto &item : m_set)
{
    cout << item << " "; // aaa aaa bbb bbb ccc
}
cout << endl;
cout << m_set.size() << endl; // 5
// multimap
multimap<string, string> m_map = {{"aaa", "ccc"}, {"aaa", "vvv"}};
for (auto &item : m_map)
{
    cout << item.first << " " << item.second << endl;
    // aaa ccc
    // aaa vvv
}

关键字类型要求

对于有序容器，map、multimap、set、multiset，关键字类型要求必须定义元素比较方法，默认情况下，标准库使用关键字类型的<运算符来比较两个关键字
算法允许自定义比较操作，与之类似也可以提供自定义的操作代替关键字上的<运算符

自定义关键字比较函数

//example5.cpp
struct Person
{
    int age;
    string name;
};

//关键字比较函数必须满足上面比较函数的条件
bool comparePerson(const Person &a, const Person &b)
{
    return a.age < b.age && a.name < b.name;
}

int main(int argc, char **argv)
{
    // decltype(comparePerson) * 为函数指针
    map<Person, int, bool (*)(const Person &a, const Person &b)> m_map(comparePerson);
    // 或者使用decltype
    // map<Person, int, decltype(comparePerson) *> m_map(comparePerson);
    Person person1;
    person1.age = 19;
    person1.name = "gaowanlu";
    m_map[person1] = 99999;
    auto val = m_map[person1];
    cout << val << endl; // 99999
    return 0;
}

pair 类型

pair 的标准库类型，定义在 utility 头文件中
一个 piar 保存两个数据成员，类似容器 piar 是一个用来生成特定类型的模板，大致可以认为是一个键值对

//example6.cpp
//空初始化
pair<string, int> m_pair1;

//列表初始化
pair<int, string> m_pair2{999, "gaowanlu"};
cout << m_pair2.first << " " << m_pair2.second << endl; // 999 gaowanlu

pair<int, string> m_pair4 = {999, "gaowanlu"};
cout << m_pair4.first << " " << m_pair4.second << endl; // 999 gaowanlu

//构造函数初始化
pair<string, int> m_pair3("gaowanlu", 888);
cout << m_pair3.first << " " << m_pair3.second << endl; // gaowanlu 888

//使用make_piar
m_pair4 = make_pair(888, "hello");

//赋值
m_pair4.first = 666;
m_pair4.second = "gaowanlu";
cout << m_pair4.first << " " << m_pair4.second << endl; // 666 gaowanlu

// <、>、<=、>=比较pair
pair<int, int> m_pair5(2, 3);
pair<int, int> m_pair6(4, 3);
//当first与second同时满足才返回true
cout << (m_pair5 < m_pair6) << endl;  // 1
cout << (m_pair5 <= m_pair6) << endl; // 1
cout << (m_pair5 > m_pair6) << endl;  // 0
cout << (m_pair5 >= m_pair6) << endl; // 0

// ==比较pair
m_pair5 = make_pair(4, 3);
cout << (m_pair5 == m_pair6) << endl; // 1

// !=比较piar
cout << (m_pair5 != m_pair6) << endl; // 0

key_type、mapped_type、value_type 操作

只有 map 类型(unordered_map、unordered_multimap、multimap 和 map)才定义了 mapped_type

//example7.cpp
#include <iostream>
#include <utility>
#include <set>
#include <map>
using namespace std;
int main(int argc, char **argv)
{
    // set value_type与key_type
    set<string>::value_type v1; // td::string
    set<string>::key_type v2;   // std::string
    // map key_type value_type mapped_type
    map<string, int>::value_type v3;  // std::pair<const std::string, int>
    map<string, int>::key_type v4;    // std::string
    map<string, int>::mapped_type v5; // int
    return 0;
}

关联容器迭代器

重点：set 迭代器解引用返回 const 引用，map 迭代器解引用返回 pair 的引用，但 pair 的 first 类型是 const 的，也就是我们只能用迭代器修改 second 不能修改 first

//example8.cpp
set<string> m_set = {"aaa", "bbb", "ccc"};
map<string, int> m_map = {{"aaa", 111}, {"bbb", 222}, {"ccc", 333}};
auto set_iter = m_set.begin(); // std::set<std::string>::iterator
while (set_iter != m_set.end())
{
    cout << *set_iter++ << endl; // aaa bbb ccc
    // set的迭代器是const的
    //*set_iter = "dscs";//*set_iter返回的是 const string&
}
auto map_iter = m_map.begin(); // std::map<std::string, int>::iterator
while (map_iter != m_map.end())
{
    // map_iter->first = "dscs"; //因为解引用返回的是 std::pair<const std::string, int> &
    map_iter->second++;
    cout << map_iter->first << " " << map_iter->second << endl;
    // aaa 112
    // bbb 223
    // ccc 334
    map_iter++;
}

关联容器和泛型算法

一般不对关联容器使用泛型算法，关键字是 const 着意味着不能使用修改或重排容器元素的算法，因为这类算法要向元素写入值，而 set 的元素是 const 的，map 中元素是 pair 但 first 是 const 的

关联容器只用于只读元素的算法，例如泛型算法 find 查找为顺序查找，而关联容器的特定的 find 则是进行 hash 查找，会比泛型算法的 find 快很多，还可以利用泛型 copy 算法将元素拷贝

//example9.cpp
map<string, int> m_map = {{"aaa", 111}, {"bbb", 222}, {"ccc", 333}};
// copy到vector
vector<pair<string, int>> vec;
copy(m_map.begin(), m_map.end(), back_inserter(vec));
cout << vec.size() << endl; // 3
// copy到新的map
map<string, int> m_map_copy;
copy(m_map.begin(), m_map.end(), inserter(m_map_copy, m_map_copy.end()));
for (auto &item : m_map_copy)
{
    cout << item.first << " " << item.second << endl;
    // aaa 111
    // bbb 222
    // ccc 333
}

添加元素

//example10.cpp
map<string, int> m_map;
m_map.insert({"hello", 3});
m_map.insert(make_pair("aaa", 6));
m_map.insert(pair<string, int>("bbb", 2));
auto res = m_map.insert(map<string, int>::value_type("ccc", 3));
if (res.second) //插入成功
{
    map<string, int>::iterator iter = res.first;
    cout << iter->first << " " << iter->second << endl; // ccc 3
}
m_map.emplace("ddd", 4);                   //背后使用构造函数int(4)
cout << m_map.find("ddd")->second << endl; // 4

set<string> m_set;
m_set.insert("aaa");
m_set.insert({"aaa", "bbb", "ccc"});
m_set.insert(string("ddd"));
m_set.emplace("hello");       //背后调用构造函数string("hello")
cout << m_set.size() << endl; // 4

向 multiset 或 multimap 添加元素

知道二者可以存储多个相同的关键字,insert 返回 void 不像 map 或者 set 一样返回一个 pair

//example11.cpp
multimap<string, int> m_map;
multiset<string> m_set;
m_map.insert({{"aaa", 111}, {"aaa", 222}});
m_set.insert({"aaa", "ccc", "ccc"});
cout << m_map.size() << endl; // 2
cout << m_set.size() << endl; // 3

删除元素

//example12.cpp
//使用关键字
map<string, int> m_map = {{"aaa", 111}, {"bbb", 222}, {"ccc", 333}};
set<string> m_set = {"aaa", "bbb", "ccc", "ddd"};
printMap(m_map); //<aaa,111>  <bbb,222>  <ccc,333>
printSet(m_set); // aaa bbb ccc ddd
size_t count = m_map.erase("aaa");
cout << count << endl; // 1 被删除1个
printMap(m_map);
count = m_set.erase("ccc");
cout << count << endl; // 1
printSet(m_set);

//使用迭代器指定删除的元素位置
m_set.erase(m_set.cbegin());
printSet(m_set); // bbb ddd

//使用迭代器范围
m_set.erase(m_set.cbegin(), m_set.end());
printSet(m_set); //

map 的下标操作

map、uordered_map 有下标操作，而 multimap 与 unordered_multimap 没有下标操作，因为一个关键词可对应多个值

//example13.cpp
map<string, int> m_map = {{"aaa", 111}, {"bbb", 222}, {"ccc", 333}};
printMap(m_map); // <aaa,111>  <bbb,222>  <ccc,333>
m_map["aaa"] = 4;
printMap(m_map); // <aaa,4>  <bbb,222>  <ccc,333>

//下标赋值没有的关键字则创建新的元素
m_map["ddd"] = 444;
printMap(m_map); // <aaa,4>  <bbb,222>  <ccc,333>  <ddd,444>

//如果k不再c内，添加一个关键字为k的元素并对值初始化
cout << m_map["eee"] << endl; // 0
printMap(m_map);
// <aaa,4>  <bbb,222>  <ccc,333>  <ddd,444>  <eee,0>

// at方法有检查机制，如果k不在c内则抛出out_of_range异常
int &val = m_map.at("bbb");
cout << val << endl; // 222
try
{
    m_map.at("fff");
}
catch (std::out_of_range e)
{
    // RUNTIME ERROR:: map::at
    cout << "RUNTIME ERROR:: " << e.what() << endl;
}

find、count、lower_bound、upper_bound、equal_range 访问元素

主要为根据关键字查找元素的操作，在 multimap 与 multiset 中相同关键字的元素总是相邻存放

//example14.cpp
multimap<int, string> m_map{{111, "aaa"}, {222, "bbb"}, {444, "ddd"}, {222, "ccc"}};
printMap(m_map); // <111,aaa>  <222,bbb>  <222,ccc>  <444,ddd>

// count方法
cout << m_map.count(222) << endl; // 2

// find方法
auto res = m_map.find(222);
int size = 0, count = m_map.count(222);
while (size < count && res != m_map.cend())
{
    //<222,bbb> <222,ccc>
    cout << "<" << res->first << "," << res->second << ">" << endl;
    res++;
    size++;
}
// lower_bound方法
//返回第一个关键字不小于333的迭代器
res = m_map.lower_bound(333);
cout << "<" << res->first << "," << res->second << ">" << endl; //<444,ddd>

// upper_bound方法
//返回第一个关键字大于100的迭代器
res = m_map.upper_bound(100);
cout << "<" << res->first << "," << res->second << ">" << endl; //<111,aaa>

// equal_range方法
auto range = m_map.equal_range(222); //返回区间[bengin,end)
res = range.first;
while (res != range.second)
{
    cout << "<" << res->first << "," << res->second << ">" << endl;
    //<222,bbb> <222,ccc>
    res++;
}

无序容器

无序是 C++11 的新标准，新标准定义了 4 个无序关联容器，这些容器不是使用比较运算符来组织元素，而是使用哈希函数和关键字类型的==运算符
无序容器在关键字杂乱无章的情况下效率更高

使用无序容器

//example15.cpp
unordered_map<string, int> m_map = {{"aaa", 111}, {"bbb", 222}, {"ccc", 333}};
for (auto &item : m_map)
{
    //<ccc,333> <bbb,222> <aaa,111>
    cout << "<" << item.first << "," << item.second << "> ";
}
cout << endl;
//可见存放顺序不是有序的

管理无序容器

无序容器的存放原理为，无序容器有多个桶，每个桶存放 0 个或多个元素，先对关键字进行 hash 然后找到对应的桶，在桶内存放要存放的元素，在访问元素时也是同样的原理

桶接口

//example16.cpp
unordered_map<string, int> m_map = {{"aaa", 111}, {"bbb", 222}, {"ccc", 333}};
// bucket_count 正在使用的桶的数目
cout << m_map.bucket_count() << endl; // 3
// max_bucket_count 容器能容纳的最多的桶的数量
cout << m_map.max_bucket_count() << endl; // 59652323
// bucket_size(n) 第n个桶中有多少个元素
for (size_t i = 0; i < m_map.bucket_count(); i++)
{
    cout << m_map.bucket_size(i) << " "; // 0 2 1
}
cout << endl;

桶迭代

//example17.cpp
unordered_map<string, int> m_map = {{"aaa", 111}, {"bbb", 222}, {"ccc", 333}};
cout << m_map.bucket_size(1) << endl; // 2
unordered_map<string, int>::local_iterator iter = m_map.begin(1);
while (iter != m_map.cend(1))
{
    // bbb 222 aaa 111
    cout << iter->first << " " << iter->second << endl;
    // begin返回的为local_iterator即可以利用迭代器修改pair的value
    iter++;
}
// cbegin返回的为const_local_iterator不可以利用迭代器修改pair的value

哈希策略

//example18.cpp
unordered_map<string, int> m_map = {{"aaa", 111}, {"bbb", 222}, {"ccc", 333}};

// load_factor 每个桶的平均元素数量
cout << m_map.load_factor() << endl;                        // 1
cout << (float)m_map.size() / m_map.bucket_count() << endl; // 3

// max_load_factor 即 load_factor的阈值,load_factor<=max_load_factor总成立
cout << m_map.max_load_factor() << endl; // 1

// rehash(n) 重组存储 使得bucket_count>=n 且 bucket_count>size/max_load_factor
m_map.rehash(4);
cout << m_map.bucket_count() << endl; // 5

// reserve(n) 重组元素，使得容器可保存n个元素，且不rehash也就是不改变hash函数
m_map.reserve(100);
cout << m_map.bucket_count() << endl; // 103

自定义 hash 函数与相等比较函数

当关键字类型为自定义符合类型时，需要定义相关的 hash 函数与等于判断函数

//example19.cpp
class Person
{
public:
    int age;
    bool operator==(const Person &b) const
    {
        if (this->age == b.age)
        {
            return true;
        }
        return false;
    }
};

// hash函数
size_t hasher(const Person &person)
{
    return hash<int>()(person.age);
}

//==比较函数
bool equalPerson(const Person &a, const Person &b)
{
    return a.age == b.age;
}

int main(int argc, char **argv)
{
    using namespace std;
    using Person_map = unordered_map<Person, string, decltype(hasher) *, decltype(equalPerson) *>;
    //使用Person_multimap 42:桶大小 hasher：哈希函数 equalPerson: 相等性判断函数
    Person_map persons(42, hasher, equalPerson);
    Person person;
    person.age = 19;
    persons.insert({person, "gaowanlu"});
    cout << persons[person] << endl; // gaowanlu

    //如果类内定义了==运算符，则可以只重载哈希函数
    // unordered_map<Person, string, decltype(hasher) *>;
    unordered_map<Person, string, decltype(hasher) *> persons_overide(42, hasher);
    persons_overide.insert(make_pair(person, "gaowanlu"));
    cout << persons[person] << endl;
    return 0;
}

😉 第 11 章关联容器

第 11 章关联容器

关联容器类型

使用 map

使用 set

定义关联容器

初始化 map 与 set

初始化 multimap 与 multiset

关键字类型要求

自定义关键字比较函数

pair 类型

key_type、mapped_type、value_type 操作

关联容器迭代器

关联容器和泛型算法

添加元素

向 multiset 或 multimap 添加元素

删除元素

map 的下标操作

find、count、lower_bound、upper_bound、equal_range 访问元素

无序容器

使用无序容器

管理无序容器

桶接口

桶迭代

哈希策略

自定义 hash 函数与相等比较函数

😉 第 11 章 关联容器

第 11 章 关联容器

关联容器类型

使用 map

使用 set

定义关联容器

初始化 map 与 set

初始化 multimap 与 multiset

关键字类型要求

自定义关键字比较函数

pair 类型

key_type、mapped_type、value_type 操作

关联容器迭代器

关联容器和泛型算法

添加元素

向 multiset 或 multimap 添加元素

删除元素

map 的下标操作

find、count、lower_bound、upper_bound、equal_range 访问元素

无序容器

使用无序容器

管理无序容器

桶接口

桶迭代

哈希策略

自定义 hash 函数与相等比较函数

😉 第 11 章关联容器

第 11 章关联容器