struct rectype
{ string s; int num;
bool operator<(const rectype &b)const
{ return s < b.s;
} };
int mainO
{ const int N = 20; string t[20] =
{"Judy", "John", "John", "Judy", "John", "Judy", "Paul", "Judy", "Paul", "Mary", "Mary", "John", "Judy", "Paul", "John", "Paul", "Judy", "John", "Judy", "Judy"}; int k;
rectype a[N]; for (k=0; k<N; k++) { a[k].s = t[k]; a[k].num = 10 + k; }
sort(a, a+N); for (k=0; k<N; k++) { cout « a[k].s « " "
« a[k].num « (k % 5 == 4 ? "\n" : " "); }
return 0; }
Программа создает следующий вывод:
John 11 John 12 John 14 John 27 John 24
John 21 Judy 29 Judy 28 Judy 26 Judy 22
Judy 17 Judy 15 Judy 13 Judy 10 Mary 20
Mary 19 Paul 18 Paul 23 Paul 25 Paul 16
В этом отсортированном списке имена следуют в лексикографическом порядке. Как вы можете заметить уже в первой из четырех выведенных строк, номера, связанные с одним и тем же ключом, следуют не по возрастанию.
Поскольку до сортировки они шли в порядке возрастания, мы видим, что относительный порядок при сортировке не сохранен. Например, в сортированном массиве записи (John, 27) и (John, 24) появляются перечислением, хотя изначально запись (John, 24) была расположена раньше, чем (John, 27). Это происходит из-за того, что алгоритм sort нестабилен. Однако для него есть и стабильная версия. Чтобы использовать ее, мы просто заменим вызов алгоритма sort на следующий:
stable_sort(a, a+N) ;
После этой модификации программа напечатает:
John 11 John 12 John 14 John 21 John 24
John 27 Judy 10 Judy 13 Judy 15 Judy 17
Judy 22 Judy 26 Judy 28 Judy 29 Mary 19
Mary 20 Paul 16 Paul 18 Paul 23 Paul 25
Записи с равными ключами (как те, которые содержат имя John) теперь располагаются в порядке возрастания чисел; другими словами, относительный порядок этих записей сохраняется.
Как и для алгоритма sort, для stable_sort существует версия, которая в качестве третьего аргумента принимает предикат.
7.3.4. Частичная сортировка
<< назад вперед >>