Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Sorting a std::list using iterators

Tags:

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.

like image 997
lfgtm Avatar asked May 23 '18 08:05

lfgtm


People also ask

Can you use std::sort with a list?

std::sort requires random access iterators and so cannot be used with list .

Can you sort list in C++?

The C++ function std::list::sort() sorts the elements of the list in ascending order. The order of equal elements is preserved.

Is std::list sort () stable?

Yes, std::list<>::sort is guaranteed to be stable.

Why does std::list need a special sort method?

std::list , being a linked list, cannot provide random access to its elements efficiently. That's why it provides its own specialized sort algorithm.


1 Answers

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.

like image 182
StoryTeller - Unslander Monica Avatar answered Oct 08 '22 00:10

StoryTeller - Unslander Monica