Using STL sort with custom classes?

Oct 8, 2013 at 9:00pm
Hello, everyone. I've written a doubly linked list per my assignment instructions. I've implemented begin() and end() iterators for it, and they work with no problems when traversing the list. However, I need to sort the elements in the list. We are allowed to use the sort function defined in the <algorithm> header since we haven't yet covered sorting algorithms.

But, I'm running into a ton of problems. I figured as long as the begin() and end() iterators were defined for the list, then sort(list.begin(), list.end(), compare) would do the trick. The main errors I'm getting are:

error: no type named iterator_category
error: no type named value_type
error: no type named difference_type
error: no type named pointer
error: no type named reference

And also errors for no match of the + and - operators for the iterator class.

I understand reference, pointer, and value_type, but I have no idea about iterator_category and difference_type. Additionally, I'm a little unsure why the + and - operators need to be overloaded. Any help would be much appreciated!

Oct 9, 2013 at 1:41am
Those messages are saying that what your begin and end return aren't random access iterators (which std::sort requires), and in fact aren't iterators at all. Look up iterator categories, std::iterator, std::iterator_traits, and optionally, boost iterators library (which makes it a bit easier to write the)
Oct 9, 2013 at 3:24am
What do begin and end return? If they return pointers it should work just fine, but if they return the actual elements then you don't understand begin and end properly.
Oct 9, 2013 at 1:57pm
Begin and end do return pointers. I ended up just writing my own sorting algorithm. It was ironically a lot easier than trying to sort out this mess. I appreciate the responses, though.
Oct 9, 2013 at 2:20pm
Begin and end do return pointers.
They return iterators, which aren't the same thing.
Oct 9, 2013 at 2:40pm
raw pointers are most certainly iterators, of random access variety:

1
2
3
4
5
6
7
8
#include <iterator>
#include <type_traits>
int main()
{
    static_assert(
        std::is_same<std::iterator_traits<int*>::iterator_category,
                     std::random_access_iterator_tag>::value, "");
}
Oct 9, 2013 at 3:28pm
@kbw you can definitely use std::sort with pointers (e.g. sorting a c-style array). EDIT: Though as Duoas points out below, this is not possible for Linked Lists.
Last edited on Oct 9, 2013 at 4:26pm
Oct 9, 2013 at 4:03pm
OP is iterating over a custom linked list. Even the STL linked list doesn't work with std::sort(), and provides its own member sort function.

As already noted, std::sort() requires random-access iterators, which is a wasted effort on a linked list. A better choice would be to use a mergesort instead of a quicksort/introsort.

And kbw's assessment is spot-on (spot-on == correct). There's no way to return raw pointers to iterate over a linked list.
Last edited on Oct 9, 2013 at 8:03pm
Oct 9, 2013 at 7:09pm
I know
Topic archived. No new replies allowed.