在C++中std :: map里面有什么数据结构？

Question

我是初学者并且正在学习C++很难理解std :: map概念,因为我正在玩的代码暗示它map是一个搜索树,即std :: map对象的所有名称都有*tree作为以及评论.

但是阅读本材料后http://www.cprogramming.com/tutorial/stl/stlmap.html我倾向于认为性病::地图都有无关树或哈希值.

所以我很困惑 - 代码中的变量和注释对我来说,或者主题更复杂然后我认为它是:)

Answer 1

逐步调试 g++ 6.4 stdlibc ++源代码中

您是否知道在Ubuntu 16.04默认g++-6软件包或从源代码构建的GCC 6.4您无需任何进一步设置即可直接进入C ++库？

通过这样做，我们很容易得出结论，在此实现中使用了红黑树。

这是有道理的，因为std::map与std::unordered_map可以不，可以按键顺序遍历，这在使用哈希映射时效率不高。

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);
}

编译和调试：

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

现在，如果您介入其中s.emplace(1, -1)，立即可以达到/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)...); }

显然只是向前_M_t._M_emplace_unique。

因此，我们在中打开源文件vim并找到的定义_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;

所以_M_t是类型_Rep_type，_Rep_type是_Rb_tree。

好的，这对我来说已经足够了。如果您不相信那_Rb_tree是一棵黑红色的树，请再走一步，然后阅读算法

unordered_map 使用哈希表

相同的过程，但更换map用unordered_map的代码。

这是有道理的，因为 std::unordered_map不能按顺序遍历，所以标准库选择哈希图而不是红黑树，因为哈希图具有更好的摊销插入时间复杂度。

进入emplace导致/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)...); }

因此，我们在中打开源文件vim并搜索的定义_M_h：

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

所以是哈希表。

std::set 和 std::unordered_set

类似于std::mapvs std::unordered_map：用C ++设置的STL的底层数据结构是什么？

性能特点

您还可以通过对它们进行计时来推断使用的数据结构：

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

由于std::map类似于，std::set我们清楚地看到：

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

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

  • 在非缩放图上，我们可以清楚地看到，支持动态数组在线性增加的尖峰上的巨大幅度上翻了一番

  • 在放大的图上，我们看到时间基本上是恒定的，接近250ns，因此比快得多std::map，但地图尺寸非常小

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

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

Answer 2

std::map是一个关联容器.标准的唯一要求是容器必须具有关联容器接口和行为,实现未定义.虽然实现符合复杂性和接口要求,但是是有效的实现.

另一方面,正如参考文献所述,std::map通常用红黑树实现.

Answer 3

我想说的是，如果您将地图视为一对，就不会出错。Map 可以实现为树或哈希映射，但它的实现方式并不那么重要，因为您可以确定 STL 的任何实现都是高效的。