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;
}