4

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

  • Insertion and removal of elements at any position
  • Accessing elements by their index
  • Iterate over the elements in any order

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?

akif
  • 12,034
  • 24
  • 73
  • 85
  • 2
    What problem are you trying to solve? – GManNickG Oct 15 '09 at 05:05
  • Possible duplicate of [In which scenario do I use a particular STL container?](https://stackoverflow.com/questions/471432/in-which-scenario-do-i-use-a-particular-stl-container) – Arthur Dent Jul 11 '18 at 15:07

10 Answers10

7

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'
Jack Lloyd
  • 8,215
  • 2
  • 37
  • 47
  • I meant that as long as I can get an iterator from the beginning/end and then using that iterator iterate over all the elements – akif Oct 15 '09 at 05:19
  • +1 Very ingenious answer. :-) I was gonna say it doesn't provide indexed access, but if you use the index as the key, that actually could work and be decent. – C. K. Young Oct 15 '09 at 05:25
  • 1
    ...although the indices won't be contiguous after a removal other than at the end. – CB Bailey Oct 15 '09 at 07:48
4

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

teZeriusz
  • 81
  • 2
  • 8
3

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

sharptooth
  • 167,383
  • 100
  • 513
  • 979
  • Only at the end (and beginning?). Otherwise, they're the same, no? – mpen Oct 15 '09 at 05:34
  • 1
    vector stores everythiong in one block, so accesses are very fast, but random insertions and removals are slow. deque stores as multiple connected blocks, so accesses are slower than for vector, but random insertions and removals are faster than vector. Insertions at start and end are faster for deque - less buffer reallocation and corresponding moving of elements. – sharptooth Oct 15 '09 at 06:23
  • @sharptooth: deque inserts in the middleish to the end are little faster than a vector. It's only much faster near the beginning. – Mooing Duck Feb 20 '13 at 17:48
1

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).

mpen
  • 272,448
  • 266
  • 850
  • 1,236
1

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.
aJ.
  • 34,624
  • 22
  • 86
  • 128
1

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.

UncleBens
  • 40,819
  • 6
  • 57
  • 90
1

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:

Sam Harwell
  • 97,721
  • 20
  • 209
  • 280
1

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.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
0

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.

Glorfindel
  • 21,988
  • 13
  • 81
  • 109
Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
-4

std::vector

[padding for "15 chars" here]

Test
  • 1,697
  • 1
  • 11
  • 10
  • 1
    With insertion in the middle? – MSalters Oct 15 '09 at 10:04
  • are you a beginner? are you thinking that std::vector doesn't support that kind of inseartion? – Test Oct 15 '09 at 11:21
  • No - but I readd the question. He's already complaing that merely iterating to the right position in a `std::list<>` is slow. That takes O(N) pointer dereferences. Inserting in the middle of a `std::vector` requires copying O(N) elements. That's likely more expensive. – MSalters Oct 15 '09 at 12:28
  • almost every one knows vector::insert() is very expensive, but did you consider processor cache? std::list and std::map cause cache misses and access memory are expensive extremely (e.g. accessing L1 cache cost: 3 cycles, but accessing memory needs 140 cycles!!!); but vector has continuous storage, so if the vector has good reallocation policy (e.g. 128 or 256 bytes), then std::vector::insert is better than std::list or std::map. while i agree that if the programmer didn't aware of cache-line boundary across issue, vector is very bad. – Test Oct 15 '09 at 13:52
  • i also agree that hashmap or unordered would be a good chooice. and i agree that if N becomes very very large, vector will have very bad perfromance. – Test Oct 15 '09 at 13:53
  • The minimum character limit exists to encourage you to write full sentences that form well-composed and insightful answers... not to dump the name of a type then "pad" the rest of your answer with useless bumf. – Lightness Races in Orbit Jun 02 '11 at 14:37
  • And, no, `std::vector` is _not_ appropriate for "insertion and removal of elements at any position". – Lightness Races in Orbit Jun 02 '11 at 14:38