2

For my application I am using STD vector. I am inserting to the vector at the end, but erasing from vector randomly i.e element can be erased from middle, front anywhere. These two are only requirement, 1)insert at the end 2) erase from anywhere.

So should I use STD List, since erasing does shifting of data. Or I would retain Vector in my code for any reason??

Please give comment, If Vector is the better option, how it would be better that List here?

Chris
  • 229
  • 1
  • 2
  • 11
  • IMO, if removing elements is an important aspect of your code, then choose the std::list; if you do not remove elements that often or if the vector is small, keep the vector. – Max Nov 05 '13 at 14:06
  • 3
    Some would say use `std::vector`, period. In terms of performance, cache locality is often more important than the complexity of insertion or deletion. http://www.youtube.com/watch?v=YQs6IC-vgmo – Marc Claesen Nov 05 '13 at 14:19
  • @MarcClaesen I've been posting that Bjarn video all over stackoverflow for months, no-one ever takes a blind bit of notice. "We know lists are better, lalala..." If you make your comment an answer I'll vote for it. – Grimm The Opiner Nov 05 '13 at 14:27
  • @user1158692 turned it into an answer :) – Marc Claesen Nov 05 '13 at 14:31

5 Answers5

4

One key reason to use std::vector over std::list is cache locality. A list is terrible in this regard, because its elements can be (and usually are) fragmented in your memory. This will degrade performance significantly.

Some would recommend using std::vector almost always. In terms of performance, cache locality is often more important than the complexity of insertion or deletion.

Here's a video about Bjarne Stroustrup's opinion regarding subject.

Community
  • 1
  • 1
Marc Claesen
  • 16,778
  • 6
  • 27
  • 62
2

I would refer you to this cheat sheet, and the conclusion would be the list.

enter image description here

DogDog
  • 4,820
  • 12
  • 44
  • 66
  • Do you draw it yourself or you copied it from somewhere on Internet? In second case, would you make a link? – masoud Nov 05 '13 at 14:13
  • I came across the image on stackoverflow, I'm sorry but I do not know the original reference to it. edit : Apparently it is from http://freenode.net/ but I do not have the original link. – DogDog Nov 05 '13 at 14:23
1

List is better in this case most probably. The advantage of a list over vector is that it supports deletion at arbitrary position with constant complexity. A vector would only be better choice if you require constant index operation of elements of the container. Still you have to take into consideration how is the element you would like to delete passed to your function for deletion. If you only pass an index, vector will be able to find the element in constant time, while in list you will have to iterate. In this case I would benchmark the two solution, but still I would bet on list performing better.

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
  • I read from following stackoverflow link, traversal of list causes cache misses, though I didn't understand completely. Does it will cost me, if I use List?? Please explain!! 5th answer of the link: http://stackoverflow.com/questions/238008/relative-performance-of-stdvector-vs-stdlist-vs-stdslist – Chris Nov 05 '13 at 14:16
  • 1
    You cannot say that for sure unless you measure it. Also, you have to find the element in the middle, which is O(1) for vector and O(N) for list. – juanchopanza Nov 05 '13 at 14:16
  • @juanchopanza I agree my initial statement was a bit strong. I have re-worded my answer a bit. – Ivaylo Strandjev Nov 05 '13 at 14:22
  • That's much better, +1. – juanchopanza Nov 05 '13 at 14:22
1

A list supports deletion at an arbitrary but known position in constant time.

Finding that position takes linear time, just like modifying a vector.

The only advantage of the list is if you repeatedly erase (or insert) at (approximately) the same position.

If you're erasing more or less at random, chances are that the better memory locality of the vector could win out in the end.

The only way to be sure is to measure and compare.

molbdnilo
  • 64,751
  • 3
  • 43
  • 82
0

It depends on many factors and how are you using your data.

One factor: do you need an erase that maintains the order of the collection? or you can live with changing order?

Other factor: what kind of data is in the collection? (numbers: ints/floats) || pointers || objects

Not keeping order

You could continue using vector if the data is basic numbers or pointers, to delete one element you could copy the last element of the vector over the deleted position, then pop_back(). This way you avoid moving all the data.

If using objects, you could still use the same method if the object you need to copy is small.

Keeping order

Maybe List would be your friend here, still, some tests would be advised, depends on size of data, size of list, etc

aaronps
  • 324
  • 1
  • 6
  • I am not bothered about order and data is the pointer. Thanks for your suggestion. Copying last element and pop_back will solve my problem. – Chris Nov 06 '13 at 06:12
  • @Chris well, if it solves your problem, maybe you could accept the answer – aaronps Nov 06 '13 at 12:58