map，set是一种什么样的数据结构？【c++吧】_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：293,462贴子：
map，set是一种什么样的数据结构？收藏
primer压根儿没说
c++培训课程,美国上市公司&达内&出品c++课程,15年教学经验,总监级c++讲师亲授!!达内首创&先就业后付款&模式.名企项目总监授课,成就&稀缺级&c/c++软件工程师
貌似标准没说 一般实现是二叉树``
标准没有规定必须是什么结构。一般是红黑树（一种比较高级的二叉查找树）
我知道是模版，就是想问元素之间的联系方式是什么样的？
Map 是有 key 和 value 组成...其中 value 是按照 key 的序关系存放在平衡二叉树中...Set 中 key 和 value 是一样的... 按照 key 的序关系存放在平衡二叉树中..
set也是红黑树吗？
你去看STL的源码就会发现有这句.typedef rb_tree&K , T , indefity(T) , Comp&Map 和 Set 都有...
感觉跟表一样
不就是哈希表嘛？搞得这么复杂
c++多少钱?万和专注it教育24年,优秀的师资团队,雄厚的教学环境,赢得数万学子的好评,万和24年不开分支机构,只为专注教学品质,传承万和不朽品牌!
谁告诉你的std里unordered_set和unordered_map才算hash容器。
哈希?? 哈希表是 HashTable ... 而且哈希查询是O(1)...哪天Map效率搞成O(1)了..我重返OI..
给个确定答案啊，我现在看stl源码还有点难度
6楼不就给了么? 至于你信不信是你的事情了
不见得要是平衡二叉树。
STL 里是红黑树..JAVA里就不知道了..好吧..我理解了..帝球会说红黑树不是平衡二叉树..其实我理解的平衡二叉树就是基本操作最坏时间都是O(logN)的树...
平衡树是不是一定是排序树子集？
其实我会认为SBT/Treap/SplayTree/Skiplist之类的都算。。
SBT在我心里是凌驾所有其他平衡树之上的... 功能太过于强大.....
我觉得也就比AVL多一个原生rank的功能。。话说现在有非递归的SBT了吗？
除了Splay以外功能应该差不多吧。。。还是RBT比较快。。。
红黑树是一种很有意思的平衡检索树。它的统计性能要好于平衡二叉树(有些书籍根
红黑树据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树)，因此，红黑树在很多地方都有应用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。
原生 Rank 多省空间啊...我瞬间就高潮了
红黑树什么时候又被称为AVL树了
MR小神犇以前有给过一个支持rank的SplayTree，单看空间效率的话也不错。。
红黑树是平衡二叉树。ISO C++只限定复杂度之类的特性，不限制具体实现应该使用什么数据结构。理论上的例子如B树。它不是平衡二叉树。skip list如果不是最坏情况下不符合要求的话也可以用来实现关联容器。
不能是平摊/随机化的最坏复杂度么？
requirement里面注明amortized的不多，剩下的应该不可以了。
登录百度帐号推荐应用【图片】STL中的set和map到底有什么区别？除了set没有键值之外【c++吧】_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：293,462贴子：
STL中的set和map到底有什么区别？除了set没有键值之外收藏
c++培训课程,美国上市公司&达内&出品c++课程,15年教学经验,总监级c++讲师亲授!!达内首创&先就业后付款&模式.名企项目总监授课,成就&稀缺级&c/c++软件工程师
开始我以为set是用数组实现的红黑树，但是看了哈西set后发现并不是。
再还有multiset，如果说它是有键值的set，那它又与map有什么区别？
在STL源码剖析中详细的说明了他们的实现，然而我看不懂…
开点人啊～
还是不能完全理解啊～
这个文章里说都是用红黑树实现的
楼主，你发的图片是那本书的啊？
看两行代码你就知道了
c++多少钱?万和专注it教育24年,优秀的师资团队,雄厚的教学环境,赢得数万学子的好评,万和24年不开分支机构,只为专注教学品质,传承万和不朽品牌!
其实只要简单的单旋甚至双旋的平衡一下就好，为什么非得要用红黑树？
登录百度帐号推荐应用浅析stl序列容器(map和set)的仿函数排序_C 语言
作者：用户
本文讲的是浅析stl序列容器(map和set)的仿函数排序_C 语言，
问题：set是一个自动有序的集合容器，这是set的一个最实惠的性质，从小到大，只要你插入进去，就有序了。但是，如果你不想要这个顺序呢，是不是可以人为控制set容器的元素顺序呢？答案是，可以的，因为stl也是程序员设计的。
首先看stl的模
问题：set是一个自动有序的集合容器，这是set的一个最实惠的性质，从小到大，只要你插入进去，就有序了。但是，如果你不想要这个顺序呢，是不是可以人为控制set容器的元素顺序呢？答案是，可以的，因为stl也是程序员设计的。
首先看stl的模板构造函数
复制代码 代码如下:
explicit set ( const Compare& comp = Compare(), const Allocator& = Allocator() );templateset ( InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() );set ( const set& x );
我们完全可以重定义set的构造函数里的比较函数，完成对set的自排序功能。
复制代码 代码如下:
bool fncomp (int lhs, int rhs) {return lhsstruct classcomp {bool operator() (const int& lhs, const int& rhs) const{return lhs&} // 控制set逆序};
void testset(){// 第一种使用方法bool(*fn_pt)(int,int) =set sixth (fn_pt);// 第二中使用方法
// class as Compares.insert(4);s.insert(5);set::for(it=s.begin();it!=s.end();it++){cout&&*it&&" ";}cout &&};
注意：如果set元素是一个结构体，你最好要设置你的仿函数，不然set一般默认是按第一个字段排序的，而我们的实际情况是想按序号i排序：
复制代码 代码如下:
struct ST_Message{public:ST_Message(int seq, int64_t time, string strfrom, string strto, string strinfo){this-&seq=this-&time=this-&strfrom=this-&strto=this-&strinfo=}
bool operator &(const ST_Message& other) const // 注意是const函数{if (seq != other.seq) // dtime按升序排序{return (seq & other.seq);}else if(time & other.time){return (time & other.time);}else if(strcmp(strfrom.c_str(), other.strfrom.c_str()) != 0){return (strcmp(strfrom.c_str(), other.strfrom.c_str()) & 0);}else if(strcmp(strto.c_str(), other.strto.c_str()) != 0){return (strcmp(strto.c_str(), other.strto.c_str()) & 0);}else{return (strcmp(strinfo.c_str(), other.strinfo.c_str()) & 0);}}};
stl中自动有序的容器map也和set有相同的应用，如果你想快速理解，那么把这篇中的set改成map就差不多了。总之，有序的stl容器在工程中应用什么方便和广泛，但是当我们需要自己的排序的时候，可以用仿函数来设置它!
以上是云栖社区小编为您精心准备的的内容，在云栖社区的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索stl
stl 容器、stl 排序、stl map 排序、stl vector 排序、stl list 排序，以便于您获取更多的相关知识。
稳定可靠、可弹性伸缩的在线数据库服务，全球最受欢迎的开源数据库之一
6款热门基础云产品6个月免费体验；2款产品1年体验;1款产品2年体验
弹性可伸缩的计算服务，助您降低 IT 成本，提升运维效率
开发者常用软件，超百款实用软件一站式提供
云栖社区()为您免费提供相关信息，包括
，所有相关内容均不代表云栖社区的意见！关于STL中的map容器的一些总结
字体：[ ] 类型：转载 时间：
对于map的学习，或者说是对STL中的容器的学习，要知道每种容器的实现原理，每种适合适合解决什么问题的，才是关键
一、关于map的介绍
map是STL的一个容器，和set一样，map也是一种关联式容器。它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，有助于我们处理一对一数据。这里说下map内部数据的组织，map内部是自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。学习map我们一定要理解什么是一对一的数据映射？比如：一个班级中，每个学生的学号跟他的姓名就存在着一一映射的关系，这个模型用map可能轻易描述，很明显学号用int 描述，姓名用字符串描述采用的string，于是我们使用的map形式如下：map&int , string&
这里说一下map和set容器的区别。
对于map中的每个节点存储的是一对信息，包括一个键和一个值，各个节点之间的键值不能重复。
对于set中的每个节点存储的是一个信息，只有一个键，但是每个键值也是唯一的。set表示的是集合的概念。
对于map的学习，或者说是对STL中的容器的学习，要知道每种容器的实现原理，每种适合适合解决什么问题的，才是关键~~~~
二、map中常用的操作
2.1 map中的构造函数 代码如下:map(); // 默认构造函数
map(const map& m) // 拷贝构造函数
map(iterator begin, iterator end ); //区间构造函数
map(iterator begin, iterator end, const traits& _compare) //带比较谓词的构造函数
map(iterator begin, iterator end, const traits& _compare, const allocator& all) //带分配器经过分析我们发现，map的构造函数主要是调用“拷贝构造函数”和利用“迭代器”进行初始化两种方式。我想原因是很简单的，因为，map中每个节点由一对值构成。这里还用写一个程序演示一下map的构造函数吗？
2.2 map中的一些基础函数begin，end，rbegin，rend，empty，clear，size，max_size。八个常用的函数，看到名字应该就知道怎么用了吧，看看代码： 代码如下:#pragma warning (disable:4786)
#include &map&#include &string&#include &iostream&
int main(){&&& map&int,string& studentM&&& map&int,string&::&&& studentMessage.insert(pair&int , string&(,"Mike"));&&& studentMessage.insert(pair&int , string&(,"Sam"));&&& studentMessage.insert(pair&int , string&(,"Jake"));&&& //begin获取map中的第一个元素的迭代器,并且等于rend&&& //end获取map中的最后一个元素下一位置的迭代器，并且等于rbegin&&& cout&&"迭代器中的元素如下："&&&&& for(iter = studentMessage.begin() ; iter != studentMessage.end() ; ++iter)&&& {&&&&&&& cout&&iter-&first&&" "&&iter-&second&&&&& }&&& //看看max_size和size的值得意义&&& cout&&"map 的 max_size 的值："&&studentMessage.max_size()&&&&& cout&&"map 的 size 的值："&&studentMessage.size()&&&&& //看看empty和clear的使用&&& studentMessage.clear();&&& if(studentMessage.empty())&&& {&&&&&&& cout&&"The map is Empty !!"&&&&& }&&& else&&& {&&&&&&& cout&&"The map is not Empty !!"&&&&& }&&& return 0;}运行结果：
2.3 map中的的查找元素
map中用来查找的函数是find，但是能完成查找功能的函数却并不止这一个，比如count也是可以完成查找的，因为map中的键值是不允许重复的，所以一个键值只能出现一次，这说明count的返回值就只能是0或1了，那么显然这就能完成查找了，但是用count来完成查找并不是最优的选择，因为原来的本意是用count来完成计数的，这在vector等序列式容器中是灰常好用的，而map中之所以有这个count函数，就是为了STL提供统一的接口，这样说来map中的upper_bound和lower_bound，equel_range等函数组合起来也是可以完成查找功能的（想一想怎么实现）。这里有个疑问：count和find对于完成的效率是不是一致的呢？？
我们分别看看分别用find和count来完成查找： 代码如下:#pragma warning (disable:4786)
#include &iostream&#include &string&#include &map&
int main(){&&& map&int,string& studentM&&& studentMessage.insert(map&int,string&::value_type(,"Mike"));&&& studentMessage.insert(map&int,string&::value_type(,"Sam"));&&& studentMessage.insert(map&int,string&::value_type(,"Jake"));&&& if(studentMessage.find() != studentMessage.end())&&& {&&&&&&& cout&&"find success !!"&&&&& }&&& if(studentMessage.count())&&& {&&&&&&& cout&&"count success !!"&&&&& }&&& return 0;}运行结果：find success !!count success !!
看到了吗，count和find还是有区别的，那就是count只能单纯的查找元素是否存在，而find能定位要查找元素的位置。有一点需要注意的是查找的参数是键值哦！！
2.4 map中数据的插入和删除
无论是对于哪个容器，插入和删除都是非常重要的操作，先说一说map中数据的插入，数据的插入大概有三种方式，第一种：insert（pair&T1,T2,&(key1,value1)）。第二种：insert(map&T1,T2&::value_type(key1,value1)）,这种插入方式和第一种基本相似。第三种：利用数组进行插入，这个一会用程序演示吧。
关于数据的删除，大概有三种方式进行删除：第一种：erase（map&T1,T2&::iterator iter），删除迭代器所指的节点。第二种：erase（key k），根据键值进行删除，删除键值k所指的节点 。第三种：erase（map&T1,T2&::iteratormap iter1，&T1,T2&::iteratoriter2），删除iter1和iter2之间的数据。 代码如下:#pragma warning(disable:4786)
#include &iostream&#include &string&#include &map&
int main(){&&& /*&&& map&int,string&&&& map&int,string&::const_iterator iter1,iter2;&&& tmp.insert(pair&int,string&(,"Bob"));&&& tmp.insert(pair&int,string&(,"Ben"));&&& iter1 = tmp.begin();&&& iter2 = tmp.end();&&& */&&& map&int,string& studentM&&& map&int,string&::&&& //向map中插入数据&&& studentMessage.insert(pair&int,string&(,"Mike"));&&& studentMessage.insert(pair&int,string&(,"MIKE"));//重复插入&&& studentMessage.insert(map&int,string&::value_type(,"Sam"));&&& studentMessage.insert(map&int,string&::value_type(,"SAM"));//重复插入&&& studentMessage[] = "Jake";&&& studentMessage[] = "JAKE";//重复插入
&&& //为了测试删除，先插入两个数据,看插入结果主要看上面的插入方式&&& studentMessage[] = "Bob";&&& studentMessage[] = "Ben";
&&& cout&&"完成插入后map中的数据："&&&&& for(iter = studentMessage.begin() ; iter != studentMessage.end() ; ++iter)&&& {&&&&&&& cout&&iter-&first&&" "&&iter-&second&&&&& }
&&& //从map中删除数据&&& iter = studentMessage.begin();&&& studentMessage.erase(iter);&&& cout&&"利用迭代器删除map中第一个元素："&&&&& for(iter = studentMessage.begin() ; iter != studentMessage.end() ; ++iter)&&& {&&&&&&& cout&&iter-&first&&" "&&iter-&second&&&&& }&&& studentMessage.erase();&&& cout&&"利用键值删除map中的第一个元素："&&&&& for(iter = studentMessage.begin() ; iter != studentMessage.end() ; ++iter)&&& {&&&&&&& cout&&iter-&first&&" "&&iter-&second&&&&& }&&& studentMessage.erase(studentMessage.begin(),studentMessage.end());&&& cout&&"利用范围迭代器删除map中的所有数据："&&&&& for(iter = studentMessage.begin() ; iter != studentMessage.end() ; ++iter)&&& {&&&&&&& cout&&iter-&first&&" "&&iter-&second&&&&& }&&& return 0;}运行结果：
注意：通过观察输出结果，利用数组进行插入对数据进行了覆盖，而其他两种插入方式没有进行覆盖，实际上属于插入失败，还要注意的是，利用数组进行插入下标实际上是键值。
2.5 其他一些常用的函数或运算符
比如swap和key_comp函数，还有操作符：==，!=，&,&=,&,&=等，对于==运算符，只有两个map中所有的元素完全一致，才说两个map相等，而&,&=,&,&=起着决定作用的是两个map第一个不同的元素，这和string库中的strcmp相似。这些东西就不多说了。。
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具