CODEWITHSUNDEEP
c++listvectordata-structurescontainers
user2039981
user2039981

Reputation:

std::list and std::vector - Best of both worlds?

By vector vs. list in STL:

I need a container such that you can both access the element at any index in O(1) time, but also insert/remove an element at any index in O(1) time. It must also be able to manage thousands of entries. Is there such a container?

Edit: If not O(1), some X << O(n)?

Upvotes: 4

Views: 200

Answers (2)

templatetypedef
templatetypedef

Reputation: 372784

There's a theoretical result that says that any data structure representing an ordered list cannot have all of insert, lookup by index, remove, and update take time better than O(log n / log log n), so no such data structure exists.

There are data structures that get pretty close to this, though. For example, an order statistics tree lets you do insertions, deletions, lookups, and updates anywhere in the list in time O(log n) apiece. These are reasonably good in practice, and you may be able to find an implementation online.

Depending on your specific application, there may be alternative data structures that are more tailored toward your needs. For example, if you only care about finding the smallest/biggest element at each point in time, then a data structure like a Fibonacci heap might fit the bill. (Fibonacci heaps are usually slower in practice than a regular binary heap, but the related pairing heap tends to run extremely quickly.) If you're frequently updating ranges of elements by adding or subtracting from them, then a Fenwick tree might be a better call.

Hope this helps!

Upvotes: 10

Zan Lynx
Zan Lynx

Reputation: 54325

Look at a couple of data structures.

  • The Rope
    Tree of arrays. The tree is sorted by array index for fast index search.
  • B+Tree
    Sorted tree of sorted arrays. This thing is used by almost every database ever.

Neither one is O(1) because that's impossible. But they are pretty good.

Upvotes: 0

Related Questions