C++：STL - set & map-阿里云开发者社区

关联式容器

关联式容器是C++标准库提供的一种数据结构，用于存储操作键值对（key-value）。每个键值对都包含一个键和一个关联的值。关联式容器提供了通过键快速查找和访问值的功能。

C++98标准库提供了四种树形结构的关联式容器：set、multiset、map和multimap。

set：set是一个无序集合，存储唯一的元素。内部实现使用红黑树，因此元素是按照特定的顺序进行存储。查找和插入操作的平均时间复杂度为O(log n)。
multiset：multiset和set类似，不同之处在于它可以存储重复的元素。
map：map是一个键值对的集合，其中的键是唯一的。内部实现也是使用红黑树。查找和插入操作的平均时间复杂度为O(log n)。
multimap：multimap和map类似，不同之处在于它可以存储重复的键。

后续C++11又提供了哈希结构的关联式容器，此博客不做讲解。

关联式容器与序列式容器的区别在于元素的顺序。关联式容器内部使用二叉搜索树（如红黑树）实现，因此元素是按照特定的顺序进行存储。而序列式容器内部使用动态数组或链表实现，元素按照插入的顺序进行存储。

pair

在讲解map与set之前，我们要先了解一个类：pair。

pair是一个模板类，封装了两个成员变量first，second，用于存储两个不同类型的值。它被定义在头文件<utility>中。

pair类的定义如下：

template <class T1, class T2>
struct pair
{
    T1 first;
    T2 second;
};

pair类有两个模板参数T1和T2，分别表示两个值的类型。

pair类有两个成员变量first和second，分别表示两个值。

pair类的构造函数有多个重载形式，可以根据需要来创建pair对象。其中，最常用的是以下几种：

pair()：默认构造函数，创建一个pair对象，默认初始化first和second。
pair(const T1& x, const T2& y)：构造函数，初始化first为x，second为y。

pair类还支持拷贝构造函数、移动构造函数和赋值运算符重载，以及比较运算符重载。

使用pair类可以方便地将两个不同类型的值组合在一起，便于传递和操作。例如：

pair<int, string> p1(1, "hello");
cout << p1.first << " " << p1.second << endl;

pair<double, char> p2;
p2.first = 3.14;
p2.second = 'a';
cout << p2.first << " " << p2.second << endl;

输出结果为：

1 hello
3.14 a

另外的，C++还提供了一个函数make_pair用于创建pair对象，需要时直接传入两个参数，分别对应first和second，make_pair内部会自动推演参数类型，返回一个pair对象。

auto p = make_pair("hello world", 10);

此时make_pair就会推演对象的类型为pair<const char*, int>。

因为pair可以存储任意两个不同类型的数据，所以任何需要封装两个变量的地方，都可以使用pair。而我们的key - value结构，就是需要封装两个变量key和value，所以map和set的底层都是使用pair来完成的。

set

set是一种集合容器。它是基于红黑树实现的，它可以存储不重复的元素，并且会自动按照元素的大小进行排序。

下面是一些set的概念和特点：

不重复的元素：set中的元素是不重复的，每个元素只能出现一次。
自动排序：set中的元素会根据元素的大小进行自动排序。默认情况下，set按照升序排列。你也可以通过传入自定义的比较函数来进行降序排序。
红黑树实现：set内部使用红黑树（一种自平衡二叉搜索树）来存储元素。这个数据结构保证了素的快速插入、查找和删除，时间复杂度为O(logn)。
迭代器支持：set提供了迭代器，可以用于遍历集合中的元素。
查找和插入的效率高：由于set是基于红黑树实现，查找和插入操作的平均时间复杂度为O(logn)，效率比较高。
元素的值是不可修改的：在set中，元素的值是不可修改的。如果需要修改元素的值，需要先删除旧的元素，然后插入新的元素。

接下来我们讲解set的接口使用以及注意事项。

模板参数

set的模板如下：

template < class T, class Compare = less<T>> class set;

其有两个模板参数：

T：代表value值的类型

Compare：代表了比较规则的仿函数

也就是说，我们在定义set的时候，可以在模板参数中传入仿函数，用于制定规则：

template <class T>
struct comp
{
    bool operator()(const T& t1, const T& t2) const
    {
        return T1 > T2;
    }
};

int main()
{
    set<int, comp<int>> s1;
    return 0;
}

其中，s1通过仿函数comp完成了逆序排列，而set的模板参数有缺省值Compare = less<T>，所以set的默认情况是升序排列。

typedef的类型

类型	含义	缺省值
`key_type`	第一个模板参数`T`的类型，即`value`的类型

`value_type`	第一个模板参数`T`的类型，即`value`的类型
`key_compare`	第二个模板参数的类型，即用于比较的仿函数的类型	less<key_type>
`value_compare`	第二个模板参数的类型，即用于比较的仿函数的类型	less<value_type>

由于在set中，key和value是一致的，所以以上表格中，key_type和value_type是一致的，key_compare与value_compare是一致的。

而key_compare与value_compare的缺省值是 less<key_type>，即升序排序的仿函数。

构造函数

默认构造：

explicit set (const key_compare& comp = key_compare());

迭代器区间构造：

template <class InputIterator>
set (InputIterator first, InputIterator last,
  const key_compare& comp = key_compare());

通过一个迭代器区间来构造set，由于是模板，所以可以是其它容器的迭代器。

迭代器

set的迭代器用法与其它容器一致，就是通过begin和end来进行遍历，或者说使用反向迭代器。值得注意的是容器set的迭代器走中序遍历，得到的是有序的数据。

常规接口

empty：

bool empty() const;

即返回这个set是否为空，如果为空返回true，不为空返回false。

size：

size_type size() const;

返回当前set存储的节点个数。

swap：

void swap (set& x);

交换两个set的根节点指针。

clear：

void clear();

清空当前set。

key_comp 与 value_comp：

key_compare key_comp() const;
value_compare value_comp() const;

可以看到，两者的返回类型分别是key_compare 与value_compare ，也就是比较key与value的仿函数，这两个函数的功能就是返回当前比较set的仿函数。

find：

iterator find (const value_type& val) const;

find函数用于查找val值的节点，如果找到了，返回指向val的迭代器；如果没找到，则返回end()处的迭代器。

count：

size_type count (const value_type& val) const;

count函数用于检测set中存在几个val值的节点，但是由于set不可以存在重复的元素，所以这个函数的返回值只有可能是1或0。返回类型为size_type即size_t无符号整型。

特殊接口

lower_bound 与 upper_bound：

iterator lower_bound (const value_type& val) const;
iterator upper_bound (const value_type& val) const;

两者都传入一个val值，返回值一个iterator迭代器，它们的功能如下：

lower_bound ：返回第一个 >=val节点的迭代器

upper_bound ：返回第一个 >val节点的迭代器

在STL设计中，都是利用左闭右开的区间特性，而迭代器也利用了此特性，我们可以使用lower_bound 与upper_bound配合得到一个一开一闭的迭代器区间，从而进行遍历，删除等等操作。

比如现在我们想遍历一个set中[3, 20]的闭区间，你会如何查找迭代器？

假设我们有一个名为s1的set，看一段代码：

auto it1 = s1.find(3);
auto it2 = s2.find(21);

while(it1 != it2)
{
  cout << *it1 << endl;
  ++it1;
}

请问这个代码正确吗？

以上代码存在两个问题：

在s1中可能不存在值为3或者21的节点，find有可能是失败的，此时我们就无法遍历到[3， 20]了。

由于我们要遍历[3， 20]，迭代器遵循左闭右开的特性，所以我们找了一个比20大的迭代器21来遍历。但是如果我们的set存储的是float类型的数据，20与21之间可能还会存在其它节点，此时我们可能就会多遍历到其它节点。

因此我们可以利用lower_bound 与upper_bound配合来得到迭代器：

auto it1 = s1.lower_bound(3);
auto it2 = s2.upper_bound(21);

while(it1 != it2)
{
  cout << *it1 << endl;
  ++it1;
}

以上代码中lower_bound(3)可以得到第一个>=3节点的迭代器，这样就不怕3节点不存在的情况了，如果3存在，此函数得到3，如果不存在，就得到大于3的下一个节点。

而upper_bound(21)则是得到第一个>21节点的迭代器，如果我们存储了float类型的数据，而刚好存储了一个21.0001的数据，那么此时upper_bound(21)就刚刚好返回这个只大21一点点的节点。

通过两者配合，我们就可以得到一个等效的左闭右开迭代器区间，后续方便操作。

erase：

set的erase存在三个重载：

void erase (iterator position);

这个erase用于删除迭代器指向的节点，迭代器必须有效。

void erase (iterator first, iterator last);

这个erase用于删除整个迭代器区间[first, last)，迭代器必须有效。

size_type erase (const value_type& val);

这个erase用于删除val值的节点，val值可以不存在，删除后返回删除节点的个数。在set中，由于不存在重复节点，所以返回值只可能是0或1。

insert：

set的insert也存在三个重载：

iterator insert (iterator position, const value_type& val);

这个重载用于提高插入效率，如果迭代器position位于插入val值的节点之前，那么此次插入val的效率会提高，但是如果迭代器position与插入val节点无关，那么与一般的插入一致。

template <class InputIterator>
void insert (InputIterator first, InputIterator last);

这个重载用于插入一整个迭代器区间[first, last)。

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

这是最常用的插入，其用于直接插入一个val值的节点，但是其返回值比较特别：pair<iterator,bool>

如果原先val存在，此时iterator指向原先的val节点，bool值返回false表示插入失败

如果原先val不存在，此时iterator指向新插入的val节点，bool值返回true表示插入成功

但是函数不能一次性返回两个值，于是把iterator和bool两个值封装进pair中返回。这样我们就既可以得到迭代器，又可以检测是否插入成功了。

multiset

multiset是一个允许存在重复元素的set，其它的效果与set完全一致。

但是有几个接口还是值得注意：

find：

对multiset使用find时，由于一个val可能有多个节点，此时返回中序遍历的第一个节点。

count：

对于set而言，count用于返回某个val值的个数，由于set不能重复，所以这个count接口没有多大意义。而对于multiset才有用，可以检测val的个数。

map

map是一种关联容器，用于存储键-值对（key-value）。map中的每个元素都由一个键和一个与之关联的值组成，键和值可以是任意类型。其将key和value封装进了pair中，所以每一个节点都是一个pair<key, value>。

模板参数

set的模板如下：

template < class Key,  class T, class Compare = less<Key> >class map

其有三个模板参数：

Key：代表key值的类型

T：代表value值的类型

Compare：代表了比较规则的仿函数

同样的，map也可以在模板参数中定义仿函数，与set相似。

typedef的类型

类型	含义	缺省值

`key_type`	第一个模板参数`Key`的类型，即`key`的类型
`mapped_type`	第二个模板参数`T`的类型，即`value`的类型
value_type	将`key`与`value`封装后 `pair<const key_type,mapped_type>`的类型
`key_compare`	第二个模板参数的类型，即用于比较的仿函数的类型	less<key_type>

在map中，value的类型是mapped_type，而value_type却是pair<const key_type,mapped_type>的类型，这是值得注意的。

常规接口

由于map的很多接口和set一致，这里就用一张表格概括：

函数	声明	功能	注意事项
迭代器	begin , end等	遍历map	走中序遍历，得到有序数据
empty	bool empty() const;	判空	-
size	size_type size() const;	返回元素个数	-

erase	void erase (iterator position);	删除迭代器指向的节点	迭代器必须有效
	size_type erase (const key_type& k);	删除key值的节点	key值可以不存在
	void erase (iterator first, iterator last);	删除迭代器区间	-

swap	void swap (map& x);	交换两棵树根节点指针	-
clear	void clear();	清空map	-
key_comp	key_compare key_comp() const;	得到比较key的仿函数	-

value_comp	value_compare value_comp() const;	得到比较value的仿函数	-
find	iterator find (const key_type& k);	得到key位置的迭代器	如果没有找到，返回end()等效的迭代器

count

size_type count (const key_type& k) const;

返回值为key的节点个数

lower_bound

iterator lower_bound (const key_type& k);

返回第一个>=key值节点的迭代器

upper_bound

iterator upper_bound (const key_type& k);

返回第一个>key值节点的迭代器

特殊接口

insert：

对于map而言，insert的功能其实和set是一致的，但是不一样的是我们需要插入pair<key, value>，所以此处拿出来额外讲解。

重点看到以下insert的重载：

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

其插入的值val的类型时候value_type，而我们先前说明过，value_type就是pair<key, value>的类型。也就是说，我们要构造出一个pair插入进去。

现在我们有map<string, int>：

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

现在我们对其进行插入：

利用匿名对象插入：

m.insert(pair<string, int>("hello", 100));

以上代码，我们利用pair<string, int>("hello", 100)这种语法构造了一个匿名对象，然后进行插入。

利用多参数默认构造的类型转化：

m.insert({ "hello", 100 });

由于pair具有一个多参数的默认构造，具有类型转化的功能，所以我们可以利用隐式类型转化进行传参。而我们有多个参数，所以要把这些参数用{}括起来。

利用make_pair进行插入：

m.insert(make_pair("hello", 100));

即利用make_pair函数，让其自动推导类型构造pair。

operator[ ]：

map还重载了[]，这个重载比较复杂，但是非常有用，我们先看到声明：

mapped_type& operator[] (const key_type& k);

其接收一个key_type类型的参数，也就是接受一个key，然后返回一个mapped_type&，也就是一个value的引用。其功能为：接受一个key值，然后返回这个key对应的value的引用。

其等效于下面的代码：

(*((this->insert(make_pair(k,mapped_type()))).first)).second

现在我们来解读以上代码，我们将其拆解为四个部分：make_pair(k, mapped_type( )) + this->insert( ) + ( ).first + (*( )).second，我们一层层解析。

第一层：

make_pair(k, mapped_type( ))

可以看出，这是在利用参数k，通过make_pair构造一个pair，而这个pair的value使用了mapped_type( )（mapped_type就是value的类型）来调用默认构造。这样我们最后就得到了一个pair<key, value>。

第二层：

this->insert( )

上一层我们构造了一个pair<key, value>，然后它被作为参数，传入到这个insert中，相当于把刚刚构造的节点插入进map中。map的插入后，不论成功与否，都会返回一个pair<iterator, bool>，iterator用于指向key的迭代器，bool用于标识插入是否成功。所以这一层最后得到了一个pair，分别存储了指向key的迭代器和bool。

第三层：

( ).first

上一层中我们得到了pair<iterator, bool>，这一层访问它的first，也就是访问了iterator，所以这一层得到了指向key值的迭代器。

第四层：

(*( )).second

我们上一层拿到了指向key的迭代器，这一层先对迭代器解引用*( )，此时就得到了一个map的节点。而map的节点是pair<key, value>，所以我们解引用得到了一个pair，随后通过( ).second访问pair<key, value>的second，也就是value。最后返回这个value的引用。

所以我们最后得到了key对应的value的引用。那么这有什么用呢？

假设我们有一个map<string, string>类型的字典dict，通过这个来展示operator[ ]的功能：

插入一个key值：
dict["left"];
以上语句在dict中插入了一个key = "left"但是没有value的节点
插入一对key - value：
dict["left"] = "左边";
由于operator[ ]返回的是对应的引用，因此我们可以直接给返回值赋值，此时我们就插入了一个节点key = "left" - value = "左边"
修改key对应的value：
dict[“coffe”] = "咖啡";
如果我们的dict原先就存在key = "coffe"的节点，以上代码可以修改这个key的value值

得到key对应的value：
cout << dict["coffe"] << endl;
由于我们拿到的是value的引用，我们也可以把它作为一个值赋值给别人或者输出

可以看到，operator[]的功能非常丰富，整体来说还是一个很好用的重载。

multimap

原本的map同一个key只能存在一个value，而multimap则可以存在多个key相同的节点，不过多赘述了。

C++：STL - set & map

关联式容器

pair

set

模板参数

typedef的类型

构造函数

迭代器

常规接口

特殊接口

multiset

map

模板参数

typedef的类型

常规接口

特殊接口

multimap

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

C++：STL - set & map

关联式容器

pair

set

模板参数

typedef的类型

构造函数

迭代器

常规接口

特殊接口

multiset

map

模板参数

typedef的类型

常规接口

特殊接口

multimap

热门文章

最新文章

相关课程

相关电子书