comp.lang.c++

Andy Champ wrote:
> desktop wrote:
>> How long does it take to sort elements in a std::list in worst case?
>>
>> I have read that quicksort on average (depends on partitioning) takes
>> O(nlgn). But is quicksort used when sorting a std::list?
>>
>> And is it possible to sort faster than O(nlgn) in general - not
>> looking a best case?
>
> I have to wonder why you put the elements in a list (rather than,
> say, a map) if you're going to sort them. Then they could be sorted
> on-the-fly as they go in...

The speed of adding to a map has no comparison with that of a list.

> Also, you don't *have* to use std::sort.

Actually, you can think of a map as using std::sort _every time_
you insert something, plus rebalancing. The price is there, you
just never think you're paying it until you profile the insertions.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask