C++ map & hash_map
1.Map的使用 map简介： map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字key，每个关键字只能在map中出现一次（multimap是可以出现多个关键字的），第二个可能称为该关键字的值alue）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建
·
1.Map的基本使用
map简介：
map是STL的一个关联容器，可以理解为关联数组。它提供一对一（其中第一个可以称为关键字key，每个关键字只能在map中出现一次（multimap是可以出现多个关键字的），第二个可能称为该关键字的值alue）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的，后边我们会见识到有序的好处。
它的特点是增加和删除节点对迭代器的影响很小，除了那个操作节点，对其他的节点都没有什么影响。对于迭代器来说，可以修改实值，而不能修改key。
map功能（为什么要使用map）
1.map可以提供key-value 类型的对应关系。key和value可以是我们任意需要的类型，提供编程的需要。例如我们可以创建一个int-string的key-value容器，用来存放学生的学号和姓名。形成一一对应的关系。
2.根据key值快速查找记录，查找的复杂度基本是Log(N)，如果有1000个记录，最多查找10次，1,000,000个记录，最多查找20次。
3.快速插入和删除记录。
4.可以根据key值快速修改value的值。
如何使用map
首先要使用map，必须包含map头文件，在定义的时候，需要知道key 和 value的类型。
1.定义map类型的对象
map< int, string > s1;
s1[1] = "hehe";
s1[2] = "haha";
map< int, string > s2(s1);//s2必须和s1有相同的key value 类型
map< int, string >::iterator start = s1.begin();
map< int, string >::iterator last = s1.end();
map< int, string > s3( start, last ); //start 和end 指向的类型必须能转换为pair<const int, string>
2. map中的类型。
map< K, V >::key_type //key的类型 就是K的类型
map< K, V >::mapped_type //value的类型 就是V的类型
map< K, V >::value_type //pair类型，first元素是const的key类型（K），second元素是value类型（V） cout << ( *start ).first << " " << ( *start ).second << endl;//对上文的代码进行解引用得到pair对象。
( *start ).second = "hehexixi";//OK
( *start ).first = 3;//Error: assignment of read-only member ‘std::pair<const int, std::basic_string<char> >::first
3.给map中添加元素。
1)使用下标访问map对象。
map< int, string > s1;
s1[1] = "hehe";
1.首先查找key为1的元素，没有找到 2.将一个新的key-value插入到s1中，key 为const int 类型， value为string类型。value值采取初始化，为空。并将这个新的key-value对插入到s1中。3.读取s1[1],并将其value赋值为"hehe".
使用key访问map的时候，如果不存在这个元素将会导致在map容器中添加一个新的元素。所关联的value采用值初始化。内置类型元素初始化为0，类类型则采用默认构造函数初始化。
2）map::insert的使用
1.m.insert(e) (e为pair类型的值 ,如果e.first不再map中则插入一个value为e.second的元素，如果存在则保持不变。返回pair类型，包含指向e.first的map迭代器，和一个bool类型的对象，表示是否已经插入该元素。（如果不存在则为true，存在则返回false).
map< int, string > s1;
typedef pair< map< int, string >::iterator, bool > returnPair;
returnPair p1 = s1.insert( map < int, string >::value_type ( 1, "haha" ) );
returnPair p2 = s1.insert( map < int, string >::value_type ( 1, "haha" ) );
cout << ( *p1.first ).second << " " << p1.second << endl;
cout << ( *p2.first ).second << " " << p2.second << endl;返回类型为pair类型，first元素为插入map的迭代器类型，第二个是bool对象。
返回值为 haha 1， haha 0，表示第一次成功插入，第二次没有成功插入。(已经存在）
2.m.insert(beg,end) beg 和end 是迭代器。元素必须是m.value_type类型的key- value。该操作将对于beg和end之间的所有元素插入到m，方式如1，如果存在，不变，如果不存在，插入。
map< int, string > s1;
s1.insert( map < int, string >::value_type ( 1, "haha" ) );
s1.insert( map < int, string >::value_type ( 2, "hehe" ) );
s1.insert( map < int, string >::value_type ( 3, "xixi" ) );
map< int, string >::iterator beg = s1.begin();
map< int, string >::iterator end = s1.end();
map< int, string > s2;
s2.insert( beg, end );
cout << s2[ 1 ] << " " << s2[ 2 ] << " " << s2[ 3 ] << endl;
map< int, string > s3;
cout << s3[ 1 ] << " " << s3[ 2 ] << " " << s3[ 3 ] << endl;
显示值为 haha hehe xixi 和 3个空，表示s2插入成功。
4.两种添加元素方式的区别。
我们通过上文可以得到两种插入元素的方法。采用下标和调用insert函数。那么他们之间的区别是什么呢？哪个效率更高呢？先看下代码
map< int, string > s3;
s3[1] = "haha";
s3[1] = "xixi";
cout << s3[1] << endl;
s3.insert( map< int, string >::value_type( 2,"haha" ) );
s3.insert( map< int, string >::value_type( 2,"xixi" ) );
cout << s3[2] << endl;
另外：insert插入的开销比较小。因为下标插入如果不存在的话会首先初始化value的值。如果是类对象的话，会调用构造函数。然后在根据value的值进行更新。造成多余的开销。
5.count 和find 函数来查找map中的元素。
用下标来判断元素是否存在是危险的，如果你想判断某个key是否存在，如果不存在，赋给它一个初始值，则用下标来操作是非常完美的。如果我们只想判断map中是否存在某个key，而不想插入它。则不可以使用下标操作来判断元素是否存在，map中提供了2个函数用来适应后边的这个情况。
m.count(key)//返回值为0或者1，如果存在返回1，如果不存在返回0
m.find(key)//如果存在则返回该key对应pair对象的迭代器，如果不存在返回map 的end 迭代器。 map< int, string > s3;
s3[1] = "haha";
s3.insert( map< int, string >::value_type( 2,"xixi" ) );
if( s3.count(1) )
cout << s3[1] << endl;
if( s3.find(1) != s3.end() )
cout << ( *s3.find(1) ).second << endl;这两个函数都可以用来查找map中是否存在某key对应的pair对象，区别是一个返回1或者0，另外一个返回迭代器。
6.map的删除操作
1）.m.erase(k) k必须为m 中的key-value类型中的key类型。删除m中key 为m的元素，返回size_type类型的值，表示删除的元素个数。0或者1
2）.m.erase(p) p是迭代器。删除p所指向的元素，且p不等与m.end()，返回为void
3）.m.erase(b,e) b 和e 都为迭代器，删除一段范围，且 b 和 e 都指向m中的元素，或者最后一个元素的下一个位置。且b必须在e前面。或者相等。
map进阶
我们上文了解了如何使用map，那么下面先介绍下map的优点：
1.map的插入删除效率比较高（相比与其他容器）
2.map 每次insert 后，以前保留的iterator不会失效。
3.当map中元素翻倍增加的时候，查找次数和搜索次数没有太大变化。
原因：C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树，也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般的平衡二叉树所以被STL选择作为了关联容器的内部结构。关于RB树的详细实现可以去专门查阅相关资料了解红黑树的实现。
map因为内部使用红黑树结构，所以插入和删除操作不需要进行内存移动。元素都是以节点的形式来存储。因此插入和删除只需要修改指针就OK了，与内存移动没有关系，内存没有变，所以以前的iterator不会失效。那么为什么vector等容器插入或者删除操作会导致iterator失效呢。
vector容器为了保证内存中内部数据的连续存放，插入或者删除过程中，原先iterator指向的内存可能被覆盖或者释放掉。即使是push_back也可能导致失效的原因是。如果内存恰好不够，则需要重新分配内存，
对于查找或者删除的效率问题：在map中查找是使用二分查找的（红黑树的特点），时间复杂度为log2 n。当你存储数据的个数翻倍的时候，其查找次数也就是多了一次。
map< int, string > s3;
s3[2] = "haha";
s3.insert( map< int, string >::value_type( 1,"xixi" ) );
s3.insert( map< int, string >::value_type( 6,"xixi" ) );
s3.insert( map< int, string >::value_type( 3,"xixi" ) );
s3.insert( map< int, string >::value_type( 5,"xixi" ) );
s3.insert( map< int, string >::value_type( 4,"xixi" ) );
for( map< int, string >::iterator s = s3.begin(); s != s3.end(); s++ )
cout << ( *s ).first << " ";
cout << endl;C++hash_map
上边我们介绍了map容器，了解到了其查找效率为log2 n，也就是100万条记录我们需要对key进行compare 20次，200万条记录也就是21次，看起来效率很高的样子。但是如果有上亿条记录的话，那么查询的次数也是比较大的。那么我们想在任意多条记录中只需要花费1次，或者几次就可以查询到，该如何实现呢？
hash_map就是为了解决上述问题出现的，hash_map基于hash table（哈希表）。 我们在本科数据结构课程上应该都有了解和学习过哈希表。哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的 情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。
哈希表是根据关键码值(Key-Value)而直接进行访问的数据结构，它用哈希函数处理数据得到关键码值，关键码值对应表中一个特定位置再由应该位置来访问记录，这样可以在时间复杂性度为O(1)内访问到数据。但是很有可能出现多个数据经哈希函数处理后得到同一个关键码——这就产生了冲突，解决冲突的方法也有很多，最方便最有效的一种——链地址法，当有冲突发生时将具同一关键码的数据组成一个链表。
其基本原理是：使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即 数组下标，hash值）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应 “类”所对应的地方，称为桶。
hash_map的使用：
unordered_map< int, string > s3;
s3[2] = "haha";
s3.insert( unordered_map< int, string >::value_type( 1,"xixi" ) );
s3.insert( unordered_map< int, string >::value_type( 6,"xixi" ) );
s3.insert( unordered_map< int, string >::value_type( 3,"xixi" ) );
s3.insert( unordered_map< int, string >::value_type( 5,"xixi" ) );
s3.insert( unordered_map< int, string >::value_type( 4,"xixi" ) );
for( unordered_map< int, string >::iterator s = s3.begin(); s != s3.end(); s++ )
cout << ( *s ).first << " ";
cout << endl;
使用方式和map一样，那么hash函数和比较函数是如何确定的呢。应该可以猜到是缺省的。
template <class _Key, class _Tp, class _HashFcn = hash<_Key>, class _EqualKey = equal_to<_Key>, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) > class hash_map { ... }
也就是说，在上例中，有以下等同关系：
...
hash_map<int, string> mymap;
//等同于:
hash_map<int, string, hash<int>, equal_to<int> > mymap;
hash_map和map的区别在哪里？
构造函数。hash_map需要hash函数，等于函数；map只需要比较函数(小于函数).
存储结构。hash_map采用hash表存储，map一般采用红黑树(RB Tree)实现。因此其memory数据结构是不一样的。
存储结构。hash_map采用hash表存储，map一般采用红黑树(RB Tree)实现。因此其memory数据结构是不一样的。
什么时候需要用hash_map，什么时候需要用map?
总体来说，hash_map 查找速度会比map快，而且查找速度基本和数据数据量大小，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小，hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且hash_map的构造速度较慢。
总体来说，hash_map 查找速度会比map快，而且查找速度基本和数据数据量大小，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小，hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且hash_map的构造速度较慢。
权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)