stl的map,stl的map底层实现

　　Std map是STL的一个关联容器，提供了一对一的数据处理能力(第一个可以称为关键字，每个关键字在map中只能出现一次，第二个可以称为关键字的值)。由于这个特性，当我们处理一对一的数据时，可以在编程中提供一个快速通道。在这里，我们来谈谈std map中数据的组织。std map中构建了一棵红黑树(一种非正式意义上的平衡二叉树)。这个树有自动排序数据的功能，所以std图中的所有数据都是有序的。我们以后会看到秩序的好处。

　　这里有一个关于什么是一对一数据映射的例子。比如在一个班级里，每个学生的学号和他的名字是一一对应的映射关系。这个模型可以很容易地用地图来描述。很明显，学号是用int描述的，名字是用string描述的(在本文中，不是用char *来描述string，而是用STL中的string来描述)。以下是地图描述代码：

　　Map int，string mapStudent

　　1.地图的构造者

　　Map提供了六个构造函数。这个问题涉及内存分配器，所以我们将跳过这个表。下面，我们将会谈到一些地图的构造方法。这里想说的是，我们通常用以下方法构造地图：

　　Map int，string mapStudent

　　2.数据插入

　　构建地图容器后，我们可以向其中插入数据。以下是三种插入数据的方法：

　　第一种：用insert函数插入pair数据，下面是一个例子(下面的代码虽然写的很随便，但是应该是在VC和GCC下编译通过的，可以运行一下看看会有什么效果。请在VC下添加此语句以阻止4786警告# #pragma警告(disable:4786))

　　#包含地图

　　#包含字符串

　　#包括iostream

　　使用命名空间std

　　Int main()

　　{

　　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:iterator ITER；

　　for(ITER=map student . begin()；iter！=map student . end()；iter)

　　{

　　cout ITER-first " " ITER-second end；

　　}

　　}

　　第二种方法是用insert函数插入value_type数据。下面是一个例子。

　　#包含地图

　　#包含字符串

　　#包括iostream

　　使用命名空间std

　　Int main()

　　{

　　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:iterator ITER；

　　for(ITER=map student . begin()；iter！=map student . end()；iter)

　　{

　　cout ITER-first " " ITER-second end；

　　}

　　}

　　第三种方法是在数组中插入数据，如下所示。

　　#包含地图

　　#包含字符串

　　#包括iostream

　　使用命名空间std

　　Int main()

　　{

　　Map int，string mapStudent

　　map student[1]=" student _ one "；

　　map student[2]=" student _ two "；

　　map student[3]=" student _ three "；

　　map int，string:iterator ITER；

　　for(ITER=map student . begin()；iter！=map student . 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=地图学生。insert(map int，string :value_type (1，" student _ one "))；

　　我们通过一副的第二个变量来知道是否插入成功，它的第一个变量返回的是一个地图的迭代器，如果插入成功的话插入_配对。秒应该是真实的的，否则为错误。

　　下面给出完成代码，演示插入成功与否问题

　　#包含地图

　　#包含字符串

　　#包括输入输出流

　　使用命名空间标准

　　Int main()

　　{

　　Map int，string mapStudent

　　对映射int，string :iterator，bool Insert _ Pair

　　insert _ Pair=地图学生。insert(Pair int，string (1，“student _ one”)；

　　If(Insert_Pair.second==true)

　　{

　　Cout "插入成功“恩德尔

　　}

　　其他

　　{

　　Cout "插入失败“恩德尔

　　}

　　insert _ Pair=地图学生。insert(Pair int，string (1，“student _ two”)；

　　If(Insert_Pair.second==true)

　　{

　　Cout "插入成功“恩德尔

　　}

　　其他

　　{

　　Cout "插入失败“恩德尔

　　}

　　map int，string:迭代器ITER；

　　对于(ITER=地图学生。begin()；iter！=地图生。end()；iter)

　　{

　　cout ITER-第一”“ITER-第二端；

　　}

　　}

　　大家可以用如下程序，看下用数组插入在数据覆盖上的效果

　　#包含地图

　　#包含字符串

　　#包括输入输出流

　　使用命名空间标准

　　Int main()

　　{

　　Map int，string mapStudent

　　map student[1]=" student _ one "；

　　map student[1]=" student _ two "；

　　映射学生[2]="学生_三"；

　　map int，string:迭代器ITER；

　　对于(ITER=地图学生。begin()；iter！=地图生。end()；iter)

　　{

　　cout ITER-第一”“ITER-第二端；

　　}

　　}

　　3.地图的大小

　　在往地图里面插入了数据，我们怎么知道当前已经插入了多少数据呢，可以用大小函数，用法如下：

　　int nSize=地图学生。size()；

　　4.数据的遍历

　　这里也提供三种方法，对地图进行遍历

　　第一种：应用前向迭代器，上面举例程序中到处都是了，略过不表

　　第二种：应用反相迭代器，下面举例说明，要体会效果，请自个动手运行程序

　　#包含地图

　　#包含字符串

　　#包括输入输出流

　　使用命名空间标准

　　Int main()

　　{

　　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 _ iterator ITER；

　　对于(ITER=地图学生。Rb egin()；iter！=地图生。rend()；iter)

　　{

　　cout ITER-第一”“ITER-第二端；

　　}

　　}

　　第三种：用数组方式，程序说明如下

　　#包含地图

　　#包含字符串

　　#包括输入输出流

　　使用命名空间标准

　　Int main()

　　{

　　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 "))；

　　int nSize=mapStudent.size()

　　//此处有误，应该是for(int nIndex=1；nIndex=nSizenIndex)

　　//通过雨鱼

　　for(int nIndex=0；nIndex nSizenIndex)

　　{

　　cout map student[nIndex]end；

　　}

　　}

　　5.数据的查找（包括判定这个关键字是否在地图中出现)

　　在这里我们将体会，地图在数据插入时保证有序的好处。

　　要判定一个数据（关键字)是否在地图中出现的方法比较多，这里标题虽然是数据的查找，在这里将穿插着大量的地图基本用法。

　　这里给出三种数据查找方法

　　第一种：用数数函数来判定关键字是否出现，其缺点是无法定位数据出现位置，由于地图的特性，一对一的映射关系，就决定了数数函数的返回值只有两个，要么是0,要么是1,出现的情况，当然是返回一了

　　第二种：用发现函数来定位数据出现位置，它返回的一个迭代器，当数据出现时，它返回数据所在位置的迭代器，如果地图中没有要查找的数据，它返回的迭代器等于目标函数返回的迭代器，程序说明

　　#包含地图

　　#包含字符串

　　#包括输入输出流

　　使用命名空间标准

　　Int main()

　　{

　　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:iterator ITER；

　　ITER=map student . find(1)；

　　如果(iter！=mapStudent.end())

　　{

　　Cout "Find，值为" ITER-second endl；

　　}

　　其他

　　{

　　Cout“不要找”endl

　　}

　　}

　　第三种方法：这种方法用来判断数据是否出现，看起来很蠢，但我打算在这里说明一下。

　　Lower_bound函数的用法，用于返回要查找的关键字的下界(它是一个迭代器)。

　　Upper_bound函数的用法，用于返回要查找的关键字的上界(是一个迭代器)。

　　例如，如果在地图中插入了1，2，3，4，那么lower_bound(2)将返回2，upper-bound(2)将返回3。

　　Equal_range函数返回一对。对中的第一个变量是Lower_bound返回的迭代器，对中的第二个迭代器是Upper_bound返回的迭代器。如果这两个迭代器相等，这个关键字就不会出现在映射中。程序描述

　　#包含地图

　　#包含字符串

　　#包括iostream

　　使用命名空间std

　　Int main()

　　{

　　Map int，string mapStudent

　　map student[1]=" student _ one "；

　　map student[3]=" student _ three "；

　　map student[5]=" student _ five "；

　　map int，string:iterator ITER；

　　ITER=map student . lower _ bound(2)；

　　{

　　//返回下界为3的迭代器

　　count ITER-second endl；

　　}

　　ITER=map student . lower _ bound(3)；

　　{

　　//返回下界为3的迭代器

　　count ITER-second endl；

　　}

　　ITER=map student . upper _ bound(2)；

　　{

　　//返回上限3的迭代器

　　count ITER-second endl；

　　}

　　ITER=map student . upper _ bound(3)；

　　{

　　//返回上限5的迭代器

　　count ITER-second endl；

　　}

　　Pair map int，string :iterator，map int，string:iterator map pair；

　　map pair=map student . equal _ range(2)；

　　if(map pair . first==map pair . second)

　　{

　　cout“不要找”endl

　　}

　　其他

　　{

　　Cout“查找”endl

　　}

　　map pair=map student . equal _ range(3)；

　　if(map pair . first==map pair . second)

　　{

　　cout“不要找”endl

　　}

　　其他

　　{

　　Cout“查找”endl

　　}

　　}

　　6.清除和判断数据。

　　Clear()函数可以用来清除地图中的数据，empty()函数可以用来判断地图中是否有数据。如果返回true，则表示地图是空的。

　　7.数据删除

　　这里使用了erase函数，它有三个重载函数。下面的例子详细说明了它们的用法。

　　#包含地图

　　#包含字符串

　　#包括iostream

　　使用命名空间std

　　Int main()

　　{

　　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:iterator ITER；

　　ITER=map student . find(1)；

　　map student . erase(ITER)；

　　//如果要删除1，用关键字删除

　　int n=map student . erase(1)；//如果删除，则返回1，否则返回0

　　//使用迭代器删除片段。

　　//用代码清空整个地图。

　　map student . earse(map student . begin()、map student . end())；

　　//分段删除需要注意的是，这也是STL的特点，删除区间是一个前闭后开的集合。

　　//自己添加遍历代码，打印出来。

　　}

　　8.一些其他功能的使用

　　这里有swap，key _ comp，value _ comp，get _ allocator等函数。感觉编程用不到这些函数，有兴趣可以跳过表自己研究。

　　9.分类

　　这里要讲的是稍微高级一点的用法。排序问题，STL默认使用小于号排序。上面的代码在排序上没有问题，因为上面的关键字是int类型，它支持小于号操作。在一些特殊情况下，比如keyword是一个结构，在排序的时候就会出现问题，因为没有小于号操作，在编译的时候insert之类的函数就过不去。这里有两种方法可以解决这个问题。

　　第一种：小于号重载，有程序例子。

　　#包含地图

　　#包含字符串

　　使用命名空间std

　　Typedef结构tagStudentInfo

　　{

　　Int nID

　　字符串strName

　　}StudentInfo，* PStudentInfo//学生信息

　　Int main()

　　{

　　int nSize

　　//用学生信息映射分数

　　map StudentInfo，int mapStudent

　　map StudentInfo，int:iterator ITER；

　　StudentInfo studentInfo

　　studentinfo . NID=1；

　　student info . strname=" student _ one "；

　　map student . insert(pair student info，int (studentInfo，90))；

　　studentinfo . NID=2；

　　student info . strname=" student _ two "；

　　map student . insert(pair student info，int (studentInfo，80))；

　　for(ITER=map student . begin()；iter！=map student . end()；iter)

　　cout ITER-first . NID endl ITER-first . strname endl ITER-second endl；

　　}

　　上面的程序编译不了，只要重载小于数就OK，如下：

　　Typedef结构tagStudentInfo

　　{

　　Int nID

　　字符串strName

　　布尔运算符(tagStudentInfo const _A) const

　　{

　　//此函数指定排序策略，按nID排序，如果nID相等，则按strName排序

　　If(nID _A.nID)返回true

　　If(nID==_A.nID)返回strName.compare(_A.strName)

　　返回false

　　}

　　}StudentInfo，* PStudentInfo//学生信息

　　第二：模仿功能的应用。此时，在结构和程序描述中没有小于号的直接重载。

　　#包含地图

　　#包含字符串

　　使用命名空间std

　　Typedef结构tagStudentInfo

　　{

　　Int nID

　　字符串strName

　　}StudentInfo，* PStudentInfo//学生信息

　　类别排序

　　{

　　公共：

　　Bool运算符()(学生信息常量_A，学生信息常量_B)常量

　　{

　　If(_A.nID _B.nID)返回true

　　if(_ a . NID==_ b . NID)return _ a . strname . compare(_ b . strname)

　　返回false

　　}

　　};

　　Int main()

　　{

　　//用学生信息映射分数

　　Map StudentInfo，int，sort mapStudent

　　StudentInfo studentInfo

　　studentinfo . NID=1；

　　student info . strname=" student _ one "；

　　map student . insert(pair student info，int (studentInfo，90))；

　　studentinfo . NID=2；

　　student info . strname=" student _ two "；

　　map student . insert(pair student info，int (studentInfo，80))；

　　}

　　10.另外

　　由于STL是一个统一的整体，所以在STL中，地图的许多用法都是与其他事物结合在一起的。比如排序，这里默认用的是less sign，也就是less。如果要从大到小排序的话，这里涉及的东西很多，这里就不一一说明了。

　　还需要注意的是，由于其内部的顺序和红黑树的保证，map中很多函数的时间复杂度都是log2N。如果功能可以用map函数实现，STL算法也可以完成这个功能，建议用map的内置函数，效率更高。

　　先说地图的空间特征。不然估计你用的时候有时候会很郁闷。因为map的每个数据都对应红黑树中的一个节点，所以这个节点在你不保存数据的时候占用了16个字节。有一个父节点指针，左右子指针，还有一个枚举值(用红色和黑色标记，相当于平衡二叉树中的平衡因子)。我想你应该知道这些地方需要很大的内存。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。