Re: STL container question
On Oct 1, 6:40 pm, Pete Becker <p...@versatilecoding.com> wrote:
On 2008-10-01 10:23:13 -0400, Ioannis Vranos
<ivra...@no.spam.nospamfreemail.gr> said:
Victor Bazarov wrote:
Ioannis Vranos wrote:
Victor Bazarov wrote:
Store first, then sort, then search (using 'std::binary_search'), yo=
u
could just use 'std::vector'.
For that case, I think std::list is a better option, since the sortin=
g
will be faster,
Do you have any proof of that?
Lists are implemented using pointers to point to the previous and to
the next elements, so list::sort(), is more efficient by changing
pointer values, while sorting a vector involves copying objects.
In other words, no. <g> One could also point out that quicksort can be
used to sort a vector but can't be used on a list, so obviously sorting
a vector is faster.
Not always so.
You are correct that as lists do not provide random-access iterators
quicksort can not be used. Instead, lists are normally sorted using
merge sort. Merge sort has better worst-case performance than
quicksort. The drawback of merge sort is that it normally requires
extra memory, whereas quicksort does not.
http://en.wikipedia.org/wiki/Merge_sort
<quote>
In the worst case, merge sort does about 39% fewer comparisons than
quicksort does in the average case; merge sort always makes fewer
comparisons than quicksort, except in extremely rare cases, when they
tie, where merge sort's worst case is found simultaneously with
quicksort's best case. In terms of moves, merge sort's worst case
complexity is O(n log n)=97the same complexity as quicksort's best case,
and merge sort's best case takes about half as many iterations as the
worst case.
</quote>
--
Max