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好很多。原因主要在一下几个方面。
vector使用线性存储，map是二叉树形状，所以vector的局部性更好。
vector可以一次分配很大的内存，而map需要每次分配一个节点，而且map中相对于vector有很多冗余数据，比如指向子节点的指针。
vector是插入完成后统一进行排序，而map每次insert都有一次查找和树的旋转。
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;