1

I was wondering if there was any append-only data structure that supports worst-case O(1) appending, and random access.

I saw this answer, but the problem in my eyes is that whenever you fill up the array, you have to allocate a new array that's twice the size, so that would be O(n) worst case for appending.

However, I saw one of the answers in that question was to use std::deque. It also said that std::deque supports O(1) random access & insertion. Is that true?

I'm using C++.

WowThere
  • 51
  • 3
  • How is your question different from the question you've linked to? – mkrieger1 Apr 05 '21 at 20:53
  • Perhaps [`std::colony`](http://wg21.link/p0447)? – Guillaume Racicot Apr 05 '21 at 20:54
  • @mkrieger1 It's not different, but the answer for that question doesn't really answer my question because it has to reallocate another array twice the size – WowThere Apr 05 '21 at 20:55
  • 5
    I'm voting to close this as duplicate of [A data structure supporting O(1) random access and worst-case O(1) append?](https://stackoverflow.com/questions/4834490/a-data-structure-supporting-o1-random-access-and-worst-case-o1-append) Any new answers should go to that question. – mkrieger1 Apr 05 '21 at 20:55
  • I think the question should probably be worded differently. Maybe something like, "Why is the answer given there O(1) and not O(n)?" – General Grievance Apr 05 '21 at 20:56
  • @GuillaumeRacicot - nice! But: `an O(1) time complexity [ ] operator is not possible and the container is bidirectional, but not random-access.` – Vlad Feinstein Apr 05 '21 at 21:01
  • The cost of allocation is not (usually) proportional to the size. – Marc Glisse Apr 05 '21 at 21:14
  • It's going to be worth looking into amortized cost. – sweenish Apr 05 '21 at 21:15
  • *Is that true?* No, it's O(1)(amortized), so the worst case is O(n). – Eljay Apr 05 '21 at 21:17
  • I have set the question as duplicate, but I highly support writing new answers in that question so OP has something that suit its needs. If there are compelling reasons to remove the duplicate, please ping me. – Guillaume Racicot Apr 05 '21 at 21:26
  • @GuillaumeRacicot I think I was wrong, allocations might actually be O(1) – WowThere Apr 05 '21 at 21:29
  • @WowThere yes. I would expect it to be constant time, but less predictable. Any allocation can be from almost instantly to taking a considerable amount of time. – Guillaume Racicot Apr 05 '21 at 21:59
  • Another trick would be to have a maximum size a preallocate everything beforehand. That will cost a lot of memory, but will be faster. I also suggest looking at [`pinned_vector`](https://github.com/mknejp/vmcontainer), which is a vector that does resize its buffer in place using virtual memory. I haven't found the implementation, try asking the author. – Guillaume Racicot Apr 05 '21 at 22:01

0 Answers0