C++ STL 容器详解：set、map 及其底层原理

4.3 set 的增删查

set 的增删查关注以下几个接口即可：

Member types
key_type -> The first template parameter (T)
value_type -> The first template parameter (T)

// 单个数据插入，如果已经存在则插入失败
pair<iterator,bool> insert(const value_type& val);
// 列表插入，已经在容器中存在的值不会插入
void insert(initializer_list<value_type> il);
// 迭代器区间插入，已经在容器中存在的值不会插入
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
// 查找 val，返回 val 所在的迭代器，没有找到返回 end()
iterator find(const value_type& val);
// 查找 val，返回 Val 的个数
size_type count(const value_type& val) const;
// 删除一个迭代器位置的值
iterator erase(const_iterator position);
// 删除 val，val 不存在返回 0，存在返回 1
size_type erase(const value_type& val);
// 删除一段迭代器区间的值
iterator erase(const_iterator first, const_iterator last);
// 返回大于等于 val 位置的迭代器
iterator lower_bound(const value_type& val) const;
// 返回大于 val 位置的迭代器
iterator upper_bound(const value_type& val) const;

4.4 insert 和迭代器遍历使用样例

#include<set>
#include<iostream>
using namespace std;
int main() {
    // 去重 + 升序排序
    set<int> s1;
    // 去重 + 排降序 (传一个大于的仿函数)
    set<int, greater<int>> s2;
    s2.insert(1);
    s2.insert(4);
    s2.insert(-2);
    s2.insert(100);

    // 使用迭代器
    set<int>::iterator it = s2.begin();
    // auto it = s2.begin();
    while (it != s2.end()) {
        cout << *it << " ";
        it++;
    }
    cout << endl;

    // 使用范围 for 打印
    for (auto e : s2) {
        cout << e << " ";
    }
    cout << endl;

    // 支持插入一段 initializer_list 列表值，已经存在的值插入失败
    s2.insert({ 2, 3, 4, 5 });
    for (auto e : s2) {
        cout << e << " ";
    }
    cout << endl;

    // set 里面存入 string 类型的值
    set<string> strset = { "sort","animal","list","young" };
    // 遍历 strset 比较 ASCII 码大小进行插入，注意这里并不是比较字符串的长度
    // 注意下面 e 最好使用引用，set 里面存的是 string 类型，多次的拷贝构造 e 会降低效率，不想改变就加上 const 即可
    for (const auto& e : strset) {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

4.5 find 和 erase 使用样例

erase 删除成功就返回 1，删除失败就返回 0。

【erase+find+count】

#include<iostream>
#include<set>
using namespace std;
int main() {
    set<int> s = { 1,4,0,34,12,56 };
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;

    // 1.利用迭代器进行删除，删除最小值
    s.erase(s.begin());
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;

    // 2.直接输入 x，删除 x
    int x = 0;
    cin >> x;
    // erase 的返回值帮助我们去判断是否删除成功
    int num = s.erase(x);
    if (num == 0) {
        cout << x << "不存在!" << endl;
    }
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;

    // 3.先查找再利用迭代器去删除
    int y = 0;
    cin >> y;
    auto pos = s.find(y);
    if (pos != s.end()) s.erase(pos);
    else cout << "不存在！" << endl;
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;

    // 算法库的查找 O(N)，全部进行遍历
    auto pos1 = find(s.begin(), s.end(), x);
    // set 自身实现的查找 O(logN),按照平衡二叉树的特点进行寻找
    auto pos2 = s.find(x);
    // 利用 count 间接实现快速查找
    cin >> x;
    if (s.count(x)) {
        cout << x << "在！" << endl;
    } else {
        cout << x << "不存在！" << endl;
    }
    return 0;
}

【lower_bound+upper_bound】

#include<iostream>
#include<set>
using namespace std;
int main() {
    set<int> s = { 10,20,35 ,40 ,50 ,65 ,70 ,80 ,90 };
    for (int i = 1; i < 10; i++) {
        s.insert(i * 10);
    }
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;

    // 实现查找到 [itlow,itup) 包含 [30, 60] 区间]，注意 [itlow,itup) 左闭右开
    // 返回 >= 30
    auto itlow = s.lower_bound(30);
    // 返回 > 60
    auto itup = s.upper_bound(60);
    // 删除这段区间的值
    s.erase(itlow, itup);
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

4.6 multiset 和 set 的差异

multiset 和 set 的使用基本完全类似，主要区别点在于 multiset 支持值冗余，那么 insert/find/count/erase 都围绕着支持值冗余有所差异。

#include<iostream>
#include<set>
using namespace std;
int main() {
    // 相比 set 不同的是，multiset 是排序，但是不去重
    multiset<int> s = { 1,4,3,4,6,4,8,3,0 };
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;

    // multiset 相比于 set 不同的是，里面可以存在多个 x，find 查找中序里面的第一个 x
    int x = 0;
    cin >> x;
    // 返回的是 pos 位置的迭代器，返回的是中序里面的第一个 x
    auto pos = s.find(x);
    while (pos != s.end() && *pos == x) {
        cout << *pos << " ";
        ++pos;
    }
    cout << endl;

    // 相比 set 不同的是，count 会返回 x 的实际个数
    cout << s.count(x) << endl;

    // 相比 set 不同的是，erase 给值时会删除所有的 x
    s.erase(x);
    for (auto e : s) {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

4.7 set 相关题目练习

我们需要知道，set 是间接实现去重操作，如果存在该值就不再插入到 set 里面。

两个数组的交集

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> s1(nums1.begin(), nums1.end());
        set<int> s2(nums2.begin(), nums2.end());
        // 因为 set 遍历是有序的，有序值，依次比较
        // 小的++，相等的就是交集
        vector<int> ret;
        auto it1 = s1.begin();
        auto it2 = s2.begin();
        while (it1 != s1.end() && it2 != s2.end()) {
            if (*it1 < *it2) {
                it1++;
            } else if (*it1 > *it2) {
                it2++;
            } else {
                ret.push_back(*it1);
                it1++;
                it2++;
            }
        }
        return ret;
    }
};

环形链表 II

数据结构初阶阶段，我们通过证明一个指针从头开始走一个指针从相遇点开始走，会在入口点相遇，理解证明都会很麻烦。这里我们使用 set 查找记录解决非常简单方便，这里体现了 set 在解决一些问题时的价值，完全是降维打击。

快速判断一个值在不在，下面类似的算法很有用。

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        set<ListNode*> s;
        ListNode* cur = head;
        while (cur) {
            // 如果 cur 在 s.count 的返回值是 1，则表明带环，返回值是 0 是插入即可
            if(s.count(cur)) return cur;//入环节点
            else s.insert(cur);
            cur=cur->next;
        }
        return nullptr;
    }
};

五、multiset

5.1 multiset 介绍

multiset 当作 set 使用，同样属于 key 模型，区别在于 multiset 允许数据冗余也就是不去除重复数据。multiset 是一种允许元素重复出现的集合类型，你可以像使用 set 一样使用它，但它会保留重复的元素并且不进行去重操作。

5.2 multiset 使用

int main() {
    multiset<int> s1;
    s1.insert(1);
    s1.insert(11);
    s1.insert(3);
    s1.insert(1);
    s1.insert(4);
    s1.insert(2);
    s1.insert(4);
    s1.insert(2);
    s1.insert(1);
    s1.insert(2);
    s1.insert(1);
    multiset<int>::iterator it = s1.begin();
    while (it != s1.end()) {
        //*it = 1;
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    auto pos = s1.find(2);
    while (pos != s1.end() && *pos == 2) {
        cout << *pos << " ";
        ++pos;
    }
    return 0;
}

六、map

6.1 map 介绍

map 是关联容器，它按照特定的次序 (按照 key 来比较) 存储由键值 key 和值 value 组合而成的元素。

在 map 中，键值 key 通常用于排序和唯一地标识元素，而值 value 中存储与此键值 key 关联的内容。

键值 key 和值 value 的类型可能不同，并且在 map 的内部，key 与 value 通过成员类型 value_type 绑定在一起，为其取别名称为 pair: typedef pair<const key, T> value_type;。

在内部，map 中的元素总是按照键值 key 进行比较排序的。

map 中通过键值访问单个元素的速度通常比 unordered_map 容器慢，但 map 允许根据顺序对元素进行直接迭代 (即对 map 中的元素进行迭代时，可以得到一个有序的序列)。

map 支持下标访问符，即在 [] 中放入 key，就可以找到与 key 对应的 value。

map 通常被实现为二叉搜索树 (更准确的说：平衡二叉搜索树 (红黑树))。

map 的模板参数说明：

• key: 键值对中 key 的类型
• T: 键值对中 value 的类型
• Compare: 比较器的类型，map 中的元素是按照 key 来比较的，缺省情况下按照小于来比较，一般情况下 (内置类型元素) 该参数不需要传递，如果无法比较时 (自定义类型)，需要用户自己显式传递比较规则 (一般情况下按照函数指针或者仿函数来传递)
• Alloc: 通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器

注意：在使用 map 时，需要包含头文件 <map>。

key 与 value 通过成员类型 value_type 绑定在一起，为其取别名称为 pair: typedef pair<const key, T> value_type; 的意思就是说，之前 key 和 value 是单个单个的存储的，现在将 key 和 value 存在一个结构中。

6.2 掌握 pair 与 make_pair

6.2.1 pair

在 C++ 中，pair 确实是一个模板类，允许用户将两个不同类型的数据组合在一起。模板的关键特性是它能够为不同类型的元素提供通用的实现，因此 pair 能够处理任意类型的两个数据项。

pair 底层实现逻辑

template <class T1, class T2>
struct pair {
    typedef T1 first_type;
    typedef T2 second_type;
    //Key T1 first;
    //value T2 second;
    pair():first(T1(), T2()){}
    pair(const T1& a, const T2& b):first(a), second(b){}
};

6.2.2 make_pair

make_pair 是 C++ 标准库中的一个函数模板，用于简化 std::pair 对象的创建。它可以自动推导出 pair 的类型，因此在构造 pair 对象时，无需显式地指定模板参数类型。

6.2.3 pair 与 make_pair 区别

相对于 pair 使用中需要明确数据类型，而 make_pair 是函数模板可以自动去推类型。

函数模板：支持类型推导，编译器根据传递的参数自动推导模板参数。类模板：不支持类型推导，必须显式指定模板参数类型，因为类的结构和使用方式更复杂，无法通过简单的参数推导出类型。

6.3 map 对象多种插入场景

int main() {
    map<string, string> dict;
    pair<string, string> kv1("sort", "排序");
    dict.insert(kv1);
    // 使用匿名对象
    dict.insert(pair<string, string>("left", "左边"));
    // 使用 make_pair，省略类型的书写
    dict.insert(make_pair("right", "右边"));
    // 隐式类型转化
    pair<string, string> kv2("string", "字符串");
    dict.insert({ "string", "字符串" });
    // 初始化列表
    map<string,string> dic2 = { {"string", "字符串"}, {"left", "左边"}, {"right", "右边"} };
    return 0;
}

关于以上两种 map 初始化的方式，推荐使用第一种写法。同时需要注意的是 dict.insert({ "string", "字符串" }); 这里不是列表初始化 initializer_list，而是调用 pair 构造函数，强制类型转化为 pair 类型插入数据。

6.3.1 map 当中列表初始化

而对于 map<string,string> dic2 = { {"string", "字符串"}, {"left", "左边"}, {"right", "右边"} }; 属于初始化列表，std::map 的构造函数接受一个 std::initializer_list<std::pair<const Key, T>> 类型的参数。所以当你使用 {"i", "dd"} 进行初始化时，它会被转换为 std::pair<const std::string, std::string> 类型，然后添加到 map 中。

6.4 将数据存在结构体

我们知道 map 中的元素类型是 pair 或 make_pair，但是为什么 map 不分开来存储数据呢？而是需要将数据放在一个结构体中，通过结构体间接访问这些对象。

//map<string, string>::iterator it = dict.begin();
//auto 的作用就重复体现到了
auto it = dict.begin();
while (it != dict.end()) {
    // iterator key 不能修改 value 可以修改
    // const_iterator key 不能修改 value 不能修改
    //it->first += 'x';
    it->second += 'x';
    ++it;
}
cout << endl;

关于 key 不是能被修改的。在 map 中，键值 key 通常用于排序和唯一地标识元素，而值 value 中存储与此键值 key 关联的内容。对此 key 是不能随意修改的，可能会破坏搜索树结构，但 key 所对的内容 value 是支持修改的。

auto it = dict.begin();
while (it != dict.end()) {
    cout << (*it).first << ":" << (*it).second << endl;
}
cout << endl;

对于如果不将 key 和 value 放在同一个结构体中，operator *只能返回一个值，但是我们希望可以得到 key 也可以得到 value 的值，对此将这两个变量放在结构体中，间接调用这两个变量，就会不出现冲突。对于上面的写法过于麻烦，这里喜欢使用→来解引用。

底层是调用 operator ->接口，这里编译器会省略一个箭头进行优化，使得使用更加便捷。

6.5 map 相关接口使用

6.5.1 map 的构造

map 的构造我们关注以下几个接口即可。

map 的支持正向和反向迭代遍历，遍历默认按 key 的升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围 for，map 支持修改 value 数据，不支持修改 key 数据，修改关键字数据，破坏了底层搜索树的结构。

// empty (1) 无参默认构造
explicit map(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
// range (2) 迭代器区间构造
template <class InputIterator>
map(InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type & = allocator_type());
// copy (3) 拷贝构造
map(const map& x);
// initializer list (5) initializer 列表构造
map(initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
// 迭代器是一个双向迭代器
iterator->a bidirectional iterator to const value_type
// 正向迭代器
iterator begin(); iterator end();
// 反向迭代器
reverse_iterator rbegin(); reverse_iterator rend();

6.5.2 map 的增删查

map 的增删查关注以下几个接口即可：map 增接口，插入的 pair 键值对数据，跟 set 所有不同，但是查和删的接口只用关键字 key 跟 set 是完全类似的，不过 find 返回 iterator，不仅仅可以确认 key 在不在，还找到 key 映射的 value，同时通过迭代还可以修改 value。

Member types
key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type,mapped_type>

// 单个数据插入，如果已经 key 存在则插入失败，key 存在相等 value 不相等也会插入失败
pair<iterator,bool> insert(const value_type& val);
// 列表插入，已经在容器中存在的值不会插入
void insert(initializer_list<value_type> il);
// 迭代器区间插入，已经在容器中存在的值不会插入
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
// 查找 k，返回 k 所在的迭代器，没有找到返回 end()
iterator find(const key_type& k);
// 查找 k，返回 k 的个数
size_type count(const key_type& k) const;
// 删除一个迭代器位置的值
iterator erase(const_iterator position);
// 删除 k，k 存在返回 0，存在返回 1
size_type erase(const key_type& k);
// 删除一段迭代器区间的值
iterator erase(const_iterator first, const_iterator last);
// 返回大于等于 k 位置的迭代器
iterator lower_bound(const key_type& k);
// 返回大于 k 位置的迭代器
const_iterator lower_bound(const key_type& k) const;

6.5.3 构造遍历及增删查使用样例

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main() {
    // 转换成多参数的直接构造 kv1
    pair<string, string> kv1 = { "sky","天空" };
    // 正常情况下是这样的，先构造 kv1 对象，再用 initializer list (5) initializer 列表构造
    //map<string, string> dict = { kv1 };
    //这里是 pair 的多参数的构造的转换，以前的单参数是直接构造，这里省略了上面的步骤
    map<string, string> dict = { {"left","左边"},{"right","右边"},{"list","列表"},{"animal","动物"} };
    auto it = dict.begin();
    while (it != dict.end()) {
        cout << (*it).first << ":"<<(*it).second << endl;
        // map 的迭代基本都使用 operator->，这里省略了一个->
        // 第一个->是迭代器运算符重载，返回 pair*，第二个箭头是结构指针解引用取 pair 数据
        //cout << it->first << ":"<<it->second << endl;
        //cout << it.operator->()->first << ":" << it->second << endl;
        it++;
    }
    cout << endl;

    // 范围 for，为什么这里使用引用？
    for (const auto& e : dict) {
        cout << e.first << ":" << e.second << endl;
    }
    cout << endl;

    /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // insert 插入 pair 对象的 4 种方式，对比之下，最后一种最方便
    pair<string, string> kv2("one","一");
    dict.insert(kv2);
    // 匿名对象去插入
    dict.insert(pair<string, string>("num", "数字"));
    // 前两个都是创建 pair 的对象，有名和匿名的区别
    dict.insert(make_pair("two", "二"));
    // 多参数也支持隐式类型转换
    dict.insert({ "three", "三" });
    for (const auto& e : dict) {
        cout << e.first << ":" << e.second << endl;
    }
    cout << endl;

    // 结构化绑定，将 dict 里面的值分别赋值给 k 和 v，C++17 才开始支持的
    for (const auto& [k,v] : dict) {
        cout << k << ":" << v << endl;
    }

    // 经典的 key/value 场景，通过一个值去找另一个值
    string str;
    while (cin >> str) {
        auto ret = dict.find(str);
        if (ret != dict.end()) {
            cout << "->" << ret->second << endl;
        } else {
            cout << "不存在！请重新输入" << endl;
        }
    }
    return 0;
}

// 修改 map 里面的 second
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main() {
    map<string, string> dict = { {"left","左边"},{"right","右边"},{"list","列表"},{"animal","动物"} };
    // 通过迭代器进行修改，但是仅能修改 second
    for (auto& e : dict) {
        e.second += "y";
        cout << e.second << endl;
    }
    cout << endl;

    // 通过 find 进行修改
    auto ret = dict.find("left");
    ret->second = "左边";
    for (const auto& e : dict) {
        cout << e.first << ":" << e.second << endl;
    }
    return 0;
}

6.5.4 map 的数据修改+map 的迭代器和 [] 功能样例

[] 的底层是用 insert 实现的，我们先来了解 insert。

前面我提到 map 支持修改 mapped_type 数据，不支持修改 key 数据，修改关键字数据，破坏了底层搜索树的结构。map 第一个支持修改的方式是通过迭代器，迭代器遍历时或者 find 返回 key 所在的 iterator 修改，map 还有一个非常重要的修改接口 operator[]，但是 operator[] 不仅仅支持修改，还支持插入数据和查找数据，所以他是一个多功能复合接口需要注意。

从内部实现角度，map 这里把我们传统说的 value 值，给的是 T 类型，typedef 为 mapped_type。而 value_type 是红黑树结点中存储的 pair 键值对值。日常使用我们还是习惯将这里的 T 映射值叫做 value。

Member types
key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type,mapped_type>

// 查找 k，返回 k 所在的迭代器，没有找到返回 end()，如果找到了通过 iterator 可以修改 key 对应的 mapped_type 值
iterator find(const key_type& k);
// 文档中对 insert 返回值的说明
// The single element versions (1) return a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to the element with an equivalent key in the map.
// The pair::second element in the pair is set to true if a new element was inserted or false if an equivalent key already existed.
// insert 插入一个 pair<key, T> 对象
// 1、如果 key 已经在 map 中，插入失败，则返回一个 pair<iterator,bool> 对象，返回 pair 对象 first 是 key 所在结点的迭代器，second 是 false
// 2、如果 key 不在在 map 中，插入成功，则返回一个 pair<iterator,bool> 对象，返回 pair 对象 first 是新插入 key 所在结点的迭代器，second 是 true
// 也就是说无论插入成功还是失败，返回 pair<iterator,bool> 对象的 first 都会指向 key 所在的迭代器
// 那么也就意味着 insert 插入失败时充当了查找的功能，正是因为这一点，insert 可以用来实现 operator[]
// 需要注意的是这里有两个 pair，不要混淆了，一个是 map 底层红黑树节点中存的 pair<key, T>，另一个是 insert 返回值 pair<iterator,bool>
pair<iterator,bool> insert(const value_type& val);
mapped_type& operator[](const key_type& k);

// operator 的内部实现
mapped_type& operator[](const key_type& k) {
    // 1、如果 k 不在 map 中，insert 会插入 k 和 mapped_type 默认值，同时 [] 返回结点中存储 mapped_type 值的引用，那么我们可以通过引用修改返映射值。所以 [] 具备了插入 + 修改功能
    // 2、如果 k 在 map 中，insert 会插入失败，但是 insert 返回 pair 对象的 first 是指向 key 结点的迭代器，返回值同时 [] 返回结点中存储 mapped_type 值的引用，所以 [] 具备了查找 + 修改的功能
    pair<iterator, bool> ret = insert({ k, mapped_type() });
    iterator it = ret.first;
    return it->second;
}

【应用 1】

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main() {
    map<string, string> dict;
    // 不存在，插入{"insert",string()}，value 中插入的是 string() 的默认值
    dict["insert"];
    // 不存在，成功插入，返回的是 value 的引用，可以完成修改
    dict["list"] = "列表";
    // 修改
    dict["list"] = "列表，清单";
    // 查找，已存在就返回已存在 list 结点迭代器中 value 的引用
    cout << dict["list"] << endl;
    return 0;
}

【应用 2】

int main() {
    // 利用 find 和 iterator 修改功能，统计水果出现的次数
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    map<string, int> countMap;
    for (const auto& str : arr) {
        // 先查找水果在不在 map 中
        // 1、不在，说明水果第一次出现，则插入{水果，1}
        // 2、在，则查找到的节点中水果对应的次数++
        auto ret = countMap.find(str);
        if (ret == countMap.end()) {
            countMap.insert({ str, 1 });
        } else {
            ret->second++;
        }
    }
    for (const auto& e : countMap) {
        cout << e.first << ":" << e.second << endl;
    }
    cout << endl;
    return 0;
}

根据上面学的知识，下面一句代码就搞定上面代码的场景，厉害！

int main() {
    // 利用 [] 插入 + 修改功能，巧妙实现统计水果出现的次数
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    map<string, int> countMap;
    for (const auto& str : arr) {
        // [] 先查找水果在不在 map 中
        // 1、不在，说明水果第一次出现，则插入{水果，0}，同时返回次数的引用，++一下就变成了 1 次了
        // 2、在，则返回水果对应的次数++
        countMap[str]++;
    }
    for (const auto& e : countMap) {
        cout << e.first << ":" << e.second << endl;
    }
    cout << endl;
    return 0;
}

6.5.5 erase

这里使用 insert 不会出现迭代器实现的问题，而 erase 可能会出现迭代器失效的问题，这里搜索树可以看成链表的加强版。

6.5.6 operator[]

首先这里 operator 不是通过下标进行访问，而是通过 key 来进行访问对应 value。关于 operator[] 实现不是通过 find 来实现而是通过 insert 来实现。

6.5.7 insert 实现 operator[]

解释上面两段话：

• key 存在，插入失败，返回 ->pair < 存在的 key 所在节点的迭代器，false>
• key 不存在，插入成功，返回 ->pair < 新插入 key 所在节点的迭代器，true>

对此我们可以看出来，insert 在 find 功能基础上增加了插入的功能。这里 insert 的功能就是查找 + 插入 (如果该元素存在，就是查找)。

6.5.8 operator[] 底层逻辑

V& operator[](const K& key) {
    // 不管插入成功还是失败，pair 中 iterator 始终指向 key 所在节点的 iterator
    //这个 V() 就是调用默认构造，不是一个明确的数值
    pair<iterator, bool> ret = this->insert(make_pair(key, V()));
    iterator it = ret.first;
    return it->second;
}

七、map 使用方面

7.1 operator[] 使用

int main() {
    map<string, string> dict;
    dict.insert({ "string", "字符串" });
    // 插入（一般不会这么用，单纯的插入）
    dict["right"];
    // 插入 left + 修改 left 对应内容
    dict["left"] = "左边";
    // "查找"
    cout << dict["string"] << endl;
    // 修改
    dict["right"] = "右边";
    string str;
    cin >> str;
    if (dict.count(str)) {
        cout << "在" << endl;
    } else {
        cout << "不在" << endl;
    }
    return 0;
}

7.2 如何统计水果出现的次数并排序（map 用法和排序稳定性）

瑕疵版本

string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };
map<string, int> countMap;
for (auto& e : arr) {
    auto it = countMap.find(e);
    if (it != countMap.end()) {
        it->second++;
    } else {
        //const pair<string, int>& val = { e, 1 };
        countMap.insert({ e, 1 });
    }
}
for (auto& kv : countMap) {
    cout << kv.first << ":" << kv.second << endl;
}
cout << endl;

优化版本

通过 operator[] 学习，我们可以对上面代码进行优化。

string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };
map<string, int> countMap;
for (auto& e : arr) {
    countMap[e]++;
}
for (auto& kv : countMap) {
    cout << kv.first << ":" << kv.second << endl;
}
cout << endl;

通过次数来排序

只需将 countMap 的 first 和 second 位置数据，分别存放在 sortMap 的 second 和 first 位置上就行了。

map<int, string> sortMap;
for (auto& kv : countMap) {
    //sortMap[kv.second] = kv.first;
    sortMap.insert({ kv.second, kv.first });
}
cout << endl;
for (auto& kv : sortMap) {
    cout << kv.first << ":" << kv.second << endl;
}
cout << endl;

这里问题就是香蕉不见。对此我们知道 map 底层是通过搜索树实现的，而二叉搜索树是不允许冗余数据，并且是通过 K 对比较的，如果出现重复的 K 不会进行插入操作。（现在是次数对内容，而不是内容对次数，搞清楚 K 现在是谁)

multimap 允许冗余

真的需要排序，可以使用 multimap 允许冗余。

八、multimap

8.1 multimap 和 map 的差异

multimap 和 map 的使用基本完全类似，主要区别点在于 multimap 支持关键值 key 冗余，那么 insert/find/count/erase 都围绕着支持关键值 key 冗余有所差异，这里跟 set 和 multiset 完全一样，比如 find 时，有多个 key，返回中序第一个。其次就是 multimap 不支持 []，因为支持 key 冗余，[] 就只能支持插入了，不能支持修改。

8.2 multimap 使用事项

• Multimaps 是关联式容器，它按照特定的顺序，存储由 key 和 value 映射成的键值对 <key,value>，其中多个键值对之间的 key 是可以重复的
• 在 multimap 中，通常按照 key 排序和惟一地标识元素，而映射的 value 存储与 key 关联的内容。key 和 value 的类型可能不同，通过 multimap 内部的成员类型 value_type 组合在一起，value_type 是组合 key 和 value 的键值对：typedef pair<const Key, T> value_type;。在内部，multimap 中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对 key 进行排序的。
• multimap 通过 key 访问单个元素的速度通常比 unordered_multimap 容器慢，但是使用迭代器直接遍历 multimap 中的元素可以得到关于 key 有序的序列。
• multimap 在底层用二叉搜索树 (红黑树) 来实现。
• multimap 中的 key 是可以重复的。
• multimap 中的元素默认将 key 按照小于来比较。
• multimap 中没有重载 operator[] 操作，允许数据冗余，那么查找有冲突。
• 使用时与 map 包含的头文件相同。