reference operator[](size type n); const reference operator[](size type n) const;

Если мы имеем дело с типом vector<int>, тип reference означает int&, win ссылку-на-целое. Тип difference type представляет собой целочисленное значение со знаком, которое может использоваться для представления разности между двумя итераторами, а size type отличается от difference type только тем, что является беззнаковым типом.

Тип vector<bool>

Векторы, состоящие из элементов типа bool, представляют собой особый случай, чтобы обеспечить их эффективное размещение: выделение целого слова на каждый элемент, которому достаточно одного бита, было бы неэкономным расходованием памяти. Очевидно, особый подход к типу bool возможен только тогда, когда он является встроенным типом, а не синонимом типа int. Напомним, что эта тема затрагивалась нами в разделе 1.1.

Функция-член flipO определена для типа vector<bool>, но не для vector<int>. Она обращает значение всех либо выбранного бита в векторе, как показывает следующий пример:

vector<bool> b(lOO); 100 бит, все установлены в 0. b.flipO; Все биты инвертированы и сейчас равны 1. Ь[73] .flipO ;

cout b[72] b[73] b[74]; Вывод: 101

Также существует функция-член swap для перестановки двух булевских векторов. Например:

vector<bool> u(100, true), v(50, false); u.swap(v);

cout << U.sizeO << << v.sizeO <<

u[0]; Вывод: 50 100 0

Следующая программа использует булевский вектор для реализации решета Эратосфена. Это хорошо известный эффективный способ нахождения простых чисел 2, 3, 5, 7, И, 13,... Все элементы булевского вектора S, решета, сначала равны true, а впоследствии некоторые из них принимают значение false:

S[i] = true означает: i может быть простым числом (делители пока

не найдены);

S[i] = false означает: i не есть простое число (поскольку является

кратным меньшего простого числа).

Чтобы уменьшить объем выводимых данных, программа не показывает длинный список простых чисел. Вместо этого она подсчитывает количество простых чисел, меньших заданного значения N, а также печатает наибольшее из них:

erastos.cpp: Решето Эратосфена для нахождения

всех простых чисел, меньших заданного предела.

iinclude <iostream> iinclude <vector> iinclude <math.h>

using namespace std;

int main() { cout

To generate all prime numbers < N, enter N: ; long N, i, sqrtN, count = 0, j; cin N;

sqrtN = int(sqrt(N)) + 1; vector<bool> S(N, true);

Вначале все S[i] равны true.

S[i] = false только и когда

мы обнаруживаем, что i не есть простое.

for (i=2; i < sqrtN; i++) if (S[i])

for (int j=i*i; j<N; j+=i) S[j] = false;

for (i=2; i<N; i++)

if (S[i]) {j = i; count++;}

cout There are count

prime numbers less than N.\n ; cout Largest prime number less than N is

j << . endl; return 0;

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

То generate all prime numbers < N, enter N: 1000000 There are 78498 prime numbers less than N. Largest prime number less than N is 999983.

Время, которое потребовалось на выполнение примера, составило около 10 секунд на компьютере с процессором 80486; это показывает, что решето

Эратосфена позволяет очень быстро находить простые числа. Также этот пример показывает, что булевские векторы не только очень удобны, но и эффективны.

3.2. Функции capacity и reserve

До сих пор мы принимали как данность, что векторы имеют переменный размер, не беспокоясь о том, как это реализовано. Теперь предположим, что мы хотим добавить к вектору элемент, так что размер этого вектора вырастет на 1. Если такое будет происходить часто, то неэффективно было бы каждый раз перераспределять память, потому что это может потребовать копирования всех элементов в область памяти, в которой размещается увеличенный вектор. Гораздо лучше выделить больше памяти, чем требуется, так что во многих случаях дополнительная память уже будет иметься в наличии, когда возникнет необходимость в увеличении размера вектора. Число элементов вектора v, для которых выделена память, называется емкостью вектора и равняется значению выражения

V. capacity()

Это значение больше или равно значению vsizeQ, как показано на рисунке 3.1.

v.beginO

v.endO

Рисунок 3.1. Размер и емкость вектора v

Следующая программа демонстрирует, что значение v.capacityQ остается постоянным относительно долго, пока вектор v постепенно растет, а vsizeQ увеличивается на единицу каждый раз, когда к v добавляется новый элемент:

capacity.срр: Функция-член capacity для векторов.

♦ include <iostreani> ♦include <iomanip> ♦include <vector>

using namespace std;