STL для программистов на C++

1.4. Сортировка

Ниже следует расширение программы readwr.cpp, рассмотренной в начале раздела 1.2. Эта программа сортирует вектор v, то есть располагает элемен­ты v в восходящем порядке:

// sortl.cpp: Сортировка вектора. #include <iostream> #include <vector> #include <algorithm> using namespace std;

int main()

{ vector<int> v;

int x;

cout « "Enter positive integers, followed by 0:\n";

while (cin » x, x != 0) v.push_back(x);

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

cout « "After sorting: \n";

vector<int>::iterator i;

for (i=v.begin)) ; i != v.endO; + + i)

cout << *i << " "; cout « endl; return 0; }

Сама сортировка выполняется выражением

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

Мы используем два значения итераторов в качестве аргументов: первый, v.beginQ, ссылается на начальный элемент вектора и второй, v.endQ, ссы­лается на следующий за последним элемент вектора. Вывод этой програм­мы содержит введенные пользователем целые числа, отсортированные в восходящем порядке.

Вышеприведенный вызов функции sort отличается от вызовов push_back, insert, begin и др. Поскольку мы пишем не v.sort(...), а просто sort(...), видно, что sort является не функцией-членом класса vector, а шаб­лонной функцией, которая не является членом класса. Технический термин, обозначающий такую шаблонную функцию в STL,- обобщенный {generic) алгоритм, или просто алгоритм. Строчка

#include <algorithm>

необходима, поскольку мы используем алгоритм sort. Для некоторых реа­лизаций STL компилятор не выдает сообщения об ошибках, если мы опу­стим эту строчку, поскольку заголовок algorithm включается неявным об­разом с помощью строки

#include <vector>

Так как было бы неразумно рассчитывать на это, мы используем обе строчки Uinclude. Напротив, в следующей программе, которая сортирует обычный мас­сив вместо вектора, достаточно включить только заголовок algorithm:

II  sort2.cpp:   Сортировка массива. #include <iostream> #include <algorithm> using namespace  std;

int main()

{ int а[10], х, n = 0, *р;

cout « "Enter at most 10 positive integers, " "followed by O:\n\-

while (cin » x, x != 0 && n < 10) a[n++] = x;

sort(a, a+n);

cout « "After sorting: \n";

for (p=a; p != a+n; p++) cout « *p « " ";

cout « endl;

return 0; }