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!
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)
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.
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.
@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.
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.