Sorting a std::list using iterators

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.