首页 > 程序人生 > 手把手教你调试STL容器(下)

手把手教你调试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的介绍,我们便可以方便的查看到这些容器中的所有内容。

    1. 2011年5月16日19:43 | #1

      沙发!!!! 正在自觉这方面呢,目前还是看不太懂。嘻嘻

    1. 本文目前尚无任何 trackbacks 和 pingbacks.
    您必须在 登录 后才能发布评论.