C++ STL map和set的使用

序列式容器和关联式容器

想必大家已经接触过一些容器如：list，vector，deque，array，forward_list，string等，这些容器统称为系列容器。因为逻辑结构为线性的，两个位置的存储的值一般是没有固定关系的，比如交换一下并不会破坏它的结构特点。序列式容器一般是通过来顺序保存和访问的

关联式容器也是用来存储数据的，与序列式容器不同，关联式容器逻辑结构通常是非线性的，两个位置之间通常有紧密的联系，如果进行位置交换，那么就会破坏容器的结构。关联式容器中的元素一般是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。

本博客主要讲map和set系列容器的使用

map和set底层都是由红黑树来实现的，本质是一颗平衡二叉树，因此效率是极高的。

其中set是Key结构，map是Key-Value结构

pair类的介绍

在正式了解map、set前，我们要知道pair这个类型。

pair在关联式容器里面的使用是很频繁的，需要大家知道它是什么，这里直接给出它的底层代码：

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

我们可以看出，它就是一个结构体，存的两个数据。因为我们写代码的过程有很多数据有对应关系，因此pair的使用非常频繁。它可以免去我们自己构造一个相同类的麻烦。

make_pair(1, 2);
pair<int, int>(1, 2);

make_pair和下面的使用是一样的，但是make_pair可以推到出类型。下面的需要手动输入类型。

set的使用

首先set是一个存储K结构，存储的数据不能重复的容器。

下面是相关的函数

begin	返回正向迭代器的开头
end	返回正向迭代器的结尾
rbegin	返回反向迭代器的开头
rend	返回反向迭代器的结尾
cbegin	返回正向常迭代器的开头
cend	返回正向常迭代器的结尾
crbegin	返回反向常迭代器的开头
crend	返回反向常迭代器的结尾
empty	判断容器是否为空
size	返回容器的数据个数
max_size	返回容器存储的最大值，一般系统会检测计算机内存做出合理的返回值
insert	插入一个值
erase	删除一个值
swap	交换两个set的数据
clear	清除一个set容器的数据
emplace	插入一个数据，和insert的效果等效
key_comp	返回一个比较对象
value_comp	返回一个比较对象
find	对数据进行查找
count	查找某个值的数量
lower_bund	返回一个大于等于某个值的迭代器
upper_bound	返回一个大于某个值的迭代器
equal_range	返回大于等于某个值和大于某个值两个的迭代器

首先在了解上面的函数前，我们要了解set的构造函数、

构造函数

这里我只说一些常用的构造方式：

默认构造

	set<int>con;

这种方式构造出来的set容器为空。可以进行后续的插入

拷贝构造

set<int>con;
set<int>con_(con);
set<int>con__ = con;

用其他的set值来构造一个新的set

初始化生定向列表构造

set<int>con{ 1,2,3,4,5,6,34,2 };
set<int>con_({ 1,3,4,5,6 });
set<int>con__ = { 1234,325,2 };

这种构造输入十分方便

迭代器构造

vector<int>vec{ 1,2,34,5,2 };
set<int>(vec.begin(), vec.end());
int arr[] = { 1,2,3,4 };
set<int>(arr, arr + 3);

迭代器构造能够夸容器，进行数据的流通。

同时我们在构造的时候可以传函数指针或者仿函数来改变set的存储形式

bool compare(int x, int y) {return x > y;
}struct compare_ {bool operator()(const int&x,const int& y)const {return x > y;}
};
int main(){bool(*pare)(int, int) = compare;compare_ pare_;set<int, bool(*)(int, int)>con({ 2432423,21,23,4,5,345,34,5 },pare);set<int,compare_>con_({ 2432423,21,23,4,5,345,34,5 });set<int, greater<int>>con__({ 2432423,21,23,4,5,345,34,5 });for (auto& num : con)cout << num<<" ";cout << endl;for (auto& num : con_)cout << num<<" ";cout << endl;for (auto& num : con__)cout << num << " ";return 0;
}
//打印结果
//2432423 345 34 23 21 5 4
//2432423 345 34 23 21 5 4
//2432423 345 34 23 21 5 4

通过比较的改变将升序变为降序。

这几个构造基本上可以满足所有的构造需求了。

下面的构造是优化效率

右值引用构造

这个构造是将右值构造直接夺取其值来进行构造，减少拷贝，加快了构造的速度。

一般大家传常量值机会出发它的构造

	set<int>contain(set<int>{1, 3});

成员函数

下面开始看成员函数的使用

迭代器相关的函数

如果还不知道迭代器是什么或者迭代器还不会使用的，可以看看这篇博客：迭代器的使用

看完之后对于迭代器的几个函数应该是懂的，这里就不做过多的讲解了。

这里只提迭代器是怎么走的：

map和set支持的双向迭代器，但是随机迭代器，像vector那样支持随机访问。迭代器的顺序是走的底层搜索二叉树的中序遍历，所以map/set的迭代器往后走是一个顺序遍历。

size empty

这里size和empty函数也不做讲解，就是返回容器的数据量和判空。

max_size：

这个函数就是在我们插入比较多的数据时，我们要判断一下这些数据能否一下存的完。

int arr[10000] = { 123,21,321,3,12,3,21,4,3243,543,6,34,43,4124/*...........*/ };
int len = sizeof(arr) / sizeof(int);
set<int>con;
if (len < con.max_size()) {for (int x = 0; x < len; ++x)con.insert(arr[x]);
}
else {cout << "存不下" << endl;assert(false);
}

insert

insert虽然大家知道是干什么的，但是它的重载形式是有很多的，还有返回值是怎么返回的都需要知道

//1
pair<iterator,bool> insert (const value_type& val);
//2
pair<iterator,bool> insert (value_type&& val);
//3
iterator insert (const_iterator position, const value_type& val);
//4
iterator insert (const_iterator position, value_type&& val);
//5
template <class InputIterator>
void insert (InputIterator first, InputIterator last);	
//6
void insert (initializer_list<value_type> il);

第一个和第二个的输入我就不多说了，这里说一下它的返回值，上面我讲解了pair的使用，那么这里就返回了两个值，first是成功插入后的这个值的迭代器或者失败后已经有的值的迭代器，second是判断这个值是否插入成功。

例如：

set<int>con{ 1,2};
pair<set<int>::iterator, bool>p = con.insert(1);
if (p.second) {cout << "插入成功" << endl;
}
else cout << "插入失败";
//输出插入失败

第三个和第四个是在对应迭代器的后面插入一个值，返回这个插入的迭代器,如果set里面已经有了这个值，那么就会返回这个值的迭代器。

int arr[10000] = { 123,21,321,3,12,3,21,4,3243,543,6,34,43,4124/*...........*/ };
int len = sizeof(arr) / sizeof(int);
set<int>con{ 1,2};
set<int>::iterator it = con.insert(con.begin(), 2);
for (auto num:con)cout << num;
// 1 2

第四个就是插入一个迭代器区间的值，相当于进行了n次单个迭代器的插入。

第五个就是插入一段初始化设定项列表里面的数据。

第四个和第五个因为是多插入，不好返回各个插入情况的布尔值。所以是void。

erase

//(1)	
iterator  erase (const_iterator position);
//(2)	
size_type erase (const value_type& val);
//(3)	
iterator  erase (const_iterator first, const_iterator last);

对于用值来查找

就返回成功删除值的个数，这里因为值不能重复，因此只会返回0或1

对于用迭代器或则迭代器区间来删除，会返回这个值或者迭代器最后一次删除的值的下一个迭代器。区间迭代器删除时迭代器是左开右闭的，考虑删除begin()，end()区间就理解什么了。

那么就有这种写法：可以删除里面的偶数

set<int>con{ 1,2,3,4,5,6 };
for (auto it = con.begin(); it != con.end();) {if ((*it) % 2 == 0)it = con.erase(it);else ++it;
}
for (auto& num : con)cout << num << " ";
//1 3 5

我们不能一直it++，因为erase后it会直接跳到下一个值上。

swap

交换两个map的值

是否是以下面的代码交换的呢？

template<class K>
void swap(set<K>& x, set<K>& y) {set<K>temp = x;x = y;y = temp;
}

觉得是就错了，这种会有大量的拷贝，效率急转直下。

只要把里面的_root的指针交换一下就行了，数据就交换了。

clear

这个不多说，就是将数据清完

emplace

这个用到了右值引用移动构造，在插入右值的时候构造速度会快一些。效果和insert一样。

key_comp

会返回一个key_compare类型，它的效果类似于operator<重载，用的不多，看下面代码演示就行了

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

value_comp

从k的比较换成了value的比较,这里的value和key是相同的，因此这两个函数相同

find

查找一个值并返回它的迭代器

如果找不到就会返回end()迭代器。

count

查找某个值的个数，因为容器不允许重复数据，因此返回值只有0或者1。

lower_bound

返回第一个大于等于某个值的迭代器

因为set的去重性，最后要么返回等于这个值的迭代器，要么返回第一个大于这个值的迭代器。

upper_bound

返回第一个大于某个值的迭代器

这个比lower_bound稍微窄一点，当没有要查找的那个值时lower_bound的效果等于upper_bound效果。

例如要删除[10,60]的数据：

set<int>con{ 0,10,20,30,40,50,60,70};
con.erase(con.lower_bound(10), con.upper_bound(60));
for (auto num : con)cout << num << " ";
//0 70

equal_range

作用是找到等于某个值的区间，返回装有两个迭代器的pair类，范围是做开右闭。

那么就和上面的lower_bound和upper_bound差不多了，等价返回make_pair(lower_bound,upper_bound)。但是估计这个函数的效率更高，因为两次_bound都是从开始往后找，但是equal_range可以在lower_bound的基础上找upper_bound的迭代器。

multiset的使用

成员函数

multiset和set的差异就multiset支持冗余值。其它是一模一样的。那么我就只说函数里面不同的地方。

erase

删除的时候，会把所有等于它的值删除，并不是只删一个。

find

他是寻找中序的第一个目标值

count

因为有冗余值，因此范围可以是[0,max_size]

其它就是一样的，这里就不重复说了

map的使用

map就是K-V的结构，通过K来寻找，同时可以找到对应的映射值V。其中K是不能修改的，不然破坏了结构，V可以修改。

增删查改和set的不同

这里我不具体一个一个讲，只讲和set不同的点。不同点只有一个，插入删除都是直接作用pair整体，插入用pair，删除就删除K-V整体。

value_comp和key_comp

在set里面两个函数是一样的，这里稍微不一样，一个是比较value，一个是比较key。就这里不同

operator[]

这个是非常重要的修改接口，不仅仅支持修改，还支持插入数据和查找数据，所以他是一个多功能复合接口

我们来看它底层是怎么实现的，首先我们复习一下insert的插入方法

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[]

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

也可以用一行代码搞定

mapped_type& operator[] (const key_type& k){return (*con.insert(k).first).second;
}

它有一点要注意，就是访问过的一定会插入到列表，做查找的话要考虑是否要让它插入进来，否则就用count查找，或者find查找。

multimap和map的差异

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