Сортировка 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 :: sort?

Полагаю, вы имели в виду std :: list ::Сортировать.Реализация 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;
        }
    }

Answer 2

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

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