宁静的天空

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  5 随笔 :: 0 文章 :: 3 评论 :: 0 Trackbacks
题目如下:
设计一双向map;
1,key可以找到value,value也可以找到key;
2,key和value的对应关系是多对多的关系;
3,key的值为1000万左右,最大为2000万;
4,value为char[128],最多为1000万个;
5,尽量对设计进行优化;
 1 class Data
 2 {
 3     public:
 4       Data(char *);
 5       ~Data();
 6       Data &operator=(char *);
 7       //比较两个对象是否相等,如果指针相同则相等,如果指针不同,内容相同,也是相等!!
 8       bool operatoe==(const Data &tmpdata)const
 9       {
10          if(tmpdata.m_lpdata == this->m_lpdata)
11             return true;
12          if(tmpdata.m_lpdata == NULL || this->m_lpdata == NULL)
13             return false;
14          if(memcmp(tmpdata.m_lpdata,this->m_lpdata,128)!=0)
15             return false;
16          return true;
17       };
18       bool operatoe<(const Data &tmpdata)const
19       {
20          if(tmpdata.m_lpdata == this->m_lpdata)
21             return false;
22          if(tmpdata.m_lpdata == NULL || this->m_lpdata == NULL)
23             return false;
24          if(memcmp(this->m_lpdata,tmpdata.m_lpdata,128)<0)
25             return true;
26          return false;
27       };
28    private:
29       char *m_lpdata;
30       Data();
31 };
32 //内存管理,管理所有存储数据;该处可以简单实现,也可复杂实现;看实际情况;
33 class MemManager
34 {
35 };
36 class DoubleLinkMap
37 {
38     public:
39       DoubleLinkMap();
40       ~DoubleLinkMap();
41    private:
42       //内存管理
43       MemManager m_memmanager;
44       //数据结构
45       #define MAXKEYVALUE 20000000
46       std::list<char *> m_KeyArray[MAXKEYVALUE];
47       std::multimap<Data,int> m_mulmap_value_key;
48 };
49 
对以上数据结构说明:
1,由key获取value,直接访问m_KeyArray,其下标为key,那么得到的值为list,该list为指定key的所有value指针组成的list;可以由指针直接获取到数据;
2,由数据获取key,使用m_mulmap_value_key的lower_bound及upper_bound操作,直接可以获取到指定Data的所有key;主要实现了Data的==及<操作运算符,这两个运算符优先判断指针是否相等,后判断数据是否的大小;
3,当对数据进行删除操作时,比较麻烦些,如果删除指定key的所有value,那么需要通过m_KeyArray找到所有value的指针,然后再挨个删除所有指针在m_mulmap_value_key里的映射;注意,删除时需要判断key是否相等再删除;
4,对内存管理这里有了一个说明,可以对存储所有value的内存进行优化;暂时没有写关于内存管理的部分;
posted on 2011-12-16 00:25 heying 阅读(2978) 评论(2)  编辑 收藏 引用 所属分类: 技术文章

评论

# re: 双向map简单讨论 2011-12-16 15:32 陈梓瀚(vczh)
直接把两个map封装起来不行吗……这样查询速度会更快  回复  更多评论
  

# re: 双向map简单讨论 2011-12-19 10:42 heying
@陈梓瀚(vczh)
使用两个map简单实现的话,缺点有以下几个:
1,由key找到value需要多次查询;
2,内存存储value存储了两份;
3,对数据的删除可能需要多次内存操作;  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理