​
关联式容器
在介绍set、map、multiset、multimap之前我们先了解什么是关联式容器，

C++STL包含了序列式容器和关联式容器：

序列式容器：序列容器以线性序列的方式存储元素。它没有对元素进行排序，元素的顺序和存储它们的顺序相同。一般来说，有 5 种标准的序列容器，每种容器都具有不同的特性。

array (数组容器) ：是一个长度固定的序列，有N个T类型的对象，不能增加或删除元素。
vector (向量容器) ：
是一个长度可变的序列，用来存放T类型的对象。必要时，可以自动增加容量，但只能在序列的末尾高效地增加或删除元素。
deque (双向队列容器) ：
是一个长度可变的、可以自动增长的序列，在序列的两端都不能高效地增加或删除元素。
list (链表容器) ：
是一个长度可变的、由 T 类型对象组成的序列，它以双向链表的形式组织元素，在这个序列的任何地方都可以高效地增加或删除元素。访问容器中任意元素的速度要比前三种容器慢，这是因为
list 必须从第一个元素或最后一个元素开始访问，需要沿着链表移动，直到到达想要的元素。
forward list (正向链表容器) ：是一个长度可变的、由 T 类型对象组成的序列，它以单链表的形式组织元素，是一类比链表容器快、更节省内存的容器，但是它内部的元素只能从第一个元素开始访问。

关联式容器： 里面存储的是结构的键值对，在数据检索时比序列式容器效率更高。比如：set、map、unordered_set、unordered_map等。

关联式容器存储的元素，都是一个一个的“键值对”（ ），这是和序列式容器最大的不同。除此之外，序列式容器中存储的元素默认都是未经过排序的，而使用关联式容器存储的元素，默认会根据各元素的键值的大小做升序排序。

下面开始这篇的讲解set、map、multiset、multimap。

如果查阅相关资料可以得知，set、map、multiset、multimap的底层是用红黑树来实现的，关于红黑树是什么，后面会单独写一篇文章进行详细讲解，在这里只需要其底层是红黑树即可（红黑树是比二叉搜索树更有的树）。

键值对

比如说我们去买菜，每种菜都对应着不同的单价，这就是一一对应关系，可以通过其菜名知道其多少钱一斤。

在SGI-STL中关于键值对的定义如下：

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

set
set的介绍

set的构造函数与其定义
这里就不给官方的函数声明截图了，直接展示使用案例

bool fncomp(int lhs, int rhs)
{
return lhs < rhs;
}
struct classcomp
{
bool operator() (const int& lhs, const int& rhs) const
{
return lhs < rhs;
}
};
int main()
{
set first; // 最基本的定义，其里面为空
int myints[] = { 10,20,30,40,50 };
set second(myints, myints + 5); // 利用数组定义

set<int> third(second);                  // 拷贝构造

set<int> fourth(second.begin(), second.end());  // 使用迭代器构造

set<int, classcomp> fifth;                 // 使用仿函数定义set是升序还是降序
                                           // 小于是升序，大于是降序
bool(*fn_pt)(int, int) = fncomp;
set<int, bool(*)(int, int)> sixth(fn_pt);  // 利用函数指针的方式定义是升序还是降序

return 0;

}

set的常用的成员函数
set当中常用的成员函数如下：

成员函数 功能
insert 插入指定元素
erase 删除指定元素
find 查找指定元素//返回的是迭代器，没有找到返回end（）
size 获取容器中元素的个数
empty 判断容器是否为空//是空返回真
clear 清空容器
swap 交换两个容器中的数据
count 获取容器中指定元素值的元素个数
erase

最常用的也就是第二种，第一种的传参可以传find的返回值。第三种是删除某个特定的区间，但着个通常还是与别的函数一起使用。比如下面这三个函数

lower_bound
upper_bound
equal_range
然而set函数还有几个成员函数是我们没有见过的几个函数

因为set是有序的，所以这三个函数就达到了返回大于/小于/等于某个值的部分；

就比如一个set函数内存储着 1，2，6，8，9，11；

如果想返回比6小的部分，就可以用 lower_bound，解释起来很简单，但是里面还是有很多的细节的，下面用代码来解释细节部分。

首先前两个函数的返回值为迭代器。其使用大多是与erase同用

int main()
{
set myset;
set::iterator itlow, itup;

for (int i = 1; i < 10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90


//itlow = myset.lower_bound(30);              //
itlow = myset.lower_bound(25);                // >= val值位置的iterator 30
itup = myset.upper_bound(70);                 // >  val值位置的iterator 80

// 删除区间：[30,80)
myset.erase(itlow, itup);                     // 10 20 80 90

for (auto e : myset)
{
    cout << e << " ";
}
cout << endl;


//运行结果：
//10 20 80 90
return 0;

}

第三个成员函数的返回值略有不同

pair的first与second所接收的是两个不同的迭代器，但也有可能相同

first接收>=val的迭代器
second接收>val的迭代器
int main()
{
set myset;
set::iterator itlow, itup;

for (int i = 1; i <= 5; i++) myset.insert(i * 10);   // myset: 10 20 30 40 50


auto ret = myset.equal_range(35);

cout << "the lower bound points to: " << *ret.first << '\n';   // >= val
cout << "the upper bound points to: " << *ret.second << '\n';  // > val

//运行结果：
//  the lower bound points to : 40
//    the upper bound points to : 40
return 0;

}

multiset
multiset容器与set容器的底层实现一样，都是红黑树，其次，multiset容器和set容器所提供的成员函数的接口都是基本一致的，但set是有序，并且没有重复的，那么与之对应的就是multiset无序，并且有重复的。用官方的话来说就是multiset允许键值冗余，即multiset容器当中存储的元素是可以重复的。

用法与set几乎完全相同，这里不在举例说明。

但还是有很多细节要注意的，就比如说因为multiset是无序存在重复元素的，那么find如果要查找重复的元素找到了要返回哪一个呢？

因此两个容器中成员函数find和count的意义也有所不同：

find
成员函数find 功能
set对象 返回值为val的元素的迭代器
multiset对象 返回底层搜索树中序的第一个值为val的元素的迭代器
count
成员函数count 功能
set对象 值为val的元素存在则返回1，不存在则返回0（find成员函数可代替）
multiset对象 返回值为val的元素个数（find成员函数不可代替）
erase

对于第二个同样的erase也会删除多个，然后返回值删除的个数。

count同样是如此，找在不在，并且返回再次对象中有几个这样的值

map
map的介绍
底层同样是用红黑树来写的。

set的构造函数与其定义
这里就不给官方的函数声明截图了，直接展示使用案例

bool fncomp(char lhs, char rhs) { return lhs < rhs; }

struct classcomp {
bool operator() (const char& lhs, const char& rhs) const
{
return lhs < rhs;
}
};

int main()
{
map first;// 空，也是最简单的定义

first['a'] = 10;
first['b'] = 30;
first['c'] = 50;
first['d'] = 70;

map<char, int> second(first.begin(), first.end());// 用迭代器，使用一个区间定义

map<char, int> third(second); // 拷贝构造定义

map<char, int, classcomp> fourth;                  // 使用仿函数定义set是升序还是降序
                                                   // 小于是升序，大于是降序

bool(*fn_pt)(char, char) = fncomp;
map<char, int, bool(*)(char, char)> fifth(fn_pt); // 利用函数指针的方式定义是升序还是降序

return 0;

}

以下的知识在set中同样适用，只需要进行转化为set的特点即可。

insert

返回值
用的最多的也就是这个了。其返回值的pair是返回的迭代器，其产生的效果与set相似，如果插入成功就返回这个位置的迭代器，反之如果这个数已经存在，那么也是返回这个数位置的迭代器。

pair的second为一个bool类型。插入成功返回true，失败为false。

参数列表（map）
insert函数的参数显示是value_type类型的，实际上value_type就是pair类型的别名：

typedef pair value_type;

因此，我们向map容器插入元素时，需要用key和value构造一个pair对象，然后再将pair对象作为参数传入insert函数。

方式一： 构造匿名对象插入。

int main()
{
map m;

m.insert(pair<int, string>(2, "two"));
m.insert(pair<int, string>(1, "one"));
m.insert(pair<int, string>(3, "three"));
for (auto e : m)
{
    cout << "<" << e.first << "," << e.second << ">" << " ";
}
cout << endl; //<1,one> <2,two> <3,three>
return 0;

}

但是这种方式会使得我们的代码变得很长，尤其是没有直接展开命名空间的情况下，因此我们最常用的是方式二。

方式二： 调用make_pair函数模板插入。
在库当中提供以下make_pair函数模板

template
pair make_pair(T1 x, T2 y)
{
return (pair(x, y));
}
我们只需向make_pair函数传入key和value，该函数模板会根据传入参数类型进行自动隐式推导，最终构造并返回一个对应的pair对象。

int main()
{
map m;
//方式二：调用函数模板make_pair，构造对象插入
m.insert(make_pair(2, "two"));
m.insert(make_pair(1, "one"));
m.insert(make_pair(3, "three"));
for (auto e : m)
{
cout << "<" << e.first << "," << e.second << ">" << " ";
}
cout << endl; //<1,one> <2,two> <3,three>
return 0;
}

find

返回值
查找函数是根据所给key值在其中当中进行查找，若找到了，则返回对应元素的迭代器，若未找到，则返回容器中最后一个元素下一个位置的正向迭代器，即也就是end（）。

int main()
{
map m;
m.insert(make_pair(2, "two"));
m.insert(make_pair(1, "one"));
m.insert(make_pair(3, "three"));
//获取key值为2的元素的迭代器
map::iterator pos = m.find(2);
if (pos != m.end())
{
cout << pos->second << endl; //two
}
return 0;
}

erase

用的最多的也就是第二个，这个返回值没有什么特的，返回值为实际删除的元素个数。

int main()
{
map m;

m.insert(make_pair(2, "two"));
m.insert(make_pair(1, "one"));
m.insert(make_pair(3, "three"));

auto it = m.begin();
m.erase(it); // 删除了  2, "two"

m.erase(1); // 删除了   1, "one"
//   返回值为1

m.erase(m.begin(), m.end());// 删除了   3, "three"
return 0;

}

map的[ ]运算符重载
这个成员函数也是map与set与众不同的一点，set中没有这个函数，其的功能特别的强大。

其在官方中的函数原型如下：

mapped_type& operator[] (const key_type& k);
[ ]运算符重载函数的参数就是一个key值，而这个函数的返回值如下：

(*((this->insert(make_pair(k, mapped_type()))).first)).second
就这样看着不太好理解，我们整理一下，实际上[ ]运算符重载实现的逻辑实际上就是以下三个步骤：

调用insert函数插入键值对。
拿出从insert函数获取到的迭代器。
返回该迭代器位置元素的值value。
对应分解代码如下：

mapped_type& operator[] (const key_type& k)
{
//1、调用insert函数插入键值对
pair ret = insert(make_pair(k, mapped_type()));
//2、拿出从insert函数获取到的迭代器
iterator it = ret.first;
//3、返回该迭代器位置元素的值value
return it->second;
}

那么这个函数的价值体现在哪里呢？我们来看看下面这段代码：

统计出现次数：

int main()
{
string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
map ht;
for (auto& e : arr)
{
ht[e]++;
}

for (auto& kv : ht)
{
    cout << kv.first << ":" << kv.second << endl;
}
cout << endl;

//打印结果：
//苹果 : 6
//甜瓜 : 1
//西瓜 : 3
//香蕉 : 3
return 0;

}

说明一下：

如果k不在map中，则先插入键值对，然后返回该键值对中V对象的引用。其中的v()是默认构造，比如说如果v为int类型，那么就会默认构造为0，char为’0‘，指针为nullptr.
如果k已经在map中，则返回键值为k的元素对应的V对象的引用。注意是引用！！！
同样还可以修改其中的value：

int main()
{
string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
map ht;
for (auto& e : arr)
{
ht[e]++;
}

for (auto& kv : ht)
{
    cout << kv.first << ":" << kv.second << endl;
}
cout << endl;

//打印结果：
//苹果 : 6
//甜瓜 : 1
//西瓜 : 3
//香蕉 : 3

ht["苹果"] = 100;

//打印结果：
//苹果 : 100
//甜瓜 : 1
//西瓜 : 3
//香蕉 : 3
return 0;

}

迭代器
迭代器的遍历其实是比较麻烦的，因为set，map的底层使用红黑树来写的，不是简单的进行++/--就可以了，走起来还是不叫麻烦的，这里就不说了，会在红黑树中解释。迭代器使用起来还是没难度的，也不举例了。

再次提醒： 编译器在编译时会自动将范围for替换为迭代器的形式，因此支持了迭代器实际上就支持了范围for。

map的其他成员函数
成员函数 功能
size 获取容器中元素的个数
empty 判断容器是否为空
clear 清空容器
swap 交换两个容器中的数据
count 获取容器中指定key值的元素个数

include

include

include

using namespace std;

int main()
{
map m;
m.insert(make_pair(2, "two"));
m.insert(make_pair(1, "one"));
m.insert(make_pair(3, "three"));
//获取容器中元素的个数
cout << m.size() << endl; //3
//容器中key值为2的元素个数
cout << m.count(2) << endl; //1
//清空容器
m.clear();
//容器判空
cout << m.empty() << endl; //1
//交换两个容器中的数据
map tmp;
m.swap(tmp);
return 0;
}

multimap
multimap容器与map容器的底层实现一样，也都是平衡搜索树（红黑树），其次，multimap容器和map容器所提供的成员函数的接口都是基本一致的，这里也就不再列举了，multimap容器和map容器的区别与multiset容器和set容器的区别一样，multimap允许键值冗余，即multimap容器当中存储的元素是可以重复的。

同样其因为允许存在重复的K，所以erase还是与set的操作是相似的，不在说明，有问题可以看set部分，也可以评论，看见必解释。

由于multimap容器允许键值冗余，因此两个容器中成员函数find和count的意义也有所不同：

成员函数find 功能
map对象 返回值为键值为key的元素的迭代器
multimap对象 返回底层搜索树中序的第一个键值为key的元素的迭代器
成员函数count 功能
map对象 键值为key的元素存在则返回1，不存在则返回0（find成员函数可代替）
multimap对象 返回键值为key的元素个数（find成员函数不可代替）

​