Menu
I have a linked list that I want to sort part of, eg:
std::sort(someIterator, otherIterator, predicate);
std::sort requires random-access iterators so this approach doesn't work. There is a specialisation std::list::sort, but that can only sort the entire list. I don't think I have enough access to the list members to write something myself.
Is there a way to do this without changing to, say, vector?
900
std::sort requires random access iterators and so cannot be used with list .
C++ Algorithm partial_sort() function is used to rearrange the elements in the range[first, last), in such a way that the elements between the first and middle will be sorted and the elements between the middle and last will be in an unspecified order.
Yes, std::list<>::sort is guaranteed to be stable.
std::sort is a generic algorithm that's supposed to work for anything that provides iterators. However, it really expects a random access iterator to sort efficiently. std::list , being a linked list, cannot provide random access to its elements efficiently. That's why it provides its own specialized sort algorithm.
How about unhooking the part of the list that you want sorted, into a standalone list, then use the specialized list sort, then hook it back into the original list?
68
Yes, but you will have to use a merge sort.
29
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
