sort on vector type

[Allan Bruce]

Hi there,

I am reading through accelerated c++, and have just finshed chapter 3.
My question is what sorting algorithm is used on vectors? e.g. if I had:

std::vector<int> scores;
// adding some values to scores
std::sort(scores.begin(), scores.end());

then what algorithm is used? or is this implementation specific?

Thanks
Allan

 

[Victor Bazarov]

I am reading through accelerated c++, and have just finshed chapter 3.
My question is what sorting algorithm is used on vectors? e.g. if I had:

std::vector<int> scores;
// adding some values to scores
std::sort(scores.begin(), scores.end());

then what algorithm is used? or is this implementation specific?

It is implementation-specific, it is only defined to adhere to
certain performance requirements. It's probably a quick-sort.

Victor

 

[Mike Wahler]

Hi there,

I am reading through accelerated c++, and have just finshed chapter 3.
My question is what sorting algorithm is used on vectors? e.g. if I had:

std::vector<int> scores;
// adding some values to scores
std::sort(scores.begin(), scores.end());

then what algorithm is used?

The language standard does not specify the
algorithm, only the 'complexity'.

or is this implementation specific?

Yes.

Also note that this is not specific to 'vector'.
'std::sort' can be used with any container
which supports random access iterators (this
includes arrays).


-Mike

 

[Kevin Goodsell]

I have programmed my own sorts as macros in c, and just wondered if it was
worthwhile using them over the standard sorts.
Allan

Almost certainly not. The standard routines are much less likely to have
errors, are available everywhere (while your versions may have
non-portable parts), and are probably faster than yours. Besides that,
they are standard. Everyone recognizes them and knows what they mean.
Add to that the fact that macros are bad, and the standard routines fit
with the rest of the standard library framework, and there's really no
good reason to use your own routines, and a number of reasons not to.

-Kevin