关联容器

概述

关联容器和序列容器相比，进行索引是通过键值对，而是不是索引数字。

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main()
{
    std::vector<int> a{1, 2, 3};
    cout << a[1] << endl;

    std::map<char, int> m{{'a', 3}, {'b', 4}};
    cout << m['a'] << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

序列容器，数字键是从0开始递增的，对于关联容器，可以使用int或者char或者string等来作为键。

c++键值对的数据类型有8种，大体分成2类：
set / map / multiset / multimap：底层使用红黑树实现

unordered_set / unordered_map / unordered_multiset / unordered_multimap：底层使用hash实现

set

set在数学上讲，是一个集合，上面包含元素.
set的键类型是我们定义的，它的值类型是bool(false or true). 如果这个键在set里，那么就返回true，如果不在，就返回false。

#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;

int main()
{
    std::set<int> s{100, 56, 25, 8};
}

1
2
3
4
5
6
7
8
9
10
11

set里面是无序的。如果两个set元素个数和数值都相同，那么set就是相等的。

int main()
{
    std::set<int> s{100, 56, 25, 8};
    std::set<int> s1{8, 25, 100, 56};
    cout << (s == s1) << endl; // 1
}
1
2
3
4
5
6

从数学上讲，set所有的元素不能重复。

红黑树

左右子树最多相差1层，整体是比较平衡的。给定一个元素，我们就会和树根进行比较，等于直接返回，小于树根左子树查，大于树根右子树去查。因为比较平衡，所以是O(logn)的时间复杂度。

int main()
{
    std::set<int> s{100, 56, 25, 8};
    for (auto ptr = s.begin(); ptr != s.end(); ++ptr)
    {
        cout << *ptr << endl; // 遍历，由小到大，这不是一个巧合，这是因为红黑树的机制，树的中序遍历
    }
}
1
2
3
4
5
6
7
8

std::less，比较2个数，如果前者小于后者，返回true。set插入元素的时候，就是通过less比较数值。
std::greater，与less相反。

int main()
{
    std::set<int, std::greater<int>> s{25, 100, 8, 56}; // 改变了compare方法，从less改成greater
    for (auto ptr = s.begin(); ptr != s.end(); ++ptr)
    {
        cout << *ptr << endl; // 100 56 25 8
    }
}
1
2
3
4
5
6
7
8

当然我们可以自定义一个comparator。



插入元素： insert / emplace / emplace_hint

int main()
{
    std::set<int, std::greater<int>> s{25, 100, 8, 56}; 
    s.insert(111); // s插入111
    s.emplace(222); // 避免了拷贝或者移动
    s.emplace_hint(s.begin(), 333); // 提示系统大约插入到哪里
}
1
2
3
4
5
6
7

删除元素： erase

访问元素： find / contains，因为set是红黑树实现，所以有这两个方法，查找起来比较快，但是vector就没有这个方法。

int main()
{
    std::set<int, std::greater<int>> s{25, 100, 8, 56};
    auto ptr = s.find(100);
    if (ptr != s.end()) // 如果找到了元素
    {
        cout << *ptr << endl;
    }
    else
    {
        //... 没找到就返回 end()
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

contain在c++20引入

修改元素： extract

map

map本质也是基于红黑树实现的，map是一个映射，要有键值对。构建红黑树的时候只考虑key，不考虑value的值。

#include <iostream>
#include <map>
using namespace std;

int main()
{
    std::map<int, bool> m{{3, true}, {4, false}, {1, true}};
    for (auto ptr = m.begin(); ptr != m.end(); ++ptr)
    {
        auto pair = *ptr; // pair的类型是<const int, bool>
        cout << pair.first << ' ' << pair.second << endl;
        /*  1 1
            3 1
            4 0  key按照由小到大顺序 
        */
    }
    // range based for
    for (auto p : m)
    {
        cout << p.first << ' ' << p.second << endl;
    }

    // 基于绑定函数返回值的，这里k v是拷贝的
    for (auto [k, v] : m)
    {
        cout << k << ' ' << v << endl;
    }

    // 基于绑定函数返回值的，这里k v是引用
    for (auto& [k, v] : m)
    {
        cout << k << ' ' << v << endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

在map中，键是需要支持比较大小的，因为要排序红黑树。

#include <iostream>
#include <map>
using namespace std;

int main()
{
    std::map<int, bool> m{{3, true}, {4, false}, {1, true}};
    m.insert(std::pair<int, bool>(5, true));
    m.erase(3);

    for (auto p : m)
    {
        cout << p.first << ' ' << p.second << endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

访问元素： find / contains / [] / at

#include <iostream>
#include <map>
using namespace std;

int main()
{
    std::map<int, bool> m{{3, true}, {4, false}, {1, true}};
    m.insert(std::pair<int, bool>(5, true));
    m.erase(3);

    for (auto p : m)
    {
        cout << p.first << ' ' << p.second << endl;
    }
    
    // find
    auto ptr = m.find(5);
    cout << ptr->first << ' ' << ptr->second << endl;

    // []
    cout << m[5] << endl; // 1

    // []
    cout << m[500] << endl; // 0 500不在，会自动加入key=500，value=0

    // at
    cout << m.at(5) << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

map 迭代器所指向的对象是 std::pair ，其键是 const 类型：
因为我们不希望迭代器去改变key的值，但是可以改变value值。key构造了红黑树的基础，value没事。

[] 操作不能用于常量对象：

multiset / multimap

与 set / map 类似，但允许重复键
本质上也是使用了红黑树，所以也是按照key排序的。

int main()
{
    std::multiset<int> s{1, 3, 1};
    for (auto i : s)
    {
        cout << i << endl; // 1 1 3 允许重复
    }
}
1
2
3
4
5
6
7
8

find 返回首个查找到的元素
返回第一个查找到的元素。
set和map也有count，

#include <iostream>
#include <set>
#include <map>
using namespace std;

int main()
{
    std::multiset<int> s{1, 3, 1};
    auto ptr = s.find(1); // ptr找到第一个1
    ++ptr; // 第二个1
    cout << s.count(1) << endl; // 2 包含1 的个数

    for (auto i : s)
    {
        cout << i << endl; // 1 1 3 允许重复
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

lower_bound / upper_bound / equal_range 返回查找到的区间

#include <iostream>
#include <set>
#include <map>
using namespace std;

int main()
{
    std::multiset<int> s{1, 3, 1};
    auto b = s.lower_bound(1); 
    auto e = s.upper_bound(1);
    for (auto ptr = b; ptr != e; ++ptr)
    {
        cout << *ptr << endl; // 1 1
    }

    auto p = s.equal_range(1);
    for (auto ptr = p.first; ptr != p.second; ++ptr)
    {
        cout << *ptr << endl; // 1 1
    }
    

    auto [b1, e1] = s.equal_range(1);
    for (auto ptr = b1; ptr != e1; ++ptr)
    {
        cout << *ptr << endl; // 1 1
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

unordered_set / unordered_map / unordered_multiset / unordered_multimap

unordered就是没有排序，通过哈希表来查找。哈希的基本要求是输入同样的key，输出同样的整数值。整数值与bucket vector的长度相除取余数，然后会把这个值放在vector顺序中，第余数个的顺序。然后放在bucket list中。哈希表引入一个判等操作，如果查找，相等就是找到了。如果插入，如果不相等，就插入。

int main()
{
    std::unordered_set<int> s{3, 1, 5, 4, 1};
    for (auto p : s)
    {
        cout << p << endl; // 4 5 1 3 顺序是乱的， 1只出现了一次
    }
}
1
2
3
4
5
6
7
8
9

与 set / map 相比查找性能更好：
通常unordered比正常的set或者map，速度要快。正常的set和map底层是红黑树（O(logn)）。但是hash容器更快，先通过hash函数找到bucket list，然后再查找。很多时候，bucket list元素很少，很多时候只有1个。所以hash的复杂度是O(1)。

但插入操作一些情况下会慢：
bucket list的长度不能很长，需要先转换hash值，再进行判等操作。每次插入，有可能涉及到bucket vector的重新分配内存，并且复制，这里涉及到rehash的过程。所以插入操作当hash内存不够时，很慢。

通常来讲，插入情况不多，查找比较多的时候，用unordered的容器。

除 ==，!= 外，不支持容器级的关系运算，但速度较慢 ：

set和map可以字典序比较，因为底层红黑树的key支持compare操作，但是unordered set和unordered map不提供大小比较。只支持判等操作。
在判等时，我们会对bucket list进行重新排列，然后再比较，可以想见，这样的操作比较耗时耗资源。当然这样的排序不是显示的，而是通过std::is_permu的内建算法，判断是否相等的算法。

自定义 hash 与判等函数：

适配器与生成器

类型适配器

basic_string_view

把不同类型统一到相同的类型。

string_view只是原始string的一个视图，只能读取，不能写操作。

string_view通常作为函数的参数，而不是函数的返回值。
string_veiw一般存的就是string开头的结尾的指针。

span （ C++20 ）


span也和string_view差不多，只指向头尾的指针。但是span可以读，也可以写。因为soan返回的是一个reference。

接口适配器

stack / queue / priority_queue


container是底层容器deque。
上面的方法，底层都是deque的方法。对deque的接口进行了封装。替换成了stack的概念。

queue：先进先出

priority_queue

数值适配器

生成器