CODEWITHSUNDEEP
c++algorithmlistsortinglinked-list
Rob Rob
Rob Rob

Reputation: 3

Sorting a custom linked list with <algorithm> sort

I've written my own doubly linked list, complete with begin() and end() iterators. These work fine with traversing the list using a loop. However, as part of my assignment, I need to sort the list according to certain criteria. Since we haven't yet covered the chapter on sorting algorithms, we are allowed to use the sort function defined in the header. But sort(list.begin(), list.end(), compare) returns quite a few errors related to my iterator class:

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

Additionally, I receive errors regarding the + and - operators. I understand how to define value_type, pointer, and reference, but I'm lost when it comes to the others. Is what I'm trying to do possible? Thanks!

Upvotes: 0

Views: 429

Answers (1)

Jerry Coffin
Jerry Coffin

Reputation: 490218

It's possible, but can be somewhat painful, as you'll end up writing a fair amount of boilerplate code.

Worse, when you're done, it won't work very well -- std::sort doesn't absolutely require random access iterators, but with (say) bidirectional iterators, performance will generally be fairly poor. Just for example, it's poor enough that (unlike most standard containers) std::list has a sort member function to make up for the fact that std::sort works poorly on linked lists.

Basically, operator+ and operator- just advance a pointer N items forward or backward. typically you overload operator++ to advance by one, something like pos = pos -> next; (and operator-- uses something like pos = pos->prev;. Then you can use std::advance or std::next to advance by more than one item at a time (but be aware: for a bidirectional iterator it'll do that by calling ++ or -- repeatedly -- one of the reasons for poor performance).

Upvotes: 1

Related Questions