STL中map的用法剖析

摘 要　本文深入剖析了C++标准模板库(STL)中的map，对其概念和用法进行了深入探讨，并结合实例，详细阐述了map的相关用法。
关键词　STL；map；插入；删除；排序

1　map概述
STL(Standard Template Library 标准模版库)是C++标准程序库的核心，它深刻影响了标准程序库的整体结构。STL是一个范型(generic)程序库，提供一系列软件方案，利用先进、高效的算法来管理数据。STL的好处在于封装了许多数据结构和算法(algorithm)，map就是其典型代表。
map是STL的一个关联容器，它提供一对一(key/value 其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可以称为该关键字的值)的数据处理能力，由于这个特性，在处理一对一数据的时候，可以提供编程的快速通道。
2　map的用法
假设一个班级中，每个学生的学号和他的姓名存在一一映射的关系，这个模型用map可以轻易描述，学号用int描述，姓名用字符串描述，给出map的描述代码：map<int， string> mapStudent 。
2.1 插入数据
map元素的插入功能可以通过以下操作实现：
第一种通过主键获取map中的元素，如果获取到，则返回对应结点对应的实值(存储在map结点中的对象)。但这个方法会产生副作用，如果以主键“key”获取结点的实值，在map中并不存在这个结点，则会直接向map中插入以key为主键的结点，并返回这个结点，这时可以对其进行赋值操作。但如果在map中存在了以key为主键的结点，则会返回这个结点的实值，如果此时进行复制操作，则会出现原来结点被新结点覆盖的危险，如果是指针类型则会出现内存泄漏等问题。由于存在这样的副作用，不建议使用这种方法进行元素的插入。
第二种插入value_type数据。
insert方法接口原型：pair<ierator， bool> insert(const value_type& X)
该方法需要构建一个键值对，即value_type，然后调用insert方法，在该方法中实现根据键值对中的key值查找对应的结点，如果查找到，则不插入当前结点，并返回找到的那个结点，并将pair中的第二个量置为false；否则插入当前结点，并返回插入的当前结点，且第二个值置为true。在插入结点的时候，在map内部会重新构造一个新的value_type结点并将传入的X进行copy构造，内部使用了placement new方式，通过内存分配器分配一个map结点，再在获取的结点空间中调用value_type构造函数。所以调用者构造的键值对value_type是一个临时变量，不会加入到map中(不要被引用操作符迷惑，这里仅仅是传参效率上的考虑)。这种结点插入的方式是安全的，建议使用这种方式向map中插入元素，并判断返回的插入结果，根据插入结果进行后续处理。
#pragma warning(disable：4786)
#include <map>
#include <string>
#include <iostream>
using namespace std；
int main()
{
map<int，string> mapStudent；
mapStudent.insert(map<int，string>：：value_type(1，"one"))；
mapStudent.insert(map<int，string>：：value_type(2，"two"))；
mapStudent.insert(map<int，string>：：value_type(3，"three"))；
map<int，string>：：iterator iter；
for(iter=mapStudent.begin()；iter!=mapStudent.end()；iter++)
{
cout<<iter->first<<" "<<iter->second<<endl；
}
}
2.2 map的大小
往map中插入了数据，可以用size()函数得到当前已经插入了多少数据：
int nSize=mapStudent.size()
2.3 排序
STL中默认是采用小于号来排序的，以上代码在排序上是不存在任何问题的，因为上面例子中的关键字是int型，它本身支持小于号运算。在一些特殊情况下，比如关键字是一个结构体，涉及到排序就会出现问题，因为它没有小于号运算，insert等函数在编译的时候过不去。给出一种方法解决排序问题——小于号重载。
#pragma warning(disable：4786)

#include <map>
#include <string>
#include <iostream>
using namespace std；
typedef struct tagStudentInfo
{
int nID；
string strName；
} StudentInfo， *PStudentInfo； // 学生信息
int main()
{
//用学生信息映射分数
map<StudentInfo， int> mapStudent；
StudentInfo studentInfo；
studentInfo.nID=2；
studentInfo.strName="one"；
mapStudent.insert(map<StudentInfo， int>：：value_type (studentInfo，90))；
studentInfo.nID=1；
studentInfo.strName="two"；
mapStudent.insert(map<StudentInfo， int>：：value_type (studentInfo，80))；
}
以上程序无法编译通过，需要重载小于号。
typedef struct tagStudentInfo
{
int nID；
string strName；
bool operator <(tagStudentInfo const& _A) const
{//这个函数指定排序策略，按nID排序，如果nID相等按strName排序
if(nID<_A.nID) return true；
if(nID==_A.nID) return strName.compare(_A.strName) <0；
return false；
}
} StudentInfo， *PStudentInfo；
2.4 map中结点的删除操作
两种应用场景：
第一种：一次只从map中查找一个结点并删除。
这种删除较为简单，只需要根据键值在map中查找，并将找到的结点删除就可以了。
#pragma warning(disable：4786)
#include <map>
#include <string>
#include <iostream>
using namespace std；
void main()
{
map<int，string> mapStudent；
mapStudent.insert(map<int，string>：：value_type(1，"one"))；
mapStudent.insert(map<int，string>：：value_type(2，"two"))；
mapStudent.insert(map<int，string>：：value_type(3，"three"))；
map<int，string>：：iterator iter；
iter=mapStudent.find(1)；
mapStudent.erase(iter)；
for(iter=mapStudent.begin()；iter!=mapStudent.end()；iter++)
{
cout<<iter->first<<" "<<iter->second<<endl；
}
}
第二种：从map中遍历检查所有结点，将符合条件的结点删除。
应用场景描述：系统定期检查垃圾会话(会话放在map表中)，根据当前系统时间减去会话最近活动时间，得到会话最近未活动时间间隔，如果这个间隔超过预定的值(认为会话是垃圾会话，可以被强制删除)，则删除该会话并从map中删除这个结点。
做法有两种：
（1）先遍历一遍map，找出所有满足条件的结点，将每一个对应结点的key放入一个vector中，后面再从vector中依次取出key值，做单结点删除操作。
这种方法是很原始且效率低下的做法，之所以会这样实现，是由于开发人员对map使用不甚了解的基础上做出来的。这种方法不但增加了中间处理过程的系统开销(多构建了一个缓存空间)，而且多了N(待删除结点的结点数)次的查询操作，对于经常出现的操作，这种低效是不可容忍的。
（2）在map遍历的过程中，完成对符合条件结点的删除操作(这个是由map本身数据结构特性保证的)。在遍历的过程中最主要的就是怎么保证删除的结点在删除前将指针指向下一个结点(这一点正是我们要做的)，在删除了当前结点后，map中的数据结构能够保证后续的迭代器指针是有效的，而且后续的结点都没有遍历过(这个特性是由map底层的红黑树的相关操作保证的)。所以需要将迭代器指向下一个结点后再删除当前符合条件的结点。

#pragma warning(disable：4786)
#include <map>
#include <string>
#include <iostream>
using namespace std；
void main()
{
map<int，string> mapStudent；
mapStudent.insert(map<int，string>：：value_type(1，"one"))；
mapStudent.insert(map<int，string>：：value_type(2，"two"))；
mapStudent.insert(map<int，string>：：value_type(3，"three"))；
map<int，string>：：iterator iter；
string aa="three"；
iter=mapStudent.begin()；
for(；iter!=mapStudent.end()；)
{
if((iter->second)>=aa)
{
//满足删除条件，删除当前结点，并指向下面一个结点
mapStudent.erase(iter++)；
}
else
{
//条件不满足，指向下面一个结点
iter++；
}
}
for(iter=mapStudent.begin()；iter!=mapStudent.end()；iter++)
{
cout<<iter->first<<" "<<iter->second<<endl；
}
}
这种删除方式也是STL源码一书中推荐的方式。比较一下mapStudent.erase(iter++)和mapStudent.erase(iter)； iter++；这个执行序列。不妨做个简单的测试，看看汇编执行下的执行序列：
void func(int a)
{}
int main(int， char**)
{
int iPos=0；
func(iPos++)；
}
函数调用func(iPos++)执行序列：将iPos放入寄存器edx中(缓存起来)，随机对iPos做加操作 inc dword ptr [ebp-0x04]。也就是说函数调用中的iPos++的执行时期在函数体func执行前就已经完成，而函数体中的参数使用的是iPos未做加操作之前的副本。再分析mapStudent.erase(iter++)语句，map中在删除iter的时候，先将iter做缓存，然后执行iter++使之指向下一个结点，再进入erase函数体中执行删除操作，删除时使用的iter就是缓存下来的iter(也就是当前iter(做了加操作之后的iter)所指向结点的上一个结点)。
根据以上分析，可以看出mapStudent.erase(iter++)和map Student.erase(iter)； iter++；这个执行序列是不相同的。前者在erase执行前进行了加操作，在iter被删除(失效)前进行了加操作，是安全的；后者是在erase执行后才进行加操作，而此时iter已经被删除(当前的迭代器已经失效了)，对一个已经失效的迭代器进行加操作，行为是不可预期的，这种写法势必会导致map操作的失败并引起进程的异常。
3　结束语
充分利用map的强大功能，可以使程序员的工作量大大减轻，采用传统方法编写的许多行代码，往往通过调用一两个算法模板就可实现。map技术可以让程序员编写出简洁而高效的代码，使编程工作更加简单而有效。
参考文献
[1] Nicolai M.Josuttis. C++标准程序库[M]. 武汉： 华中科技大学出版社，2006.
[2] Scott Meyers. Effective STL中文版——50条有效使用STL的经验[M]. 北京： 清华大学出版社，2006.
[3] 侯捷. STL源码剖析[M]. 武汉： 华中科技大学出版社，2002.
[4] 王昌晶，薛锦云. 从C++到STL[J]. 江西师范大学学报，2004(8)：231-234.