时间戳

首页 > 解决方案 > 使用迭代器对 std::list 进行排序

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

问题描述

是否可以像这样对迭代器定义的列表的一部分（列表的子集）进行排序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()});

我很欣赏一旦对项目执行移动操作，迭代器就会失效，我认为这意味着如果在下一次“比较”之前不重新迭代到所需位置，列表就无法按迭代器排序？

在这种情况下，在不为此过程填充另一个容器（如果有的话）的情况下对列表子集进行排序的最佳实践是什么？

非常感谢。

标签： c++listsortingiterator

解决方案

填充另一个容器是不可避免的。但是您不必移动或复制您自己的任何数据。您可以使用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是用输入分配器的副本构造的，以实现最大的通用性。拼接回是在我们选择的范围保护中完成的，以支持比较函数抛出的情况，所以我们的基础现在被覆盖了。

这是一个活生生的例子，为了说明目的，使用了一个幼稚且有点愚蠢的范围保护实现。

推荐阅读