Сортировка 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()});

Я понимаю, что итераторы становятся недействительными, как только операция перемещения выполняется над элементом, который, как я полагаю, означает, что список не может быть отсортирован с помощью итераторов без повторной итерации в нужное место до следующего "сравнения"?

В каком случае лучше всего сортировать подпрограммы списков без заполнения другого контейнера для этого процесса (если таковые имеются)?

Большое спасибо.

Ответ 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 построен с копией входного распределителя для максимальной типичности. Склеивание назад выполняется в области защиты по нашему выбору, чтобы поддерживать случай, когда функция сравнения выбрасывается, поэтому наши базы теперь покрыты.

Вот живой пример, с наивной и несколько глупой реализацией охранника области для целей экспозиции.

Ответ 2

Возможно ли отсортировать часть списка (подмножество списка), определенного итераторами типа std :: sort?

Я предполагаю, что вы имели в виду std :: list :: sort. Внедрение 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;
        }
    }