Программирование >>  Немодифицирующие последовательные алгоритмы 

1 ... 4 5 6 [ 7 ] 8 9 10 ... 78


{ int а[10], X, n = О, *р;

cout Enter at most 10 positive integers,

followed by 0:\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;

Важно заметить сходство между вызовами

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

в программе sortl.cpp и

sort(а, a+n);

в программе sort2.cpp. В обоих случаях первый аргумент ссылается на первый элемент последовательного контейнера, а второй - на элемент, следующий за последним, точнее на позицию, находящуюся непосредственно после последнего элемента. Это общий принцип, справедливый не только для алгоритма sort, но и для большинства алгоритмов STL. Мы можем применить этот принцип также и к заданной подпоследовательности. Например, мы можем отсортировать только элементы а[3], а[4], а[5] и а[6], написав

sort(a+3, а+7);

или, что эквивалентно,

sort[&a[3], &а[7]);

как показывает рисунок 1.2.

Массив до сортировки

Массив

после

сортировки

четырех

элементов

sort(a+3, а+7)

Рисунок 1.2. Сортировка подпоследовательности



Может показаться более логичным передавать адрес последних элементов, а не следующих за ними, в этом примере а[6] вместо а[7]. Однако использование элементов, следующих за последним, имеет несколько преимуществ. Например, мы можем определить количество элементов с помощью простого вычитания:

количество элементов = 7-4 = 3

Принятое соглащение также позволяет нам написать цикл for.

for (i=3; i!=7; ++i) ...

если мы хотим сделать что-либо с отсортированными элементами. Возможность выбрать подпоследовательность применима и к контейнерам STL, таким как векторы. Например, если в программе sort 1.срр вектор v также содержит не менее семи элементов, отсортируем v[3], v[A], v[5] и y[6], написав

vector<int>::iterator i, j; i = V.begin () + 3 ; j = V.beginO + 7; sort(i, j ) ;

ИЛИ просто

sort (v. begin о + 3, v.beginO + 7);

Такое использование оператора + рассмотрим более подробно в разделе 1.9.

Произвольный доступ, доступ по индексу и сортировка

Вы могли заметить, что в предыдущем обсуждении мы использовали выражения типа v[3], хотя v не является массивом, а определен как

vector<int> v;

Доступ по индексу возможен в этом случае, поскольку вектор является контейнером произвольного доступа, для которого определен operator[] доступа по индексу. Заметьте, однако, что мы не можем заменить v[3] на *(v + 3), потому что тип переменной v является классом, для которого не определен ни бинарный оператор +, ни унарный оператор *.

Алгоритм STL sort требует произвольного доступа. Поскольку такой доступ обеспечивают векторы и массивы, мы могли использовать этот алгоритм в программах sortl.cpp и sort2.cpp. Как показывает рисунок 1.1, двусторонняя очередь также обеспечивает произвольный доступ, в отличие от списка. Это объясняет, почему вызов

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



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

встречающийся в программе sortl.cpp, будет работать, если мы в программе заменим всюду vector на. deque, но не на list. Более подробно - см. раздел 1.9.

Инициализация контейнеров

Как известно каждому программисту на С(++), определение массива может содержать список начальных значений. Например, мы можем написать

int а[3] = {10, 5, 7}; int b[] = {8, 13};

эквивалентно int b[2] = {8, 13}; int c[3] = {4};

эквивалентно int c[3] = {4, 0, 0};

Инициализация также возможна и для трех других типов последовательных контейнеров, как показано в следующем примере:

int а[3] = {10, 5, 7}; vector<int> v(a, а+3); deque<int> w(a, а+3); list<int> х(а, а+3);

Но не только массив, а также и вектор, двусторонняя очередь или список могут служить основой для инициализации контейнера того же типа. Например, если мы продолжим этот пример строчкой

vector<int> vl (v.begin() , v.endO);

вектор v\ станет идентичен вектору v, оба будут состоять из трех элементов типа int, 10, 5 и 7. Этот пример откомпилируется, поскольку и il относятся к одному типу - vector<int>. Напротив, следующий пример не будет компилироваться, поскольку мы не можем использовать значения списках для инициализации вектора vV:

vector<int> vl (x.begin () , x.endO);

Ясно, что этот способ инициализации обеспечивается конструкторами контейнерных классов. Кроме этого, существуют конструкторы, принимающие в качестве параметра целое, означающее желаемый размер,



1 ... 4 5 6 [ 7 ] 8 9 10 ... 78

© 2006 - 2024 pmbk.ru. Генерация страницы: 0.001
При копировании материалов приветствуются ссылки.
Яндекс.Метрика