В алгоритме stable sort() применяется сортировка со слиянием, которая действительно сохраняет исходный порядок следования элементов, но в среднем работает несколько медленнее алгоритма быстрой сортировки.

fendif PRINTSEQUENCE H /:-

По умолчанию этот шаблон функции выводит данные в поток cout, разделяя их символами перевода строк, однако вы можете выбрать другой разделитель и передать его вместо аргумента по умолчанию. Также можно задать текст сообщения, выводимого перед основными данными. Функция print() использует алгоритм сору() для передачи объектов в cout через ostreamjterator, поэтому итератор ostreamjterator должен знать тип выводимого объекта, который мы определяем по члену valuejype переданного итератора.

Шаблон std::iterator traits позволяет шаблону функции print() обрабатывать интервалы, ограниченные любыми типами итераторов. В итераторах, возвращаемых стандартными контейнерами (такими, как vector), определяется вложенный тип valuejype, представляющий тип элемента. Но при работе с массивами итераторы представляют собой обычные указатели, не имеющие вложенных типов. Чтобы обеспечить поддержку необходимых типов, связанных с итераторами в стандартной библиотеке, шаблон std::iterator Jraits предоставляет следующую неполную специализацию для указателей:

tempiate<class Т> struct iterator traits<T*> { typedef random access iterator tag iterator category: typedef T value type: typedef ptrdiff t difference type: typedef T* pointer typedef T& reference:

В результате тип элементов, на которые ссылается указатель (а именно Т), становится доступным через имя типа valueJype.

Устойчивая и неустойчивая сортировка

Для некоторых алгоритмов STL, перемещающих элементы интервалов, различают устойчивую и неустойчивую сортировку. Устойчивая сортировка сохраняет исходный относительный порядок элементов, эквивалентных с точки зрения функции сравнения. Например, возьмем последовательность {c(l),b(l),c(2),a(l),b(2),a(2)}. Пусть элементы сравниваются по своим буквенным обозначениям, а цифры означают порядок их следования в исходном интервале. Если отсортировать эту последовательность с применением неустойчивой сортировки, порядок следования элементов с совпадающими буквами не гарантируется, поэтому в итоге может быть получен интервал вида {a(2),a(l),b(l),b(2),c(2),c(l)}. С другой стороны, при устойчивой сортировке вы получите {a(l),a(2),b(l),b(2),c(l),c(2)}. Алгоритм STL sort() использует разновидность алгоритма быстрой сортировки и поэтому является неустойчивым, однако в библиотеку также входит устойчивый алгоритм stable sort()

std::iterator traits<Iter>::value type T: std::copy(first, last, std::ostreamJterator<T>(std::cout. sep)): OS std::endl:

Чтобы продемонстрировать устойчивую и неустойчивую сортировку алгоритмов, изменяющих порядок элементов последовательности, мы должны как-то отслеживать исходный порядок элементов. Приведенная ниже разновидность объекта string запоминает исходную относительную позицию данного объекта при помощи статической карты, связывающей строки с числовыми индексами. В каждом объекте NString присутствует поле thisOccurrence, обозначающее номер вхождения данного объекта.

: C06:NString.h

Нумерованная строка , отслеживающая номер вхождения

данного слова

fifndef NSTRING H

fdefine NSTRING H

find ude <algorithni>

find ude <iostream>

linclude <string>

linclude <utility>

linclude <vector>

typedef std::pair<std::string. int> psi:

Сравнение только по первому элементу bool operator==(const psi& 1. const psi& r) { return 1.first =- r.first:

class NString { std::string s: int thisOccurrence: Отслеживание количества вхождений: typedef std::vector<psi> vp: typedef vp::iterator vpit: static vp words:

void addStringCconst std::string& x) { psi p(x. 0):

vpit it = std: :find(words.beginO. words.endO. p): if(it != words.endO)

thisOccurrence = ++it->second: else {

thisOccurrence = 0:

words.push back(p):

public:

NStringO : thisOccurrence(O) {}

NStringCconst std::string& x) : s(x) { addString(x): }

NStringCconst char* x) : s(x) { addString(x): }

Автоматически сгенерированные оператор =

и копирующий конструктор здесь подойдут.

friend std: :ostreams operator (

std::ostream& os. const NStringS ns) {

return OS ns.s [ ns.thisOccurrence ] :

Оператор необходим для сортировки. Сравнение

производится только по строкам, без учета счетчиков вхождений:

friend bool

operator<(const NStringS 1. const NStringS r) {

friend

bool operator==(const NStringS 1. const NStringS r) { return 1.s == r.s:

Для сортировки с greater<NString>: friend bool

operator>(const NStringS 1. const NStringS r) { return 1.s > r.s:

Для прямого обращения к строке:

operator const std::string&O const {return s:}

Поскольку NString::vp является шаблоном, a мы используем модель с включением, шаблон должен определяться в этом заголовочном файле. NString::vp NString::words: lendif NSTRING H III:-

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

Для выполнения обычной сортировки по возрастанию необходима только операторная функция NString::operator<(). Чтобы сортировка могла выполняться в обратном порядке, мы также определяем функцию operator>(), вызываемую из шаблона greater.

Заполнение интервалов и генерирование значений

Алгоритмы, представленные в этом разделе, предназначены для автоматического заполнения интервалов. Функции fill и fill n многократно включают в контейнер одно и то же значение. Функции generate и generate n генерируют наборы значений, включаемых в контейнер, при помощи специальных функций-генераторов.

void fill (Forwardlterator first. Forwardlterator last, const T& value): void fill n(0utputlterator first. Size n. const T& value):

Алгоритм fill() присваивает значение value каждому элементу в интервале [first, last). Алгоритм fill n() присваивает значение value n элементам интервала, начиная с first.

void generate(Forwardlterator first. Forwardlterator last. Generator gen): void generate n(OutputIterator first. Size n. Generator gen):

Алгоритм generate() генерирует новые значения (вероятно, разные) для каждого элемента в интервале [first, last). Алгоритм generate n() вызывает gen() n раз и присваивает результаты п элементам, начиная с first.

В следующем примере эти алгоритмы заполняют и генерируют новые значения в векторах. Кроме того, пример демонстрирует применение функции print():

: C06:FillGenerateTest.cpp

Демонстрация алгоритмов fill и generate

{L} Generators

return 1.s < r.s: