CODEWITHSUNDEEP
c++liststlcontainers
akif
akif

Reputation: 12344

Which STL Container?

I need a container (not necessarily a STL container) which let me do the following easily:

I used std::list, but it won't let me insert at any position (it does, but for that I'll have to iterate over all elements and then insert at the position I want, which is slow, as the list may be huge). So can you recommend any efficient solution?

Upvotes: 4

Views: 1932

Answers (10)

Lightness Races in Orbit
Lightness Races in Orbit

Reputation: 385405

Containers
(source: adrinael.net)

But it sounds like you're looking for a single container with the following properties:

  • All the best benefits of various containers
  • None of their ensuing downsides

And that's impossible. One benefit causes a detriment. Choosing a container is about compromise.

Upvotes: 0

Jerry Coffin
Jerry Coffin

Reputation: 490728

An order statistic tree might be useful here. It's basically just a normal tree, except that every node in the tree includes a count of the nodes in its left sub-tree. This supports all the basic operations with no worse than logarithmic complexity. During insertion, anytime you insert an item in a left sub-tree, you increment the node's count. During deletion, anytime you delete from the left sub-tree, you decrement the node's count. To index to node N, you start from the root. The root has a count of nodes in its left sub-tree, so you check whether N is less than, equal to, or greater than the count for the root. If it's less, you search in the left subtree in the same way. If it's greater, you descend the right sub-tree, add the root's count to that node's count, and compare that to N. Continue until A) you've found the correct node, or B) you've determined that there are fewer than N items in the tree.

Upvotes: 1

teZeriusz
teZeriusz

Reputation: 91

This diagram will help you a lot, I think so.

Upvotes: 4

Sam Harwell
Sam Harwell

Reputation: 100029

By "iterating over the elements in any order", do you mean you need support for both forward and backwards by index, or do you mean order doesn't matter?

You want a special tree called a unsorted counted tree. This allows O(log(n)) indexed insertion, O(log(n)) indexed removal, and O(log(n)) indexed lookup. It also allows O(n) iteration in either the forward or reverse direction. One example where these are used is text editors, where each line of text in the editor is a node.

Here are some references:

Upvotes: 1

UncleBens
UncleBens

Reputation: 41351

A vector. When you erase any item, copy the last item over one to be erased (or swap them, whichever is faster) and pop_back. To insert at a position (but why should you, if the order doesn't matter!?), push_back the item at that position and overwrite (or swap) with item to be inserted.

Upvotes: 1

Test
Test

Reputation: 1727

std::vector

[padding for "15 chars" here]

Upvotes: -4

aJ.
aJ.

Reputation: 35490

You can try std::deque, but it will not provide the constant time removal of elements in middle but it supports

  • random access to elements
  • constant time insertion and removal of elements at the end of the sequence
  • linear time insertion and removal of elements in the middle.

Upvotes: 1

sharptooth
sharptooth

Reputation: 170559

Either a vector or a deque will suit. vector will provide faster accesses, but deque will provide faster instertions and removals.

Upvotes: 3

Jack Lloyd
Jack Lloyd

Reputation: 8405

It's not completely clear to me what you mean by "Iterate over the elements in any order" - does this mean you don't care about the order, as long as you can iterate, or that you want to be able to iterate using arbitrarily defined criteria? These are very different conditions!

Assuming you meant iteration order doesn't matter, several possible containers come to mind:

std::map [a red-black tree, typically]

  • Insertion, removal, and access are O(log(n))
  • Iteration is ordered by index

hash_map or std::tr1::unordered_map [a hash table]

  • Insertion, removal, and access are all (approx) O(1)
  • Iteration is 'random'

Upvotes: 7

mpen
mpen

Reputation: 283345

Well, you can't have all of those in constant time, unfortunately. Decide if you are going to do more insertions or reads, and base your decision on that.

For example, a vector will let you access any element by index in constant time, iterate over the elements in linear time (all containers should allow this), but insertion and removal takes linear time (slower than a list).

Upvotes: 1

Related Questions