Когсуэлл Джефф
Шрифт:
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