Sorting a std::list using iterators

Question

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.

I don't see a disadvantage in using std::sort(). From cppreference: type of dereferenced doesn't have to be copyable, which implies that no copying is involved. And time complexity is O(n*log(n)). — Yksisarvinen
– Yksisarvinen, Commented May 23, 2018 at 8:53
@Yksisarvinen - It requires a random access iterator, which std::list doesn't provide. — StoryTeller - Unslander Monica
– StoryTeller - Unslander Monica, Commented May 23, 2018 at 8:55

T.C. · Accepted Answer · 2018-05-23 18:17:00Z

25

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.

edited May 23, 2018 at 18:17

T.C.

139k18 gold badges306 silver badges440 bronze badges

answered May 23, 2018 at 8:54

StoryTeller - Unslander Monica

172k22 gold badges401 silver badges481 bronze badges

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

20 Comments

StoryTeller - Unslander Monica Over a year ago

@SaufenmitProgramming - Only the second call. Unfortunately the first one is linear. Though of course the complexity is dominated by the sorting function here.

catnip Over a year ago

If you're going to copy them before you sort them, it would make more sense to copy them into a vector. Sorting that will obviously be faster, unless the number of elements is very small.

T.C. Over a year ago

For more genericity you'd want to a) construct sorter with the input list's allocator and b) splice the nodes back if the sorting throws (which it can, e.g., from the comparator).

lfgtm Over a year ago

Thankyou very much! This worked as I need it to :) and I have learnt something I probably should have learnt many a moon ago 0.o.

StoryTeller - Unslander Monica Over a year ago

@PaulSanders - It is the goto container indeed. But I don't think it's my place to question the OP's need for using a list, and as such impose a vector. Their data may not be move constructible, for instance. Or they may not wish to copy/move it for other reasons. So moving it into a vector and sorting is a non starter in this case.

|

rcgldr · Accepted Answer · 2018-05-24 19:41:24Z

Is it possible to sort portion of a list (subset of a list) defined by iterators like std::sort does?

I assume you meant std::list::sort. Visual Studio 2015's implementation does this, and without having to populate another container. It is a top down merge sort that is less efficient than the prior bottom up merge sort, but it avoids allocating memory that the prior version did since the prior version allocated a small array of lists. Psuedo code would look something like this:

    right = std::next(right, 1);   // right = end of sub-list
    size = std::distance(left, right);
    left = MyListSort(list, left, right, size);
    right = std::next(left, size-1);  // right = last element of sub-list
    // ...
    MyListSort(list, left, right, size)
    {
        if(size < 2)
            return left;
        mid = std::next(left, size/2);
        MyListSort(list, left, mid, size/2);
        MyListSort(list, mid, right, size-size/2);
        firstloop = true;
        newleft = left;
        while(true){
            if(*left <= *mid){
                if(++left == mid)
                    return newleft;
            } else {
                if(firstloop)
                    newleft = mid;
                list.splice(left, list, mid);
                if(++mid == right)
                    return newleft;
            }
            firstloop = false;
        }
    }

Collectives™ on Stack Overflow

Sorting a std::list using iterators

2 Answers 2

20 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

20 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related