当前位置：文档之家 › STL中map的用法剖析

STL中map的用法剖析

  • 格式：doc
  • 大小：28.50 KB
  • 文档页数：6

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(constvalue_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 pare(_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；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"；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源码一书中推荐的方式。

合集下载

c++中的map的用法

c++中的map的用法

c++中的map的用法Map是一种关联容器，它提供了一种映射的方式，将一个值（value）与一个键（key）相对应。

在C++ STL（Standard Template Library）中，Map是一个非常常用的容器类型，它具有很高的效率和灵活性。

Map内部使用红黑树（一种自平衡的二叉搜索树）来进行高效的查找和插入操作，它的不同之处在于，它的每个节点都包含了一个键值对，其中键是唯一的。

使用Map之前需要引入头文件<map>，其使用方法是：```c++#include <map>map<key_type, value_type> my_map;```key_type表示键的类型，value_type表示值的类型。

Map的常用操作包括：1. 插入Map的插入可以使用insert()函数，例如：```c++//插入键值对//使用数组下标插入my_map["Jerry"] = 20;```2. 查找Map的查找可以使用find()函数，例如：```c++//查找键为"Tom"的值map<string, int>::iterator it = my_map.find("Tom");if (it != my_map.end()) { //如果找到了cout << "Tom's age is " << it->second << endl; //输出Tom的年龄}```3. 删除Map的删除可以使用erase()函数。

例如：```c++//删除键为"Tom"的值my_map.erase("Tom");```4. 遍历Map的遍历可以使用迭代器，例如：```c++//遍历map中的所有键值对for (auto it = my_map.begin(); it != my_map.end(); it++) {cout << "key is " << it->first << " , value is " << it->second << endl;}```需要注意的是，Map中的元素是按照键的大小进行排序的，如果需要按照值的大小进行排序，可以使用multimap容器。

C++STL中哈希表hash_map从头到尾详细介绍

C++STL中哈希表hash_map从头到尾详细介绍

C++STL中哈希表hash_map从头到尾详细介绍0 为什么需要hash_map⽤过map吧？map提供⼀个很常⽤的功能，那就是提供key-value的存储和查找功能。

例如，我要记录⼀个⼈名和相应的存储，⽽且随时增加，要快速查找和修改：岳不群－华⼭派掌门⼈，⼈称君⼦剑张三丰－武当掌门⼈，太极拳创始⼈东⽅不败－第⼀⾼⼿，葵花宝典...这些信息如果保存下来并不复杂，但是找起来⽐较⿇烦。

例如我要找"张三丰"的信息，最傻的⽅法就是取得所有的记录，然后按照名字⼀个⼀个⽐较。

如果要速度快，就需要把这些记录按照字母顺序排列，然后按照⼆分法查找。

但是增加记录的时候同时需要保持记录有序，因此需要插⼊排序。

考虑到效率，这就需要⽤到⼆叉树。

讲下去会没完没了，如果你使⽤STL 的map容器，你可以⾮常⽅便的实现这个功能，⽽不⽤关⼼其细节。

关于map的数据结构细节，感兴趣的朋友可以参看。

看看map的实现:1 #include <map>2 #include <string>3using namespace std;4 ...5 map<string, string> namemap;6//增加。

7 namemap["岳不群"]="华⼭派掌门⼈，⼈称君⼦剑";8 namemap["张三丰"]="武当掌门⼈，太极拳创始⼈";9 namemap["东⽅不败"]="第⼀⾼⼿，葵花宝典";10 ...11//查找。

12if(namemap.find("岳不群") != namemap.end()){13 ...14 }不觉得⽤起来很easy吗？⽽且效率很⾼，100万条记录，最多也只要20次的pare的⽐较，就能找到你要找的记录;200万条记录事，也只要⽤21次的⽐较。

std：：map用法

std：：map用法

std：：map⽤法STL是标准C++系统的⼀组模板类，使⽤STL模板类最⼤的好处就是在各种C++编译器上都通⽤。

在STL模板类中，⽤于线性数据存储管理的类主要有vector, list, map 等等。

本⽂主要针对map对象，结合⾃⼰学习该对象的过程，讲解⼀下具体⽤法。

本⼈初学，⽔平有限，讲解差错之处，请⼤家多多批评指正。

map对象所实现的功能跟MFC得CMap相似，但是根据⼀些⽂章的介绍和论述，MFC CMap在个⽅⾯都与STL map有⼀定的差距，例如不是C++标准，不⽀持赋值构造，对象化概念不清晰等等。

使⽤map对象⾸先要包括头⽂件,包含语句中必须加⼊如下包含声明#include <map>注意，STL头⽂件没有扩展名.h包括头⽂件后就可以定义和使⽤map对象了，map对象是模板类，需要关键字和存储对象两个模板参数，例如：std:map<int, CString> enumMap;这样就定义了⼀个⽤int作为关键字检索CString条⽬的map对象，std表⽰命名空间，map对象在std名字空间中，为了⽅便，在这⾥我仍然使⽤了CString类，其实应该使⽤标准C++的std::string类，我们对模板类进⾏⼀下类型定义，这样⽤的⽅便，当然，不定义也可以，代码如下：typedef std:map<int, CString> UDT_MAP_INT_CSTRING;UDT_MAP_INT_CSTRING enumMap;如此map对象就定义好了，增加，改变map中的条⽬⾮常简单，因为map类已经对[]操作符进⾏了重载，代码如下:enumMap[1] = "One";enumMap[2] = "Two";.....enumMap[1] = "One Edit";或者insert⽅法enumMap.insert(make_pair(1,"One"));返回map中⽬前存储条⽬的总数⽤size()⽅法：int nSize = enumMap.size();查找map中是否包含某个关键字条⽬⽤find⽅法，传⼊的参数是要查找的key，在我们的例⼦⾥，是⼀个int数据，map中的条⽬数据是顺序存储的，被称作为⼀个sequence，在这⾥需要提到的是begin()和end()两个成员，分别代表map对象中第⼀个条⽬和最后⼀个条⽬，这两个数据的类型是iterator，iterator被定义为map中条⽬的类型，查找是否包含某个条⽬的代码如下：int nFindKey = 2; //要查找的KeyUDT_MAP_INT_CSTRING::iterator it; //定义⼀个条⽬变量(实际是指针)it = enumMap.find(nFindKey);if(it == enumMap.end()) {//没找到}else {//找到}//find的时候注意key的数据类型，最好⽤CString之类的能消除数据类型差异的key，否则可能会出现强制转换后仍找不到的情况。

C++ STL模板和Map使用大全

C++ STL模板和Map使用大全

C++ STL模板和Map使用大全C++map的基本操作和使用(2009-09-23 14:58:21)分类：nguages标签：cmap编程基本操作livehaiitMap是c++的一个标准容器，她提供了很好一对一的关系，在一些程序中建立一个map可以起到事半功倍的效果，总结了一些map基本简单实用的操作！1. map最基本的构造函数；map<string , int >mapstring; map<int ,string >mapint;map<sring, char>mapstring; map< char ,string>mapchar;map<char ,int>mapchar; map<int ,char >mapint；2. map添加数据；map<int ,string> maplive;1.maplive.insert(pair<int,string>(102,"aclive"));2.maplive.insert(map<int,string>::value_type(321,"hai"));3, maplive[112]="April";//map中最简单最常用的插入添加！3，map中元素的查找：find()函数返回一个迭代器指向键值为key的元素，如果没找到就返回指向map尾部的迭代器。

map<int ,string >::iterator l_it;;l_it=maplive.find(112);if(l_it==maplive.end())cout<<"we do not find 112"<<endl;else cout<<"wo find 112"<<endl;4,map中元素的删除：如果删除112；map<int ,string >::iterator l_it;;l_it=maplive.find(112);if(l_it==maplive.end())cout<<"we do not find 112"<<endl;else maplive.erase(l_it); //delete 112;5,map中swap的用法：Map中的swap不是一个容器中的元素交换，而是两个容器交换； For example：#include <map>#include <iostream>using namespace std;int main( ){map <int, int> m1, m2, m3;map <int, int>::iterator m1_Iter;m1.insert ( pair <int, int> ( 1, 10 ) );m1.insert ( pair <int, int> ( 2, 20 ) );m1.insert ( pair <int, int> ( 3, 30 ) );m2.insert ( pair <int, int> ( 10, 100 ) );m2.insert ( pair <int, int> ( 20, 200 ) );m3.insert ( pair <int, int> ( 30, 300 ) );cout << "The original map m1 is:";for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ )cout << " " << m1_Iter->second;cout << "." << endl;// This is the member function version of swap//m2 is said to be the argument map; m1 the target mapm1.swap( m2 );cout << "After swapping with m2, map m1 is:";for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ )cout << " " << m1_Iter -> second;cout << "." << endl;cout << "After swapping with m2, map m2 is:";for ( m1_Iter = m2.begin( ); m1_Iter != m2.end( ); m1_Iter++ )cout << " " << m1_Iter -> second;cout << "." << endl;// This is the specialized template version of swapswap( m1, m3 );cout << "After swapping with m3, map m1 is:";for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ )cout << " " << m1_Iter -> second;cout << "." << endl;}6.map的sort问题：Map中的元素是自动按key升序排序,所以不能对map用sort函数：For example：#include <map>#include <iostream>using namespace std;int main( ){map <int, int> m1;map <int, int>::iterator m1_Iter;m1.insert ( pair <int, int> ( 1, 20 ) );m1.insert ( pair <int, int> ( 4, 40 ) );m1.insert ( pair <int, int> ( 3, 60 ) );m1.insert ( pair <int, int> ( 2, 50 ) );m1.insert ( pair <int, int> ( 6, 40 ) );m1.insert ( pair <int, int> ( 7, 30 ) );cout << "The original map m1 is:"<<endl;for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ ) cout << m1_Iter->first<<" "<<m1_Iter->second<<endl;}The original map m1 is:1 202 503 604 406 407 30请按任意键继续. . .7， map的基本操作函数：C++ Maps是一种关联式容器，包含“关键字/值”对begin() 返回指向map头部的迭代器clear(）删除所有元素count() 返回指定元素出现的次数empty() 如果map为空则返回trueend() 返回指向map末尾的迭代器equal_range() 返回特殊条目的迭代器对erase() 删除一个元素find() 查找一个元素get_allocator() 返回map的配置器insert() 插入元素key_comp() 返回比较元素key的函数lower_bound() 返回键值>=给定元素的第一个位置max_size() 返回可以容纳的最大元素个数rbegin() 返回一个指向map尾部的逆向迭代器rend() 返回一个指向map头部的逆向迭代器size() 返回map中元素的个数swap() 交换两个mapupper_bound() 返回键值>给定元素的第一个位置value_comp() 返回比较元素value的函数C++map的基本操作和使用(2009-09-23 14:58:21)分类：nguages标签：cmap编程基本操作livehaiitMap是c++的一个标准容器，她提供了很好一对一的关系，在一些程序中建立一个map可以起到事半功倍的效果，总结了一些map基本简单实用的操作！1. map最基本的构造函数；map<string , int >mapstring; map<int ,string >mapint;map<sring, char>mapstring; map< char ,string>mapchar;map<char ,int>mapchar; map<int ,char >mapint；2. map添加数据；map<int ,string> maplive;1.maplive.insert(pair<int,string>(102,"aclive"));2.maplive.insert(map<int,string>::value_type(321,"hai"));3, maplive[112]="April";//map中最简单最常用的插入添加！3，map中元素的查找：find()函数返回一个迭代器指向键值为key的元素，如果没找到就返回指向map尾部的迭代器。