Array Points

[Hiura]

EDIT : don't read my crappy post!

Removing elements from a vector is painful.

It is not. This is only known by few people, but ignoring the element order, you can remove elements of a std::vector in O(1). And this is much faster than at std::list, because no dynamic deallocation comes to play.

You're wrong. (isn't it the first one I read? héhé <- French laughing)

From dinkumware :

Erasing N elements causes N destructor calls and an assignment for each of the elements between the insertion point and the end of the sequence. No reallocation occurs, so iterators and references become invalid only from the first element erased through the end of the sequence.

So erasing an/some element(s) is O(n), where n is the number of element «behind» the erased one(s).

Well, if you're using pointers you can take it as O(1) (negligible). Lists are more powerful otherwise FOR INSERTION/ERASING, not for iterating.

NB : run some performance tests to see if you really need list instead of vector. If you're doing only a few insertion-erasing per second it won't matter to use vector.

[Laurent]

So erasing an/some element(s) is O(n), where n is the number of element «behind» the erased one(s).

"ignoring the element order" means that in this case, you can swap the element to remove and the last one, and then erase the last one. This is O(1)

[Hiura]

So erasing an/some element(s) is O(n), where n is the number of element «behind» the erased one(s).

"ignoring the element order" means that in this case, you can swap the element to remove and the last one, and then erase the last one. This is O(1)

oupsi  :roll:

[Nexus]

In my own applications, the reason to choose std::list over other containers was mostly the fact that pointers, references and iterators to elements remain valid unless the element itself is removed. The same also applies to the four associative containers of the standard library.

@ Laurent: Thank you for reading my mind