sorting a std::list

[velthuijsen]

I tried taking a list and pass it through std::sort like the following:
sort(Unsorted.begin(), Unsorted.end());
I got an error back stating that the list iterator doesn't have a
binary substraction operator.
Peeking in the algoritm header file it's clear why seeing that sort
there calls _sort(_First, _Last, _Last-_First) which might be a tad
challenging seeing that the different values stored in a list do not
need to be stored consecutively.
My question is there another way to sort the list in the STL?

 

[Mike Hewson]

I tried taking a list and pass it through std::sort like the following:
sort(Unsorted.begin(), Unsorted.end());
I got an error back stating that the list iterator doesn't have a
binary substraction operator.
Peeking in the algoritm header file it's clear why seeing that sort
there calls _sort(_First, _Last, _Last-_First) which might be a tad
challenging seeing that the different values stored in a list do not
need to be stored consecutively.
My question is there another way to sort the list in the STL?

I think you want

list::sort( CompFunc op )

where

op( elem1, elem2 )

compares two elements?

( See 'The C++ Standard Library" - Josuttis p 245-6 )

After all, you have a list of somethings - the elem1's and elem2's - of
a type for which some way of ordering is presumably available. The
comparison function takes any two elements and determines their relative
ranking. The implementation may well complain if it has no way of telling.
Hope this helps.

 

[velthuijsen]

list::sort( CompFunc op )

You know, I feel really stupid now. I don't know how I managed to miss
the sort function of list.

 

[Mike Hewson]

I think you want

list::sort( CompFunc op )

where

op( elem1, elem2 )

compares two elements?

( See 'The C++ Standard Library" - Josuttis p 245-6 )

After all, you have a list of somethings - the elem1's and elem2's -
of a type for which some way of ordering is presumably available. The
comparison function takes any two elements and determines their relative
ranking. The implementation may well complain if it has no way of telling.
Hope this helps.

Also I found ( Josuttis again p 397 ) that std::sort and
std::stable_sort use *random access iterators*. Hence can't be used for
lists, as they are not provided for that type of container.

 

[Mike Hewson]

You know, I feel really stupid now. I don't know how I managed to miss
the sort function of list.

Tre Cool, dude.
Ah, I'm still *re-reading* Josuttis, two years later!

 

[Ioannis Vranos]

I tried taking a list and pass it through std::sort like the following:
sort(Unsorted.begin(), Unsorted.end());
I got an error back stating that the list iterator doesn't have a
binary substraction operator.
Peeking in the algoritm header file it's clear why seeing that sort
there calls _sort(_First, _Last, _Last-_First) which might be a tad
challenging seeing that the different values stored in a list do not
need to be stored consecutively.
My question is there another way to sort the list in the STL?

someList.sort();


However I would expect an std::sort overload for std::list in an
implementation. Does anyone know if this is required by the standard?

 

[Buster]

someList.sort();


However I would expect an std::sort overload for std::list in an
implementation. Does anyone know if this is required by the standard?

It is not (or at least, was not in 1998). The std::sort function in the
<algorithm> header only takes random access iterators. In any case, if
you're thinking you could write std::sort to take its two iterators and
delegate the sorting to a list object, I think you're mistaken. I don't
see how you would get access to the container object. (Cf. the situation
with the remove algorithm and the erase member function.)

 

[Ioannis Vranos]

In any case, if
you're thinking you could write std::sort to take its two iterators and
delegate the sorting to a list object, I think you're mistaken. I don't
see how you would get access to the container object. (Cf. the situation
with the remove algorithm and the erase member function.)

Indeed, you are right about that. I think TC++PL states this somewhere.

 

[Jon Wilson]

I tried taking a list and pass it through std::sort like the following:
sort(Unsorted.begin(), Unsorted.end());
I got an error back stating that the list iterator doesn't have a
binary substraction operator.
Peeking in the algoritm header file it's clear why seeing that sort
there calls _sort(_First, _Last, _Last-_First) which might be a tad
challenging seeing that the different values stored in a list do not
need to be stored consecutively.
My question is there another way to sort the list in the STL?

For a very good STL reference (especially if your STL implementation is
SGI's, which is fairly common I think (its free)), look at
http://www.sgi.com/tech/stl/

There, we see (http://www.sgi.com/tech/stl/sort.html):

template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);

Complexity
O(N log(N)) comparisons (both average and worst-case), where N is last -
first. [2]


So the sort function only takes Random Access Iterators, whereas
list::iterator is a Bidirectional Iterator.

Thus, we go to the list page (http://www.sgi.com/tech/stl/List.html),
and we have:

New members
These members are not defined in the Reversible Container, Front
Insertion Sequence, and Back Insertion Sequence requirements, but are
specific to list.
----
void sort(); Sorts *this according to operator<. The sort is stable,
that is, the relative order of equivalent elements is preserved. All
iterators remain valid and continue to point to the same elements. [6]
The number of comparisons is approximately N log N, where N is the
list's size.
----
[6] The sort algorithm works only for random access iterators. In
principle, however, it would be possible to write a sort algorithm that
also accepted bidirectional iterators. Even if there were such a version
of sort, it would still be useful for list to have a sort member
function. That is, sort is provided as a member function not only for
the sake of efficiency, but also because of the property that it
preserves the values that list iterators point to.



So, use the list::sort() function to sort a list, or if you need a
comparison function other than STL's less functor, there is a member
template version of list::sort(BinaryPredicate Comp) which lets you do that.

One warning: if you are not using SGI's STL, then watch out for SGI
extensions to the standard on this reference site.

 

[Dave O'Hearn]

someList.sort();

However I would expect an std::sort overload for std::list in an
implementation. Does anyone know if this is required by the standard?

It's not required. Depending on how the list is implemented, it may not
be possible to do it well. list::sort can work simply by rearranging
its pointers without copying. std::sort would not have access to the
list object itself, and would have trouble reassigning the 'begin' and
'end' data. It could work by swapping the values themselves, but it
would be no substitute for list::sort.

 

[Mike Wahler]

You know, I feel really stupid now. I don't know how I managed to miss
the sort function of list.

Perhaps the approach I use might help:
When looking for a function to operate on
a container, I first peruse its member functions,
then if not found, look 'globally', e.g. the
stuff in <algorithm>. An aside, not specific to
your problem: Most of my books advise that if both
member and nonmember solutions are available, one
should generally prefer the member solution, as it's
more likely to have better performance. But of course,
depending upon the implementation used, YMMV.

-Mike

 

[Karthik Kumar]

someList.sort();


However I would expect an std::sort overload for std::list in an
implementation. Does anyone know if this is required by the standard?

C++ 2003 standard : Section 23.2.2.4 - mentions about the sort()
method in the list container, with a complexity of (n.log n).