0

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!

Improve this question

1 Answer 1

Reset to default
1

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

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

So, it would probably be best to just write my own sorting algorithm, haha?
@RobRob: Unfortunately, yes. Better still: just avoid linked lists, where are rarely useful anyway.
Ah, okay. I would love to, honestly, but since this is for an assignment, I am bound to a linked list, haha.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.