Is it possible to sort portion of a list (subset of a list) defined by iterators like std::sort
does?
i.e with a std::list
the only sort available is via a method (http://en.cppreference.com/w/cpp/container/list/sort), I would like to be able to sort part of a list from its iterators using std::sort
. e.g
std::sort(listItrStart, listItrEnd, [](T& a, T& b){ return a.something() < b.something()});
I appreciate that iterators would become invalidated once a move operation is done on an item, which I assume means that a list cannot be sorted by iterators without re-iterating to the desired location before the next 'compare'?
In which case what is the best practice for sorting subsests of lists without populating another container for this process (if any)?
Many thanks.
std::sort requires random access iterators and so cannot be used with list .
The C++ function std::list::sort() sorts the elements of the list in ascending order. The order of equal elements is preserved.
Yes, std::list<>::sort is guaranteed to be stable.
std::list , being a linked list, cannot provide random access to its elements efficiently. That's why it provides its own specialized sort algorithm.
Populating another container is unavoidable. But you don't have to move or copy any of your own data. You can use std::list::splice
to extract and reinsert the nodes you want to process into sorted order.
using list_t = std::list<widget>; void process(list_t& in, list_t::const_iterator begin, list_t::const_iterator end) { list_t sorter; sorter.splice(sorter.end(), in, begin, end); sorter.sort(); in.splice(end, sorter); }
The function transfers the nodes you wish to sort into the sorter list (the first iterator argument is the position before which the nodes are inserted, in this case the end of the list).
The sorter list is sorted (obviously), and then the sorted content is transferred back into the source list, exactly into the original sub-range it originally populated.
As commented by @T.C. The next step is to generalize it. It can be made into a template much like this one:
template<class List, class Compare = std::less<>> void sort_subrange(List& in, typename List::const_iterator begin, typename List::const_iterator end, Compare c = {}) { List sorter(in.get_allocator()); sorter.splice(sorter.end(), in, begin, end); [[maybe_unused]] ScopeGuard sg([&]() { in.splice(end, sorter); }); sorter.sort(std::move(c)); }
The comparator is taken as an argument here as well, and sorter
is constructed with a copy of the input's allocator for maximum genericity. The splicing back is done in a scope guard of our choosing to support the case where the compare function throws, so our bases are now covered.
Here is a live example, with a naive and somewhat silly implementation of a scope guard, for exposition purposes.
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