From: /zhongjiekangping/article/details/6934571
红黑树实现——STL中的map
[ -07-24 13:55:31 | 作者: dklkt ] 字号: 大 | 中 | 小[转载]STL中map实现技术来源：/Fandywang_jlu/archive//03/23/2208363.aspx
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由RudolfBayer发明的，他称之为"对称二叉B树"，它现代的名字是在LeoJ.Guibas和RobertSedgewick于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的:它可以在O(logn)时间内做查找，插入和删除，这里的n是树中元素的数目。
红黑树是一种很有意思的平衡检索树。它的统计性能要好于平衡二叉树(有些书籍根据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树)，因此，红黑树在很多地方都有应用。在C++STL中，很多部分(目前包括set,multiset,map,multimap)应用了红黑树的变体(SGISTL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。
背景和术语
红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。所有数据块都存储在节点中。这些节点中的某一个节点总是担当启始位置的功能，它不是任何节点的儿子；我们称之为根节点或根。它有最多两个"儿子"，都是它连接到的其他节点。所有这些儿子都可以有自己的儿子，以此类推。这样根节点就有了把它连接到在树中任何其他节点的路径。
如果一个节点没有儿子，我们称之为叶子节点，因为在直觉上它是在树的边缘上。子树是从特定节点可以延伸到的树的某一部分，其自身被当作一个树。在红黑树中，叶子被假定为null或空。
由于红黑树也是二叉查找树，它们当中每一个节点都的比较值都必须大于或等于在它的左子树中的所有节点，并且小于或等于在它的右子树中的所有节点。这确保红黑树运作时能够快速的在树中查找给定的值。
用途和好处
红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如即时应用(realtimeapplication)中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树。
红黑树在函数式编程中也特别有用，在这里它们是最常用的持久数据结构之一，它们用来构造关联数组和集合，在突变之后它们能保持为以前的版本。除了O(logn)的时间之外，红黑树的持久版本对每次插入或删除需要O(logn)的空间。
红黑树是2-3-4树的一种等同。换句话说，对于每个2-3-4树，都存在至少一个数据元素是同样次序的红黑树。在2-3-4树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得2-3-4树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍2-3-4树的原因，尽管2-3-4树在实践中不经常使用。
属性
红黑树是每个节点都有颜色特性的二叉查找树，颜色的值是红色或黑色之一。除了二叉查找树带有的一般要求，我们对任何有效的红黑树加以如下增补要求:
1.节点是红色或黑色。
2.根是黑色。
3.所有叶子（外部节点）都是黑色。
4.每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从每个叶子到根的所有路径都包含相同数目的黑色节点。
这些约束强制了红黑树的关键属性:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值都要求与树的高度成比例的最坏情况时间，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
要知道为什么这些特性确保了这个结果，注意到属性4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据属性5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。
在很多树数据结构的表示中，一个节点有可能只有一个儿子，而叶子节点包含数据。用这种范例表示红黑树是可能的，但是这会改变一些属性并使算法复杂。为此，本文中我们使用"nil叶子"或"空(null)叶子"，如上图所示，它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略，导致了这些树好像同上述原则相矛盾，而实际上不是这样。与此有关的结论是所有节点都有两个儿子，尽管其中的一个或两个可能是空叶子。
操作
在红黑树上只读操作不需要对用于二叉查找树的操作做出修改，因为它也二叉查找树。但是，在插入和删除之后，红黑属性可能变得违规。恢复红黑属性需要少量(O(logn))的颜色变更(这在实践中是非常快速的)并且不超过三次树旋转(对于插入是两次)。这允许插入和删除保持为O(logn)次，但是它导致了非常复杂的操作。
STL中的另一个类hashmap是通过使用hash表来构造map的
参考：/view/133754.htm
对于STL中的具体实现可以参考《STL源码剖析》
208页5.2RB-tree(红黑树)
237页5.4map
=========================================================
[转载]STLmap常用操作简介
来源：/TianFang/archive//12/30/607859.html
1。目录
map简介
map的功能
使用map
在map中插入元素
查找并获取map中的元素
从map中删除元素
2。map简介
map是一类关联式容器。它的特点是增加和删除节点对迭代器的影响很小，除了那个操作节点，对其他的节点都没有什么影响。对于迭代器来说，可以修改实值，而不能修改key。
3。map的功能
自动建立Key－value的对应。key和value可以是任意你需要的类型。
根据key值快速查找记录，查找的复杂度基本是Log(N)，如果有1000个记录，最多查找10次，1,000,000个记录，最多查找20次。
快速插入Key-Value记录。
快速删除记录
根据Key修改value记录。
遍历所有记录。
4。使用map
使用map得包含map类所在的头文件
#include<map>//注意，STL头文件没有扩展名.h
map对象是模板类，需要关键字和存储对象两个模板参数：
std:map<int,string>personnel;
这样就定义了一个用int作为索引,并拥有相关联的指向string的指针.
为了使用方便，可以对模板类进行一下类型定义，
typedefmap<int,CString>UDT_MAP_INT_CSTRING;
UDT_MAP_INT_CSTRINGenumMap;
5。在map中插入元素
改变map中的条目非常简单，因为map类已经对[]操作符进行了重载
enumMap[1]="One";
enumMap[2]="Two";
.....
这样非常直观，但存在一个性能的问题。插入2时,先在enumMap中查找主键为2的项，没发现，然后将一个新的对象插入enumMap，键是2，值是一个空字符串，插入完成后，将字符串赋为"Two";该方法会将每个值都赋为缺省值，然后再赋为显示的值，如果元素是类对象，则开销比较大。我们可以用以下方法来避免开销：
enumMap.insert(map<int,CString>::value_type(2,"Two"))
6。查找并获取map中的元素
下标操作符给出了获得一个值的最简单方法：
CStringtmp=enumMap[2];
但是,只有当map中有这个键的实例时才对，否则会自动插入一个实例，值为初始化值。
我们可以使用Find()和Count()方法来发现一个键是否存在。
查找map中是否包含某个关键字条目用find()方法，传入的参数是要查找的key，在这里需要提到的是begin()和end()两个成员，分别代表map对象中第一个条目和最后一个条目，这两个数据的类型是iterator.
intnFindKey=2;//要查找的Key
//定义一个条目变量(实际是指针)
UDT_MAP_INT_CSTRING::iteratorit=enumMap.find(nFindKey);
if(it==enumMap.end()){
//没找到
}
else{
//找到
}
通过map对象的方法获取的iterator数据类型是一个std::pair对象，包括两个数据iterator->first和iterator->second分别代表关键字和存储的数据
7。从map中删除元素
移除某个map中某个条目用erase()
该成员方法的定义如下
iteratorerase(iteratorit);//通过一个条目对象删除
iteratorerase(iteratorfirst,iteratorlast);//删除一个范围
size_typeerase(constKey&key);//通过关键字删除
clear()就相当于enumMap.erase(enumMap.begin(),enumMap.end());
=========================================================
[转载]STL中map用法详解
来源：/cpluspluslib/1231/3265.html
Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的，后边我们会见识到有序的好处。
下面举例说明什么是一对一的数据映射。比如一个班级中，每个学生的学号跟他的姓名就存在着一一映射的关系，这个模型用map可能轻易描述，很明显学号用int描述，姓名用字符串描述(本篇文章中不用char*来描述字符串，而是采用STL中string来描述),下面给出map描述代码：
Map<int,string>mapStudent;
1.map的构造函数
map共提供了6个构造函数，这块涉及到内存分配器这些东西，略过不表，在下面我们将接触到一些map的构造方法，这里要说下的就是，我们通常用如下方法构造一个map：
Map<int,string>mapStudent;
2.数据的插入
在构造map容器后，我们就可以往里面插入数据了。这里讲三种插入数据的方法：
第一种：用insert函数插入pair数据，下面举例说明(以下代码虽然是随手写的，应该可以在VC和GCC下编译通过，大家可以运行下看什么效果，在VC下请加入这条语句，屏蔽4786警告＃pragmawarning(disable:4786))
#include<map>
#include<string>
#include<iostream>
Usingnamespacestd;
Intmain()
{
Map<int,string>mapStudent;
mapStudent.insert(pair<int,string>(1,“student_one”));
mapStudent.insert(pair<int,string>(2,“student_two”));
mapStudent.insert(pair<int,string>(3,“student_three”));
map<int,string>::iteratoriter;
for(iter=mapStudent.begin();iter!=mapStudent.end();iter++)
{
Cout<<iter->first<<””<<iter->second<<end;
}
}
第二种：用insert函数插入value_type数据，下面举例说明
#include<map>
#include<string>
#include<iostream>
Usingnamespacestd;
Intmain()
{
Map<int,string>mapStudent;
mapStudent.insert(map<int,string>::value_type(1,“student_one”));
mapStudent.insert(map<int,string>::value_type(2,“student_two”));
mapStudent.insert(map<int,string>::value_type(3,“student_three”));
map<int,string>::iteratoriter;
for(iter=mapStudent.begin();iter!=mapStudent.end();iter++)
{
Cout<<iter->first<<””<<iter->second<<end;
}
}
第三种：用数组方式插入数据，下面举例说明
#include<map>
#include<string>
#include<iostream>
Usingnamespacestd;
Intmain()
{
Map<int,string>mapStudent;
mapStudent[1]=“student_one”;
mapStudent[2]=“student_two”;
mapStudent[3]=“student_three”;
map<int,string>::iteratoriter;
for(iter=mapStudent.begin();iter!=mapStudent.end();iter++)
{
Cout<<iter->first<<””<<iter->second<<end;
}
}
以上三种用法，虽然都可以实现数据的插入，但是它们是有区别的，当然了第一种和第二种在效果上是完成一样的，用insert函数插入数据，在数据的插入上涉及到集合的唯一性这个概念，即当map中有这个关键字时，insert操作是插入数据不了的，但是用数组方式就不同了，它可以覆盖以前该关键字对应的值，用程序说明
mapStudent.insert(map<int,string>::value_type(1,“student_one”));
mapStudent.insert(map<int,string>::value_type(1,“student_two”));
上面这两条语句执行后，map中1这个关键字对应的值是“student_one”，第二条语句并没有生效，那么这就涉及到我们怎么知道insert语句是否插入成功的问题了，可以用pair来获得是否插入成功，程序如下
Pair<map<int,string>::iterator,bool>Insert_Pair;
Insert_Pair=mapStudent.insert(map<int,string>::value_type(1,“student_one”));
我们通过pair的第二个变量来知道是否插入成功，它的第一个变量返回的是一个map的迭代器，如果插入成功的话Insert_Pair.second应该是true的，否则为false。
下面给出完成代码，演示插入成功与否问题
#include<map>
#include<string>
#include<iostream>
Usingnamespacestd;
Intmain()
{
Map<int,string>mapStudent;
Pair<map<int,string>::iterator,bool>Insert_Pair;
Insert_Pair＝mapStudent.insert(pair<int,string>(1,“student_one”));
If(Insert_Pair.second==true)
{
Cout<<”InsertSuccessfully”<<endl;
}
Else
{
Cout<<”InsertFailure”<<endl;
}
Insert_Pair＝mapStudent.insert(pair<int,string>(1,“student_two”));
If(Insert_Pair.second==true)
{
Cout<<”InsertSuccessfully”<<endl;
}
Else
{
Cout<<”InsertFailure”<<endl;
}
map<int,string>::iteratoriter;
for(iter=mapStudent.begin();iter!=mapStudent.end();iter++)
{
Cout<<iter->first<<””<<iter->second<<end;
}
}
大家可以用如下程序，看下用数组插入在数据覆盖上的效果
#include<map>
#include<string>
#include<iostream>
Usingnamespacestd;
Intmain()
{
Map<int,string>mapStudent;
mapStudent[1]=“student_one”;
mapStudent[1]=“student_two”;
mapStudent[2]=“student_three”;
map<int,string>::iteratoriter;
for(iter=mapStudent.begin();iter!=mapStudent.end();iter++)
{
Cout<<iter->first<<””<<iter->second<<end;
}
}
3.map的大小
在往map里面插入了数据，我们怎么知道当前已经插入了多少数据呢，可以用size函数，用法如下：
IntnSize=mapStudent.size();
4.数据的遍历
这里也提供三种方法，对map进行遍历
第一种：应用前向迭代器，上面举例程序中到处都是了，略过不表
第二种：应用反相迭代器，下面举例说明，要体会效果，请自个动手运行程序
#include<map>
#include<string>
#include<iostream>
Usingnamespacestd;
Intmain()
{
Map<int,string>mapStudent;
mapStudent.insert(pair<int,string>(1,“student_one”));
mapStudent.insert(pair<int,string>(2,“student_two”));
mapStudent.insert(pair<int,string>(3,“student_three”));
map<int,string>::reverse_iteratoriter;
for(iter=mapStudent.rbegin();iter!=mapStudent.rend();iter++)
{
Cout<<iter->first<<””<<iter->second<<end;
}
}
第三种：用数组方式，程序说明如下
#include<map>
#include<string>
#include<iostream>
Usingnamespacestd;
Intmain()
{
Map<int,string>mapStudent;
mapStudent.insert(pair<int,string>(1,“student_one”));
mapStudent.insert(pair<int,string>(2,“student_two”));
mapStudent.insert(pair<int,string>(3,“student_three”));
intnSize=mapStudent.size()
//此处有误，应该是for(intnIndex=1;nIndex<=nSize;nIndex++)
//byrainfish
for(intnIndex=0;nIndex<nSize;nIndex++)
{
Cout<<mapStudent[nIndex]<<end;
}
}
5.数据的查找（包括判定这个关键字是否在map中出现）
在这里我们将体会，map在数据插入时保证有序的好处。
要判定一个数据（关键字）是否在map中出现的方法比较多，这里标题虽然是数据的查找，在这里将穿插着大量的map基本用法。
这里给出三种数据查找方法
第一种：用count函数来判定关键字是否出现，其缺点是无法定位数据出现位置,由于map的特性，一对一的映射关系，就决定了count函数的返回值只有两个，要么是0，要么是1，出现的情况，当然是返回1了
第二种：用find函数来定位数据出现位置，它返回的一个迭代器，当数据出现时，它返回数据所在位置的迭代器，如果map中没有要查找的数据，它返回的迭代器等于end函数返回的迭代器，程序说明
#include<map>
#include<string>
#include<iostream>
Usingnamespacestd;
Intmain()
{
Map<int,string>mapStudent;
mapStudent.insert(pair<int,string>(1,“student_one”));
mapStudent.insert(pair<int,string>(2,“student_two”));
mapStudent.insert(pair<int,string>(3,“student_three”));
map<int,string>::iteratoriter;
iter=mapStudent.find(1);
if(iter!=mapStudent.end())
{
Cout<<”Find,thevalueis”<<iter->second<<endl;
}
Else
{
Cout<<”DonotFind”<<endl;
}
}
第三种：这个方法用来判定数据是否出现，是显得笨了点，但是，我打算在这里讲解
Lower_bound函数用法，这个函数用来返回要查找关键字的下界(是一个迭代器)
Upper_bound函数用法，这个函数用来返回要查找关键字的上界(是一个迭代器)
例如：map中已经插入了1，2，3，4的话，如果lower_bound(2)的话，返回的2，而upper-bound（2）的话，返回的就是3
Equal_range函数返回一个pair，pair里面第一个变量是Lower_bound返回的迭代器，pair里面第二个迭代器是Upper_bound返回的迭代器，如果这两个迭代器相等的话，则说明map中不出现这个关键字，程序说明
#include<map>
#include<string>
#include<iostream>
Usingnamespacestd;
Intmain()
{
Map<int,string>mapStudent;
mapStudent[1]=“student_one”;
mapStudent[3]=“student_three”;
mapStudent[5]=“student_five”;
map<int,string>::iteratoriter;
iter=mapStudent.lower_bound(2);
{
//返回的是下界3的迭代器
Cout<<iter->second<<endl;
}
iter=mapStudent.lower_bound(3);
{
//返回的是下界3的迭代器
Cout<<iter->second<<endl;
}
iter=mapStudent.upper_bound(2);
{
//返回的是上界3的迭代器
Cout<<iter->second<<endl;
}
iter=mapStudent.upper_bound(3);
{
//返回的是上界5的迭代器
Cout<<iter->second<<endl;
}
Pair<map<int,string>::iterator,map<int,string>::iterator>mapPair;
mapPair=mapStudent.equal_range(2);
if(mapPair.first==mapPair.second)
{
cout<<”DonotFind”<<endl;
}
Else
{
Cout<<”Find”<<endl;
}
mapPair=mapStudent.equal_range(3);
if(mapPair.first==mapPair.second)
{
cout<<”DonotFind”<<endl;
}
Else
{
Cout<<”Find”<<endl;
}
}
6.数据的清空与判空
清空map中的数据可以用clear()函数，判定map中是否有数据可以用empty()函数，它返回true则说明是空map
7.数据的删除
这里要用到erase函数，它有三个重载了的函数，下面在例子中详细说明它们的用法
#include<map>
#include<string>
#include<iostream>
Usingnamespacestd;
Intmain()
{
Map<int,string>mapStudent;
mapStudent.insert(pair<int,string>(1,“student_one”));
mapStudent.insert(pair<int,string>(2,“student_two”));
mapStudent.insert(pair<int,string>(3,“student_three”));
//如果你要演示输出效果，请选择以下的一种，你看到的效果会比较好
//如果要删除1,用迭代器删除
map<int,string>::iteratoriter;
iter=mapStudent.find(1);
mapStudent.erase(iter);
//如果要删除1，用关键字删除
Intn=mapStudent.erase(1);//如果删除了会返回1，否则返回0
//用迭代器，成片的删除
//一下代码把整个map清空
mapStudent.earse(mapStudent.begin(),mapStudent.end());
//成片删除要注意的是，也是STL的特性，删除区间是一个前闭后开的集合
//自个加上遍历代码，打印输出吧
}
8.其他一些函数用法
这里有swap,key_comp,value_comp,get_allocator等函数，感觉到这些函数在编程用的不是很多，略过不表，有兴趣的话可以自个研究
9.排序
这里要讲的是一点比较高深的用法了,排序问题，STL中默认是采用小于号来排序的，以上代码在排序上是不存在任何问题的，因为上面的关键字是int型，它本身支持小于号运算，在一些特殊情况，比如关键字是一个结构体，涉及到排序就会出现问题，因为它没有小于号操作，insert等函数在编译的时候过不去，下面给出两个方法解决这个问题
第一种：小于号重载，程序举例
#include<map>
#include<string>
Usingnamespacestd;
TypedefstructtagStudentInfo
{
IntnID;
StringstrName;
}StudentInfo,*PStudentInfo;//学生信息
Intmain()
{
intnSize;
//用学生信息映射分数
map<StudentInfo,int>mapStudent;
map<StudentInfo,int>::iteratoriter;
StudentInfostudentInfo;
studentInfo.nID=1;
studentInfo.strName=“student_one”;
mapStudent.insert(pair<StudentInfo,int>(studentInfo,90));
studentInfo.nID=2;
studentInfo.strName=“student_two”;
mapStudent.insert(pair<StudentInfo,int>(studentInfo,80));
for(iter=mapStudent.begin();iter!=mapStudent.end();iter++)
cout<<iter->first.nID<<endl<<iter->first.strName<<endl<<iter->second<<endl;
}
以上程序是无法编译通过的，只要重载小于号，就OK了，如下：
TypedefstructtagStudentInfo
{
IntnID;
StringstrName;
Booloperator<(tagStudentInfoconst&_A)const
{
//这个函数指定排序策略，按nID排序，如果nID相等的话，按strName排序
If(nID<_A.nID)returntrue;
If(nID==_A.nID)pare(_A.strName)<0;
Returnfalse;
}
}StudentInfo,*PStudentInfo;//学生信息
第二种：仿函数的应用，这个时候结构体中没有直接的小于号重载，程序说明
#include<map>
#include<string>
Usingnamespacestd;
TypedefstructtagStudentInfo
{
IntnID;
StringstrName;
}StudentInfo,*PStudentInfo;//学生信息
Classssort
{
Public:
Booloperator()(StudentInfoconst&_A,StudentInfoconst&_B)const
{
If(_A.nID<_B.nID)returntrue;
If(_A.nID==_B.nID)pare(_B.strName)<0;
Returnfalse;
}
};
Intmain()
{
//用学生信息映射分数
Map<StudentInfo,int,sort>mapStudent;
StudentInfostudentInfo;
studentInfo.nID=1;
studentInfo.strName=“student_one”;
mapStudent.insert(pair<StudentInfo,int>(studentInfo,90));
studentInfo.nID=2;
studentInfo.strName=“student_two”;
mapStudent.insert(pair<StudentInfo,int>(studentInfo,80));
}
10.另外
由于STL是一个统一的整体，map的很多用法都和STL中其它的东西结合在一起，比如在排序上，这里默认用的是小于号，即less<>，如果要从大到小排序呢，这里涉及到的东西很多，在此无法一一加以说明。
还要说明的是，map中由于它内部有序，由红黑树保证，因此很多函数执行的时间复杂度都是log2N的，如果用map函数可以实现的功能，而STLAlgorithm也可以完成该功能，建议用map自带函数，效率高一些。
下面说下，map在空间上的特性，否则，估计你用起来会有时候表现的比较郁闷，由于map的每个数据对应红黑树上的一个节点，这个节点在不保存你的数据时，是占用16个字节的，一个父节点指针，左右孩子指针，还有一个枚举值（标示红黑的，相当于平衡二叉树中的平衡因子），我想大家应该知道，这些地方很费内存了吧，不说了……
============================================================
[转载]MSDN
StandardC++LibraryReference
map::insert,map::find,andmap::end
SeeAlsoExample
CollapseAllExpandAllLanguageFilter:AllLanguageFilter:MultipleLanguageFilter:VisualBasicLanguageFilter:C#LanguageFilter:C++LanguageFilter:J#LanguageFilter:JScript
VisualBasic(Declaration)
VisualBasic(Usage)
C#
C++
J#
JScript
Illustrateshowtousethemap::insert,map::find,andmap::endStandardTemplateLibrary(STL)functionsinVisualC++.
iteratormap::end();
iteratormap::find(
constKey&Key
);
pair<iterator,bool>
map::insert(
constvalue_type&x
);
Remarks
Note
Theclass/parameternamesintheprototypedonotmatchtheversionintheheaderfile.Somehavebeenmodifiedtoimprovereadability.
Theendfunctionreturnsaniteratorthatpointsonepasttheendofasequence.findreturnsaniteratorthatdesignatesthefirstelementwhosesortkeyequalsKey.Ifnosuchelementexists,theiteratorequalsend.Ifthekeydoesnotalreadyexist,insertwilladdittothesequenceandreturnpair<iterator,true>.Ifthekeyalreadyexists,insertdoesnotaddittothesequenceandreturnspair<iterator,false>.Thefollowingsamplecreatesamapofintstostrings.Inthiscase,themappingisfromdigitstotheirstringequivalents(1->"One",2->"Two",andsoon).Theprogramreadsanumberfromtheuser,findsthewordequivalentforeachdigit(usingthemap),andprintsthenumberbackasaseriesofwords.Forexample,iftheuserenters25463,theprogramrespondswith:TwoFiveFourSixThree.
Example
CopyCode view plaincopy to clipboardprint? //map_insert_find_end.cpp //compilewith:/EHsc #pragmawarning(disable:4786) #include<iostream> #include<string> #include<map> usingnamespacestd; typedefmap<int,string,less<int>>INT2STRING; intmain() { //1.CreateamapofintstostringsINT2STRINGtheMap; INT2STRING::iteratortheIterator; stringtheString=""; intindex; //Fillitwiththedigits0-9,eachmappedtoitsstringcounterpart//Note:value_typeisapairformaps...theMap.insert(INT2STRING::value_type(0,"Zero")); theMap.insert(INT2STRING::value_type(1,"One")); theMap.insert(INT2STRING::value_type(2,"Two")); theMap.insert(INT2STRING::value_type(3,"Three")); theMap.insert(INT2STRING::value_type(4,"Four")); theMap.insert(INT2STRING::value_type(5,"Five")); theMap.insert(INT2STRING::value_type(6,"Six")); theMap.insert(INT2STRING::value_type(7,"Seven")); theMap.insert(INT2STRING::value_type(8,"Eight")); theMap.insert(INT2STRING::value_type(9,"Nine")); //ReadaNumberfromtheuserandprintitbackaswordsfor(;;) { cout<<"Enter\"q\"toquit,orenteraNumber:"; cin>>theString; if(theString=="q") break; //extracteachdigitfromthestring,finditscorresponding//entryinthemap(thewordequivalent)andprintitfor(index=0;index<(signed)theString.length();index++) { theIterator=theMap.find(theString[index]-'0'); if(theIterator!=theMap.end())//is0-9cout<<(*theIterator).second<<""; else//somecharacterotherthan0-9cout<<"[err]"; } cout<<endl; } }[cpp]view plaincopy //map_insert_find_end.cpp//compilewith:/EHsc#pragmawarning(disable:4786)#include<iostream>#include<string>#include<map>usingnamespacestd;typedefmap<int,string,less<int>>INT2STRING;intmain(){//1.CreateamapofintstostringsINT2STRINGtheMap;INT2STRING::iteratortheIterator;stringtheString="";intindex;//Fillitwiththedigits0-9,eachmappedtoitsstringcounterpart//Note:value_typeisapairformaps...theMap.insert(INT2STRING::value_type(0,"Zero"));theMap.insert(INT2STRING::value_type(1,"One"));theMap.insert(INT2STRING::value_type(2,"Two"));theMap.insert(INT2STRING::value_type(3,"Three"));theMap.insert(INT2STRING::value_type(4,"Four"));theMap.insert(INT2STRING::value_type(5,"Five"));theMap.insert(INT2STRING::value_type(6,"Six"));theMap.insert(INT2STRING::value_type(7,"Seven"));theMap.insert(INT2STRING::value_type(8,"Eight"));theMap.insert(INT2STRING::value_type(9,"Nine"));//ReadaNumberfromtheuserandprintitbackaswordsfor(;;){cout<<"Enter\"q\"toquit,orenteraNumber:";cin>>theString;if(theString=="q")break;//extracteachdigitfromthestring,finditscorresponding//entryinthemap(thewordequivalent)andprintitfor(index=0;index<(signed)theString.length();index++){theIterator=theMap.find(theString[index]-'0');if(theIterator!=theMap.end())//is0-9cout<<(*theIterator).second<<"";else//somecharacterotherthan0-9cout<<"[err]";}cout<<endl;}} Input
12
q
SampleOutput
CopyCode
Enter"q"toquit,orenteraNumber:12
OneTwo
Enter"q"toquit,orenteraNumber:q
Requirements
Header:<map>
SeeAlso
Concepts
StandardTemplateLibrarySamples
TomakeasuggestionorreportabugaboutHelporanotherfeatureofthisproduct,gotothefeedbacksite.
================================================================
Illustrateshowtousethemap::max_size,map::clear,map::erase,andmap::sizeStandardTemplateLibrary(STL)functionsinVisualC++.
size_typemax_size()const;
voidclear()const;
boolempty()const;
iteratorerase(
iteratorFirst,
iteratorLast
);
size_typesize()const;
A::referenceoperator[](//Aistheallocator
constKey&Key
);
iteratormap::begin();
iteratormap::end();
iteratormap::find(
constKey&Key
);
Remarks
Note
Theclass/parameternamesintheprototypedonotmatchtheversionintheheaderfile.Somehavebeenmodifiedtoimprovereadability.
Thefollowingsamplecreatesamapofstringstointsandfillsitfirstwithamapofmonthnamestomonthnumbers,andthenemptiesandrefillsitwithamapofweekdaynamestocorrespondingints.
Example
CopyCode view plaincopy to clipboardprint? //map_max_size_etc_sample.cpp //compilewith:/EHsc // //Functions:iteratormap::max_size();//voidclear()const;//boolempty()const; //iteratorerase(iteratorfirst,iteratorlast);//size_typesize()const; //A::referenceoperator[](constKey&key);//iteratormap::begin(); //iteratormap::end();//iteratormap::find(constKey&key);#pragmawarning(disable:4786) #include<iostream> #include<string> #include<map> usingnamespacestd; typedefmap<string,int>STRING2INT; intmain() { STRING2INTMyMap; STRING2INT::iteratorMyIterator; stringMyBuffer; //printthemaximumnumberof<key,data>pairsthatMyMapcanholdcout<<"MyMapiscapableofholding"<<MyMap.max_size() <<"<string,int>pairs"<<endl; if(!MyMap.empty()) cout<<"MyMaphas"<<MyMap.size()<<"entries"<<endl; elsecout<<"MyMapisempty"<<endl; cout<<"EnteringnewentriesinMyMap"<<endl; //FillinMyMapwiththemonthsoftheyear,mappedtotheirnumber//January-1,February-2,etc.usingoperator[].MyMap["January"]=1; MyMap["February"]=2; MyMap["March"]=3; MyMap["April"]=4; MyMap["May"]=5; MyMap["June"]=6; MyMap["July"]=7; MyMap["August"]=8; MyMap["September"]=9; MyMap["October"]=10; MyMap["November"]=11; MyMap["December"]=12; if(!MyMap.empty()) cout<<"MyMaphas"<<MyMap.size()<<"entries"<<endl; elsecout<<"MyMapisempty"<<endl; //Asktheuserforamonthoftheyearandprintthenumber//thatcorrespondstothemonthenteredMyIterator=MyMap.end(); while(MyIterator==MyMap.end()) { cout<<endl<<"EnteraMonth:"; cin>>MyBuffer; if((MyIterator=MyMap.find(MyBuffer))!=MyMap.end()) cout<<(*MyIterator).first<<"isMonthNumber"<<(*MyIterator).second<<endl; elsecout<<"EnteraValidMonth(example:March)"<<endl; } //emptyMyMap-notethatclearsimplycallserase(begin(),end());MyMap.clear(); if(!MyMap.empty()) cout<<"MyMaphas"<<MyMap.size()<<"entries"<<endl; elsecout<<"MyMapisempty"<<endl; cout<<"EnteringnewentriesinMyMap"<<endl; //FillMyMapwiththedaysoftheweek,eachmappedtoanintMyMap["Monday"]=1; MyMap["Tuesday"]=2; MyMap["Wednesday"]=3; MyMap["Thursday"]=4; MyMap["Friday"]=5; MyMap["Saturday"]=6; MyMap["Sunday"]=7; if(!MyMap.empty()) cout<<"MyMaphas"<<MyMap.size()<<"entries"<<endl; elsecout<<"MyMapisempty"<<endl; //Asktheuserforadayoftheweekandprintthenumber//thatcorrespondstothedayentered MyIterator=MyMap.end(); while(MyIterator==MyMap.end()) { cout<<endl<<"EnteraDayoftheWeek:"; cin>>MyBuffer; if((MyIterator=MyMap.find(MyBuffer))!=MyMap.end()) cout<<(*MyIterator).first<<"isDayNumber"<<(*MyIterator).second<<endl; elsecout<<"EnteraValidDayoftheWeek(example:Monday)"<<endl; } //NowclearMyMapagain-thistimeusingeraseinsteadofclearMyMap.erase(MyMap.begin(),MyMap.end()); if(!MyMap.empty()) cout<<"MyMaphas"<<MyMap.size()<<"entries"<<endl; elsecout<<"MyMapisempty"<<endl; }[cpp]view plaincopy //map_max_size_etc_sample.cpp//compilewith:/EHsc////Functions:iteratormap::max_size();//voidclear()const;//boolempty()const;//iteratorerase(iteratorfirst,iteratorlast);//size_typesize()const;//A::referenceoperator[](constKey&key);//iteratormap::begin();//iteratormap::end();//iteratormap::find(constKey&key);#pragmawarning(disable:4786)#include<iostream>#include<string>#include<map>usingnamespacestd;typedefmap<string,int>STRING2INT;intmain(){STRING2INTMyMap;STRING2INT::iteratorMyIterator;stringMyBuffer;//printthemaximumnumberof<key,data>pairsthatMyMapcanholdcout<<"MyMapiscapableofholding"<<MyMap.max_size()<<"<string,int>pairs"<<endl;if(!MyMap.empty())cout<<"MyMaphas"<<MyMap.size()<<"entries"<<endl;elsecout<<"MyMapisempty"<<endl;cout<<"EnteringnewentriesinMyMap"<<endl;//FillinMyMapwiththemonthsoftheyear,mappedtotheirnumber//January-1,February-2,etc.usingoperator[].MyMap["January"]=1;MyMap["February"]=2;MyMap["March"]=3;MyMap["April"]=4;MyMap["May"]=5;MyMap["June"]=6;MyMap["July"]=7;MyMap["August"]=8;MyMap["September"]=9;MyMap["October"]=10;MyMap["November"]=11;MyMap["December"]=12;if(!MyMap.empty())cout<<"MyMaphas"<<MyMap.size()<<"entries"<<endl;elsecout<<"MyMapisempty"<<endl;//Asktheuserforamonthoftheyearandprintthenumber//thatcorrespondstothemonthenteredMyIterator=MyMap.end();while(MyIterator==MyMap.end()){cout<<endl<<"EnteraMonth:";cin>>MyBuffer;if((MyIterator=MyMap.find(MyBuffer))!=MyMap.end())cout<<(*MyIterator).first<<"isMonthNumber"<<(*MyIterator).second<<endl;elsecout<<"EnteraValidMonth(example:March)"<<endl;}//emptyMyMap-notethatclearsimplycallserase(begin(),end());MyMap.clear();if(!MyMap.empty())cout<<"MyMaphas"<<MyMap.size()<<"entries"<<endl;elsecout<<"MyMapisempty"<<endl;cout<<"EnteringnewentriesinMyMap"<<endl;//FillMyMapwiththedaysoftheweek,eachmappedtoanintMyMap["Monday"]=1;MyMap["Tuesday"]=2;MyMap["Wednesday"]=3;MyMap["Thursday"]=4;MyMap["Friday"]=5;MyMap["Saturday"]=6;MyMap["Sunday"]=7;if(!MyMap.empty())cout<<"MyMaphas"<<MyMap.size()<<"entries"<<endl;elsecout<<"MyMapisempty"<<endl;//Asktheuserforadayoftheweekandprintthenumber//thatcorrespondstothedayenteredMyIterator=MyMap.end();while(MyIterator==MyMap.end()){cout<<endl<<"EnteraDayoftheWeek:";cin>>MyBuffer;if((MyIterator=MyMap.find(MyBuffer))!=MyMap.end())cout<<(*MyIterator).first<<"isDayNumber"<<(*MyIterator).second<<endl;elsecout<<"EnteraValidDayoftheWeek(example:Monday)"<<endl;}//NowclearMyMapagain-thistimeusingeraseinsteadofclearMyMap.erase(MyMap.begin(),MyMap.end());if(!MyMap.empty())cout<<"MyMaphas"<<MyMap.size()<<"entries"<<endl;elsecout<<"MyMapisempty"<<endl;}
如果觉得《红黑树实现——STL中的map》对你有帮助，请点赞、收藏，并留下你的观点哦！
