Классы и объекты в С++ (стр. 16 )

vectordnputlter first. Inputlter last);

vectorCconst vector<T>& x); //4

Ключевое слово explicit используется для того, чтобы при создании объекта запретить выполняемое неявно преобразование при присваивании значения другого типа. Конструктор 1 является конструктором по умолчанию. Конструктор 2 создает вектор длиной п и заполняет его одинаковыми элементами — копиями value. Конструктор 3 создает вектор путем копирования указанного с помощью итераторов диапазона элементов. Тип итераторов должен быть «для чтения». Конструктор 4 является конструктором копирования.

Примеры конструкторов:

/ / Создается вектор из 10 равных единице элементов:

vector <1nt> v2 (10. 1);

/ / Создается вектор, равный вектору v l:

vector <int> v4 (vl);

/ / Создается вектор из двух элементов, равных первым двум элементам v l:

vector <1nt> v3 (vl. beginO. vl. begInO + 2);

/ / Создается вектор из 10 объектов класса monstr (см. с. 183)

/ / (работает конструктор по умолчанию):

vector <monstr> ml (10):

/ / Создается вектор из 5 объектов класса monstr с заданным именем

/ / (работает конструктор с параметром char*):

vector <monstr> m2 (5. monstr("Bacя")):

В шаблоне vector определены операция присваивания и функция копирования:

vector<T>& operator=(const vector<T>& х):

void assign(size_type п. const Т& value):

template <class Inputlter>

void assigndnputlter first. Inputlter last):

Здесь через Т обозначен тип элементов вектора. Вектора можно присваивать друг другу точно так же, как стандартные типы данных или строки. После присваивания размер вектора становится равным новому значению, все старые элементы удаляются.

Функция assign в первой форме аналогична по действию конструктору 2, но применяется к существующему объекту. Функция assign во второй форме предназначена для присваивания элементам вызывающего вектора значений из диапазона, определяемого итераторами first и last, аналогично конструктору 3. Доступ к элементам вектора осуществляется с помощью специальных операций и методов.

Существуют функция выделения памяти reserve, изменения размеров вектора resize.

Определены следующие методы для изменения объектов класса vector:

void push__back(const Т& value):

void pop_back();

Функция pushback добавляет элемент в конец вектора, функция рорЬаск — удаляет элемент из конца вектора. Другие функции: insert - вставка элемента в вектор; erase - удаление одного элемента вектора; swap - обмен элементов двух векторов одного типа, но не обязательно одного размера.

Для векторов определены операции сравнения =, !=,<,,<= и =. Два вектора считаются равными, если равны их размеры и все соответствующие пары элементов. Один вектор меньше другого, если первый из элементов одного вектора, не равный соответствующему элементу другого, меньше него (то есть сравнение лексикографическое).

Пример:

#inc1ude <vector>

using namespace std;

vector <int> v7. v8;

int ma1n(){

for (int i = 0: i<6: i++)v7.push__back(i);

cout « "v7: ":

for dnt i = 0; i<6: i++) cout « v7[i] « " ";

cout « end!;

for (int i = 0; i<3; i++)v8.push_back(i+l):

cout « "v8: ":

for (int i = 0; i<3; i++) cout « v8[i] « " ":

cout « end!:

if (v7 < v8 ) cout « " v7 < v8" « endl:

else cout « " v7 > v8" « endl;

}

Результат работы программы:

v7: О 1 2 3 4 5

v8: 1 2 3

v7 < v8

Для эффективной работы с векторами в стандартной библиотеке определенышаблоны функций, называемые алгоритмами. Они включают в себя поиск значений, сортировку элементов, вставку, замену, удаление и другие операции.

Векторы логических значений (vector <booi>). Специализация шаблона vector <boo1> определена для оптимизации размещения памяти, поскольку можно реализовать вектор логических значений так, чтобы его элемент занимал 1 бит. При этом адресация отдельных битов выполняется программно. Итератор такого вектора не может быть указателем. В остальном векторы логических значений аналогичны обычным и реализуют тот же набор операций и методов. В дополнение к ним определены методы инвертирования бита и вектора в целом (flip).

Двусторонние очереди (deque. Двусторонняя очередь — это последовательный контейнер, который, наряду с вектором, поддерживает произвольный доступ к элементам и обеспечивает вставку и удаление из обоих концов очереди за постоянное время. Те же операции с элементами внутри очереди занимают время, пропорциональное количеству перемещаемых элементов. Распределение памяти выполняется автоматически.

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

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

explicit deque() // 1

explicit deque(size__type п. const Т& value = TO): / / 2

template <class InputIter> // 3

dequeCInputlter f i r s t. InputIter last):

dequeCconst vector<T>& x): //4

Конструктор 1 является конструктором по умолчанию. Конструктор 2 создает очередь длиной п и заполняет ее одинаковыми элементами — копиями value. Конструктор 3 создает очередь путем копирования указанного с помощью итераторов диапазона элементов. Тип итераторов должен быть «для чтения». Конструктор 4 является конструктором копирования.

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

void push_front(const Т& value);

void pop_front();

При выборке элемент удаляется из очереди.

Для очереди не определены функции capacity и reserve, но есть функции resize и size. К очередям можно применять алгоритмы стандартной библиотеки.

Списки (list). Список не предоставляет произвольного доступа к своим элементам, зато вставка и удаление выполняются за постоянное время. Класс list реализован в STL в виде двусвязного списка, каждый узел которого содержит ссылки на последующий и предыдущий элементы. Поэтому операции инкремента и декремента для итераторов списка выполняются за постоянное время, а передвижение на п узлов требует времени, пропорционального n. После выполнения операций вставки и удаления значения всех итераторов и ссылок остаются действительными.

Список поддерживает конструкторы, операцию присваивания, функцию копирования, операции сравнения и итераторы, аналогичные векторам и очередям.

Доступ к элементам для списков ограничивается следующими методами:

reference front(); const_reference front() const;

reference back(): const_reference back() const:

Для занесения в начало и конец списка определены методы, аналогичные соответствующим методам очереди:

void push_front(const Т& value); void pop_front();

void push_back(const T& value); void pop_back():

Действуют все остальные методы для изменения объектов, аналогичные векторам и очередям.

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

Для списков определено несколько специфических методов.

Сцепка списков (splice) - для перемещения элементов из одного списка в другой без перераспределения памяти, только за счет изменения указателей. Оба списка должны содержать элементы одного типа.

Удаления элемента по его значению - функция remove: void remove(const Т& value). Если элементов со значением value в списке несколько, все они будут удалены. Можно удалить из списка элементы, удовлетворяющие некоторому условию.

Упорядочивания элементов списка - метод sort.

Слияния списков - метод merge: void mergedist<T>& x); Оба списка должны быть упорядочены. Результат — упорядоченный список.

Метод reverse служит для изменения порядка следования элементов списка на обратный (время работы пропорционально количеству элементов): void reverse();

Пример работы со списком.

К спискам можно применять алгоритмы стандартной библиотеки.

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

В STL стек определен по умолчанию на базе двусторонней очереди. Метод занесения в стек push соответствует методу занесения в конец push_back, метод выборки из стека pop — методу выборки с конца рор_Ьаск, кроме того, добавлен метод top для получения или изменения значения элемента на вершине стека.

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