歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

C++ 中各種map的使用

C++中有很多中key-value形式的容器,map/hash_map/unordered_map/vector_map。下面講述各個map的使用及其區別。

首先,map的基本使用方法如下:

#include <iostream>
#include <map>
using namespace std;

typedef std::map<int, string> Map;
typedef Map::iterator MapIt;

int main()
{
 Map *map = new Map();
 int key;
 string value;
 while(cin>>key>>value)
 {
  map->insert(make_pair(key, value));
 }
 for(MapIt it = map->begin(); it != map->end(); ++it)
  cout<<"key:"<<it->first<<" value:"<<it->second<<endl;
 delete map;
 return 0;
}

map使用紅黑樹實現。查找時間在O(lg(n))-O(2*log(n))之間,構建map花費的時間比較長,因而,map使用於那種插入和查詢混合的情況。如果是先插入後查詢的情況,可以考慮使用vector_map.

vector_map在C++中沒有實現,想使用可以自己實現。其基本思想在於使用vector來保存數據,插入完成後進行排序,然後使用而分查找進行查詢。這樣在先插入後查詢的條件下,性能會比map好很多。原因主要在一下幾個方面。

  1. vector使用線性存儲,map是二叉樹形狀,所以vector的局部性更好。
  2. vector可以一次分配很大的內存,而map需要每次分配一個節點,而且map中相對於vector有很多冗余數據,比如指向子節點的指針。
  3. vector是插入完成後統一進行排序,而map每次insert都有一次查找和樹的旋轉。
  4. vector_map是二分查找,查找時間穩定在O(lg(n)),而map的存儲結構是紅黑樹,查找時間為O(lg(n))-O(2*log(n))。

map的key可以是自定義數據結構,但是需要重載<運算符。如下代碼所示:

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

Copyright © Linux教程網 All Rights Reserved