【STL】map和set的原理及其使用

关联容器

关联容器是c++中的一种数据结构，提供了一种通过键来访问值的方式。根据使用场景的不同，STL的关联容器有两种结构，树型结构和哈希结构。常见树形结构的关联容器有：map和set。map是一种键值对容器，里面存储的结构是<key，value>.set是一种集合容器，有序且唯一。常见的哈希结构的关联容器有unordered_map和unordered_set。

键值对

键值对用来表示具有一一对应关系的一种结构，该结构中包含两个成员变量key和value，key表示键值，value表示与key对应的值。我们常用的pair<key,value> 就是键值对。

下面观察STL源码中是如何定义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)
{}
};

所以pair其实就是一个类模板，根据<>里的两个参数来实例化类，第一个参数表示key，第二个表示value。

pair的两个成员变量first表示key，second表示value。

set

set的介绍

在c++文档中是这么定义set的：

1. set是按照一定次序存储元素的容器，其中class Compare控制比较逻辑，默认是小于。可以是一个仿函数，也可以是一个函数指针。
2. set中的key必须是唯一的。不能修改key但是可以删除或者插入一个key。
3. 在内部，set中的元素总是按照其内部比较对象（类型比较）所指定的特定严格强弱排序准则进行排序。
4. set访问元素的平均时间复杂度为O(logn).
5. set的底层是通过二叉搜索树（红黑树）来实现的

与map等容器不同，set存储的元素其实只有value，在底层是<value,value>.所以在插入元素时，只需要提供value即可，不需要构造键值对。使用set的迭代器进行遍历set时，会得到一个有序的序列。这是因为遍历的方式其实是二叉搜索树的中序遍历。

set的使用

set的模板参数列表有三个：

• T:元素类型
• Compare：用于控制set的比较逻辑，默认是小于

• Alloc:控制set的空间管理方式，使用STL提供的空间管理配置器.

set的构造

函数声明1：

explicit set (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());

构造一个空的set，里面没有元素

函数声明2：

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

根据提供的范围[InputIterator,InputIerator last)里的值来一一构造。

函数声明3：

set (const set& x);
• 1

拷贝构造，根据提供的一个set对象去构造一个一模一样的另一个set对象。

set的迭代器

begin和end

分别指向set第一个元素和最后一个元素的下一个位置。

rbegin和rend表示const修饰的begin和end。

rbegin和rend

方向迭代器，分别指向set最后一个元素的下一个位置和第一个元素的位置。

crbegin和crend表示被const修饰的 rbegin和rend。

注意，const迭代器并不是指迭代器本身不能被修改，而是指向的元素不能被修改。

set的容量

empty()

检测set中的元素是否为空，空返回true，否则false.

size（）

返回set中有效元素的个数

set的修改操作

下面讲一些比较常用的修改操作

insert

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

在set中插入元素x，实际上插入的是<x,x>构成的键值对，如果插入成功，返回一个迭代器和true构成的键值对。该迭代器指向插入set后的x。如果插入失败，说明x已经存在，返回一个迭代器和false构成的键值对。

erase

void erase ( iterator position )
void erase ( iterator first, iterator last )

1. 删除set中position位置上的元素。
2. 删除[first,last)这个区间的所有元素

clear

void clear ( ) 

清空set中的所有元素

find

iterator find ( const key_type& x ) const

返回指向元素x的迭代器

count

size_type count ( const key_type& x ) const

返回set中值为x的元素的个数.

map

map的介绍

map的文档介绍：

1. 键值对映射 ：map中的元素是一对键值对，每一个key都有一个value对应。
2. 自动排序：与set类似，mao中的元素在插入的同时会进行排序，默认情况下是key小的排在前面。
3. 唯一键：每个键在map中都是唯一的。
4. map查找的时间复杂度是O(logn).
5. 迭代器支持：支持使用迭代器来遍历map中的元素。本质上是搜索二叉树的中序遍历。
6. 底层是用二叉搜索树（红黑树）实现的。
7. 可以使用[key]访问对应的value

map和set的特性其实很像，只不过map中的元素更像是一个键值对。

map的构造

函数声明1

explicit map (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());

构造一个空的map对象，没有元素。

函数声明2

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

迭代器范围构造map，根据[first，last)范围内的元素一一构造出与其对应的map元素。

函数声明3

map (const map& x);

拷贝构造

map的迭代器

begin和end

begin:首元素的位置，end最后一个元素的下一个位置

cbegin和cend：与begin和end意义相同，但cbegin和cend所指向的元素不能修改

rbegin和rend

反向迭代器，rbegin在end位置，rend在begin位置，其++和–操作与begin和end操作移动相反

crbegin和crend：与rbegin和rend意义相同，但crbegin和crend所指向的元素不能修改

map的[]访问

当访问的key不存在，[key]操作会先将key插入到map中，返回默认的value.否则直接返回其value值。

map的修改操作

multiset

multiset的文档介绍：

multiset和set的区别就在于multiset可以存相同的元素。因此我们可以使用multiset对数组进行排序。

其内部结构和set都是一样的，都是用二叉搜索树（红黑树）实现的。

multimap

multimap的文档介绍：

multimap和map的区别就在于multimap可以存重复的key。此外，multimap不支持[key]操作

其内部结构和map都是一样的，都是用二叉搜索树（红黑树）实现的。