3

I need a container that allows me to fast erasing ONE element while I am looping over it. I don't need direct access because I always access it within a loop.

Is List faster than Vector for this case?

Pseudocode:

vector<Item*> myContainer;

for(..loop over it...) {

  if (someCondition)
    myContainer.erase(currentElement)
}

After having deleted an element I need to keep looping over the rest of elements

3 Answers3

8

Yes, in theory lists offer faster removal than vectors, but in practice, nobody uses lists. Why not? Because vectors generate much less heap activity, and they offer much better cache locality.

Are you sure you absolutely need to loop over the vector and erase elements one by one? That would result in quadratic complexity for vectors, but the erase-remove-idiom does it in linear time:

#include <algorithm>

myContainer.erase(
    std::remove_if(
        myContainer.begin(),
        myContainer.end(),
        [](Item* p) {
            return p->someCondition;
        }
    ),
    myContainer.end()
);

(If the vector owns the Items, you should probably replace it with a vector<unique_ptr<Item>>.)

As an alternative, if you really must remove the elements one by one, and you don't care about the relative order of the Items, there is a neat little trick to remove one element of a vector in constant time.

Community
  • 1
  • 1
fredoverflow
  • 256,549
  • 94
  • 388
  • 662
  • @yes123 Sure, just put whatever you want to do with each item inside the lambda, before the `return p->someCondition;` line. It's a bit unusual to have a mutating predicate, but I don't see why it shouldn't work in this specific case. Alternatively, first do a `for_each` to update the items, and then apply the erase/remove idiom to remove the unwanted items. That would be a bit cleaner but also probably a bit less cache-friendly. – fredoverflow Jul 22 '12 at 18:09
5

Erasing elements at arbitrary positions is faster with lists:

Complexity of std::vector::erase: Linear on the number of elements erased (destructors) plus the number of elements after the last element deleted (moving).

Complexity of std::list::erase: Linear on the number of elements erased (destructors).

Also, after erase the iterator will be invalid, so you need to update your iterator:

it = list.erase(it);
Community
  • 1
  • 1
perreal
  • 94,503
  • 21
  • 155
  • 181
  • It also depends on how long the vector is. Moving a bunch of pointers (`Item*`) already in the CPU cache can be just as fast as deallocating a list node (which also requires some relinking). It isn't a given that O(1) is *always* faster than O(n). – Bo Persson Jul 22 '12 at 09:53
  • @yes123 - Right, I'm talkning about "in practice". Using a vector is often surprisingly fast, because its elements are adjacent in memory and end up in the same cache line. A linked list of pointers will also use 3 times as much memory as a vector of pointers. I'm just saying that moving one big box (`O(1)`) isn't *always* better than n small boxes (`O(n)`). – Bo Persson Jul 22 '12 at 10:45
1

A c++ list is a linked list. So elements will be arranged like follows,

 head <--> 1 <--> 2 <--> 3 <--> 4 <--> 5

So, when I want to remove 3, it is just a pointer shuffling. I want to erase 3, I need to move 2's pointer to point to 4. In this case, I need to travel till 3(spot the element). Time complexity will be O(1) worst case since it is a doubly linked list and you already pin point to the element you are deleting.

However on the other hand a c++ vector is just an array. So a vector element removal follows removing element from the array. In this case, you can spot the element to be erased in O(1) complexity. But to erase it, you need to left shift all the elements to remove the void created. So the complexity is O(n) worst case. Verbally the complexity can be something like "n - index of element to be removed".

List yield a deletion complexity of O(1) and vector O(n) asymptotic. But the list will have additional overhead of maintaining pointers(O(2n) space additional overall) for each element.

Mohan
  • 1,850
  • 1
  • 19
  • 42
  • Hmm, since you are already iterating, list will be faster. Sorry bro missed that part. – Mohan Jul 22 '12 at 10:39
  • To continue to press my point (sorry :-). In this example, the objects themselves are also pointers. So, with a linked list you have to change two pointers (in `2` and `4`), and then dispose of the node containing `3`. With a vector, you just copy two pointers (`4` and `5`), and then you are done. Which operation is the fastest? – Bo Persson Jul 22 '12 at 11:26
  • @BoPersson Assume the list has upto 20 elements. What will be faster? List, no? – Mohan Jul 22 '12 at 12:52
  • @MohanKumar - I would still bet on the vector. We are still talking nanoseconds for copying 10 or 20 pointers. If it was a million entries, it might be different. – Bo Persson Jul 22 '12 at 12:57