C++ STL 关联容器 set 与 map 使用详解

3. 容量的操作

std::set::size

#include<iostream>
#include<set>
int main(){
    std::set<int> myints;
    std::cout << "初始状态下的 set 大小的 size 为：" << myints.size() << '\n';
    for(int i = 0; i < 10; ++i) myints.insert(i);
    std::cout << "插入 10 个元素后 set 大小的 size 为：" << myints.size() << '\n';
    myints.insert(100);
    std::cout << "插入元素 100 后 set 大小的 size 为：" << myints.size() << '\n';
    myints.erase(5);
    std::cout << "删除 5 个元素后 set 大小的 size 为：" << myints.size() << '\n';
    return 0;
}

std::set::empty

#include<iostream>
#include<set>
int main(){
    std::set<int> myset;
    myset.insert(20); myset.insert(30); myset.insert(10);
    std::cout << "myset 容器中的内容为:";
    while(!myset.empty()){
        std::cout << ' ' << *myset.begin();
        myset.erase(myset.begin());
    }
    std::cout << '\n';
    return 0;
}

4. 修改的操作

std::set::clear

#include<iostream>
#include<set>
int main(){
    std::set<int> myset;
    myset.insert(100); myset.insert(200); myset.insert(300);
    std::cout << "初始状态下 myset 容器中的内容为:";
    for(std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it){
        std::cout << ' ' << *it;
    }
    std::cout << '\n';
    myset.clear();
    myset.insert(1101); myset.insert(2202);
    std::cout << "进行清空和插入操作后 myset 容器中的内容为:";
    for(std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it){
        std::cout << ' ' << *it;
    }
    std::cout << '\n';
    return 0;
}

std::set::swap

#include<iostream>
#include<set>
int main(){
    int myints[] = {12, 75, 10, 32, 20, 25};
    std::set<int> first(myints, myints + 3); // 10, 12, 75
    std::set<int> second(myints + 3, myints + 6); // 20, 25, 32
    first.swap(second);
    std::cout << "交换后 first 容器中的内容为:";
    for(std::set<int>::iterator it = first.begin(); it != first.end(); ++it){
        std::cout << ' ' << *it;
    }
    std::cout << '\n';
    std::cout << "交换后 second 容器中的内容为:";
    for(std::set<int>::iterator it = second.begin(); it != second.end(); ++it){
        std::cout << ' ' << *it;
    }
    std::cout << '\n';
    return 0;
}

std::set::insert

#include<iostream>
#include<set>
int main(){
    std::set<int> myset;
    std::set<int>::iterator it;
    std::pair<std::set<int>::iterator, bool> ret;

    // 单个元素的插入
    for(int i = 1; i <= 5; ++i){ myset.insert(i * 10); }
    
    // 尝试插入已存在的元素 20
    ret = myset.insert(20);
    if(ret.second == false) it = ret.first;
    std::cout << "myset 容器中的内容为:";
    for(it = myset.begin(); it != myset.end(); ++it){
        std::cout << ' ' << *it;
    }
    std::cout << '\n';

    // 带提示位置的插入
    myset.insert(it, 25);
    myset.insert(it, 24);
    myset.insert(it, 26);
    std::cout << "myset 容器中的内容为:";
    for(it = myset.begin(); it != myset.end(); ++it){
        std::cout << ' ' << *it;
    }
    std::cout << '\n';

    // 范围插入
    int myints[] = {5, 10, 15};
    myset.insert(myints, myints + 3);
    std::cout << "myset 容器中的内容为:";
    for(it = myset.begin(); it != myset.end(); ++it){
        std::cout << ' ' << *it;
    }
    std::cout << '\n';
    return 0;
}

std::set::erase

#include<iostream>
#include<set>
int main(){
    std::set<int> myset;
    std::set<int>::iterator it;

    for(int i = 1; i < 10; i++){ myset.insert(i * 10); }
    it = myset.begin(); ++it;

    // 迭代器位置删除
    myset.erase(it);

    // 按值删除
    myset.erase(40);

    // 迭代器范围删除
    it = myset.find(60);
    myset.erase(it, myset.end());

    std::cout << "myset 容器中的内容为:";
    for(it = myset.begin(); it != myset.end(); ++it){
        std::cout << ' ' << *it;
    }
    std::cout << '\n';
    return 0;
}

5. 比较的操作

std::set::key_comp

#include<iostream>
#include<set>
int main(){
    std::set<int> myset;
    std::set<int>::key_compare mycomp = myset.key_comp();
    for(int i = 0; i <= 5; i++){ myset.insert(i); }
    int highest = *myset.rbegin();
    std::set<int>::iterator it = myset.begin();
    do{
        std::cout << ' ' << *it;
    }while(mycomp(*(++it), highest));
    std::cout << '\n';
    return 0;
}

std::set::value_comp

#include<iostream>
#include<set>
int main(){
    std::set<int> myset;
    std::set<int>::value_compare mycomp = myset.value_comp();
    for(int i = 0; i <= 5; i++){ myset.insert(i); }
    int highest = *myset.rbegin();
    std::set<int>::iterator it = myset.begin();
    do{
        std::cout << ' ' << *it;
    }while(mycomp(*(++it), highest));
    std::cout << '\n';
    return 0;
}

6. 其他的操作

std::set::find

#include<iostream>
#include<set>
int main(){
    std::set<int> myset;
    std::set<int>::iterator it;
    for(int i = 1; i <= 5; i++){ myset.insert(i * 10); }
    it = myset.find(20); myset.erase(it);
    myset.erase(myset.find(40));
    std::cout << "myset 容器中的内容为:";
    for(it = myset.begin(); it != myset.end(); ++it){
        std::cout << ' ' << *it;
    }
    std::cout << '\n';
    return 0;
}

std::set::count

#include<iostream>
#include<set>
int main(){
    std::set<int> myset;
    for(int i = 1; i < 5; ++i){ myset.insert(i * 3); }
    for(int i = 0; i < 10; ++i){
        std::cout << i;
        if(myset.count(i) != 0) std::cout << "在 myset 容器中\n";
        else std::cout << "不在 myset 容器中\n";
    }
    return 0;
}

std::set::lower_bound / upper_bound / equal_range

#include<iostream>
#include<set>
int main(){
    std::set<int> myset;
    std::set<int>::iterator itlow, itup;
    for(int i = 1; i < 10; i++) myset.insert(i * 10);
    
    itlow = myset.lower_bound(30);
    itup = myset.upper_bound(60);
    myset.erase(itlow, itup);
    
    std::cout << "myset 容器的内容为:";
    for(std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it){
        std::cout << ' ' << *it;
    }
    std::cout << '\n';
    return 0;
}

#include<iostream>
#include<set>
int main(){
    std::set<int> myset;
    for(int i = 1; i <= 5; i++) myset.insert(i * 10);
    std::pair<std::set<int>::const_iterator, std::set<int>::const_iterator> ret;
    ret = myset.equal_range(30);
    std::cout << "lower_bound（ret.first）指向：" << *ret.first << '\n';
    std::cout << "upper_bound（ret.second）指向：" << *ret.second << '\n';
    return 0;
}

set 容器使用示例

基础特性与遍历

#include<iostream>
#include<set>
using namespace std;
int main(){
    set<int> s;
    s.insert(5); s.insert(2); s.insert(7); s.insert(5); // 重复元素被过滤
    auto it = s.begin();
    while(it != s.end()){ cout << *it << " "; ++it; }
    cout << endl;
    
    // 批量插入
    s.insert({2, 8, 3, 9});
    for(auto e : s){ cout << e << " "; }
    cout << endl;
    
    // 字符串 set
    set<string> strset = {"sort", "insert", "add"};
    for(auto& e : strset){ cout << e << " "; }
    cout << endl;
    return 0;
}

迭代器删除与查找

#include<iostream>
#include<set>
using namespace std;
int main(){
    set<int> s = {4, 2, 7, 2, 8, 5, 9};
    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; }
    else{ cout << x << " 存在！" << endl; }
    
    // 先查找再删除
    cin >> x;
    auto pos = s.find(x);
    if(pos != s.end()){ s.erase(pos); }
    
    // 利用 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(){
    std::set<int> myset;
    for(int i = 1; i < 10; i++){ myset.insert(i * 10); }
    
    auto itlow = myset.lower_bound(30);
    auto itup = myset.upper_bound(60);
    myset.erase(itlow, itup);
    
    for(auto e : myset){ cout << e << " "; }
    cout << endl;
    return 0;
}

multiset 容器

1. multiset 介绍

multiset 允许元素重复，底层同样基于红黑树实现。

template<class T,
class Compare = less<T>,
class Alloc = allocator<T>>
class multiset;

2. set 与 multiset 的区别

• set：自动去重，容器中元素唯一。
• multiset：允许元素重复，侧重按序存储重复数据。

代码示例

#include<iostream>
#include<set>
using namespace std;
int main(){
    multiset<int> s = {4, 2, 7, 2, 4, 8, 4, 5, 4, 9};
    
    // 遍历输出所有元素
    auto it = s.begin();
    while(it != s.end()){ cout << *it << " "; ++it; }
    cout << endl;
    
    // find 返回第一个匹配
    int x; cin >> x;
    auto pos = s.find(x);
    while(pos != s.end() && *pos == x){ cout << *pos << " "; ++pos; }
    cout << endl;
    
    // count 返回实际重复次数
    cout << "数量：" << s.count(x) << endl;
    
    // erase 按值删除所有匹配
    cin >> x;
    s.erase(x);
    for(auto it : s){ cout << it << " "; }
    cout << endl;
    return 0;
}

pair 容器

1. pair 介绍

pair 用于将两个不同类型的数据组合成一个逻辑单元，位于 <utility> 头文件。

std::pair<Type1, Type2> pairName(value1, value2);

2. 特性

• 元素访问：通过 first 和 second 成员变量访问。
• 比较操作：支持按字典序比较（先比 first，若相等再比 second）。

3. 使用示例

/*-------------任务 1：定义 map 中 value_type 的类型别名-------------*/
typedef pair<const Key, T> value_type;

/*-------------任务 2：定义 pair 模板结构体-------------*/
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){}
};

/*-------------任务 3：使用辅助函数 make_pair-------------*/
template<class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y){
    return(pair<T1, T2>(x, y));
}

map 容器

1. map 容器介绍

map 是关联容器，包含唯一的键并关联到值。

template<class Key,
class T,
class Compare = less<Key>,
class Alloc = allocator<pair<const Key, T>>
class map;

模板参数说明：

• 键类型（Key）：map 中用于索引和排序的关键字类型。
• 映射值类型（T）：与键关联的具体数据类型。
• 比较器（Compare）：用于定义键之间的排序规则。
• 内存分配器（Alloc）：负责管理 map 底层存储的键值对的内存分配。

2. map 容器的常见构造

#include<iostream>
#include<map>
int main(){
    // 默认构造函数
    std::map<char, int> m1;
    m1['a'] = 10; m1['b'] = 30;
    
    // 范围构造函数
    std::map<char, int> m2(m1.begin(), m1.end());
    
    // 拷贝构造函数
    std::map<char, int> m3(m2);
    
    // 使用自定义比较器
    struct classcomp{ bool operator()(const char& lhs, const char& rhs) const { return lhs < rhs; }};
    std::map<char, int, classcomp> m4;
    
    return 0;
}

3. 容量的操作

std::map::size / empty

#include<iostream>
#include<map>
int main(){
    std::map<char, int> mymap;
    mymap['a'] = 101; mymap['b'] = 202; mymap['c'] = 302;
    std::cout << "mymap 的大小为：" << mymap.size() << '\n';
    return 0;
}

#include<iostream>
#include<map>
int main(){
    std::map<char, int> mymap;
    mymap['a'] = 10; mymap['b'] = 20; mymap['c'] = 30;
    while(!mymap.empty()){
        std::cout << mymap.begin()->first << " => " << mymap.begin()->second << '\n';
        mymap.erase(mymap.begin());
    }
    return 0;
}

4. 访问的操作

std::map::operator[]

#include<iostream>
#include<map>
#include<string>
int main(){
    std::map<char, std::string> mymap;
    mymap['a'] = "an element";
    mymap['b'] = "another element";
    mymap['c'] = mymap['b'];
    
    std::cout << "mymap['a'] is " << mymap['a'] << '\n';
    std::cout << "mymap['d'] is " << mymap['d'] << '\n'; // 键不存在时自动插入
    std::cout << "mymap now contains " << mymap.size() << " elements.\n";
    return 0;
}

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main(){
    map<string, string> dict;
    dict.insert(make_pair("sort", "排序"));
    
    // 插入功能
    dict["insert"];
    
    // 插入 + 修改
    dict["left"] = "左边";
    
    // 修改功能
    dict["left"] = "左边、剩余";
    
    // 查找功能
    cout << dict["left"] << endl;
    return 0;
}

5. 修改的操作

std::map::clear / swap / insert / erase

#include<iostream>
#include<map>
int main(){
    std::map<char, int> mymap;
    mymap['x'] = 100; mymap['y'] = 200; mymap['z'] = 300;
    mymap.clear();
    mymap['a'] = 1101; mymap['b'] = 2202;
    for(std::map<char, int>::iterator it = mymap.begin(); it != mymap.end(); ++it){
        std::cout << it->first << " => " << it->second << '\n';
    }
    return 0;
}

#include<iostream>
#include<map>
int main(){
    std::map<char, int> foo, bar;
    foo['x'] = 100; foo['y'] = 200;
    bar['a'] = 11; bar['b'] = 22; bar['c'] = 33;
    foo.swap(bar);
    for(std::map<char, int>::iterator it = foo.begin(); it != foo.end(); ++it){
        std::cout << it->first << " => " << it->second << '\n';
    }
    return 0;
}

#include<iostream>
#include<map>
int main(){
    std::map<char, int> mymap;
    mymap.insert(std::pair<char, int>('a', 100));
    mymap.insert(std::pair<char, int>('z', 200));
    
    std::pair<std::map<char, int>::iterator, bool> ret;
    ret = mymap.insert(std::pair<char, int>('z', 500));
    if(ret.second == false){
        std::cout << "元素'z'已经存在\n";
        std::cout << "其值为：" << ret.first->second << '\n';
    }
    
    std::map<char, int>::iterator it = mymap.begin();
    mymap.insert(it, std::pair<char, int>('b', 300));
    
    std::map<char, int> anothermap;
    anothermap.insert(mymap.begin(), mymap.find('c'));
    return 0;
}

#include<iostream>
#include<map>
int main(){
    std::map<char, int> mymap;
    mymap['a'] = 10; mymap['b'] = 20; mymap['c'] = 30;
    mymap['d'] = 40; mymap['e'] = 50; mymap['f'] = 60;
    
    it = mymap.find('b'); mymap.erase(it);
    mymap.erase('c');
    it = mymap.find('e'); mymap.erase(it, mymap.end());
    
    for(it = mymap.begin(); it != mymap.end(); ++it){
        std::cout << it->first << " => " << it->second << '\n';
    }
    return 0;
}

6. 其他的操作

std::map::find / count / lower_bound / upper_bound / equal_range

#include<iostream>
#include<map>
int main(){
    std::map<char, int> mymap;
    mymap['a'] = 50; mymap['b'] = 100; mymap['c'] = 150; mymap['d'] = 200;
    it = mymap.find('b');
    if(it != mymap.end()) mymap.erase(it);
    return 0;
}

#include<iostream>
#include<map>
int main(){
    std::map<char, int> mymap;
    mymap['a'] = 101; mymap['c'] = 202; mymap['f'] = 303;
    for(char c = 'a'; c < 'h'; c++){
        std::cout << c;
        if(mymap.count(c) > 0)
            std::cout << "是 mymap 容器中的元素\n";
        else
            std::cout << "不是 mymap 容器中的元素\n";
    }
    return 0;
}

#include<iostream>
#include<map>
int main(){
    std::map<char, int> mymap;
    mymap['a'] = 20; mymap['b'] = 40; mymap['c'] = 60; mymap['d'] = 80; mymap['e'] = 100;
    itlow = mymap.lower_bound('b');
    itup = mymap.upper_bound('d');
    mymap.erase(itlow, itup);
    return 0;
}

#include<iostream>
#include<map>
int main(){
    std::map<char, int> mymap;
    mymap['a'] = 10; mymap['b'] = 20; mymap['c'] = 30;
    std::pair<std::map<char, int>::iterator, std::map<char, int>::iterator> ret;
    ret = mymap.equal_range('b');
    std::cout << "lower_bound 指向的元素是：" << ret.first->first << " => " << ret.first->second << '\n';
    std::cout << "upper_bound 指向的元素是：" << ret.second->first << " => " << ret.second->second << '\n';
    return 0;
}

7. map 核心接口设计说明

#include<map>
using namespace std;

using key_type = /* 模板参数 Key */;
using mapped_type = /* 模板参数 T */;
using value_type = pair<const key_type, mapped_type>;

iterator find(const key_type& k);

pair<iterator, bool> insert(const value_type& val);

mapped_type& operator[](const key_type& k){
    pair<iterator, bool> ret = insert({k, mapped_type()});
    iterator it = ret.first;
    return it->second;
}

8. map 使用示例

#include<iostream>
#include<map>
using namespace std;
int main(){
    map<string, string> dict = {{"left", "左边"}, {"right", "右边"}};
    auto it = dict.begin();
    while(it != dict.end()){ cout << it->first << ":" << it->second << endl; ++it; }
    
    dict.insert(make_pair("sort", "排序"));
    dict.insert({"auto", "自动的"});
    
    for(const auto& e : dict){ cout << e.first << ":" << e.second << endl; }
    return 0;
}

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main(){
    string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果"};
    map<string, int> countMap;
    for(const auto& str : arr){
        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; }
    return 0;
}

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main(){
    string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果"};
    map<string, int> countMap;
    for(const auto& str : arr){ countMap[str]++; }
    for(const auto& e : countMap){ cout << e.first << ":" << e.second << endl; }
    return 0;
}

multimap 容器

1. multimap 介绍

multimap 允许键冗余，适合存'一对多'的映射关系。

template<class Key,
class T,
class Compare = less<Key>,
class Alloc = allocator<pair<const Key, T>>
class multimap;

2. map 与 multimap 的区别

• map：自动保证键唯一，容器中每个键对应唯一的映射关系。
• multimap：允许键冗余，侧重按序存储键可重复的映射数据。

注意：multimap 不支持 operator[]，因为键可冗余的场景下无法明确指定修改哪一个键对应的值。

OJ 练习

1. set 相关题目

349. 两个数组的交集

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

142. 环形链表 II

class Solution{
public:
    ListNode *detectCycle(ListNode *head){
        set<ListNode*> s;
        ListNode* cur = head;
        while(cur){
            auto ret = s.insert(cur);
            if(ret.second == false) return cur;
            cur = cur->next;
        }
        return nullptr;
    }
};

2. map 相关题目

138. 随机链表的复制

class Solution{
public:
    Node* copyRandomList(Node* head){
        map<Node*, Node*> m;
        Node* copyHead = nullptr;
        Node* copyTail = nullptr;
        Node* curr = head;
        
        while(curr){
            if(copyTail == nullptr){
                copyHead = copyTail = new Node(curr->val);
            } else {
                copyTail->next = new Node(curr->val);
                copyTail = copyTail->next;
            }
            m[curr] = copyTail;
            curr = curr->next;
        }
        
        curr = head;
        Node* copy = copyHead;
        while(curr){
            if(curr->random == nullptr){
                copy->random = nullptr;
            } else {
                copy->random = m[curr->random];
            }
            curr = curr->next;
            copy = copy->next;
        }
        return copyHead;
    }
};

692. 前 K 个高频单词

方法一：基于 stable_sort 排序

class Solution{
public:
    struct Compare{
        bool operator()(const pair<string, int>& x, const pair<string, int>& y) const{
            return x.second > y.second;
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k){
        map<string, int> m;
        for(auto& e : words){ m[e]++; }
        vector<pair<string, int>> v(m.begin(), m.end());
        stable_sort(v.begin(), v.end(), Compare());
        vector<string> ret;
        for(int i = 0; i < k; i++){ ret.push_back(v[i].first); }
        return ret;
    }
};

方法二：基于 sort 排序

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> m;
        for(auto& e : words){ m[e]++; }
        vector<pair<string, int>> v(m.begin(), m.end());
        sort(v.begin(), v.end(), Compare());
        vector<string> ret;
        for(int i = 0; i < k; i++){ ret.push_back(v[i].first); }
        return ret;
    }
};

方法三：基于 priority_queue 大顶堆

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> m;
        for(auto& e : words){ m[e]++; }
        priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> p(m.begin(), m.end());
        vector<string> ret;
        for(int i = 0; i < k; i++){
            ret.push_back(p.top().first);
            p.pop();
        }
        return ret;
    }
};