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

1 2 [ 3 ] 4 5 6 ... 78


1.2. Знакомство с STL

Установив современный компилятор С++, мы можем сразу начать использовать STL, например откомпилировать и запустить следующую программу. Эта программа читает с клавиатуры переменное количество ненулевых целых чисел и печатает их в том же порядке после того, как введен 0. Данная задача может показаться слишком простой, но на самом деле это не так, потому что нет ограничения на количество вводимых чисел:

readwr.cpp: Чтение и вывод переменного количества

ненулевых целых (ввод завершается нулем).

#include <iostream>

#include <vector>

using namespace std;

int mainO { vector<int> v; int x;

cout << Enter positive integers, followed by 0:\n ; while (cin >> x, x != 0)

v.push back(x); vector<int>::iterator i; for (i=v. begin 0 ; i != v.endO; + + i)

cout << *i << ; cout << endl; return 0;

Мы можем использовать шаблон vector как массив переменной длины. Сначала эта длина равна нулю. Поскольку мы хотим, чтобы элементы вектора были целого типа, то всегда пишем vector<int>, чтобы обозначить класс, с которым работаем. Выражение

v.push back(x);

добавляет значение х типа int в конец вектора v.

Оператор for в этой программе используется аналогично тому, как это сделано в следующем фрагменте кода, который выводит массив а вместо вектора v:

int a[N], *р;

for (р=а; р != a+N; р++) cout << *р << ;

Напомним, что выражения &а[0] и а эквивалентны, равно как и выражения &a[N] и а + N. Начав с первого элемента, мы проходим массив, пока



не оказываемся за его концом: хотя указываем на адрес a[N], последний элемент массива - а[Л-1]. Это может выглядеть опасным, но поскольку мы не используем значение a[N], а только его адрес, такой стиль абсолютно безопасен. Переменная i, определенная как

vector<int>::iterator i;

называется итератором. Она используется таким же образом, как указатель в вышеприведенном фрагменте. Значение итератора для первого элемента вектора v обозначается выражением v.beginQ, а значение итератора для элемента, следующего за конечным, обозначается как v.endQ. Значение элемента вектора, на который ссылается допустимый итератор г, обозначается выражением * г, как если бы i был указателем. Для этого итератора i определены также операторы ++ и -, как в префиксном, так и в суффикс-ном варианте. Это объясняет смысл следующего цикла for.

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

В приведенном цикле лучше не заменять != на <. Хотя в примере это сработает, но оператор < неприменим к некоторым другим типам, отличными от vector<mt> (см. раздел 19), в то время как оператор != работает во всех случаях.

Обычно в математике запись [а, Ь] используется для обозначения закрытого интервала а < лг < 6, а запись {а, Ь) - для открытого интервала а<х<Ь. Это объясняет запись

[а, Ь)

для интервала

а < X < Jb

Подобным же образом мы иногда будем писать [ia, ijb)

для диапазона значений итератора в следующем фрагменте кода: vector<int>::iterator i, ia, ib;

for (i = ia; i != ib; ++i) ...

Ошибка выделения памяти

Поскольку все числа, которые читает программа readwr.cpp, хранятся в динамически распределяемой памяти, используемая нами компьютерная система наложит ограничение на размер ввода. Вопрос усложняется из-за



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

vector<int> v;

for (;;) V.push back(О);

приведет к ошибке выделения памяти. То же самое наблюдается при исполнении

int *р;

for (;;) р = new int;

В последнем фрагменте обычная проверка if (р \= NULL) не будет работать с современными компиляторами С++. Согласно проекту стандарта С++ ошибка выделения памяти будет приводить не к возвращению значения NULL, а к выбросу исключения . Несмотря на то что ошибка распределения памяти относится к С++, а не к STL, это была бы достаточно важная тема для обсуждения в настоящей книге, если бы существовало простое, переносимое решение, совместимое с большинством популярных компиляторов и соответствующее принятому стандарту С++. Поскольку различные компиляторы требуют разных подходов, а стандарт языка находится в стадии проекта, мы опустим обсуждение этой темы в данной книге, которая все-таки посвящена STL, а не С++.

Возвращаясь назад

Рекомендация использовать != (или ==) для сравнения значений итераторов вместо <, <=, >, >= усложняет прохождение элементов вектора в обратном порядке с помощью только что обсужденных средств. В программе readwr.q)p мы могли бы добиться этого, заменив цикл for на следующий фрагмент:

i = V.end();

if (i i= v.beginO)

do cout << *--i << ; while (i != v.beginO);

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



1 2 [ 3 ] 4 5 6 ... 78

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