这么一段程序，
1 2 3 4 5 6 7 8 9 | typedef __gnu_cxx::hash_map<object *, object *, object_equal_to, object_hasher> object_hash_map_t; object_hash_map_t hash_map; hash_map.insert(make_pair(new object, new object)); object_hash_map_t::iterator it = hash_map.begin(); while (it != hash_map.end()) { delete it->first; delete it->second; ++it; } |
该程序core而不止。因为STL的代码很多都被内联了，调试起来不方便，于是看了下sgi的STL实现，发现了问题。首先，STL的hash_map是由hashtable实现的，hash_map只是对hashtable的一个封装。hashtable也只是很普通的实现，使用单链表解决冲突。下面是hashtable中对迭代器的operator++操作的实现，
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | struct _Hashtable_node { _Hashtable_node *_M_next; _Val _M_val; //~ pair<Key, Value> }; typedef _Hashtable_node _Node; //~ omitting the template arguments struct _Hashtable_iterator { _Node *_M_cur; _Hashtable *_M_ht; _Hashtable_iterator& operator++() { const _Node* __old = _M_cur; //! preserve the old node _M_cur = _M_cur->_M_next; if (!_M_cur) { size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); //! get bucket number with hash key while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) _M_cur = _M_ht->_M_buckets[__bucket]; } return *this; } }; |
了然了，iterator的operator++需要根据key计算出迭代器当前所在的bucket，然后在此bucket及后续bucket中顺序遍历以寻找下一个元素。所以在开头的示例代码中，由于在迭代过程中释放了key的内存，当迭代器“递增”计算当前bucket number时当然就core掉了。
hash_map在STL中已经被标记为deprecated，已经过时了，若要使用hash_map，建议使用具有相同接口和特性的unordered_map。
另外，使用hash_map时，一定要注意模板参数equal_to和hash_func，前者用来判断key是否相等，后者用来计算key的hash值，稍有不慎就会出现莫名其妙的错误，例如著名的hash_map的遍历死循环问题。
你好！除了代码，此处没有多少原创之物，皆为本人搜集、整理、总结之记录与心得，欢迎转载分享！转载时请尽量注明出处，将不胜感激。祝你健康、快乐！
我去～
STL我只用过最简单的几个。
这么高级的数据结构我只是有所耳闻。
key的话用值语义会不会容易些呢…更易一些非更易性质的东西总不会太踏实的感觉…
是的，map的key一般应该是值语义或者不可变的，但有时候为了节省内存的需要，还是得需要使用指针。。。我代码里面key就会占用比较多的内存。