还记得Herb Sutter那极有味道的《C++对话系列》么，在其中《产生真正的hash对象》这个故事里就讲了map的选择。顺便回顾一下，也讲一下我在实用中的理解。

　 　选择map容器，是为了更快的从关键字查找到相关的对象。与使用list这样的线性表容器相比，一可以简化查找的算法，二可以使任意的关键字做索引，并 与目标对象配对，优化查找算法。在C++的STL中map是使用树来做查找算法，这种算法差不多相当与list线性容器的折半查找的效率一样，都是O (log2N)，而list就没有map这样易定制和操作了。

　　相比hash_map，hash_map使用hash表来排列配 对，hash表是使用关键字来计算表位置。当这个表的大小合适，并且计算算法合适的情况下，hash表的算法复杂度为O(1)的，但是这是理想的情况下 的，如果hash表的关键字计算与表位置存在冲突，那么最坏的复杂度为O(n)。

　　那么有了这样的认识，我们应该怎么样选用算法 呢？前两天看Python文章的时候，不知道哪个小子说Python的map比c++的map快，如何如何的。但是他并不知道Python是默认使用的 hash_map，而且这些语言特征本质上是使用c/c++写出来的，问题在与算法和手段，而不是在于语言本身的优劣，你熟悉了各种算法，各种语言的细 节、设计思想，还能在这偏激的嚷嚷孰好孰坏(片面与偏激的看待事物只能表明愚昧与无知，任何事物都有存在的价值，包括技术)。显然C++的STL默认使用 树结构来实现map，是有考究的。

　　树查找，在总查找效率上比不上hash表，但是它很稳定，它的算法复杂度不会出现波动。在一次 查找中，你可以断定它最坏的情况下其复杂度不会超过O(log2N)。而hash表就不一样，是O(1)，还是O(N)，或者在其之间，你并不能把握。假 若你在开发一个供外部调用的接口，其内部有关键字的查找，但是这个接口调用并不频繁，你是会希望其调用速度快、但不稳定呢，还是希望其调用时间平均、且稳 定呢。反之假若你的程序需要查找一个关键字，这个操作非常频繁，你希望这些操作在总体上的时间较短，那么hash表查询在总时间上会比其他要短，平均操作 时间也会短。这里就需要权衡了。

　　这里总结一下，选用map还是hash_map，关键是看关键字查询操作次数，以及你所需要保证 的是查询总体时间还是单个查询的时间。如果是要很多次操作，要求其整体效率，那么使用hash_map，平均处理时间短。如果是少数次的操作，使用 hash_map可能造成不确定的O(N)，那么使用平均处理时间相对较慢、单次处理时间恒定的map，考虑整体稳定性应该要高于整体效率，因为前提在操 作次数较少。如果在一次流程中，使用hash_map的少数操作产生一个最坏情况O(N)，那么hash_map的优势也因此丧尽了。

#include <string>
#include <ext/hash_map>
#include <iostream>

using namespace std;
// some STL implementations do not put hash_map in std
using namespace __gnu_cxx;

hash_map<const char*, int> days_in_month;

class MyClass {
   static int totalDaysInYear;
public:
   void add_days( int days ) { totalDaysInYear += days; }
   static void printTotalDaysInYear(void) 
   { 
       cout << "Total Days in a year are " 
           << totalDaysInYear << endl; 
   }
};

int MyClass::totalDaysInYear = 0;

int main(void)
{
   days_in_month["january"] = 31;
   days_in_month["february"] = 28;
   days_in_month["march"] = 31;
   days_in_month["april"] = 30;
   days_in_month["may"] = 31;
   days_in_month["june"] = 30;
   days_in_month["july"] = 31;
   days_in_month["august"] = 31;
   days_in_month["september"] = 30;
   days_in_month["october"] = 31;
   days_in_month["november"] = 30;
   days_in_month["december"] = 31;

// ERROR: This line doesn't compile.
   accumulate( days_in_month.begin(), days_in_month.end(),
       mem_fun( &MyClass::add_days ));

MyClass::printTotalDaysInYear();

return 0;
}

//测试3个环节:用map的效率,hash_map系统hash函数的效率及自写hash函数的效率.

11 struct str_hash{      //自写hash函数
    12     size_t operator()(const string& str) const
    13     {
    14         unsigned long __h = 0;
    15         for (size_t i = 0 ; i < str.size() ; i ++)
    16         {
    17             __h = 107*__h + str[i];
    18         }
    19         return size_t(__h);
    20     }
    21 };

23 //struct str_hash{    //自带的string hash函数
    24 //        size_t operator()(const string& str) const
    25 //      {
    26 //          return __stl_hash_string(str.c_str());
    27 //      }
    28 //};

30 struct str_equal{      //string 判断相等函数
    31     bool operator()(const string& s1,const string& s2) const
    32     {
    33         return s1==s2;
    34     }
    35 };

//用的时候
    37 int main(void)
    38 {
    39     vector<string> filtered_list;
    40     hash_map<string,int,str_hash,str_equal> file_map;
    41     map<string,int> file2_map;
    42     ifstream in("/dev/shm/list");
    43     time_t now1 = time(NULL);
    44     struct tm * curtime;
    45     curtime = localtime ( &now1 );
    46     cout<<now1<<endl;
    47     char ctemp[20];
    48     strftime(ctemp, 20, "%Y-%m-%d %H:%M:%S" , curtime);
    49     cout<<ctemp<<endl;
    50     string temp;
    51     int i=0;
    52     if(!in)
    53     {
    54         cout<<"open failed!~"<<endl;
    55     }
    56     while(in>>temp)
    57     {
    58         string sub=temp.substr(0,65);
    59         if(file_map.find(sub)==file_map.end())
    60 //      if(file2_map.find(sub)==file2_map.end())
    61         {
    62             file_map[sub]=i;
    63 //          file2_map[sub]=i;
    64             filtered_list.push_back(temp);
    65             i++;
    66 //          cout<<sub<<endl;
    67         }
    68     }
    69     in.close();
    70     cout<<"the total unique file number is:"<<i<<endl;
    71     ofstream out("./file_list");
    72     if(!out)
    73     {
    74         cout<<"failed open"<<endl;
    75     }
    76     for(int j=0;j<filtered_list.size();j++)
    77     {
    78         out<<filtered_list[j]<<endl;
    79     }
    80     time_t now2=time(NULL);
    81     cout<<now2<<endl;
    82     curtime = localtime ( &now2 );
    83     strftime(ctemp, 20, "%Y-%m-%d %H:%M:%S" , curtime);
    84     cout<<now2-now1<<"/t"<<ctemp<<endl;
    85     return 0;
    86 }