C++ 中各种map的使用(2)

需要注意的是，重载函数必须为const的。

当然，你也可以这么做：

typedef struct _Key
{
 _Key(int *p, int l)
 {
  len_ = l;
  for(int i = 0; i < l; ++i)
   p_[i] = p[i];
 }
 int p_[MaxLen];
 int len_;
}Key;
typedef struct _KeyCmp
{
 bool operator()(const Key &ls, const Key &rs)
 {
  if(ls.len_ == rs.len_)
  {
   for(int i = 0; i < ls.len_; ++i)
    return ls.p_[i] < rs.p_[i];
   return false;
  }
  else
   return ls.len_ < rs.len_;
 }
}KeyCmp;
typedef std::map<Key, vector<int> *, KeyCmp> MyMap;

与上面有相同的效果。

hash_map，STL中的实现叫做unordered_map，都是基于hash_table实现的。首先，分配一大片内存，形成很多桶。利用hash函数，将key映射到不同的桶中，当然，也有可能会有两个不同的key映射到同一个桶中，这是，就需要判别函数来进行查找了。所以，hash_map的key需要两个条件，一个是hash函数，获得映射到的桶的值，另外一个是equal_to函数，判定两个key是否相等。显然，当每个桶里的元素个数比较平均且比较少的时候，查询性能比较高。

使用样例如下：

#include <string>
#include <iostream>
#include <ext/hash_map>
using namespace std;
using namespace __gnu_cxx;

struct str_hash
{
 size_t operator()(const string &s) const
 {
  return __stl_hash_string(s.c_str());
 }
};

struct str_compare
{
 int operator()(const string &a, const string &b) const
 {
  return (a==b);
 }
};
typedef hash_map<string, string, str_hash, str_compare> StrMap;

int main()
{
 StrMap strMap;
 string a,b;
 cout<<"插入:"<<endl;
 while(cin>>a>>b)
 {
  if(a.length() <= 1)
   break;
  strMap.insert(make_pair(a,b));
 }
 cout<<"查询:"<<endl;
 while(cin>>a)
 {
  if(a.length() <= 1)
   break;
  if(strMap.find(a) != strMap.end())
   cout<<strMap[a]<<endl;
  else
   cout<<"not found"<<endl;
 }
 return 0;
}