手把手教你调试STL容器(下)

本文是《手把手教你调试STL容器》系列的下篇，阅读本文之前，请先阅读上篇《手把手教你调试STL容器(上)》。上篇中主要介绍了STL中string, vector, list, deque这些基本的容器。本篇将介绍由红黑树实现的map/set/multimap/multiset这些容器，以及由hashtable实现的hash_map/hash_set/hash_multimap/hash_multiset这些容器。

• 1. 红黑树（Red black tree)

  我们知道, STL中的map/set/multimap/multiset，都是由红黑树实现的，因此我们要了解map/set/multimap/multiset这些容器是如何实现的，就首先要了解红黑树的基本组成：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

  enum _Rb_tree_color { _S_red = false, _S_black = true };   struct _Rb_tree_node_base { typedef _Rb_tree_node_base* _Base_ptr; typedef const _Rb_tree_node_base* _Const_Base_ptr;   _Rb_tree_color _M_color; _Base_ptr _M_parent; _Base_ptr _M_left; _Base_ptr _M_right; };   template< typename _Val> struct _Rb_tree_node : public _Rb_tree_node_base { typedef _Rb_tree_node< _val>* _Link_type; _Val _M_value_field; };   template< typename _Key_compare, bool _Is_pod_comparator = std::__is_pod< _Key_compare>::__value> struct _Rb_tree_impl : public _Node_allocator { _Key_compare _M_key_compare; _Rb_tree_node_base _M_header; size_type _M_node_count; // Keeps track of size of tree. };   _Rb_tree_impl< _compare> _M_impl;

  从上面的代码中，我们知道，STL中红黑树中保存的基本信息包括：根结点对象_M_header和所有结点的个数_M_node_count，_M_header本身只是一个哨兵功能，它里面包含了指向它的左右子树的指针。在真实存放数据的结点中，每个结点都是_Rb_tree_node< _val>类型（_Val是数据类型），用户可以通过_M_value_field，得到存放的数据的值。

  另外，我们也知道，红黑树本身是非线形结构，因此遍历的过程，还是需要迭代器来帮忙的，下面的红黑树的迭代器的基本结构：

  1 2 3 4 5 6

  template< typename _Tp> struct _Rb_tree_iterator { typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; _Base_ptr _M_node; };

  从上面的定义可以看出，红黑树的迭代器本身只是保存了一个_Rb_tree_node_base的指针，我们只要按实际的数据类型，把它转型为_Rb_tree_node类型，就可以通过_M_value_field得到数据的值。

  在STL中，map/set/multimap/multiset都是由红黑树实现的，这些容器，都是在红黑树的基础上，包裹了一层，实现了相关功能，在这些容器中，都有一个这样类似的成员：

  1 2	typedef _Rb_tree< ...> _Rep_type; _Rep_type _M_t;

  从上面的代码我们可以知道，我们要想查看某个map/set/multimap/multiset里面存放的数据，只需要用_M_t，再结合前面对红黑树结构的介绍，便可以。另外，map/set/multimap/multiset的迭代器也是在红黑树迭代器基础上包裹的，这里不再做介绍。

• 2. HashTable

  在STL中，hash_map/hash_set/hash_multimap/hash_multiset中由hashtable来实现的，虽说hash_map/hash_set/hash_multimap/hash_multise这些容器，目前还不是标准C++的内容，但是由于实际应用的需要，大家目前都把这些容器当做事实标准，而且大多数的编译器也支持。这里介绍的是GNU的stdext中的实现，下面是hashtable的基本组成：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

  template < class _Val> struct _Hashtable_node { _Hashtable_node* _M_next; _Val _M_val; };   template < class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc> class hashtable { public: typedef _Key key_type; typedef _Val value_type; typedef _HashFcn hasher; typedef _EqualKey key_equal; typedef _Hashtable_node< _Val> _Node; typedef vector< _Node*, _Nodeptr_Alloc> _Vector_type;   hasher _M_hash; key_equal _M_equals; _ExtractKey _M_get_key; _Vector_type _M_buckets; size_type _M_num_elements; };

  通过上面的代码，我们可以得知，hashtable是由vector+list实现的一个结构，纵向是一个vector，横向是一个list，这正是separate chain hash的实现。我们结合上篇中对vector的介绍，用_M_impl._M_start拿到hashtable中vector中数据的起始地址，然后通过下标便可得到每个横向链表的头指针。在每个横向的链表中，只要我们得到了某个结点的指针，便可以用_M_val来查看其数据值，可以用_M_next来查看下一个结点的情况。

  另外，我们也可以通过hashtable的迭代器来查看hashtable中某个结点的数据值：

  1 2 3 4 5 6 7

  template < class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc> struct _Hashtable_iterator { _Node* _M_cur; _Hashtable* _M_ht; };

  上面是hashtable的迭代器的定义，通过_M_cur便可得知当前位置的内容。

  我们知道，hash_map/hash_set/hash_multimap/hash_multi_set都是在hashtable的基础上包裹实现的，在这些容器中，都有一个这样类似的成员：

  1 2	typedef hashtable< ...> _Ht _Ht _M_ht;

  从上面可以看出，只要我们拿到hash_map/hash_set/hash_multimap/hash_multiset这些容器的_M_ht成员，再结合前面对hashtable的介绍，我们便可以方便的查看到这些容器中的所有内容。

  链接地址：http://www.wuzesheng.com/?p=1733