一、引言

        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 90itlow = 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;
}