First of all, std::list and std::vector are part of the STL (Suspicious
and Troublesome Library). As such, they're part of the problem set, because
while they're easy to use and undenyably powerful, they have a hidden
agenda in terms of efficiency. std::vector moreso than std::list. std::vector
can - and will - decide that it needs to be copied at random times.
Nonsense. The times are not random at all -- the standard specifies
exacctly what iterators can be invalidated by what operations.
This
means that if you add items to a vector, expect them to be copied at some point
in time, especially when you're least expecting it. Every time a std::vector
claims to do something "in constant time", it really means "I'm going to hit
you over the head with a copy constructor or an assignment operator", where
if std::list cliams constant time, it usually just means updating a pointer
or two. This alone opens up a can of worms. It may be tolerable for POD, but
it's devastating if you're dealing with large objects.
The standard specifically says that adding to a vector happens in
"amortized constant time", and textbooks that explain exactly what this
means and how it relates to std::vector are easily and widely available.
Yes, some operations on std::list are constant time instead of amortized
constant time. Then again, just for one obvious example, finding an item
in a list is always linear time, where in a (sorted) vector it can be
logarithmic (which, it should be pointed out, is practically constant
for most reasonable sizes of collections).
[ ... ]
1) Inserting elements in a list is constant time, whereas it is linear time[1]
in a vector unless in the specific case of adding to the end where there
is enough reserved room.
But find the right place to insert the item in the list is linear time
except in the specific case of adding to the beginning, end, or a
previously "memorized" position.
2) Splicing a list isn't even possible with a vector without making a copy
Quite true -- but he didn't mention anything that indicated that he
cared at all about splicing anything.
3) Removing elements from a list is constant time, linear time[1] in a vector.
Removing elements from a list has the same properties as inserting them,
so see the reply to 1) above.
4) Nearly every operation on a vector will invalidate any iterator, not so
with a list.
Pure nonsense. The iterators that can be invalidated by specific
operations are clearly documented.
5) The lifetime of objects in a list is clearly defined, in a vector it's not.
This is pure FUD. In any case, one of the basic ideas of _all_ the
standard containers is that they should be used to hold _values_ that
are relatively cheap to copy; if the lifetime of specific objects is a
major concern, NO standard container is likely to work well for you.
6) Swapping two elements in a list is cheap, it can be expensive in a vector
More FUD. Swapping elements in a vector is a constant-time operation
just like with list.
7) vectors always suffer from overallocation, in an attempt to keep things
acceptable.
And so do lists. The difference is that a list inter-mixes the
overallocation (in the form or at least two pointers per node) with the
real data, hurting locality of reference. As previously mentioned, on a
typical system that uses virtual memory, the overallocation in a vector
is purely of address space, not really memory at all. Since the extra
space in a list is intermixed with the stord data, the overallocation in
a list does need to be backed by real memory.
The benefit std::vector has to offer is, of course, that it provides random
access. But in a lot of cases, you don't need random acccess - so why choose
a container that is only optimal for random access, if you don't need it?
You've mis-characterized the situation in both directions. You've
ignored many of the strengths of vectors and many of the weaknesses of
lists.
Of course, you can plug all these problems with yet another publicly available
patch from STL or boost, but they're just that: A patch.
Complete nonsense. First of all, patches are generally just to fix
coding errors, and have no effect on the fundamental trade-offs between
different types of containers. Second of all, most of what you can get
from Boost is not patches of anything -- it's things like completely new
and different containers such as array, dynamic_bitset and multiindex
that provide capabilities that simply aren't present in the standard
library -- though TR1 added some of these, and all of those in TR1 are
also included in (at least the current draft of) C++ 0x.
PS: To all those people who will doubtlessly respond with
"premature optimization": You're wrong. Choosing the right
data type isn't about optimization, and it can never be premature.
To an extent it is about optimization, and it can CERTAINLY be
premature. Nonetheless, it's true that once you've chosen a data
structure it can be more difficult than most of us would like to change
that decision.