17

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

然而，在阅读了这份材料http://www.cprogramming.com/tutorial/stl/stlmap.html之后，我倾向于认为 std::map 与树或哈希无关。

所以我很困惑——代码中的变量和注释对我来说都是骗人的，或者主题比我认为的更复杂:)

4

6 回答 6

20

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

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

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

这是有道理的，因为std::map与 不同std::unordered_map，可以按键顺序遍历，如果使用散列映射则效率不高。

主文件

#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 平均线性增加的链表遍历。然后当数组翻倍时，我们有更多的箱，所以走的更短。

于 2018-08-21T08:59:39.667 回答
9

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

另一方面，正如参考资料所说std::map，通常用红黑树实现。

于 2013-08-24T08:44:14.040 回答
1

从外部看，地图只是一个关联容器：它在外部表现为“数组”（支持a[x]表达式），其中 x 可以是任何类型（不一定是整数）“可通过 <”比较（因此是有序的）。

但：

  • 因为x可以是任何值，所以它不能是普通数组（否则它必须支持任何索引值：如果你分配 a[1] 和 a[100] 你还需要中间的 2..99 个元素）
  • 因为它必须快速插入并在任何位置找到，它不能是“线性”结构（否则元素应该移动，并且查找必须是顺序的，并且要求是“小于成比例的查找时间”。

最常见的实现在内部使用一个自平衡树（每个节点是一个键/值对，并且链接在一起，以便左侧具有较低的键，而右侧具有较高的键，以便重新进行搜索二分查找）、多跳表（检索速度比树快，插入速度慢）或基于散列的表（其中每个 x 值都被重新引导到数组的索引）

于 2013-08-24T07:48:56.280 回答
0

正如 chris 所写，该标准没有定义 std::map 或 std::set 的内部结构。它定义了诸如插入元素之类的操作的接口和复杂性要求。这些数据结构当然可以实现为树。例如，VisualStudio 附带的实现基于红黑树。

于 2013-08-24T03:50:53.780 回答
0

Map 内部使用自平衡 BST 。请查看此链接。自平衡二叉搜索树

于 2013-08-24T05:11:14.000 回答
-1

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

于 2013-08-24T03:25:23.880 回答