C++：STL - set & map

关联式容器

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

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

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

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

由于在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]了。

1. 由于我们要遍历[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的类型

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

常规接口

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

特殊接口

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[ ]的功能：

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

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

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

multimap

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