当前位置: 首页 > 工具软件 > Map picasso > 使用案例 >

about map

柴飞星
2023-12-01

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

 类似资料:

相关阅读

相关文章

相关问答