logo标签列表

寻找特殊的C++数据结构

c++data-structuresiteratorcomplexity-theory
8
我正在寻找一个C++数据结构的实现（或数据结构的组合），满足以下标准：
  • 项目的访问方式与std::vector相同
  • 提供随机访问迭代器（以及迭代器比较 <，>）
  • 平均项访问（：查找）时间的最坏情况为O(log(n))
  • 按照添加到容器中的顺序进行迭代
  • 给定迭代器，我可以在容器中找到指向的项目的序数位置，最坏情况下的复杂度为O(log(n))
  • 提供项目插入和删除在特定位置的最坏O(log(n))复杂度
  • 删除/插入项目不会使先前获得的迭代器无效

感谢您提前提供任何建议

Dalibor

（编辑）答案：

我选择的答案描述了符合所有这些要求的数据结构。但是，正如Maxim Yegorushkin所建议的那样，boost::multi_index提供了非常接近上述功能的功能。

(编辑) 一些要求没有被正确指定。它们根据更正(:原始)进行修改。

(编辑) 我找到了已接受答案中所描述的数据结构的实现。到目前为止，它按预期工作。它被称为计数器树。

(编辑) 考虑使用sp2danny建议的AVL-Array。

你不能有多行注释。最好编辑问题。 - Mike DeSimone
也许可以使用boost.multi_index，其中包含一个基于向量的索引和一个集合类型的索引，以便快速查找... - Kerrek SB
1
标准库中没有这样的容器可以满足您所有的要求。我甚至不相信在理论上存在这样的容器。您应该优先考虑您的要求，以便我们可以想出最合适的解决方案。 - Armen Tsirunyan
2
你的需求列表排除了使用任何已知的单一数据结构。满足所有需求的唯一方法是使用结合多个数据结构的东西（例如Kerrek提到的boost::multi_index）。 - Nim
1
如果有这样的容器，那将是标准库中唯一的一个。 - Bo Persson
显示剩余6条评论
5个回答
4
根据您的要求，boost::multi_index使用两个索引即可完成任务。
第一个索引是有序索引。它允许O(log(n))插入/查找/删除操作。第二个索引是随机访问索引。它允许随机访问，元素按插入顺序存储。对于这两个索引，当其他元素被删除时，迭代器不会失效。将一个迭代器转换为另一个迭代器是O(1)操作。
我猜你必须小心跟踪你拥有的迭代器。此外，按顺序遍历所有项是O(N)还是O(N*log(N))？也就是说，迭代器的operator++是O(1)还是O(log(N))？ - Mike DeSimone
有序索引的文档没有说明operator++的复杂度。然而，它是基于红黑树实现的，所以迭代器的operator++的复杂度和std::set或者std::map的一样，即O(1)。 - Maxim Egorushkin
迭代所有项的复杂度并不重要。我认为在提供的规范中表述不够清晰。我只需要按照它们插入的顺序访问这些项。我没有其他有用的排序方式，所以我认为这使得boost::multi_index的有序索引不符合要求。随机访问索引似乎几乎可以胜任，但是在除序列末尾之外的任何位置插入/删除元素的复杂度为O(log(n))。 - Dalibor Frivaldsky
@Dalibor：看起来你不熟悉boost::multi_index。我建议你先阅读教程，然后再仔细阅读我的回答。 - Maxim Egorushkin
3
让我们来看一下这些...
平均项查找时间最坏的复杂度为O(log(n))
项目的删除/插入不会使之前获取的迭代器失效
提供最坏复杂度为O(log(n))的项插入和移除
这几乎可以说是“树”了。
提供随机访问迭代器(以及迭代器比较<，>)
给定一个迭代器，我可以在容器中找到指向的项目的序数位置，最坏的复杂度为O(log(n))
项目按照添加到容器中的顺序进行迭代
我假设您提供的随机访问迭代器的索引是按照插入顺序排列的，因此[0]将是容器中最旧的元素，[1]将是接下来最旧的元素，依此类推。这意味着，在删除时，为了使迭代器有效，迭代器内部不能存储索引，因为它可能会在没有通知的情况下发生更改。所以仅使用键为插入顺序的映射是行不通的。
鉴于此，您的每个树节点需要跟踪每个子树中有多少元素，除了其常规成员外。这将允许使用O(log(N))的时间进行随机访问。我不知道是否有现成的代码集，但以std::rb_tree和std::rb_node为基础进行子类化将是我的起点。
这正是我所思考的，但我不知道是否有现有的实现。 - Dalibor Frivaldsky
这就是为什么我说你可能需要从标准库的红黑树代码开始自己编写。 - Mike DeSimone
从未听说过标准库有rb_tree和rb_node吗？ - UncleBens
rb_tree和rb_node没有文档，因为它们是所提供的STL容器的实现细节（在内部使用）。 - Dalibor Frivaldsky
0

这是我的“lv”容器，符合要求的O(log n)插入/删除/访问时间。 https://github.com/xhawk18/lv

该容器是仅包含头文件的C++库，并且具有与其他C++容器（如list和vector）相同的迭代器和函数。

“lv”容器基于红黑树，每个节点都有一个关于子树中节点数量的大小值。通过检查树的左/右子节点的大小，我们可以快速随机访问节点。

谢谢。它与问题编辑中提到的counter_tree和AVL-array相比如何？ - Dalibor Frivaldsky
嗨，Dalibor，这是一个计数树的实现，基于红黑树作为底层数据结构。 - xhawk18
0
不知道为什么这个被踩了。根据文档，所引用的数据结构满足要求。我唯一缺少的是能够根据迭代器告诉数组中对象的序数位置。我可能在文档中忽略了什么？ - Dalibor Frivaldsky
来自迭代器的序数位置在源代码中缺失。我自己需要它，所以我添加了一个一行代码。 - sp2danny
0
请参考这里：STL容器（向下滚动页面以查看有关算法复杂度的信息），我认为{{link2：std::deque}}符合您的要求。
2
deque 如何通过值快速查找？此外，容器的修改确实会使迭代器无效（但不会使元素的引用无效）。 - Kerrek SB
1
如果我没记错的话，deque 的最坏情况下查找和删除的时间复杂度是 O(N)。 - Mike DeSimone
2
我认为deque不满足插入/删除的限制（除了在前面和末尾进行插入/删除）。请参阅n3290.pdf C++0x初步标准中的23.3.3.4。 - user786653
对于一个双端队列，插入和删除操作可能不具有O(log(n))的时间复杂度。 - A. K.
@Aditya：正确。插入和/或删除应该是在任一端O(1)，或者在任何其他地方是O(N)。 - Mike DeSimone
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接