文档章节

Map以自定义类做为键值

涩女郎
 涩女郎
发布于 2015/08/20 11:55
字数 1377
阅读 48
收藏 0

map在STL中的定义

template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>

 第一个参数Key是关键字类型

第二个参数T是值类型

第三个参数Compare是比较函数(仿函数)

第四个参数是内存配置对象

map内部存储机制实际是以红黑树为基础,红黑树在插入节点时,必须依照大小比对之后在一个合适的位置上执行插入动作。所以作为关键字,起码必须有“<”这个比较操作符。我们知道,int,float,enum,size_t等等简单关键字,都有内置的比较函数,与map搭配无论是插入还是查找,都没什么问题。但是作为复杂数据类型,如果没有明确定义“<”比较操作符,就不能与map直接搭配使用,除非我们自己定义第三个参数。

在选择map的关键字时,注意以下两点,同时这两点也是改错的方法:

a) 关键字明确定义“<”比较操作符

b) 没有“<”比较操作符,自定义仿函数替代第三个参数Compare,该仿函数实现“()”操作符,提供比较功能。插入时各节点顺序以该仿函数为纲。

以std::pair为关键字掺入map
下面我们先写一个有错误的函数,在分析错误原因之后,逐步进行修正。

#include <map>
int main()
{
       std::map<std::pair<int, int>, int> res;
       res.insert(std::make_pair(12,33), 33);
}


 这个程序一定失败,如果非要如此使用,上述a方法显然不适合,std::pair是已定义好的结构体不可修改。只能使用b方法了,定义一个比较类改造如下:

[cpp]  view plain copy
  1. #include <map>  
  2.   
  3. struct comp  
  4.   
  5. {  
  6.   
  7.        typedef std::pair<int, int> value_type;  
  8.   
  9.        bool operator () (const value_type & ls, const value_type &rs)  
  10.   
  11.        {  
  12.   
  13.               return ls.first < rs.first || (ls.first == rs.first && ls.second < rs.second);  
  14.   
  15.        }  
  16.   
  17. };  
  18.   
  19. int main()  
  20.   
  21. {  
  22.   
  23.        std::map<std::pair<int, int>, int, comp> res;  
  24.   
  25.        res.insert(std::make_pair(std::make_pair(12,33), 33));  
  26.   
  27.        res.insert(std::make_pair(std::make_pair(121,331), 331));  
  28.   
  29.        res.insert(std::make_pair(std::make_pair(122,332), 332));  
  30.   
  31.         
  32.   
  33.        std::map<std::pair<int, int>, int, comp>::iterator it = res.find(std::make_pair(121,331));  
  34.   
  35.        if (it == res.end())  
  36.   
  37.               printf("NULL"n");  
  38.   
  39.        else  
  40.   
  41.               printf("%d %d %d "n", it->first.first, it->first.second, it->second);  
  42.   
  43.     return 0;  
  44.   
  45. }  

 

以结构体或类为关键字插入map

[cpp]  view plain copy
  1. #include <map>  
  2.   
  3. struct st  
  4.   
  5. {  
  6.   
  7.        int a, b;  
  8.   
  9.        st():a(0), b(0){}  
  10.   
  11.        st(int x, int y):a(x), b(y){}  
  12.   
  13. };  
  14.   
  15. int main()  
  16.   
  17. {  
  18.   
  19.        std::map<struct st, int> res;  
  20.   
  21.        res.insert(std::make_pair(st(1,2), 12));  
  22.   
  23.        res.insert(std::make_pair(st(30,4), 34));  
  24.   
  25.        res.insert(std::make_pair(st(5,6), 56));  
  26.   
  27.         
  28.   
  29.        std::map<struct st, int>::iterator it = res.find(st(30,4));  
  30.   
  31.        if (it == res.end())  
  32.   
  33.               printf("NULL"n");  
  34.   
  35.        else  
  36.   
  37.               printf("first:%d second:%d %d"n", it->first.a, it->first.b, it->second);  
  38.   
  39.        return 0;  
  40.   
  41. }  

编译这个程序也是错误的,错误意思大概也是没有定义“<”比较函数。因为struct st是我们自己定义的结构体,所以修改这个程序可以使用上面ab两种方法。我们先谈第一种,第一次修改时我也搞错了,我是这样定义比较函数的。

[cpp]  view plain copy
  1. struct st  
  2.   
  3. {  
  4.   
  5.        int a, b;  
  6.   
  7.        st():a(0), b(0){}  
  8.   
  9.        st(int x, int y):a(x), b(y){}  
  10.   
  11. bool operator < (const struct st &rs) {return (this->a < rs.a || (this->a == rs.a && this->b < rs.b));}  
  12.   
  13. };  

按照这个改动再次编译程序还是错误,有个如下这样的提示:

/usr/include/c++/3.2.3/bits/stl_function.h:197: passing `const st' as `this' argument of `bool st::operator<(const st&)' discards qualifiers

       为什么会出现这个 问题呢?我们深入STL的源代码看下。既然说是/usr/include/c++/3.2.3/bits/stl_function.h的197行出了问题,且看这行是什么。

   193 /// One of the @link s20_3_3_comparisons comparison functors@endlink.

   194 template <class _Tp>

   195 struct less : public binary_function<_Tp,_Tp,bool>

   196 {

   197       bool operator()(const _Tp& __x, const _Tp& __y) const { return __x < __y; }

   198 };

 

struct st中的“<”在编译后真正是什么样子呢?大概是bool operator < (struct st &ls, const struct st &rs)。在less调用这个比较符时,它都是以const方式传入,不可能再以非const方式调用,故出错。修正如下

struct st

{

       int a, b;

       st():a(0), b(0){}

       st(int x, int y):a(x), b(y){}

       friend bool operator < (const struct st &ls, const struct st &rs);

};

inline bool operator < (const struct st &ls, const struct st &rs)

{return (ls.a < rs.a || (ls.a == rs.a && ls.b < rs.b));}

 以友联函数代替函数内部定义的比较操作符,STL内部也多是以这种方式定义的。如果我非要以内部定义的方式呢?可以使用b方法,我们自定义一个比较仿函数,替代默认的less。

插入函数返回值
       在map容器中插入数据有很多函数可用,这里只讨论最普通的insert操作,在STL中它是这样定义的。

       pair<iterator, bool> insert(const value_type& x);

       map容器不允许键值重复,在执行插入操作后,可以凭借该返回值获取操作结果。返回值是一个迭代器和布尔值的键值对,迭代器指向map中具有该值的元素,布尔值表示是否插入成功。如果布尔值为true,表示插入成功,则迭代器为新插入值在map中的位置;布尔值为false,表示插入失败(已经存在该值),迭代器为原有值在map中的位置。

[cpp]  view plain copy
  1. #include <map>  
  2. #include <iostream>  
  3. using namespace std;  
  4.   
  5. class Key  
  6. {  
  7. public:  
  8.     Key();  
  9.     Key(int v);  
  10.     int _key;  
  11.     ~Key();  
  12.     /*重载<作为成员函数不行,两个操作数都要求是const*/  
  13.     //bool operator <(const Key& key);  
  14. };  
  15. bool operator <(const Key &key1,const Key &key2)  
  16. {  
  17.     if(key1._key<key2._key)  
  18.         return true;  
  19.     else  
  20.         return false;  
  21. }  
  22. Key::Key()  
  23. {  
  24. }  
  25. Key::Key(int v)  
  26. {  
  27.     _key=v;  
  28. }  
  29. Key::~Key()  
  30. {  
  31. }  
  32.   
  33. void main()  
  34. {  
  35.       
  36.     map<Key,int> ClassMap;  
  37.     Key one(1);  
  38.     ClassMap.insert(make_pair(one,1));  
  39.     Key two(2);  
  40.     ClassMap.insert(make_pair(two,2));  
  41.     Key three(3);  
  42.     ClassMap.insert(make_pair(three,3));  
  43.     map<Key,int>::iterator itor=ClassMap.begin();  
  44.     while(itor!=ClassMap.end())  
  45.     {  
  46.         cout<<itor->first._key<<" ~~ "<<itor->second<<endl;  
  47.         ++itor;  
  48.     }  

© 著作权归作者所有

共有 人打赏支持
涩女郎
粉丝 35
博文 104
码字总数 160210
作品 0
浦东
高级程序员
私信 提问
第十章 Scala 容器(四):使用Map方法解决问题

Map相关方法(Common methods for immutable and mutable maps) 1. 不可变Map相关方法(Methods for immutable maps) m - k:返回新的Map,内容为m去掉key=k的元素 scala> val m = Map(1......

阿拉德大陆的魔法师
2016/04/03
126
0
Map以自定义类做为键值

map在STL中的定义 template , class Alloc = alloc> 第一个参数Key是关键字类型 第二个参数T是值类型 第三个参数Compare是比较函数(仿函数) 第四个参数是内存配置对象 map内部存储机制实际...

晨曦之光
2012/04/13
1K
0
通过java api提交自定义hadoop 作业

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/qq1010885678/article/details/43734989 通过API操作之前要先了解几个基本知识 一、hadoop的基本数据类型和j...

jchubby
2015/02/11
0
0
5.Java基础复习----Map

1.Map java.util.Map<K,V> interface 实现Map接口的类用来存储键-值 对; 可以存储null键 Map类中存储的键 -- 值 对通过键来标识,所以键值不能重复 public int size();集合大小 public boo...

baibuxiha
2016/01/24
14
0
详解HashMap,Hashtable,LinkedHashMap,TreeMap的异同点

Map Map是是一种数据结构,它是把数据按照key-value键值对的形式保存起来,一般来说,Map的定义是key是独一无二的,即存在map中的各个键一定是不能相同的。当然,对于一般的基本数据类型和S...

断桥残雪断桥残雪
2015/08/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

js垃圾回收机制和引起内存泄漏的操作

JS的垃圾回收机制了解吗? Js具有自动垃圾回收机制。垃圾收集器会按照固定的时间间隔周期性的执行。 JS中最常见的垃圾回收方式是标记清除。 工作原理:是当变量进入环境时,将这个变量标记为“...

Jack088
昨天
17
0
大数据教程(10.1)倒排索引建立

前面博主介绍了sql中join功能的大数据实现,本节将继续为小伙伴们分享倒排索引的建立。 一、需求 在很多项目中,我们需要对我们的文档建立索引(如:论坛帖子);我们需要记录某个词在各个文...

em_aaron
昨天
27
0
"errcode": 41001, "errmsg": "access_token missing hint: [w.ILza05728877!]"

Postman获取微信小程序码的时候报错, errcode: 41001, errmsg: access_token missing hint 查看小程序开发api指南,原来access_token是直接当作parameter的(写在url之后),scene参数一定要...

两广总督bogang
昨天
31
0
MYSQL索引

索引的作用 索引类似书籍目录,查找数据,先查找目录,定位页码 性能影响 索引能大大减少查询数据时需要扫描的数据量,提高查询速度, 避免排序和使用临时表 将随机I/O变顺序I/O 降低写速度,占用磁...

关元
昨天
15
0
撬动世界的支点——《引爆点》读书笔记2900字优秀范文

撬动世界的支点——《引爆点》读书笔记2900字优秀范文: 作者:挽弓如月。因为加入火种协会的读书活动,最近我连续阅读了两本论述流行的大作,格拉德威尔的《引爆点》和乔纳伯杰的《疯传》。...

原创小博客
昨天
35
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部