C++ STL 有序关联容器 set、multiset、map、multimap 使用指南

1.2、迭代器——iterator

begin() 和 end() 最常用，都是结合在一些其他场景使用，比如，遍历 set 对象，或者用于迭代器区间构造等场景。由于 set 底层特殊的数据结构，begin 返回的迭代器指向最小的元素。

void test02() {
    set<int> st({ 4,5,2,9,6,8,3,1,7,7,7,7 }); // 初始化列表构造
    auto begin = st.begin(); // 返回第一个节点的迭代器
    auto end = st.end(); // 返回最后一个节点后一个位置的迭代器
    cout << *begin << endl;
    cout << *(--end) << endl; // --end 找到最后一个有效节点
}

我们可以用迭代器实现一个打印函数，方便我们后面观察。

1.3、插入——insert

set 底层的数据结构就是平衡二叉搜索树（红黑树），所以插入数据满足二叉搜索树的规则，但是，set 不允许插入相同的值。插入数据的形式也比较多，最常用的就是上面的第一种。我们看到，对于第一种插入数据的接口，最特别的就是它的返回值，这和我们以前见到的都不一样。其实它的返回值 pair 类类型的对象。其中 pair 对象的第一个值为迭代器，如果要插入的值原来不存在，则返回新插入节点的迭代器，如果原来存在，则返回值与 val 相等的那个节点；第二个值为 bool 类型的变量。下面就是 pair 类：

然后我们插入数据来观察一下：

void test03() {
    set<int> st;
    pair<set<int>::iterator, bool> p1,p2; // 创建 pair 对象，记下插入数据后的返回值
    // 插入数据
    p1 = st.insert(5);
    st.insert(3);
    p2 = st.insert(5); // 插入原来已经存在的值
    cout << *(p1.first) << endl; // 检查 pair 对象的第一个值是否为插入节点的迭代器
    if (p2.second) cout << "原来不存在" << endl;
    else cout << "原来存在" << endl;
}

通过打印结果，pair 对象 p1 的 first 指向插入节点的迭代器；当插入值相等的节点时，pair 对象的 second 的值为 false，则打印出原来存在。

1.4、删除——erase

void test04() {
    set<int> st({ 4,5,2,9,6,8,3,1,7,7,7,7 }); // 初始化列表构造
    Print_container(st);
    set<int>::iterator it = st.erase(st.begin()); // 删除第一个节点
    cout << *it << endl;
}

当删除第一个节点之后，erase 函数返回该节点后一个节点的迭代器，要删除节点的迭代器失效。

1.5、查找——find

找到就返回节点的迭代器，没找到就返回 set::end()。

void test05() {
    set<int> st({ 4,5,2,9,6,8,3,1,7,7,7,7 }); // 初始化列表构造
    auto it = st.find(5);
    if(it!=st.end()) {
        cout << *it << endl;
    }
}

1.6、统计指定节点个数——count

由于 set 不允许插入相同的值，所以存在就返回 1，反之返回 0。所以，count 也可以用来查找元素。

void test06() {
    set<int> st({ 4,5,2,9,6,8,3,1,7,7,7,7 }); // 初始化列表构造
    cout << st.count(5) << endl;
    cout << st.count(50) << endl;
}

1.7、区间查找——lower_bound/upper_bound

// 删除区间内的值
void test07() {
    set<int> st1({ 20,10,50,30,10,90,70,40,80 });
    Print_container(st1); // 删除 [30,50)
    auto begin1 = st1.find(30);
    auto end1 = st1.find(50);
    while (begin1 != end1) {
        begin1 = st1.erase(begin1);
    }
    Print_container(st1); // 10 20 50 70 80 90
    // 删除 [30,50]
    // lower_bound/upper_bound
    set<int> st2({ 20,10,50,30,10,90,70,40,80 });
    Print_container(st2);
    auto begin2 = st2.lower_bound(30);
    auto end2 = st2.upper_bound(50);
    while (begin2 != end2) {
        begin2 = st2.erase(begin2);
    }
    Print_container(st2); // 10 20 70 80 90
}

lower_bound 和 upper_bound 还有一个优势：可以根据 set 中不存在的值来确定区间。

2、multiset 容器

multiset 容器相比于 set 容器，不同点就在与其支持插入相同的值，其他方面与 set 完全一样。由于 multiset 支持插入相同的值，所以，其有一部分的接口与 set 略有所差异，比如，查找 val 时多个节点的值与 val 相等，那么该返回哪一个；对于有相同值的节点删除时应该删掉哪一个；count 统计节点个数时返回值可能大于 1 等。

常用接口说明

2.1、插入——insert

void test1() {
    multiset<int> multi;
    multi.insert(3);
    multi.insert(2);
    multi.insert(3);
    multi.insert(3);
    Print_container(multi);
}

2.2、查找——find

当有相同的值时，find 返回中序遍历得到的序列中的第一个。

我们做一个实验验证一下：只有当 find 返回中序遍历的序列的第一个 3 的节点的迭代器时，才能完整打印出所有的 3。

2.3、删除——erase

与 set 容器的 erase 函数基本相同，只是，当 multiset 的 erase 函数删除重复的节点时，会一次将所有具有相同值的节点全部删除。

2.4、统计节点个数——count

void test4() {
    multiset<int> multi;
    multi.insert(3);
    multi.insert(3);
    multi.insert(3);
    multi.insert(3);
    Print_container(multi);
    cout << multi.count(3);
}

2.5、返回相同节点的迭代器区间——equal_range

3、map 容器

常用接口说明

map 的常用接口其实与 set 差别不大，因为 map 执行查找，删除，统计节点个数，区间查找（lower_bound/upper_bound），以及 equal_range 都是根据其键值来完成的，与映射值无关，这一点与 set 容器完全一致，并没有什么较大的差异，除了 insert 插入时可能需要更新映射值等一些小差异。

3.1、构造函数——constructor

3.2、插入——insert

最常用的就是第一个函数，它的返回值 pair 类类型的对象。其中 pair 对象的第一个值为迭代器，如果要插入的值原来不存在，则返回新插入节点的迭代器，如果原来存在，则返回值与 val 相等的那个节点；第二个值为 bool 类型的变量。

map 对象应该有一个键值和映射值，那么应该怎么插入呢？

我们在前面已经介绍了 pair 类，而 pair 对象恰好有两个值，所以我们可以用键值和映射值构造 pair 对象，然后插入。

void test01() {
    map<string, string> dict1;
    pair<string, string> p("first", "第一"); // 构造 pair 对象
    dict1.insert(p); // 插入
    dict1.insert(pair<string, string>("second", "第二")); // 构造匿名对象
    // 隐式类型转化（单参数/多参数）
    dict1.insert({ "third", "第三" }); // make_pair
    dict1.insert(make_pair("forth", "第四")); // 初始化列表
    map<string, string> dict2 = { {"left", "左边"}, {"right", "右边"}, {"insert", "插入"},{ "string", "字符串" } };
    Print_Container(dict1);
    Print_Container(dict2);
}

当插入新节点的键值相等，映射值不会更新。

3.3、operator[]

map::operator[] 可以向 map 对象中插入数据，当要插入的数据 map 对象中不存在时，直接插入；当原来已经存在时，可以修改映射值；若插入数据时不给定映射值，则映射值采用默认值。所以可以看出，operator[] 具有 查找 + 插入 + 修改映射值的功能。operator[] 的返回值是 mapped_type 类型的引用，通过查看文档，mapped_type 其实就是映射值的类型，所以，operator[] 返回一个节点的映射值。

void test_4() {
    map<string, string> dict;
    dict.insert({ "left", "左边" });
    dict.insert(make_pair("right", "右边")); // 原来不存在的：查找 + 插入
    dict["sort"]; // 查找 + 插入 + 修改
    dict["string"] = "字符串"; // 查找 + 修改
    dict["left"] = "左边的"; // 测试返回值
    auto it = dict["left"];
    cout << it << endl;
}

返回了 left 节点的映射值。

实现一个打印函数，方便观察。

这里有一个 map 常见的场景：当我们想要统计一串字符串中元素的出现次数，就可以将元素作为键值，将出现次数作为映射值，利用 operator[] 有查找 + 插入 + 修改功能和返回映射值的特点来统计出现次数。

4、multimap 容器

multimap 几乎与 map 一样，只是 multimap 支持插入相同键值的节点，即节点的值能重复。下面通过两个接口函数来感受一下

4.1、插入——insert

void Test01() {
    multimap<string, string> mp;
    mp.insert(make_pair("left", "左边"));
    mp.insert(make_pair("left", "左边"));
    mp.insert(make_pair("left", "左边"));
    Print_Container(mp);
}

4.2、删除——erase

void Test02() {
    multimap<string, string> mp;
    mp.insert(make_pair("left", "左边"));
    mp.insert(make_pair("left", "左边"));
    mp.insert(make_pair("left", "左边"));
    mp.erase("left");
    Print_Container(mp);
}