wil*_*lir 6 c++ tree haskell data-structures
是否有任何C++库实现Haskell Data.Sequence容器之类的东西？
我最感兴趣的是:
O(logn)通过索引访问.阿卡operator[](size_type pos).O(logn) 在中间插入/删除(通过索引).在我看来，实现*这种数据结构的方法需要一棵树来存储每个节点中的元素数量。它允许在 O(log(N)) 中插入和检索，并且只需计算树中给定节点“左侧”有多少个元素即可维护索引。
\n*我在这里回答的问题可能略有不同，实际的问题要求推荐一个库，这显然是偏离主题的。
\n该树的一个节点如下所示：
\ntemplate<typename T>\nstruct Node {\n Node* left;\n Node* right;\n size_t elements;\n T value\n \n T& access(size_t index) {\n if (left->elements == index) {\n return value;\n } else if (left->elements > index) {\n return left->access(index);\n } else {\n return right->access(index - left->elements - 1);\n }\n }\n\n void insert(size_t index, T&& value) {\n // insert `value` at right place, increment `elements`\n }\n}\n（我将该insert方法留给读者作为练习。）
编辑：正如 willir (OP) 在下面的评论中提到的，该树需要是一棵平衡树。Arne Vogel 建议 B 树是缓存局部性的最佳选择。
\n如果您确实实现了类似的功能，请确保测量您的应用程序，并将其与std::vector. 在任意位置插入向量的时间复杂度为 O(N)，而不是 O(log(N))，但它是一个非常便宜的操作 O(N)。与此类数据结构相比，向量具有许多优点：
无需维护代码。
\n需要存储的内容更少（在树中，您需要存储两个指针和一个计数，这在向量中是不必要的），这意味着更多的数据可以同时放入缓存中。
\n数据的访问顺序始终与存储的顺序相同。对于树，您需要遍历可以存储在内存中任意位置的节点，它们不需要靠近在一起，并且可能不按照读取的顺序存储。
\n第 2 点和第 3 点意味着向量的缓存未命中次数要少得多。这可能会导致时间上的巨大差异。
\n如果每个数据元素都很大，则在向量中移动数据会变得相当慢。但在这种情况下，您应该在向量中保留指向数据的指针，以便您移动指针列表，而不是实际数据。对于如此大的数据元素，我建议独立分配每个数据元素，并将其指针保存在std::vector<std::unique_ptr<T>>.
以下是一些相关链接：
\n