c++ - C++中是否有类似Haskell Data.Sequence的东西？

是否有C++库实现了类似Haskell Data.Sequence容器的东西？

我最感兴趣的是:

保持元素顺序(在其中插入元素)。

O(logn)通过索引访问。又名operator[](size_type pos)。

O(logn)在中间插入/删除(通过索引)。

最佳答案

在我看来，要实现这样的数据结构，您需要一棵树来存储每个节点中元素的数量。它允许在O(log(N))中进行插入和检索，并且通过简单地计算树中给定节点的“左侧”有多少个元素来维护索引。
*我在这里回答的问题可能稍有不同，实际问题需要图书馆的建议，这在SO上显然是题外话。
该树的节点如下所示:

template<typename T>
struct Node {
  Node* left;
  Node* right;
  size_t elements;
  T value

  T& access(size_t index) {
    if (left->elements == index) {
      return value;
    } else if (left->elements > index) {
      return left->access(index);
    } else {
      return right->access(index - left->elements - 1);
    }
  }

  void insert(size_t index, T&& value) {
    // insert `value` at right place, increment `elements`
  }
}

(我将insert方法留给读者作为练习。)
编辑:正如下面的注释中所述的willir(OP)，该树将需要是平衡树。 Arne Vogel建议B树将是缓存局部性的最佳选择。

但:
如果您确实实现了这样的事情，请确保您对应用程序进行了度量，并将其与std::vector进行比较。在任意位置插入 vector 的是O(N)，而不是O(log(N))，但它是非常廉价操作的O(N)。 vector 比这种数据结构有很多优点:

没有代码要维护。

需要存储的东西更少(在一棵树中，您需要存储两个指针和一个计数，而这在 vector 中是不必要的)，这意味着更多的数据可以同时放入缓存中。

始终按存储顺序访问数据。对于树，您需要遍历可以存储在内存中任意位置的节点，它们不需要彼此靠近，并且可能不会按照读取顺序存储。

点2和3表示 vector 的缓存命中次数少许多。这可能会造成巨大的时序差异。
如果每个数据元素很大，则在 vector 中移动数据的速度将变得很慢。但是在这种情况下，您应该将指向数据的指针保留在 vector 中，以便移动指针列表，而不是实际数据。对于这么大的数据元素，我建议独立分配每个元素，并将其指针保留在std::vector<std::unique_ptr<T>>中。
以下是一些相关链接:
DZone:C++ benchmark – std::vector VS std::list

YouTube:Day 1 Keynote - Bjarne Stroustrup: C++11 Style

所以:Relative performance of std::vector vs. std::list vs. std::slist?

Vector

c++ - C++中是否有类似Haskell Data.Sequence的东西？