O(1) 最坏情况仅追加数组
O(1) worst case append only array
我正在寻找一种支持 O(1) 随机访问和最坏情况 O(1) 追加的数据结构。
然而，在我的例子中，O(1) 摊销的附加时间是 不是 我正在寻找的。
除了 append 和 access[=33 之外，数据结构还将 not 执行任何操作=].没有删除，没有插入，只是一个附加结构。
在我的例子中，上限会很大，可能是 8GB。
此外，这个问题与this基本相同，但是，我对该问题的答案的问题是它降低了内存分配的成本.在 c++ 中，内存分配大部分时间是 O(1)，但是，我遇到过很多次 malloc 需要很长时间的情况。
我想知道这样的结构是否存在。我阅读了 this pdf，但是我相信最坏情况下的时间复杂度仍然是 O(1) 摊销的。
如果有人对可以支持这些条件的结构有任何想法（不是寻找实现，只是一个想法），我们将不胜感激。
std::deque 非常接近您想要的：
- 它是
O(1) 用于随机访问（是 std::vector 的两倍，因为它必须执行两次指针解引用，不只是一次，而是像这样的固定倍数不会改变 big-O )
- 它实际上是
O(1)，而不仅仅是摊销 O(1)，对于追加，如果您认为间歇性固定大小的内存分配（没有初始化）是 O(1)（它是；它是不是恒定成本，但成本与 deque) 的大小无关
与链接问题中的分配不同（当新分配的内存大小加倍时，因此新分配会线性增长），std::deques 块分配是固定大小的，因此您可以：
- 将元素插入到现有分配的 space 或
- 分配一个固定大小的块，然后将一个元素插入到新块的第一个槽中
由于新块的大小是固定的，不是持续增长的，所以还是O(1)（有时O(1 construction)有时O(1 fixed size allocation + 1 construction)，但仍然与[=16=的长度无关]).
我正在寻找一种支持 O(1) 随机访问和最坏情况 O(1) 追加的数据结构。 然而，在我的例子中，O(1) 摊销的附加时间是 不是 我正在寻找的。
除了 append 和 access[=33 之外，数据结构还将 not 执行任何操作=].没有删除，没有插入，只是一个附加结构。
在我的例子中，上限会很大，可能是 8GB。
此外，这个问题与this基本相同，但是，我对该问题的答案的问题是它降低了内存分配的成本.在 c++ 中，内存分配大部分时间是 O(1)，但是，我遇到过很多次 malloc 需要很长时间的情况。
我想知道这样的结构是否存在。我阅读了 this pdf，但是我相信最坏情况下的时间复杂度仍然是 O(1) 摊销的。
如果有人对可以支持这些条件的结构有任何想法（不是寻找实现，只是一个想法），我们将不胜感激。
std::deque 非常接近您想要的：
- 它是
O(1)用于随机访问（是std::vector的两倍，因为它必须执行两次指针解引用，不只是一次，而是像这样的固定倍数不会改变 big-O ) - 它实际上是
O(1)，而不仅仅是摊销O(1)，对于追加，如果您认为间歇性固定大小的内存分配（没有初始化）是O(1)（它是；它是不是恒定成本，但成本与deque) 的大小无关
与链接问题中的分配不同（当新分配的内存大小加倍时，因此新分配会线性增长），std::deques 块分配是固定大小的，因此您可以：
- 将元素插入到现有分配的 space 或
- 分配一个固定大小的块，然后将一个元素插入到新块的第一个槽中
由于新块的大小是固定的，不是持续增长的，所以还是O(1)（有时O(1 construction)有时O(1 fixed size allocation + 1 construction)，但仍然与[=16=的长度无关]).