Сравнения

обычные операторы сравнения ==, !=, <, <=, > и >= определяются по следующим трем правилам.

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

О Два контейнера равны, если их элементы совпадают и следуют в одинаковом порядке. Проверка на равенство элементов выполняется оператором ==.

О Отношение «меньше/больше» между контейнерами проверяется по лексикографическому критерию (см. с. 356).

Для сравнения разнотипных контейнеров применяются алгоритмы сравнения, описанные на с. 352.

Присваивание и функция swap

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

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

Векторы

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

Рис. 6.1. Структура вектора

Чтобы использовать вектор в программе, необходимо включить в нее заголовочный файл <vector>:

#include <vector>

В исходной версии STL вектор определялся в заголовочном фа11ле <vector.h>.

Тип вектора определяется как шаблон класса в пространстве имен std:

namespace std {

template <class Т.

class Allocator = allocator<T> > class vector:

Элементы вектора относятся к произвольному типу Т, поддерживаюиему присваивание и копирование. Необязательный второй параметр шаблона определяет модель памяти (см. главу 15). По умолчанию используется модель allocator, определенная в стандартной библиотеке C-I-+*.

Возможности векторов

Элементы вектора копируются во внутренний динамический массив. Элементы всегда хранятся в определенном порядке; следовательно, вектор относится к категории упорядоченных коллекций. Вектор обеспечивает произволышй доступ к своим элементам. Это означает, что обрашение к любому элементу с известной позицией выполняется напрямую и с постоянным временем. Итераторы векторов являются итераторами произвольного доступа, что позволяет применять к векторам все алгоритмы STL.

Операции присоединения и удаления элементов в конце вектора выполняются с высоки.м быстродействием. Если элементы вставляются или удаляются в середине и./1и в начале, быстродействие снижается, поскольку все элементы в последующих позициях приходится перемещать на новое место. На самом деле для каждого последующего элемента вызывается оператор присваивания.

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

Векторы поддерживают стандартные операции проверки размера size(), emptyO н nriax slze() (см. с. 155). К ним добавляется функция capacltyO, возвращающая максимальное количество элементов, которые могут храниться в текущей выделенной памяти. Если количество элементов превысит значение, возвращаемое функцией capacltyO, вектору придется перераспределить свою внутреннюю намять.

Емкость вектора необходимо учитывать но двум причинам:

О в результате перераспределения памяти становятся недействительными все ссылки, указатели и итераторы элементов вектора;

О на перераспределение памяти требуется время.

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

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

Чтобы предотвратить перераспределение памяти, можно заранее зарезервировать некоторую емкость функцией reserve(). Тем самым гарантируется, что ссылки останутся действительными, пока зарезервированная емкость не будет исчерпана:

std::vector<1nt> v; Создание пустого вектора v.reserveCSO); Резервирование памяти для 80 элементов

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

std::vectQr<T> v{5); Создание вектора и его инициализация

пятью значениями (с пятикратным вызовом конструктора по умолчанию типа Т)

Конечно, для этого при определении типа элементов должен быть определен конструктор по умолчанию. Но учтите, что для сложных типов даже при наличии конструктора по умолчанию инициализация требует времени. Если элементы инициализируются только для того, чтобы зарезервировать память, лучше воспользоваться функцией reserveQ.

Концепция емкости векторов сходна с аналогичной концепцией для строк (см. с. 468), но с одним существенным различием: в отличие от строк функция reserveO не может вызываться для уменьшенрш емкости векторов. Вызов reserve() с аргументом, меньшим текущей емкости вектора, игнорируется. Более того, способы оптимизации по скорости и затратам памяти определяются реализацией. Это означает, что реализация может увеличивать емкость с большими приращениями. Для предотвращения внутренней фрагментации многие реашзации выделяют полный блок памяти (около 2 Кбайт) при первой вставке, если ранее не вызывалась функция reserve(). Если программа работает с мтгожеством векторов, содержащих малое количество элементов, такая стратегия приводит к неэффективному расходованию памяти.

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

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

template <class Т>

void shr1nkCapdcity(std::vector<T>& v) {

std::vector<T> tmpCv); Копирование элементов в новый вектор