代码之家 › 专栏 › 技术社区 › lfgtm

排序STD::使用迭代器列表

iterator sorting list c++

lfgtm · 技术社区 · 6 年前

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

即 std::list 唯一可用的排序方法是通过一个方法( http://en.cppreference.com/w/cpp/container/list/sort ,我希望能够使用 STD::排序 . 例如

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

我很感激,一旦对一个项执行了移动操作,迭代器就会失效,我假设这意味着在下一个“比较”之前,如果不重新迭代到所需的位置,列表就不能由迭代器排序?

在这种情况下,在不填充此流程的另一个容器(如果有的话)的情况下对列表的子集排序的最佳实践是什么?

非常感谢。

2 回复 | 直到 6 年前

T.C. Yksisarvinen 6 年前

填充另一个容器是不可避免的。但您不必移动或复制任何自己的数据。你可以用 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);
}

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

排序器列表被排序(显然),然后排序的内容被传输回源列表,并精确地传输到它最初填充的原始子范围中。

正如@t.c.所评论的那样,下一步就是概括它。它可以制作成类似于此模板的模板:

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 使用输入分配器的副本构造,以获得最大的泛型。拼接是在我们选择的范围保护中完成的,以支持比较函数抛出的情况,因此我们的基础现在被覆盖了。

Here is a live example 以一种幼稚而有点愚蠢的范围保护实现,用于说明目的。

rcgldr 6 年前

是否可以排序一个列表(列表的子集)的部分,如STD::排序是否由迭代器定义?

我想你是指STD::名单:排序。Visual Studio 2015的实现可以做到这一点,而无需填充另一个容器。它是一种自上而下的合并排序,比以前的自下而上的合并排序效率低,但它避免了以前版本所分配的内存,因为以前的版本分配了一个小的列表数组。psuedo代码如下所示:

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