一、引言
map和set底层结构比较复杂，我认为我们先谈基本介绍再谈C++11，最后再谈map和set底层以及map和set封装。
二、简单介绍一下map和set
map和set底层都是红黑树，是二叉搜索树的一种，查找非常快。不像数组、链表一样一个一个对比，可以理解为创建一个非常适合使用二分查找的结构，每次查找都可以排除掉上一次排除元素的一半。
下面小编来介绍一个非常有意思的二叉树结构——二叉搜索树
小讲、map和set的底层红黑树的祖先——二叉搜索树
二叉搜索树其实很简单，就是确定一个顺序，那一边(左边还是右边)大于根结点(我们将一棵子树的顶点称为根结点，任意一棵子树(只有一个点也可以被称为子树，子树是一个小单元，不是一个数量单位。)都有它的根结点)。那我们可以假设右子树(子树的右子树)的所有结点都大于子树的根节点。那左子树的结点肯定小于根结点。那我们以此作图就是这样。红黑树呢，也只是增加了几条规则保证二叉搜索树的平衡，改变根结点使二叉树像天平，这样就可以每次查找到下一层就可以排除掉一半的结点。
2.1 map和set各自具有的特点。
首先还是说说使用map和set所要包含的头文件时<map>、<set>头文件。
先来说说map，这个主要是用来做映射的，映射大家可以想到什么？对应关系，例如说函数x带入到表达式中求出y的值(x,y)用坐标x通过数学图像可以指向坐标y点，通过给一个人或者一个事物取外号从而起到指代某个东西某个人，翻译过程中通过一个单词翻译出中文含义。这些都是映射。简单来说就是通过一个东西指代另一个东西。但是它不允许重复数据插入。
set就更好说了，set并没有映射功能，所以它就是一个普通的红黑树，可以把它看成一个集合，它不允许有相同的数据插入，至于要看是否插入进去那要看插入时的返回值了，返回值为一个结构体，可以根据结构体来判断是否插入成功。
2.2 map和set如何插入数据
set插入很简单。考虑到map插入时，要交代映射关系就有点复杂了。我们先来说说map的插入吧。
#include <iostream>
#include <map>
#include <string>
int main()
{
// map显示化模版传递类型
std::map<std::string,std::string> dic;
// 判断是否插入成功
std::pair<std::map<std::string, std::string>::iterator, bool> is_insert;
// 插入数据
// map中存在一个pair<模版1,模版2>类型
// 需要make_pair<>转化。
// 为什么不像函数一样让编译器自己推导出类型呢？
// 因为推出来的类型可能和map中显示传递的类型出现偏差。
// 一般这种对返回值类型有精密要求都会要求模版显示化传递。
is_insert = dic.insert(std::make_pair<std::string,std::string>("apple","苹果"));
std::cout << is_insert.second << std::endl;
is_insert = dic.insert(std::make_pair<std::string, std::string>("funny", "滑稽"));
std::cout << is_insert.second << std::endl;
is_insert = dic.insert(std::make_pair<std::string, std::string>("food", "食物"));
std::cout << is_insert.second << std::endl;
// 打印出map中存储的数据。
std::map<std::string,std::string>::iterator it = dic.begin();
while (it != dic.end())
{
std::cout << it->first << ":" << it->second << std::endl;
++it;
}
return 0;
}set插入直接将数据往insert上甩就行了。
#include <iostream>
#include <set>
int main()
{
std::set<int> gather;
std::pair<std::set<int>::iterator, bool> is_insert;
is_insert = gather.insert(0);
is_insert = gather.insert(1);
is_insert = gather.insert(2);
is_insert = gather.insert(3);
std::set<int>::iterator it = gather.begin();
while (it != gather.end())
{
std::cout << *it << std::endl;
++it;
}
return 0;
}2.3 size()函数
毫无疑问这就是返回插入数据的个数，相信大家都能做好这里就不演示。
2.4 find函数
查找函数，set和map查找，都会得到一个迭代器。如果没找到迭代器就返回end()。值的一提的是map和set的迭代器都是双向迭代器(只能++或--)。
#include <iostream>
#include <set>
int main()
{
std::set<int> gather;
std::pair<std::set<int>::iterator, bool> is_insert;
is_insert = gather.insert(0);
is_insert = gather.insert(1);
is_insert = gather.insert(2);
is_insert = gather.insert(3);
// 查找元素
std::set<int>::iterator it = gather.find(3);
// 判断是否存在，存在则打印，不存在不打印。
if(it != gather.end())
{
std::cout << it << std::endl;
}
return 0;
}#include <iostream>
#include <map>
#include <string>
int main()
{
std::map<std::string,std::string> dic;
std::pair<std::map<std::string, std::string>::iterator, bool> is_insert;
is_insert = dic.insert(std::make_pair<std::string,std::string>("apple","苹果"));
std::cout << is_insert.second << std::endl;
is_insert = dic.insert(std::make_pair<std::string, std::string>("funny", "滑稽"));
std::cout << is_insert.second << std::endl;
is_insert = dic.insert(std::make_pair<std::string, std::string>("food", "食物"));
std::cout << is_insert.second << std::endl;
// 查找map中的数据。
std::map<std::string,std::string>::iterator it = dic.find("apple");
if(it != dic.end())
{
std::cout << it->first << ":" << it->second << std::endl;
}
return 0;
}2.5 map中的count()函数和operator [] （模版）重载
虽然find()函数很方便。但是我们很少用它，因为使用operator[]可以返回它的迭代器而且不管写起来，用起来，还是看起来都很方便、简洁。而且find()函数因为不知道里面有没有该函数还要写一老长串的判断是否等于end()。非常不方便！
所以我们用count()和operator[]的结合。从count英文单词来看，是数数的意思，返回的是查找元素的个数，为零肯定就不存在。自然可以用operator[]访问(如果访问不存在的数据的话会报错。)。
set虽然也有count，但是并没有operator[]的改值运算符重载，如果改值，意味着要删除重新插入。
#include <iostream>
#include <map>
#include <string>
int main()
{
std::map<std::string,std::string> dic;
std::pair<std::map<std::string, std::string>::iterator, bool> is_insert;
is_insert = dic.insert(std::make_pair<std::string,std::string>("apple","苹果"));
std::cout << is_insert.second << std::endl;
is_insert = dic.insert(std::make_pair<std::string, std::string>("funny", "滑稽"));
std::cout << is_insert.second << std::endl;
is_insert = dic.insert(std::make_pair<std::string, std::string>("food", "食物"));
std::cout << is_insert.second << std::endl;
// 查看是否存在值
if(dic.count("apple"))
{
// 其实返回的是映射也就是pair中的second。
std::cout << dic["apple"] << std::endl;
}
return 0;
}2.6 lower_bond和upper_bond函数
lower_bond返回的是大于等于该值的起始数据的迭代器。
upper_bond返回的是小于等于该值的起始数据的迭代器。
// set::lower_bound/upper_bound
#include <iostream>
#include <set>
int main()
{
std::set<int> myset;
std::set<int>::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); // ^
itup = myset.upper_bound(60); // ^
// 删除一段区间，从A位置删除到B位置。
myset.erase(itlow, itup); // 10 20 70 80 90
// 打印set中存储的值。
std::cout << "myset contains:";
for (std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}