网站导航
> 技术文档 > C++11STL容器map和set简单介绍

C++11STL容器map和set简单介绍

网友: 技术文档 2025-07-26 20:25:12

一、引言

        map和set底层结构比较复杂，我认为我们先谈基本介绍再谈C++11，最后再谈map和set底层以及map和set封装。

二、简单介绍一下map和set

        map和set底层都是红黑树，是二叉搜索树的一种，查找非常快。不像数组、链表一样一个一个对比，可以理解为创建一个非常适合使用二分查找的结构，每次查找都可以排除掉上一次排除元素的一半。

        下面小编来介绍一个非常有意思的二叉树结构——二叉搜索树

小讲、map和set的底层红黑树的祖先——二叉搜索树

        二叉搜索树其实很简单，就是确定一个顺序，那一边(左边还是右边)大于根结点(我们将一棵子树的顶点称为根结点，任意一棵子树(只有一个点也可以被称为子树，子树是一个小单元，不是一个数量单位。)都有它的根结点)。那我们可以假设右子树(子树的右子树)的所有结点都大于子树的根节点。那左子树的结点肯定小于根结点。那我们以此作图就是这样。红黑树呢，也只是增加了几条规则保证二叉搜索树的平衡，改变根结点使二叉树像天平，这样就可以每次查找到下一层就可以排除掉一半的结点。

        2.1        map和set各自具有的特点。

                首先还是说说使用map和set所要包含的头文件时

、头文件。

                先来说说map，这个主要是用来做映射的，映射大家可以想到什么？对应关系，例如说函数x带入到表达式中求出y的值(x,y)用坐标x通过数学图像可以指向坐标y点，通过给一个人或者一个事物取外号从而起到指代某个东西某个人，翻译过程中通过一个单词翻译出中文含义。这些都是映射。简单来说就是通过一个东西指代另一个东西。但是它不允许重复数据插入。

                set就更好说了，set并没有映射功能，所以它就是一个普通的红黑树，可以把它看成一个集合，它不允许有相同的数据插入，至于要看是否插入进去那要看插入时的返回值了，返回值为一个结构体，可以根据结构体来判断是否插入成功。

        2.2        map和set如何插入数据

                set插入很简单。考虑到map插入时，要交代映射关系就有点复杂了。我们先来说说map的插入吧。

#include #include #include int main(){// map显示化模版传递类型std::map dic;// 判断是否插入成功std::pair<std::map::iterator, bool> is_insert;// 插入数据// map中存在一个pair类型// 需要make_pair转化。// 为什么不像函数一样让编译器自己推导出类型呢？// 因为推出来的类型可能和map中显示传递的类型出现偏差。// 一般这种对返回值类型有精密要求都会要求模版显示化传递。is_insert = dic.insert(std::make_pair(\"apple\",\"苹果\"));std::cout << is_insert.second << std::endl;is_insert = dic.insert(std::make_pair(\"funny\", \"滑稽\"));std::cout << is_insert.second << std::endl;is_insert = dic.insert(std::make_pair(\"food\", \"食物\"));std::cout << is_insert.second << std::endl;// 打印出map中存储的数据。std::map::iterator it = dic.begin();while (it != dic.end()){std::cout <first << \":\" <second << std::endl;++it;}return 0;}

                set插入直接将数据往insert上甩就行了。

#include #include int main(){std::set gather;std::pair<std::set::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::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 #include int main(){std::set gather;std::pair<std::set::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::iterator it = gather.find(3); // 判断是否存在，存在则打印，不存在不打印。 if(it != gather.end()) { std::cout << it << std::endl; }return 0;}
#include #include #include int main(){std::map dic;std::pair<std::map::iterator, bool> is_insert;is_insert = dic.insert(std::make_pair(\"apple\",\"苹果\"));std::cout << is_insert.second << std::endl;is_insert = dic.insert(std::make_pair(\"funny\", \"滑稽\"));std::cout << is_insert.second << std::endl;is_insert = dic.insert(std::make_pair(\"food\", \"食物\"));std::cout << is_insert.second << std::endl;// 查找map中的数据。std::map::iterator it = dic.find(\"apple\"); if(it != dic.end()) { std::cout <first << \":\" <second << std::endl; }return 0;}

        2.5        map中的count()函数和operator [] （模版）重载

                虽然find()函数很方便。但是我们很少用它，因为使用operator[]可以返回它的迭代器而且不管写起来，用起来，还是看起来都很方便、简洁。而且find()函数因为不知道里面有没有该函数还要写一老长串的判断是否等于end()。非常不方便！

                所以我们用count()和operator[]的结合。从count英文单词来看，是数数的意思，返回的是查找元素的个数，为零肯定就不存在。自然可以用operator[]访问(如果访问不存在的数据的话会报错。)。

                set虽然也有count，但是并没有operator[]的改值运算符重载，如果改值，意味着要删除重新插入。

#include #include #include int main(){std::map dic;std::pair<std::map::iterator, bool> is_insert;is_insert = dic.insert(std::make_pair(\"apple\",\"苹果\"));std::cout << is_insert.second << std::endl;is_insert = dic.insert(std::make_pair(\"funny\", \"滑稽\"));std::cout << is_insert.second << std::endl;is_insert = dic.insert(std::make_pair(\"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 #include int main(){ std::set myset; std::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); // ^ itup = myset.upper_bound(60);  //  ^ // 删除一段区间，从A位置删除到B位置。 myset.erase(itlow, itup);  // 10 20 70 80 90 // 打印set中存储的值。 std::cout << \"myset contains:\"; for (std::set::iterator it = myset.begin(); it != myset.end(); ++it) std::cout << \' \' << *it; std::cout << \'\\n\'; return 0;}
网络标签：

相关问题