Re: Sorting lists by struct member variables
On Sep 10, 9:31 am, Martijn van Buul <p...@dohd.org> wrote:
* LR:
Martijn van Buul wrote:
There are dozens of reasons why using a list can be more appropriate t=
han
a vector. In fact, unless you have a damn good reason why you *NEED* a
vector, you probably don't.
I'm a little surprised by that, could you expand on that?
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.
Not really that hidden. The complexity requirements of both are
part of the specification.
std::vector moreso than std::list. std::vector can
- and will - decide that it needs to be copied at random
times. 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.
It also means a separate allocation for each element. If you're
using std::vector, and appending at the end, you'll reallocate
and copy once in a while---very rarely, in fact. If you're
using std::list, you'll never copy, but you will reallocate for
every insertion, and for many objects, allocation is more
expensive than copying. And as Jerry Coffin pointed out,
std::vector has the best locality. In general, the accepted
rule seems to be to use std::vector by default, and other
containers as the need arrises.
Also, we shouldn't forget, std::deque, will never copy either,
as long as insertions are at one of the ends, and will still
have better locality than std::list.
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.
Other than being a pain in the std::end just because of
STL-ness, there's always the observation that:
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.
The original poster showed no indication that he was inserting
anywhere but at the end. Which is amortised constant time for
std::vector. Unless copying is extremely costly (in which case,
the type probably shouldn't have value semantics, and shouldn't
be put into a container to begin with), std::vector will be
faster than std::list if all insertions are at the end.
2) Splicing a list isn't even possible with a vector without making a copy
Which is only relevant is you need to splice.
3) Removing elements from a list is constant time, linear time[1] in a ve=
ctor.
It's constant time if you remove them from the end (and a very
small constant at that). It's constant time anywhere from a
list, but the constant is significantly larger. Since there was
no indication here that objects would ever be removed, the
argument is irrelevant here.
4) Nearly every operation on a vector will invalidate any iterator, not so
with a list.
Very few operations on vector actually invalidate iterators, but
it's true that this can sometimes be an argument in favor of
list. In practice, the way the STL is designed to be used, you
shouldn't have any iterators alive when doing any manipulations
on the container; iterators are designed to be short lived
objects, passed to an algorithm, and then best forgotten.
5) The lifetime of objects in a list is clearly defined, in a vector it's=
not.
??? The lifetime of an object is very exactly defined in both
cases.
6) Swapping two elements in a list is cheap, it can be expensive in a vec=
tor
You'll have to defend that; from what I can see, swapping the
value of two elements is always the same, regardless of the
container in which the elements live. Swapping the position of
two elements may be cheaper in a list, but again, that's only
relevant if you want to swap the position of elements.
7) vectors always suffer from overallocation, in an attempt to keep things
acceptable.
Not necessarily. It depends on how you manage your vector.
std::list always allocates more than the data requires, because
it needs extra pointers.
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?
It's optimal in general for simple things. As soon as you
become more complicated, you have to analyse more.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34