1. 序列式容器和关联式容器

前面我已经介绍过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系，比如交换⼀下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构， 两个位置有紧密的关联关系，交换⼀下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。
接下来我将讲解的map和set底层是红黑树，红黑树是⼀颗平衡⼆叉搜索树。set是key搜索场景的结构，map是key/value搜索场景的结构。

2. set系列的使用

2.1 set和multiset参考文档

https://legacy.cplusplus.com/reference/set/

2.2 set类的介绍

1.set的声明如下，T就是set底层关键字的类型
2.set默认要求T支持小于比较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第⼆个模版参数
3.set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参
数。
4.⼀般情况下，我们都不需要传后两个模版参数。
5.set底层是用红黑树实现，增删查效率是 O(logN），迭代器遍历是走的搜索树的中序，所以是有序的。
6.前面博客中我已经介绍了vector/list等容器的使用，STL容器接口设计，高度相似，所以这里我
就不再⼀个接口⼀个接口的介绍，而是直接带着大家看问档，挑比较重要的接口进行介绍。
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的构造我们关注以下几个接口即可。
set的支持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是⼆叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，set的iterator和const_iterator都不支持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。
// 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& = 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的增删查

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；

2.5 insert和迭代器遍历使用样例：

# include <iostream>
# include <set>
using namespace std;
int main ()
{
        // 去重 + 升序排序
        set< int > s;
        // 去重 + 降序排序（给⼀个⼤于的仿函数）
        //set<int, greater<int>> s;
        s. insert ( 5 );
        s. insert ( 2 );
        s. insert ( 7 );
        s. insert ( 5 );
        //set<int>::iterator it = s.begin();
        auto it = s. begin ();
        while (it != s. end ())
        {
                // error C3892: “it”: 不能给常量赋值
                // *it = 1;
                cout << *it << " " ;
                ++it;
        }
        cout << endl;
        // 插⼊⼀段 initializer_list 列表值，已经存在的值插⼊失败
        s. insert ({ 2 , 8 , 3 , 9 });
        for ( auto e : s)
        {
                cout << e << " " ;
        }
        cout << endl;
        set<string> strset = { "sort" , "insert" , "add" };
        // 遍历 string ⽐较 ascll 码⼤⼩顺序遍历的
        for ( auto & e : strset)
        {
                cout << e << " " ;
        }
        cout << endl;
}

2.6 find和erase使用样例：

# 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;
        // 直接删除 x
        int x;
        cin >> x;
        int num = s. erase (x);
        if (num == 0 )
        {
                cout << x << " 不存在！ " << endl;
        }
        for ( auto e : s)
        {
                cout << e << " " ;
        }
        cout << endl;
        // 直接查找在利⽤迭代器删除 x
        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(logN)
        auto pos2 = s. find (x);
        // 利⽤ count 间接实现快速查找
        cin >> x;
        if (s. count (x))
        {
                cout << x << " 在！ " << endl;
        }
        else
        {
                cout << x << " 不存在！ " << endl;
        }
        return 0 ;
}
# include <iostream>
# include <set>
using namespace std;
int main ()
{
        std::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.7 multiset和set的差异

multiset和set的使⽤基本完全类似，主要区别点在于multiset支持值冗余，那么
insert/find/count/erase都围绕着支持值冗余有所差异，具体参看下面的样例代码理解。
# include <iostream>
# include <set>
using namespace std;
int main ()
{
        // 相⽐ set 不同的是， multiset 是排序，但是不去重
        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;
        // 相⽐ 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 ;
}

3. map系列的使用

3.1 map和multimap参考文档

https://legacy.cplusplus.com/reference/map/

3.2 map类的介绍

map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key⽀持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第⼆个模版参数，map底层存储数据的内存是从空间配置器申请的。⼀般情况下，我们都不需要传后两个模版参数。map底层是用红黑树实现，增删查改效率是 O ( logN ) ，迭代器遍历是走的中序，所以是按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>存储键值对数据。
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& = 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在不在，还找到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 ;

3.6 map的数据修改

前面我提到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;
}

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

# include <iostream>
# include <map>
using namespace std;
int main ()
{
        // initializer_list构造及迭代遍历
        map<string, string> dict = { { "left" , " 左边 " }, { "right" , " 右边 " },
        { "insert" , " 插⼊ " },{ "string" , " 字符串 " } };
        //map<string, string>::iterator it = dict.begin();
        auto it = dict. begin ();
        while (it != dict. end ())
        {
                //cout << (*it).first <<":"<<(*it).second << endl;
                // map的迭代基本都使⽤operator->, 这⾥省略了⼀个 ->
                // 第⼀个-> 是迭代器运算符重载，返回 pair* ，第⼆个箭头是结构指针解引⽤取
                pair数据
                //cout << it.operator->()->first << ":" << it.operator->()-
                >second << endl;
                cout << it->first << ":" << it->second << endl;
                ++it;
        }
        cout << endl;
        // insert插⼊ pair 对象的 4 种⽅式，对⽐之下，最后⼀种最⽅便
        pair<string, string> kv1 ( "first" , " 第⼀个 " );
        dict. insert (kv1);
        dict. insert ( pair <string, string>( "second" , " 第⼆个 " ));
        dict. insert ( make_pair ( "sort" , " 排序 " ));
        dict. insert ({ "auto" , " ⾃动的 " });
        // "left"已经存在，插⼊失败
        dict. insert ({ "left" , " 左边，剩余 " });
        // 范围 for 遍历
        for ( const auto & e : dict)
        {
                cout << e.first << ":" << e.second << endl;
        }
        cout << endl;
        string str;
        while (cin >> str)
        {
                auto ret = dict. find (str);
                if (ret != dict. end ())
                {
                        cout << "->" << ret->second << endl;
                }
                else
                {
                        cout << " ⽆此单词，请重新输⼊ " << endl;
                }
        }
        // erase等接⼝跟 set 完全类似，这⾥就不演⽰讲解了
        return 0 ;
}

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

# include <iostream>
# include <map>
# include <string>
using namespace std;
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 ;
}
# include <iostream>
# include <map>
# include <string>
using namespace std;
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 ;
}
# include <iostream>
# include <map>
# include <string>
using namespace std;
int main ()
{
        map<string, string> dict;
        dict. insert ( make_pair ( "sort" , " 排序 " ));
        // key不存在 -> 插⼊ {"insert", string()}
        dict[ "insert" ];
        // 插⼊ + 修改
        dict[ "left" ] = " 左边 " ;
        // 修改
        dict[ "left" ] = " 左边、剩余 " ;
        // key存在 -> 查找
        cout << dict[ "left" ] << endl;
        return 0 ;
}

3.9 multimap和map的差异

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

# c++ # 开发语言 # 算法 # 数据结构 # c语言
Logo
亚马逊云科技技术品牌专区

更多推荐

open-code-review Codex 插件教程：对话式调用评审技能指南

本文是一份面向新手的 **open-code-review Codex 插件教程**，教你在 Codex 中通过对话式方式调用 open-code-review 的 AI 代码评审技能。open-code-review 是阿里巴巴开源的 AI 代码评审工具，采用"确定性流水线 + LLM Agent"混合架构，内置多语言评审规则（NPE、线程安全、XSS、SQL 注入等），可在 Codex 里用一

avatar 亚马逊云科技技术品牌专区

OBS Studio 完整指南：免费开源录屏与直播软件从零上手

想做一场像模像样的直播，或者把屏幕内容录成教程视频，但一想到商用软件的订阅费就有些犹豫？其实你不需要花一分钱。OBS Studio 是一款免费开源的直播与录屏软件，支持 Windows、macOS 和 Linux，采集、混音、编码、推流、录制，一条流水线全包了。## 先搞清楚 OBS Studio 是什么OBS Studio 是一个"场景化"的采集合成工具：你把摄像头、窗口、浏览器、图片、

avatar 亚马逊云科技技术品牌专区

如何用MediaCrawler爬取小红书抖音数据？7大平台爬虫从安装到实战完整指南

MediaCrawler 是一个支持小红书、抖音、快手、B站、微博、百度贴吧、知乎的开源自媒体数据采集工具。它能按关键词、按帖子、按创作者主页三种方式抓取笔记/视频内容、评论甚至二级评论，并把结果存成 JSON、CSV、Excel 或数据库。适合做市场调研、竞品监控、内容选题的运营人员，以及想要现成爬虫框架而不想从零写 JS 逆向的开发者。## 从一次"手动抄数据"说起想象这个场景：你负责

avatar 亚马逊云科技技术品牌专区