注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

回首望星辰

See you in the next world

 
 
 

日志

 
 

STL中的map和multimap  

2009-10-22 14:45:07|  分类: 软件开发 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

某网友提问:

0000172009010199999999001         他们对应的结构体是id[7];date[9],date[9];item[4]

0000202009010299999999001         这是一个纯文本文件,名字叫info(d:\info)

0000222009010399999999003

0000232009010499999999002

0000242009010599999999005

0000302009010699999999001

 

说明:A参数是一个6位的字符串,比如说是000017;由于info文件特别大,查找A是否与info中的id匹配时,要用二分法进行查找(info中已经按id排好序了),要用c++实现下面的函数,请高手帮忙!!!!!!

int  getValue( char A )

{

         if(A与info文件中id匹配,并却id对应的item是“001”的话){return 1;}

         if(A与info文件中id匹配,并却id对应的item是“002”的话){return 2;}

}

以前还碰到一个类似的问题,是在Window Mobile上的。

这个问题的解决办法有很多,用二分法自然是其中一个。但在这里,我想用STL中的map或者multimap来解决问题。

 

1) key单一的情况,用map

#include <iostream>

#include <fstream>

#include <map>

#include <string>

using namespace std;

 

// 假定info.txt的内容是:

// 0000172009010199999999001

// 0000202009010299999999001

// 0000222009010399999999003

// 0000232009010499999999002

// 0000242009010599999999005

// 0000212009010599999999005   <<<  strkey为000021,目前排第6

// 0000302009010699999999001

//* 用map的方式解决

int main(void)

{

         ifstream fin("info.txt");

         if(!fin)

         {

                   cout << "can not open file..." << endl;

         }

 

         // 创建map,第一个string做为key,第二个string作为value

         map<string, string> linemap;

         string strkey;

         string strvalue;

         char linestring[26];

         while(fin)

         {

                   // 读取info.txt的一行,存入linestring

                   fin.getline(linestring, 26);

 

                   // 将lingstring赋值给strvalue

                   strvalue = linestring;

 

                   // 取前位作为key

                   strkey = strvalue.substr(0, 6);

 

                   // 将key,value对存入map中

                   linemap.insert(pair<string, string>(strkey, strvalue));

         }

         fin.close();

 

         // 设定要查找的字符串,将查得的结果存入stringresult中

         string s = "000017";

         string stringresult;

         // 声明iterator

         map<string, string>::iterator p;

        

         // 检查数据被插入后,是否根据strkey排序了 ->  结论:排序了

         // 即使info.txt中有重复的key,也只会有第一行含有key的文本,会被读入到map中

         for(p = linemap.begin(); p != linemap.end(); ++p)

         {

                   cout << p->second << endl;

         }

 

         // 查找。用find的方式只能得到符合结果的第一条记录

         p = linemap.find(s);

 

         // 如果找到

         if(p != linemap.end())

         {

                   // 将p->second,即被找到符合条件记录的strvalue赋给stringresult

                   stringresult = p->second;

 

                   // 拆分stringresult

                   cout << "   id: " << stringresult.substr(0,6) << endl;

                   cout << "date1: " << stringresult.substr(6, 8) << endl;

                   cout << "date2: " << stringresult.substr(14, 8) << endl;

                   cout << " item: " << stringresult.substr(22) << endl;

         }

         return 0;

}

 

//  所得结果如下:

//  0000172009010199999999001

//  0000202009010299999999001

//  0000212009010599999999005    <<< 根据strkey,被排到了前面,即第3的位置

//  0000222009010399999999003

//  0000232009010499999999002

//  0000242009010599999999005

//  0000302009010699999999001

//  The result is: 0000172009010199999999001

//     id: 000017

//  date1: 20090101

//  date2: 99999999

//   item: 001

 

我们知道,the main characteristics of a map as an associative container are:

- Unique key values: no two elements in the map have keys that compare equal to each other. 即不能有重复的key。

- Each element is composed of a key and a mapped value.

- Elements follow a strict weak ordering at all times. 也就说是插入效率相对较低,因为在插入时,对根据key来做排序。

 

2) key有重复的情况,用multimap

如果需要处理有重复的key,那么就要用到multimap。

#include <iostream>

#include <fstream>

#include <map>

#include <string>

using namespace std;

// 用multimap解决,解决有重复的key

// 假定info.txt的内容如下

// 0000172009010199999999001    <<< 重复

// 0000172009010199999999002    <<< 重复

// 0000172009010199999999003    <<< 重复

// 0000172009010199999999004    <<< 重复

// 0000202009010299999999001

// 0000222009010399999999003

// 0000232009010499999999002

// 0000242009010599999999005

// 0000302009010699999999001

int main(void)

{

         ifstream fin("info.txt");

         if(!fin)

         {

                   cout << "can not open file..." << endl;

         }

 

         // 创建multimap,第一个string做为key,第二个string作为value

         multimap<string, string> linemap;

         multimap<string, string>::iterator it;

         pair<multimap<string, string>::iterator, multimap<string, string>::iterator> ret;

         string strkey;

         string strvalue;

         char linestring[26];

         while(fin)

         {

                   // 读取info.txt的一行,存入linestring

                   fin.getline(linestring, 26);

                   // 将lingstring赋值给strvalue,它value(有点数据冗余,纯为编程简单起见)

                   strvalue = linestring;

 

                   // 取前位作为key

                   strkey = strvalue.substr(0, 6);

 

                   // 将key,value对存入map中

                   linemap.insert(pair<string, string>(strkey, strvalue));

         }

         fin.close();

 

         // 设定查找字符串为"000017"

         string s = "000017";

         // stringresult用来取出一个返回文本行

         string stringresult;

 

         // 当返回结果中的记录数量超过是,必须用equal_range函数代替find方法。

         // equal_range函数的返回值:

         // The function returns a pair, where its member pair::first is an iterator to the lower bound of the range with the same

         // value as the one that would be returned by lower_bound(x), and pair::second is an iterator to the upper bound of the

         // range with the same value as the one that would be returned by upper_bound(x).

 

         ret = linemap.equal_range(s);

 

         for(it = ret.first; it != ret.second; it++)

         {

                   // stringresult就是要找的结果

                   stringresult = it->second;

                   cout << stringresult << endl;

 

                   // 拆分stringresult

                   cout << "   id: " << stringresult.substr(0,6) << endl;

                   cout << "date1: " << stringresult.substr(6, 8) << endl;

                   cout << "date2: " << stringresult.substr(14, 8) << endl;

                   cout << " item: " << stringresult.substr(22) << endl;

         }

         return 0;

}

 

//  所得结果如下(返回了条id为的记录):

//  0000172009010199999999001

//     id: 000017

//  date1: 20090101

//  date2: 99999999

//   item: 001

//  0000172009010199999999002

//     id: 000017

//  date1: 20090101

//  date2: 99999999

//   item: 002

//  0000172009010199999999003

//     id: 000017

//  date1: 20090101

//  date2: 99999999

//   item: 003

//  0000172009010199999999004

//     id: 000017

//  date1: 20090101

//  date2: 99999999

//   item: 004

//

 

3) 大数据量处理

如果的info.txt非常巨大,那么就不能将整行的数据作为strvalue存入map了,因为那样可能会吃掉很多内存, 解决的办法就是,将行号作为value存入即可,那么查询的结果得到就是行号,有了行号就可以很容易定位到那一行,从而取出该行的数据。当然这时候multimap应该声明成:multimap <string, int> linemap;

// 生成info.txt的据程序

// info.txt中有900万行数据,大小近250M

int main ()

{

         char buffer[28];

         clock_t start, finish;

         ofstream outfile ("info.txt");

 

         // 获取写物理文件起始时钟周期

         start = clock();

         for(int i = 0; i < 9000001; i++)

         {

                   sprintf(buffer, "%07d2009010120090606%03d\n", i, i%1000);

                   outfile.write (buffer, strlen(buffer));

         }

         // 获取写文件结束时钟周期

         finish = clock();

         int interval = (finish - start) * 1000 / CLOCKS_PER_SEC;

         cout << "写物理文件所花时间:" << interval << "ms" << endl;

         outfile.close();

 

         return 0;

}

// 显示结果:

// 写物理文件所花时间:20329ms

 

 

// 用multimap处理大数据量的问题的程序

#include <iostream>

#include <fstream>

#include <map>

#include <string>

using namespace std;

 

int main(void)

{

         ifstream fin("info.txt");

         if(!fin)

         {

                   cout << "can not open file..." << endl;

         }

 

         // 创建map,string作为key,int作为value

         multimap<string, int> linemap;

         multimap<string, int>::iterator it;

         pair<multimap<string, int>::iterator, multimap<string, int>::iterator> ret;

         string strkey;

         string strtemp;

         int intvalue = 0;

         char linestring[27];

 

         clock_t start, finish;

         int interval;

         start = clock();

         while(fin)

         {

                   // 读取info.txt的一行,存入linestring

                   fin.getline(linestring, 27);

                   strtemp = linestring;

 

                   // 取前7位作为key

                   strkey = strtemp.substr(0, 7);

 

                   // 将key,value(行号)对存入map中

                   linemap.insert(pair<string, int>(strkey, intvalue));

 

                   // 将行号加1

                   intvalue++;

         }

         fin.close();

         // 取结束时钟周期

         finish = clock();

         interval = (finish - start) * 1000 / CLOCKS_PER_SEC;

 

         cout << "读取info.txt到multimap所花时间:" << interval << "ms" << endl;

 

         // 设定查找字符串

         string s = "0899946";

         // intresult用来取出一个返回的行号

         int intresult;

 

         // 当返回结果中的记录数量超过是,必须用equal_range函数代替find方法。

         // equal_range函数的返回值:

         // The function returns a pair, where its member pair::first is an iterator to the lower bound of the range with the same

         // value as the one that would be returned by lower_bound(x), and pair::second is an iterator to the upper bound of the

         // range with the same value as the one that would be returned by upper_bound(x).

         

         ret = linemap.equal_range(s);

         // 获取查询起始时钟周期

         start = clock();

         for(it = ret.first; it != ret.second; it++)

         {

                   // stringresult就是要找的结果

                   intresult = it->second;

                   cout << intresult << endl;

         }

         // 获取查询结束时钟周期

         finish = clock();

         interval = (finish - start) * 1000 / CLOCKS_PER_SEC;

         cout << "查询所花时间:" << interval << "ms" << endl;

 

         // 从物理文件中读取刚才查询到的一行

         // 获取读取物理文件起始时钟周期

         start = clock();

         ifstream fin2("info.txt");

         if(!fin2)

         {

                   cout << "can not open file..." << endl;

         }

         char buffer[27];

         fin2.seekg(intresult * 28);

         fin2.read(buffer, 27);

         buffer[27] = 0;

         fin2.close();

         // 获取读取物理文件结束时钟周期

         finish = clock();

         interval = (finish - start) * 1000 / CLOCKS_PER_SEC;

         cout << "读取物理文件所花时间:" << interval << "ms" << endl;

 

         cout << buffer << endl;

 

         return 0;

}

// 显示结果:

// 读取info.txt到multimap所花时间:30904ms

// 899946

// 查询所花时间:0ms

// 读取物理文件所花时间:10ms

// 08999462009010120090606946

补充说明:

a.       上面的程序是在T42/主频1.6G/内存1.2G(单核)上完成的。说明map的写入性能略低(其实也很不错),查询性能是非常好的。

b.       返回多条重复记录的情况,和返回单条记录所消耗的时间几乎没有差别

 

本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/pathuang68/archive/2009/06/06/4248013.aspx

  评论这张
 
阅读(3779)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017