C++. Сборник рецептов - Д. Стефенс

Объединение двух list — это хороший пример ситуации, где можно использовать метод последовательности или аналогичный стандартный алгоритм. Следует предпочесть метод стандартному алгоритму, делающему то же самое, но это не всегда работает, и вот пример, который показывает, почему.

Рассмотрим список строк из примера 7.5:

lstStr1.sort(); // Сортируем, или объединение даст мусор!

lstStr2.sort(),

 lstStr1.merge(lstStr2); // Это list::merge

Есть две причины, по которым этот код отличается от вызова std::merge. Во-первых, оба списка list должны иметь один и тот же тип элементов. Это требование следует из объявления list::merge, которое имеет вид:

void merge(list<T, Alloc>& lst);

template <typename Compare>

void merge(list<T, Alloc>& lst, Compare comp)

Где T — это такой же тип, как и в самом шаблоне класса списка. Так что, например, невозможно объединить список из символьных массивов с завершающим нулем со списком из строк типа string.

Второе отличие состоит в том, что list::merge стирает входную последовательность, в то время как std::merge оставляет две входные последовательности неизменными. Скорее всего list::merge будет обладать лучшей производительностью, так как в большинстве случаев элементы списка не копируются, а перекомпонуются, но такая перекомпоновка не гарантируется, так что с целью выяснения реального поведения требуются эксперименты.

Также объединить две непрерывные последовательности можно с помощью inplace_merge. inplace_merge отличается от merge, так как он объединяет две последовательности «на месте». Другими словами, если есть две непрерывные последовательности (т.е. они являются частями одной и той же последовательности) и они отсортированы и требуется отсортировать общую последовательность, то вместо алгоритма сортировки можно использовать inplace_merge. Преимущество inplace_merge заключается в том, что при наличии достаточного объема памяти его работа занимает линейное количество времени. Если же памяти недостаточно, то он занимает n log n, что равно средней сложности сортировки.

Объявление inplace_merge несколько отличается от merge:

void inplace_merge(Bid first, Bid mid, Bid last);

void inplace_merge(Bid first, Bid mid, Bid last, BinPred comp)

inplace_merge требует двунаправленных итераторов, так что он не является взаимозаменяемым с merge, но в большинстве случаев должен работать. Как и merge, для определения относительного порядка элементов он по умолчанию использует operator<, а при наличии — comp.

7.6. Сортировка диапазона

Имеется диапазон элементов, которые требуется отсортировать.

Для сортировки диапазонов имеется целый набор алгоритмов. Можно выполнить обычную сортировку (в восходящем или нисходящем порядке) с помощью sort, определенного в <algorithm>, а можно использовать одну из других функций сортировки, таких как partial_sort. Посмотрите на пример 7.6, показывающий как это сделать

Пример 7.6. Сортировка

#include <iostream>

#include <istream>

#include <string>

#include <list>

#include <vector>

#include <algorithm>

#include <iterator>

#include "utils.h" // Для printContainer(): см. 7.10

using namespace std;

int main() {

 cout << "Введите набор строк: ";

 istream_iterator<string> start(cin);

 istream_iterator<string> end; // Здесь создается "маркер"

 vector<string> v(start, end);

 // Стандартный алгоритм sort сортирует элементы диапазона. Он

 // требует итератор произвольного доступа, так что он работает для vector.

 sort(v.begin(), v.end());

 printContainer(v);

 random_shuffle(v.begin(), v.end()); // См. 7.2

 string* arr = new string[v.size()];

 // Копируем элементы в массив

 copy(v.begin(), v.end(), &arr[0]);

 // Сортировка работает для любого типа диапазонов, но при условии, что

 // ее аргументы ведут себя как итераторы произвольного доступа.

 sort(&arr[0], &arr[v.size()]);

 printRange(&arr[0], &arr[v.size()]);

 // Создаем список с такими же элементами

 list<string> lst(v.begin(), v.end());

 lst.sort(); // Самостоятельная версия sort работать не будет, здесь требуется

         // использовать list::sort. Заметьте, что невозможно отсортировать

         // только часть списка.

 printContainer(lst);

}

Запуск примера 7.6 может выглядеть вот так.

Введите набор строк: a z b y c x d w

^Z

-----

a b c d w x y z

-----

w b y c a x z d

-----

a b c d w x y z

-----

a b c d w x y z

Сортировка — это очень часто выполняющаяся операция, и есть два способа отсортировать последовательность. Можно обеспечить хранение элементов в определенном порядке с помощью ассоциативного контейнера, но при этом длительность операции вставки будет иметь логарифмическую зависимость от размера последовательности. Либо можно сортировать элементы только по мере надобности с помощью sort, имеющей несколько опций.

Стандартный алгоритм sort делает именно то, что от него ожидается: он сортирует элементы диапазона в восходящем порядке с помощью operator<. Он объявлен вот так.

void sort(Rnd first, Rnd last);

void sort(Rnd first, Rnd last, BinPred comp);

Как и в большинстве других алгоритмов, если operator< не удовлетворяет вашим требованиям, можно указать собственный оператор сравнения. В среднем случае сложность имеет зависимость n log n. В худшем случае она может быть квадратичной.

Если требуется, чтобы одинаковые элементы сохранили свой первоначальный порядок, используйте stable_sort. Он имеет такую же сигнатуру, но гарантирует, что порядок эквивалентных элементов изменен не будет. Его сложность при наличии достаточного объема памяти в худшем случае составляет n log n. Если памяти недостаточно, то сложность может оказаться равной n(log n)².

Однако sort работает не для всех контейнеров. Он требует итераторов произвольного доступа, так что при использовании контейнера, не предоставляющего таких итераторов, он неприменим. Итераторы произвольного доступа предоставляют стандартные последовательные контейнеры deque, vector и string/wstring (которые не являются контейнерами, но удовлетворяют большинству требований к ним), list — это единственный, который такого итератора не предоставляет. Если требуется отсортировать список, используйте list::sort. Например, в примере 7.6 вы, вероятно, заметили, что list::sort не принимает никаких аргументов.

lst.sort();

Это отличает его от std::sort, с помощью которого можно отсортировать только часть последовательности. Если требуется отсортировать часть последовательности, то не следует использовать list.

Концепция сортировки очень проста, но есть несколько вариаций на тему ее реализации в стандартной библиотеке. Следующий перечень описывает эти вариации.

partial_sort

Принимает три итератора произвольного доступа — first, middle и last — и (необязательно) функтор сравнения. Он имеет два постусловия: элементы диапазона (first, middle) будут меньше, чем элементы диапазона (middle, last), и диапазон (first, middle) будет отсортирован с помощью operator< или указанного функтора сравнения. Другими словами, он сортирует только первые n элементов.

partial_sort_сору

Делает то же, что и partial_sort, но помещает результаты в выходной диапазон. Он берет первые n элементов из исходного диапазона и в соответствующем порядке копирует их в результирующий диапазон. Если результирующий диапазон (n) короче, чем исходный диапазон (m), то в результирующий диапазон копируется только n элементов.

nth_element

Принимает три итератора произвольного доступа — first, nth и last — и необязательный функтор сравнения. Он помешает элемент, на который ссылается nth, в то место, где он находился бы, если бы весь диапазон был отсортирован. Следовательно, все элементы диапазона (first, nth) будут меньше, чем элемент в позиции nth (те, что находятся в диапазоне (nth, last) не сортируются, но больше, чем те, что предшествуют nth). Этот алгоритм следует использовать тогда, когда требуется отсортировать только один или несколько элементов диапазона и избежать затрат на сортировку всего диапазона.