about map

std::map内置的数据结构是红黑树。一般在对大量数据进行频繁的插入或删除和查找时，才考虑用上二叉

树，甚至在考虑快速查找时用上hash_map。如果数据量很少，那就用vector，此时效率已经不是考虑的因

素。map的优势是，在给定key value时，能够快速找到mapped value，另外，它的使用有时可以简化算法

和简化编写代码的难度。vector的优势是，在给定相对或绝对位置时，它能快速找到对应的值。

map插入的时间复杂度是O(log(N))，并不是很快，而且map在存储上有一定的空间开销。
有时候为了快速查找，用已经排序的vector跟二分查找算法就可以满足要求了。

map的元素就是一个pair<Key, Value>，这里的key value跟它的映射值mapped value是关联起来的，所以

map是一个关联（联合）容器。map的key value是唯一的，如果进一步可以不唯一的话就是multimap了。

如果不需要mapped value，而只需要key value，那就是set了。

map的声明形式：
template < class Key, class T, class Compare = less<Key>,
           class Allocator = allocator<pair<const Key,T> > > class map;

Key跟T分别是key value和mapped value的类型。

Compare是比较函数类，在map插入数据时（插入pair），这个比较函数将被使用，它决定了哪个元素放在

前面哪个元素放在后面。这个函数输入的参数是两个Key类型的key value。默认使用的是less<Key>，就

是简单的Key a, b; return a < b; 可以写自己的compare函数，以实现自己希望的排序结果。这是一个

例子：
  // 默认情况下只是使insert进的指针大小有序,不管它指向的string
  // 现在写自己的仿函数类来实现自定义的"有序"
  struct  CompairStringPtr
  {
   bool operator( )( string const * pStrLeft,
    string const * pStrRight ) const
   {
    return *pStrLeft < *pStrRight;  // 字母从小到大为"有序"
   }
  };

  typedef map<string*, int, CompairStringPtr >  StringPtrMap;

Allocator是内存分配器。

 

//map的一个使用测试程序:

// test in vs2005

#include < map >
#include < string >
#include < iostream >

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
 map< string, int > map_test;

 map_test[ "abc" ]  = 1;  //insert
 map_test[ "aab" ]  = 2;

 pair< string, int >  insert_pair( "ade", 3 );
 map_test.insert( insert_pair );  //insert

 map_test.insert( make_pair< string, int >( "fff", 4) );   //insert

 map< string, int >::iterator  ite_find = map_test.begin( );
 ite_find = map_test.find( "abc" );  //find
 if ( ite_find != map_test.end( ) )
 {
  cout << ite_find->first << "  FOUND " << " sencode: "
   << ite_find->second << endl;
 }

 //"abc" 已经存在, vc跟vs2005均不会插入成功--原value不会被修改
     map_test.insert( make_pair< string, int >( "abc", 99 ) ); 

 ite_find = map_test.find( "abc" );
 if ( ite_find != map_test.end( ) )
 {
  cout << ite_find->first << "  FOUND " << " sencode: "
   << ite_find->second << endl;
 }

 cout << endl;
 int iValue = map_test[ "abc" ];  //由key取value，优势所在
 cout << "abc value: " << iValue << endl;

 cout << endl;
 ite_find = map_test.find( "abc" );
 if ( ite_find != map_test.end( ) )
 {
  cout << "modify abc now " << endl;
  ite_find->second = 123;  //修改value
  cout << "after modified, abc value: " << ite_find->second << endl;
  //ite_find->first = "abc";  //不允许修改key
 }

 cout << endl;
 // erases
 cout << "erase abc now " << endl;
 int iDelCount = map_test.erase( "abc" ); //返回成功删除的个数
 cout << "erase count: " << iDelCount << endl;

 cout << endl;
 cout << "all key and value now: " << endl;
 map< string, int >::iterator  ite_loop = map_test.begin( );
 for ( ; ite_loop != map_test.end( ); ++ite_loop )
 {
  cout << "first: " << ite_loop->first << "  second: "
   << ite_loop->second << endl;
 }

 return 0;
}