在C++中设置实现？

根据以下链接 - http://www.cplusplus.com/reference/set/set/在C++的STL中的集合通常实现为二叉搜索树，我能够在诸如整数或字符集或浮点数或字符串的情况下评估数据类型的行为，如在这些情况下很容易看到BST排序被强加在集合元素上，但考虑到集合的二叉搜索树数据结构实现，我无法想象如何使用二叉搜索树实现以下数据类型：在C++中设置实现？

set<vector<int>>或set<vector<string>>或set<vector<double>>或set<list<int>>
set<map<int, int>>
set<stack<int>>

或与此有关的许多其他数据类型，如何分配给这些类型的内存，以及如何保持排序。

此外，无论何时将新矢量添加到集合中，集合数据类型是否内部检查集合中的所有矢量用于相似度还是所有用于相似度的地图，我都无法弄清楚以下内容：我无法弄清楚。如果有人能帮助我想象这些概念，那将是非常棒的。

感谢提前:)

来源

2013-04-07 AnkitSablok

内存分配相同（即代替'new int'它是'new vector '），并且排序也是一样的（使用'operator <'）（例如，[这里是一个链接]（ http://en.cppreference.com/w/cpp/container/vector/operator_cmp）给vector的比较运算符）。 – Cornstalks 2013-04-07 16:02:36

一个set<T>总是以同样的，无论是什么具体类型T是。在插入时，它会通过使用std::less<T>（默认情况下调用operator<）将其与各种现有元素进行比较来计算放置新元素的树^*中的哪个位置。如果operator<没有超载为T，那么它将不会编译。

因此，如何订购T实例的细节是从如何维护集合的细节中抽象出来的。

_{*注意std::set不必使用一棵树;这只是一个典型的实现。}

来源

2013-04-07 16:04:30

该集合使用严格的弱排序来确定每个元素的位置。这是默认使用std::less<T>完成的。这将导致致电operator<(const T&, const T&)。现在，容器如std::vectorhave such operators，它们只是执行所有元素的lexicographical comparison。这就是std::set<std::vector<int>>可以开箱即用的方式。

当插入一个新元素时，设置不是必须检查所有元素。插入是一个对数复杂度操作，这就是为什么实现往往是一个自平衡二叉树（我用这个相当奇怪的因果关键词，因为C++标准没有指定实现应该是什么样子，它应该如何表现。）

来源

2013-04-07 16:04:42 juanchopanza

如果你在一个集合中插入一个向量，那么如何插入是一个对数时间操作，这是一个复杂的理解我无法弄清楚的问题 – AnkitSablok 2013-04-07 16:15:39

@Coder是二叉搜索树的全部点。如果您有一棵平衡树，则执行O（log_2（N））比较来找到正确的位置。把它想象为为给定值执行正确位置的搜索。 – juanchopanza 2013-04-07 16:17:26

实现如何决定树中插入向量的位置以及在什么基础上进行什么样的词典对比？ – AnkitSablok 2013-04-07 16:20:00

在C++中设置实现？

回答

相关问题