C ++中std :: map内部包含什么数据结构？ [英] What data structure is inside std::map in C++?

问题描述

我是初学者，正在学习C ++
很难理解std :: map概念，因为我正在使用的代码暗示 map 是搜索树，即std :: map对象的所有名称中都带有* tree以及注释。

但是在阅读了此材料后

图形生成过程和堆vs BST分析，以及位于：堆vs二进制搜索树（BST）

由于 std ::地图类似于 std :: set 我们清楚地看到了：

• std :: map ，对数插入时间



• std :: unordered_map ，更复杂的哈希图模式：

  
  
  
  
  
  • 在非缩放图上，我们清楚地看到了支持动态在缩放图上，线性增加的尖峰使数组倍增一个大
  
  

  • ，我们看到时间基本上是恒定的，接近250ns，因此比 std :: map ，除了非常小的地图尺寸

    
    
    

    几个条带清晰可见，每当数组加倍时它们的倾斜度就会变小

    
    
    

    我相信这是由于每个bin上链表走线的平均线性增加。然后，当数组加倍时，我们会有更多的垃圾箱，所以走的路更短。

  
  

I'm beginner and learning C++ Having hard times to understand std::map concepts, because the code I'm playing with implies that the map is a search tree, i.e. all the names of std::map objects have *tree in it as well as comments.

However after reading this material http://www.cprogramming.com/tutorial/stl/stlmap.html I tend to think that std::map has nothing to do with tree or hash.

So I`m confused -- either the variables and comment in the code lie to me, or the subject is more complex then I think it is :)

解决方案

Step debug into g++ 6.4 stdlibc++ source

Did you know that on Ubuntu's 16.04 default g++-6 package or a GCC 6.4 build from source you can step into the C++ library without any further setup?

By doing that we easily conclude that a Red-black tree used in this implementation.

This makes sense, since std::map, unlike std::unordered_map, can be traversed in key order, which would not be efficient in if a hash map were used.

main.cpp

#include <cassert>
#include <map>

int main() {
    std::map<int, int> m;
    m.emplace(1, -1);
    m.emplace(2, -2);
    assert(m[1] == -1);
    assert(m[2] == -2);
}

Compile and debug:

g++ -g -std=c++11 -O0 -o main.out main.cpp
gdb -ex 'start' -q --args main.out

Now, if you step into s.emplace(1, -1) you immediately reach /usr/include/c++/6/bits/stl_map.h:

556       template<typename... _Args>
557     std::pair<iterator, bool>
558     emplace(_Args&&... __args)
559     { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }

which clearly just forwards to _M_t._M_emplace_unique.

So we open the source file in vim and find the definition of _M_t:

    typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
            key_compare, _Pair_alloc_type> _Rep_type;

    /// The actual tree structure.
    _Rep_type _M_t;

So _M_t is of type _Rep_type and _Rep_type is a _Rb_tree.

OK, now that is enough evidence for me. If you don't believe that _Rb_tree is a Black-red tree, step a bit further and read the algorithm

unordered_map uses hash table

Same procedure, but replace map with unordered_map on the code.

This makes sense, since std::unordered_map cannot be traversed in order, so the standard library chose hash map instead of Red-black tree, since hash map has a better amortized insert time complexity.

Stepping into emplace leads to /usr/include/c++/6/bits/unordered_map.h:

377       template<typename... _Args>
378     std::pair<iterator, bool>
379     emplace(_Args&&... __args)
380     { return _M_h.emplace(std::forward<_Args>(__args)...); }

So we open the source file in vim and search for the definition of _M_h:

      typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
      _Hashtable _M_h;

So hash table it is.

std::set and std::unordered_set

Analogous to std::map vs std::unordered_map: What is the underlying data structure of a STL set in C++?

Performance characteristics

You could also infer the data structure used by timing them:

Graph generation procedure and Heap vs BST analysis and at: Heap vs Binary Search Tree (BST)

Since std::map is analogous to std::set we clearly see for:

• std::map, a logarithmic insertion time

• std::unordered_map, a more complex hashmap pattern:

  • on the non-zoomed plot, we clearly see the backing dynamic array doubling on huge one off linearly increasing spikes

  • on the zoomed plot, we see that the times are basically constant and going towards 250ns, therefore much faster than the std::map, except for very small map sizes

    Several strips are clearly visible, and their inclination becomes smaller whenever the array doubles.

    I believe this is due to average linearly increasing linked list walks withing each bin. Then when the array doubles, we have more bins, so shorter walks.

这篇关于C ++中std :: map内部包含什么数据结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！