使用迭代器对std :: list进行排序

Question

是否可以对迭代器定义的列表(列表的子集)的部分进行排序std::sort？

即,std::list唯一可用的排序是通过一种方法(http://en.cppreference.com/w/cpp/container/list/sort),我希望能够使用它的迭代器对列表的一部分进行排序std::sort.例如

std::sort(listItrStart, listItrEnd, [](T& a, T& b){ return a.something() < b.something()});

我感谢一旦对项目执行了移动操作,迭代器将变为无效,我认为这意味着在下一次"比较"之前,迭代器无法对列表进行排序而无需重新迭代到所需位置？

在这种情况下,排序子列表的最佳做法是什么,而不为此过程填充另一个容器(如果有的话)？

非常感谢.

Answer 1

填充另一个容器是不可避免的.但您不必移动或复制任何自己的数据.您可以使用std::list::splice提取和重新插入要处理的节点按排序顺序.

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);
}

该函数将您要排序的节点传输到排序器列表中(第一个迭代器参数是插入节点之前的位置,在本例中是列表的结尾).

排序器列表(显然)进行排序,然后将排序后的内容传输回源列表,完全转移到最初填充的原始子范围内.

由@TC评论下一步是概括它.它可以像这样制作成模板:

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));
}

比较器也作为参数,并sorter使用输入分配器的副本构造,以获得最大的通用性.拼接在我们选择的范围内进行,以支持比较函数抛出的情况,因此我们的基础现在已被覆盖.

这是一个现实的例子,为了展示目的,有一个天真的,有点愚蠢的范围保护实现.