showlist( After inserting 123 at the beginning: , L); list<int>:: iterator i = L.beginO; L.insert(+ + i, 456) ; showlist(

After inserting 456 at the second position: , L); i = L.endO ; L.insert(--i, 999); showlist(

After inserting 999 just before the end: , L); i = L.beginO; x = *i; L.pop front();

cout Deleted at the beginning: x endl; showlist( After this deletion: , L); i = L.endO ; x = *--i; L.pop backO ;

cout Deleted at the end: x endl; showlist( After this deletion: , L); i = L.beginO ;

X = *++i; cout To be deleted: x endl; L.erase(i);

showlist( After this deletion (of second element): ,

L); return 0;

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

Enter positive integers, followed by 0:

10 20 30 0

Initial list: 10 20 30

After inserting 123 at the beginning:

123 10 20 30 After inserting 456 at the second position:

123 456 10 20 30 After inserting 999 just before the end:

123 456 10 20 999 30 Deleted at the beginning: 123 After this deletion:

456 10 20 999 30 Deleted at the end: 30 After this deletion:

456 10 20 999

То be deleted: 10

After this deletion (of second element): 456 20 999

Употребление const в первых двух строчках функции showlist требует разъяснения:

void showlist(const char *str, const list<int> &L) { list<int>::const iterator i;

Добавление приставки const к параметрам типа указатель или ссылка, как это сделано выше, является хорошей практикой, если такие параметры не используются для модификации объектов, на которые они указывают. Поскольку функция showlist не модифицирует ни строку str, ни список L, отсюда происходят два употребления слова const на первой из этих двух строчек. Из-за этого на второй строчке мы должны объявить переменную i типа const iterator, чтобы иметь возможность использовать ее вместе с L. Это похоже на применение модификатора const к указателям: если хотим присвоить вышеобъявленный параметр 5ir указателю/), мы сможем сделать это, только использовав const при объявлении этого указателя:

const char *р; const необходим, поскольку str р = str; типа const char *

Стирание подпоследовательности

Если [il, f2) является действительным диапазоном для вектора v, мы можем стереть подпоследовательность в v, заданную этим диапазоном, следующим образом:

V.erase(il, i2);

То же самое относится и к остальным контейнерам.

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 х;

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.beginO; i != v.endO; + + i)

cout *i ; cout endl; return 0;

Сама сортировка выполняется выражением sort (v.beginO , v.endO);

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

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

#include <algorithm>

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

#include <vector>

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

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

int mainO