C ++: Скотт Мейерс "Эффективный STL": пункт 31: узнайте свои варианты сортировки: помогите понять

Question

Добрый день!

В своем "Эффективном STL" Скотт Мейерс написал

Третье - использовать информацию в упорядоченном контейнере итераторов, чтобы итеративно разделить элементы списка на позиции, в которых вы бы хотели, чтобы они находились. Как вы можете видеть, существует множество вариантов. (Пункт 31, вторая часть)

Может кто-нибудь объяснить мне это?

---

Больше текста (чтобы понять контекст):

Алгоритмы sort, stable_sort, частичный_сорт и nth_element требуют итераторов произвольного доступа, поэтому их можно применять только к векторам, строкам, запросам и массивам. Не имеет смысла сортировать элементы в стандартных ассоциативных контейнерах, потому что такие контейнеры используют свои функции сравнения, чтобы всегда оставаться отсортированными. Единственный контейнер, в котором мы могли бы использовать sort, stable_sort ,partal_Sort или nth_element, но не можем, это list, и list несколько компенсирует, предлагая свою функцию члена sort. (Интересно, что list :: sort выполняет стабильную сортировку.) Если вы хотите отсортировать список, то вы можете, но если вы хотите использовать part_sort или nth_element для объектов в списке, вы должны сделать это косвенно. Одним из косвенных подходов является копирование элементов в контейнер с итераторами произвольного доступа, а затем применение к нему желаемого алгоритма. Другой - создать контейнер list :: iterators, использовать алгоритм для этого контейнера, а затем получить доступ к элементам списка через итераторы. Третье - использовать информацию в упорядоченном контейнере итераторов, чтобы итеративно разделить элементы списка на позиции, в которых вы хотите, чтобы они находились. Как видите, существует множество вариантов.

Answer 1

Я не уверен, что за путаница, но я подозреваю, что это то, что относится к "объединению": std::list<T> имеет функцию-член splice() (ну, на самом деле, несколько перегрузок), которые передают узлы между списками.То есть вы создаете std::vector<std::list<T>::const_iterator> и применяете алгоритм сортировки (например, std::partial_sort()) к этому.Затем вы создаете новый std::list<T> и используете элемент splice() с итераторами из отсортированного вектора, чтобы расположить узлы в правильном порядке, не перемещая сами объекты.

Это будет выглядеть примерно так:

std::vector<std::list<T>::const_iterator> tmp;
for (auto it(list.begin()), end(list.end()); it != end; ++it) {
    tmp.push_back(it);
}
some_sort_of(tmp);
std::list<T> result;
for (auto it(tmp.begin()), end(tmp.end()); it != end; ++it) {
    result.splice(result.end(), list, it);
}

Answer 2

Допустим, вы хотели сделать partial_sort в списке.Вы можете сохранить итераторы в списке в наборе, предоставив функцию сравнения, которая может сортировать с использованием итераторов, например:

struct iterator_less
{   
    bool operator() (std::list<int>::iterator lhs,
                 std::list<int>::iterator rhs) const
    {
        return (*lhs < *rhs);
    }
};
typedef std::multiset<
    std::list<int>::iterator, iterator_less
> iterator_set;

Вы можете разрешить set выполнять сортировку, но так как она содержит итераторык списку, вы могли бы вы перечислить :: склеить, чтобы склеить их в список частично_сортированных:

std::list<int> unsorted, partialSorted;
unsorted.push_back(11);
unsorted.push_back(2);
unsorted.push_back(2);
unsorted.push_back(99);
unsorted.push_back(2);
unsorted.push_back(4);
unsorted.push_back(5);
unsorted.push_back(7);
unsorted.push_back(34);

    // First copy the iterators into the set
iterator_set itSet;
for( auto it = unsorted.begin(); it!=unsorted.end();++it)
{
    itSet.insert(it);
}
    // now if you want a partial_sort with the first 3 elements, iterate through the
    // set grabbing the first item in the set and then removing it.
int count = 3;
while(count--)
{
    iterator_set::iterator setTop = itSet.begin();
    partialSorted.splice(
        partialSorted.begin(),
        unsorted,
        *setTop);
    itSet.erase(setTop);
}

partialSorted.splice(
        partialSorted.end(),
        unsorted,
        unsorted.begin(),
        unsorted.end());

Answer 3

Заказываются контейнеры std::set и std::multiset.std::set реализует BST.Итак, это говорит о том, что вы должны создать std::set<std::list::iterators>, а затем использовать внутреннюю структуру BST для сортировки.Вот ссылка на BST , с которой можно начать.

Answer 4

Заказанный контейнер будет либо std::set, либо std::map.Если вы хотите создать компаратор, который принимает итераторы, вы должны использовать std::set<std::list<mydata>::iterator,comparator>, в противном случае вы можете использовать std::map<mydata,std::list<mydata>::iterator>.Вы просматриваете список от begin() до end() и вставляете итераторы в набор или карту;теперь вы можете использовать его для доступа к элементам в списке в отсортированном порядке, повторяя набор или карту, потому что он автоматически сортируется.

Answer 5

Редактировать Ах.Только что заметил "заказанный контейнер итераторов ".Это подразумевало бы создание индекса в другом контейнере.

Boost Multi Index имеет много примеров таких вещей (где отдельные коллекции индексируются несколькими различными предикатами упорядочения, а индексы являются не более чем коллекциями «указателей» (обычно итераторы) в базовый контейнер.

---

"Третий - использовать информацию в упорядоченном контейнере итераторов для итеративного разбиения элементов списка на те позиции, которые вы хотите, чтобы они былив "

Я думаю, что одно описание будет соответствовать этому описанию, когда выполняется std::sort_heap списка / вектора, в котором было std::make_heap / push_heap / pop_heap.

• make_heap: преобразовать последовательность в кучу
• sort_heap: отсортировать кучу
• push_heap: вставить элемент в кучу
• pop_heap: удалить верхний элемент из кучи

Кучи - это организации элементов в последовательностях, которые делают (относительно) эффективным сохранение коллекции в известном порядке.Вставка / удаление.Порядок является неявным (как рекурсивное определенное двоичное дерево, хранящееся в непрерывном массиве) и может быть преобразован в соответствующую правильно отсортированную последовательность, выполнив (высокоэффективный) алгоритм sort_heap.