struct intWrapper {

int item;

intWrapper(int i = 0)

{ item = i; } opeziAtor into const

{return item; }

type def intHrapper Index;

Конструктор в данной структуре struct преобразует любое значение типа int в Index, а операция преобразования типа operator int() преобразует любое значение Index обратно в int, следовательно, объекты типа Index можно использовать везде, где допускается применение объектов встроенного типа int.

Пример индексации, в рамках которого одни и те же элементы сортируются по двум различным ключам, представлен на рис. 6.14. Одна клиентская программа может определить operator< для работы с одним видом ключей, а другая - для использования с другим ключом, при этом оба они могут воспользоваться одной и той же программой сортировки, чтобы построить массив индексов, который позволил бы получать доступ к элементам в порядке расположения их ключей.

Переупорядочение N различных неотрицательных целых чисел, меньших N, в математике называется перестановкой: индексная сортировка выполняет перестановку. В математике перестановки обычно определяются как переупорядочения целых чисел от 1 до Л; мы же будем употреблять числа от О до Л- 1, чтобы подчеркнуть прямую связь между перестановками и массивом индексов в С++.

Такой поход, предусматривающий использование массива индексов вместо реальных элементов, работает в любом языке программирования, который поддерживает массивы. Другая возможность заключается в использовании указателей; она аналогична только что рассмотренной реализации строкового типа данных (программа 6.11). Будучи выполненной на массиве элементов фиксированного размера, сортировка по указателям во многом эквивалентна индексной сортировке, но при этом адрес массива добавляется к каждому индексу. Но сортировка по указателям - это более общая форма сортировки, ибо указатели могут указывать на что угодно, а элементы, подвергающиеся сортировке, отнюдь не обязательно должны иметь фиксированные размеры. Для индексной сортировки характерно следующее: если а есть массив указателей на ключи, то результатом вызова функции sort будет переупорядочение указателей таким образом, что пос-

2 3 4 5 6 7 8 9 10

10 4

5 6 8 7 2 3 9 О 1

9 Wilson

2 Johnson 1 Jones

О Smith

4 Washington 8 Thompson

3 Brown

10 Jackson

6 White

5 Adams

7 Black

63 86 87 90 84 65 82 61 76 86 71

РИСУНОК 6.14. ПРИМЕР ИНДЕКСНОЙ СОРТИРОВКИ

Манипулируя индексами, а не самими записями, можно выполнять сортировку одновременно по нескольким ключам. В этом примере данные могут быть фамилиями студентов и их степенями, вторая колонка представляет собой результат индексной сортировки по именам, а третья колонка представляет собой результат индексной сортировки по степени. Например, Wilson - фамилия, идущая по алфавиту последней, и ей соответствует десятая степень, в то время как фамилия Adams идет первой в алфавитном порядке, а ей соответствует шестая степень.

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

Функция qsort из стандартной библиотеки С представляет собой сортировку по указателям (см. программу 3.17), которая принимает функцию сравнения в качестве аргумента (но не берет за основу перегруженную операцию operator<, что делалось ранее). У этой функции четыре аргумента: массив, количество сортируемых элементов, размеры элементов и указатель на функцию, которая выполняет сравнение двух элементов, причем для этого ей потребуется передать указатели на эти элементы. Например, если Item есть char*, то приведенный ниже программный код выполняет сортировку строк в соответствие с принятыми соглашениями:

int compare (void *i, void *j)

{ return strcmp(*(Item *)i, *(Item *)j); } void sort (Item a[], int 1, int r)

{ qsort(a, r-1+1, sizeof(Item) , compare); }

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

Программа 6.12. Интерфейс типа данных для элементов типа запись

В записях имеются два ключа: ключ строкового типа (например, фамилия) в первом поле и целое число (например, степень) - во втором. Будем считать, что эти записи слишком большие, чтобы их копировать, поэтому Item определяется как структура struct, содержащая указатель на запись.

struct record { char name [30] ; int num; };

typedef struct { record *r; } Item;

int operator<(const Itemi, const Itemi);

void rand(Items) ;

void show(const Items);

int scan(Item£);

Программа 6.13. Реализация типа данных записей

Приведенные ниже реализации функций scan и show для записей работают в стиле реализации строкового типа данных из программы 6.11, распределяя и работая с памятью, в которой хранятся строки. Реализация операции operator< находится в отдельном файле, что дает возможность изменять представления и ключи сортировки без затрагивания основного кода.

static record data[maxN] ; static int cnt = 0; void show(const Item£ x)

{ cout x.r->narae x.r->num endl; } int scan(Items x)

x.r = Sdata[cnt++];

return (cin x.r->name x.r->num) != 0;

В обычных приложениях указатели используются для доступа к записям, которые могут иметь несколько ключей. Например, записи, содержащие фамилии студентов со степенями или фамилии людей вместе с возрастом могут определяться следующим образом:

struct record { char[30] пгипе; int num; }

Вполне может потребоваться выполнить их сортировку, используя любое из этих полей в качестве ключа. Программы 6.12 и 6.13 могут служить примерами интерфейса сортировки по указателям и реализации, которая позволила бы достигнуть этого. Для различных приложений сортировки используются массив указателей на записи и различные реализации операции operator<. Например, если откомпилировать программу 6.13 вместе с файлом, содержащим программный код

finclude Item.h

int operator<(const Item &a, const Item &b) { return a.r->num < b.r->num); }

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

tinclude Item.h include <string.h>

int operater< (const Item &a, const Item &b)

{ return strcmp (a.r->n2une, b.r->name) < 0; )

TO получим ТИП данных ш\я элемента, для которого любая реализация функции sort выполнит сортировку по указателям на строковом поле.

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

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