C++ map 与 set 容器使用详解

template <class T, // set::key_type/value_type
            class Compare = less<T>, // set::key_compare/value_compare
            class Alloc = allocator<T> // set::allocator_type
           >
class set;

2.3 set 的构造函数和迭代器

set的构造我们只需关注一下几个即可

// empty (1) 无参默认构造
explicit set(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
// range (2) 迭代器区间构造
template <class InputIterator>
set(InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
// copy (3) 拷贝构造
set(const set& x);
// initializer list (5) initializer 列表构造
set(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();

2.4 set 的增删查

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

int main() {
    // 去重 + 升序排序
    set<int> s;
    // 去重 + 降序排序，给一个大于的仿函数
    // set<int, greater<int>> s;
    // set<int, greater<int>> s = {1, 2, 7, 4, 9, 6};
    // initializer_list 初始化
    s.insert(2);
    s.insert(1);
    s.insert(5);
    s.insert(6);
    
    auto it = s.begin();
    while(it != s.end()) {
        //*it = 1; 不能修改里面的值
        cout << *it << " ";
        it++;
    }
    cout << endl;
    
    // 插入一段 initilizer_list 的值，已经存在则插入失败
    s.insert({1, 5, 3, 2, 7, 9});
    for(auto e : s) {
        cout << e << " ";
    }
    cout << endl;
    
    // 插入 string 类对象，string 类对象比较是按照 ascii 码来比较大小的
    set<string> strset = {"sort", "add", "insert"};
    for(auto &e : strset) {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

2.5 find 和 erase 的使用样例

erase, find的使用案例：

int main() {
    set<int> s = {2, 7, 4, 3, 1, 9, 5, 0};
    for(auto &e : s) {
        cout << e << " ";
    }
    cout << endl;
    
    // 删除最小值
    s.erase(s.begin());
    for(auto &e : s) {
        cout << e << " ";
    }
    cout << endl;
    
    // 删除输入的值，这个值有可能在，也有可能不在
    int x;
    cin >> x;
    int num = s.erase(x);
    if(num == 0) {
        cout << x << "不存在!" << endl;
    }
    for(auto &e : s) {
        cout << e << " ";
    }
    cout << endl;
    
    // 直接查找，再利用迭代器删除
    cin >> x;
    auto pos = s.find(x);
    if(pos != s.end()) {
        s.erase(pos);
    } else {
        cout << x << "不存在" << endl;
    }
    for(auto &e : s) {
        cout << e << " ";
    }
    cout << endl;
    
    // 算法库中的查找 O(n) 不会这样使用
    // auto pos1 = find(s.begin(), s.end(), x);
    // set 自己实现的查找 O(log n)
    auto pos2 = s.find(x);
    
    // 利用 count 快速实现间接查找
    cin >> x;
    if(s.count(x)) {
        cout << x << "在!" << endl;
    } else {
        cout << x << "不存在!" << endl;
    }
    return 0;
}

删除一段区间的值

int main() {
    set<int> myset;
    for(int i = 1; i < 10; i++) {
        myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
    }
    for(auto e : myset) {
        cout << e << " ";
    }
    cout << endl;
    
    // 实现查找到的 [itlow, itup] 包含 [30, 60] 区间
    // 返回>=30
    auto itlow = myset.lower_bound(30);
    // 返回>60
    auto itup = myset.upper_bound(60);
    
    // 删除这段区间的值
    myset.erase(itlow, itup);
    for(auto e : myset) {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

2.6 multiset 和 set 的差异

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

int main() {
    multiset<int> s = {4, 6, 4, 3, 6, 7, 8, 9, 2, 5, 3, 7, 8, 9};
    auto it = s.begin();
    while(it != s.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    
    // 相比较 set 不同的是，x 可能会存在多个，find 查找的是中序的第一个
    int x;
    cin >> 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;
}

2.7 两个数组的交集 - 力扣（LeetCode）

题目连接： 349. 两个数组的交集

解题思路： 两个数组依次比较，小的++，相等的就是交集，同时++，其中一个结束就结束了

代码实现：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // 这里用 set 实现了对数组的排序 + 去重
        set<int> s1(nums1.begin(), nums1.end());
        set<int> s2(nums2.begin(), nums2.end());
        // 小的++，相等就是交集
        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;
    }
};

2.8 环形链表 II - 力扣（LeetCode）

题目链接： 142. 环形链表 II

解题思路： 遍历这个环形链表，如果count为 0，就把此节点插入进set，如果不为 0，则此节点为入口点。

代码实现：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> s;
        ListNode* cur = head;
        while(cur) {
            if(s.count(cur)) return cur; // 等于 1 即为入口点
            else s.insert(cur);
            cur = cur->next;
        }
        return nullptr;
    }
};

3. map 系列的使用

3.1 map 和 multimap 的参考文档

点击快速到达

3.2 map 类的介绍

map的声明如下，Key 就是 map 底层关键字的类型，T 是 map 底层 Value 的类型，map 默认要求 Key 支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模板参数。map底层存储数据的内存是从空间配置器申请的。一般情况下我们都不需要传后面两个模板参数。map的底层使用红黑树实现的，增删查改的效率是 O(log n)，迭代器遍历走的是中序遍历，所以 Key 的值是有序的。

template <class Key, // map::key_type
            class T, // map::mapped_type
            class Compare = less<Key>, // map::key_compare
            class Alloc = allocator<pair<const Key, T>> // map::allocator_type
           >
class map;

3.3 pair 类型介绍

map底层红黑树节点中的数据，使用 pair<Key,T>存储键值对数据。 pair是一个类模板，里面有两个成员变量，一个是first，一个是second。

typedef pair<const Key, T> value_type;

template <class T1, class T2>
struct pair {
    typedef T1 first_type;
    typedef T2 second_type;
    T1 first;
    T2 second;
    pair(): first(T1()), second(T2()) {}
    pair(const T1& a, const T2& b): first(a), second(b) {}
    template <class U, class V>
    pair(const pair<U, V>& pr): first(pr.first), second(pr.second) {}
};

template <class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y) {
    return pair<T1, T2>(x, y);
}

3.4 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& alloc = 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();

3.5 map 的增删查

map的增删查关注以下接口即可 map的增接口，插入的是 pair 的键值对数据，跟set有所不同，但是查和删的接口只用关键字 Key，跟set完全相似。不过 find 返回的是iterator，不仅仅可以找到 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 (原文档可能有误，通常返回 1 表示删除成功)
size_type erase(const key_type& k);
// 删除一段迭代器区间的值
iterator erase(const_iterator first, const_iterator last);
// 返回大于等于 k 位置的迭代器
iterator lower_bound(const key_type& k);
const_iterator lower_bound(const key_type& k) const;

3.6 map 的数据修改

map 第一个支持修改的方式是通过迭代器，迭代器遍历时或者 find 返回 Key 所在的 iterator 修改。map 还有一个非常重要的修改接口operator[]，但是operator[]不仅仅支持数据的修改，还支持插入数据和查找数据，所以它是一个多功能复合接口。

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;
}

3.7 构造遍历以及增删查改样例

#include <map>

int main() {
    pair<string, string> kv1 = {"left", "左边"};
    // initializer_list 构造以及迭代遍历
    map<string, string> dict = {{"left", "左边"}, {"right", "右边"}, {"insert", "插入"}, {"erase", "删除"}};
    map<string, string>::iterator it = dict.begin();
    while(it != dict.end()) {
        // cout << *it << " "; // pair 不支持流提取和流插入，是一个结构体
        // cout << (*it).first << ":" << (*it).second << endl;;
        cout << it->first << ":" << it->second << endl;
        // cout << it.operator->()->first << ":" << it.operator->()->second << endl;
        // 原生写法
        ++it;
    }
    
    // map 的插入
    // insert 插入 pair 的四种方式，对比之下最后一种最方便
    pair<string, string> kv2("first", "第一个");
    dict.insert(kv2); // 匿名对象
    dict.insert(pair<string, string>("second", "第二个"));
    // make_pair
    dict.insert(make_pair("sort", "排序"));
    // make_pair 是一个函数模板，不用声明模板参数，自己推导，在底层构造一个 pair 对象再返回
    // 最后一种最好用
    dict.insert({"auto", "自动的"}); // 支持隐式类型转换
    
    // 支持范围 for 遍历
    for(auto &e : dict) {
        cout << e.first << ":" << e.second << endl;
    }
    cout << endl;
    
    // 结构化绑定 C++17
    // for (const auto& [k,v] : dict) {
    //     cout << k << ":" << v << endl;
    // }
    
    string str;
    while(cin >> str) {
        auto ret = dict.find(str);
        if(ret != dict.end()) {
            cout << "->" << ret->second << endl;
        } else {
            cout << "无此单词，请重新输入" << endl;
        }
    }
    
    // first 是不能被修改的，但是 second 可以被修改
    return 0;
}

3.8 map 的迭代器功能和 [] 功能样例

• 统计水果出现的次数

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

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

3.9 multimap 和 map 的差异

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

3.10 随机链表的复制 - 力扣（LeetCode）

题目连接： 138. 随机链表的复制

解题思路： 让原链表与拷贝链表通过map建立映射关系

代码实现：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> nodeMap;
        Node* copyhead = nullptr, *copytail = nullptr;
        // 定义一个头一个尾
        Node* cur = head;
        while(cur) {
            // 如果为空
            if(copytail == nullptr) {
                copyhead = copytail = new Node(cur->val);
            }
            // 如果不为空
            else {
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }
            // 让原节点和拷贝节点建立 map
            nodeMap[cur] = copytail;
            cur = cur->next;
        }
        
        // 处理 random
        cur = head;
        Node* copy = copyhead;
        while(cur) {
            // 原链表的 random 为空，则拷贝链表的 random 也为空
            if(cur->random == nullptr) {
                copy->random = nullptr;
            } else {
                copy->random = nodeMap[cur->random];
            }
            cur = cur->next;
            copy = copy->next;
        }
        return copyhead;
    }
};

3.11 前 K 个高频单词 - 力扣（LeetCode）

题目链接： 692. 前 K 个高频单词

解题思路 1： 用排序找前 k 个单词，因为 map 中已经对 Key 单词排序过，也就意味着遍历 map 时次序相同的单词，字典序小的在前面，字典序大的在后面，那么我们将数据放到 vector 中用一个稳定的排序就可以实现上面特殊的要求，但 sort 底层是快排，是不稳定的，所以我们要用stable_sort，是稳定的。

代码实现：

class Solution {
public:
    struct Compare {
        bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) {
            return kv1.second > kv2.second;
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        // 统计次数
        map<string, int> countMap;
        for(auto& str : words) {
            countMap[str]++;
        }
        vector<pair<string, int>> v(countMap.begin(), countMap.end());
        // 迭代器区间初始化
        stable_sort(v.begin(), v.end(), Compare());
        vector<string> retv;
        for(size_t i = 0; i < k ;++i) {
            retv.push_back(v[i].first); // 取的是每个 pair 对象中的单词
        }
        return retv;
    }
};

解题思路 2： 将 map 统计出来的次序，放到 vector 中排序，或者放到 priority_queue 中选出前 k 个，利用仿函数强制控制次数相等的，字典序小的在前面。

代码实现：

class Solution {
public:
    struct Compare {
        bool operator()(const pair<string, int>& x, const pair<string, int>& y) {
            return x.second > y.second || (x.second == y.second && x.first < y.first);
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> countMap;
        for(auto& e : words) {
            countMap[e]++;
        }
        vector<pair<string, int>> v(countMap.begin(), countMap.end());
        // 仿函数控制降序，仿函数控制次数相等，字典序小的在前面
        sort(v.begin(), v.end(), Compare());
        // 取前 k 个
        vector<string> strV;
        for(int i = 0; i < k;++i) {
            strV.push_back(v[i].first);
        }
        return strV;
    }
};

class Solution {
public:
    struct Compare {
        bool operator()(const pair<string, int>& x, const pair<string, int>& y) const {
            // 要注意优先级队列底层是反的，大堆要实现小于比较，所以这里次数相等，想要字典序小的在前面要比较字典序大的为真
            return x.second < y.second || (x.second == y.second && x.first > y.first);
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> countMap;
        for(auto& e : words) {
            countMap[e]++;
        }
        // 将 map 中的<单词，次数>放到 priority_queue 中，仿函数控制大堆，次数相同按照字典序规则排序
        priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> p(countMap.begin(), countMap.end());
        vector<string> strV;
        for(int i = 0; i < k;++i) {
            strV.push_back(p.top().first);
            p.pop();
        }
        return strV;
    }
};