在C++中设置STL的底层数据结构是什么？

Question

我想知道如何在C++中实现一个集合.如果我在不使用STL提供的容器的情况下实现自己的set容器,那么最好的方法是什么呢？

我理解STL集基于二叉搜索树的抽象数据结构.那么底层数据结构是什么？数组？

另外,如何insert()为一组工作？set如何检查元素是否已经存在？

我在维基百科上读到,实现集合的另一种方法是使用哈希表.这怎么样？

Answer 1

正如KTC所说,std::set实现的方式可能会有所不同--C++标准只是指定了一种抽象数据类型.换句话说,标准没有规定应该如何实现容器,只是指定需要支持的操作.但是,据我所知,STL的大多数实现都使用红黑树或其他某种平衡的二叉搜索树(例如,GNU libstdc ++使用红黑树).

虽然理论上你可以将一个集合实现为哈希表并获得更快的渐近性能(分摊O(密钥长度)与O(log n)进行查找和插入),这将需要让用户为他们想要的任何类型提供哈希函数存储(请参阅维基百科在哈希表上的条目,以获得有关它们如何工作的详细解释).至于二叉搜索树的实现,您不希望使用数组 - 正如Raul所提到的,您需要某种Node数据结构.

Answer 2

您可以通过首先定义Node结构来实现二叉搜索树:

struct Node
{
  void *nodeData;
  Node *leftChild;
  Node *rightChild;
}

然后,您可以使用另一个树定义树的根 Node *rootNode;

二进制搜索树上的维基百科条目有一个很好的例子来说明如何实现插入方法,所以我也建议你检查一下.

就重复而言,它们通常不允许在集合中,因此您可以根据您的规范放弃该输入,抛出异常等.

Answer 3

步骤调试到g++6.4 stdlibc ++源码

您是否知道在Ubuntu的16.04默认g++-6软件包或源代码的GCC 6.4版本中,您可以直接进入C++库而无需进一步设置？

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

这是有道理的,因为std::set可以按顺序遍历,如果使用哈希映射则不会有效.

main.cpp中

#include <cassert>
#include <set>

int main() {
    std::set<int> s;
    s.insert(1);
    s.insert(2);
    assert(s.find(1) != s.end());
    assert(s.find(2) != s.end());
    assert(s.find(3) == s3.end());
}

编译和调试:

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

现在,如果你踏入s.insert(1)你的话,马上到达/usr/include/c++/6/bits/stl_set.h:

487 #if __cplusplus >= 201103L
488       std::pair<iterator, bool>
489       insert(value_type&& __x)
490       {
491     std::pair<typename _Rep_type::iterator, bool> __p =
492       _M_t._M_insert_unique(std::move(__x));
493     return std::pair<iterator, bool>(__p.first, __p.second);
494       }
495 #endif

这显然只是转发给了_M_t._M_insert_unique.

所以我们在vim中打开源文件并找到以下定义_M_t:

      typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
           key_compare, _Key_alloc_type> _Rep_type;
       _Rep_type _M_t;  // Red-black tree representing set.

所以_M_t是类型_Rep_type,_Rep_type是一个_Rb_tree.

好的,现在这对我来说已经足够了.如果您不相信这_Rb_tree是一棵黑红色的树,请再进一步阅读算法.

unordered_set 使用哈希表

相同的过程,但更换set用unordered_set的代码.

这是有道理的,因为std::unordered_set不能按顺序遍历,所以标准库选择哈希映射而不是红黑树,因为哈希映射具有更好的分期插入时间复杂度.

走进insert导致/usr/include/c++/6/bits/unordered_set.h:

415       std::pair<iterator, bool>
416       insert(value_type&& __x)
417       { return _M_h.insert(std::move(__x)); }

所以我们打开源文件vim并搜索_M_h:

      typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc>  _Hashtable;
      _Hashtable _M_h;

所以哈希表就是这样.

std::map 和 std::unordered_map

类似于std::setvs std:unordered_set:C++中的std :: map里面有什么数据结构？

性能特点

您还可以通过计时来推断使用的数据结构.

我们清楚地看到:

• std::set,对数插入时间

• std::unordered_set,一个更复杂的模式hashmap模式:

  • 在非缩放的情节中,我们清楚地看到背景动态阵列在巨大的线性增加尖峰上加倍

  • 在缩放的情节中,我们看到时间基本上是恒定的并且朝向250ns,因此比非常快std::map,除了非常小的地图尺寸

    几个条带清晰可见,并且每当阵列加倍时它们的倾斜度变小.

    我相信这是由于平均线性增加的链表行走每个箱子.然后当阵列加倍时,我们有更多的箱子,所以更短的步行.

图表生成:

• 代码:https://github.com/cirosantilli/cpp-cheat/blob/15066739601a701d5f4d702ec28c6c615cdbb17b/cpp/interactive/bst_vs_heap.cpp
• 系统:Ubuntu 18.04,GCC 7.3,Intel i7-7820HQ CPU,DDR4 2400 MHz RAM,联想Thinkpad P51.

堆与BST分析:堆与二元搜索树(BST)

Answer 4

我理解STL集基于二叉搜索树的抽象数据结构.那么底层数据结构是什么？数组？

正如其他人所指出的,它有所不同.一组通常被实现为树(红黑树,平衡树等),但是可能存在其他实现.

另外,insert()如何适用于一组？

这取决于您的集合的底层实现.如果它是作为二叉树实现的,则Wikipedia具有insert()函数的示例递归实现.你可能想看一下.

set如何检查元素是否已经存在？

如果它是作为树实现的,那么它遍历树并检查每个元素.但是,集合不允许存储重复元素.如果你想要一个允许重复元素的集合,那么你需要一个multiset.

我在维基百科上读到,实现集合的另一种方法是使用哈希表.这怎么样？

您可能指的是hash_set,其中使用哈希表实现该集合.您需要提供哈希函数来了解存储元素的位置.当您希望能够快速搜索元素时,此实现非常理想.但是,如果按特定顺序存储元素很重要,那么树实现更合适,因为您可以按顺序遍历它,按顺序或后序.

Answer 5

如何在C++中实现特定容器完全取决于实现.所需要的只是结果满足标准中规定的要求,例如各种方法的复杂性要求,迭代器要求等.