На этом шаге мы рассмотрим возможности векторов.

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

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

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

    Векторы поддерживают стандартные операции проверки размера size(), empty() и max_size() (126 шаг). К ним добавляется функция capacity(), возвращающая максимальное количество элементов, которые могут храниться в текущей выделенной памяти. Если количество элементов превысит значение, возвращаемое функцией capacity(), вектору придется перераспределить свою внутреннюю память.

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

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

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

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

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

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

  std::vector<T> v(5); // Создание вектора и его инициализация
                       // пятью значениями (с пятикратным вызовом 
                       // конструктора по умолчанию типа Т)

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

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

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

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

  template <class T>
  void shrinkCapacity (std::vector<T>& v)
  {
    std::vector<T> tmp(v); // Копирование элементов в новый вектор
    v.swap(tmp);           // Перестановка внутренних данных векторов
  }

    Емкость вектора можно уменьшить даже без вызова этой функции, просто выполнив следующую команду:

  // Уменьшение емкости вектора v для типа Т 
  std::vector<T>(v).swap(v);

    Но не следует забывать, что после вызова функции swap() все ссылки, указатели и итераторы переключаются на новый контейнер. Они продолжают ссылаться на те элементы, на которые они ссылались первоначально. Значит, после вызова функции shrinkCapacity() все ссылки, указатели и итераторы становятся недействительными.

    Со следующего шага мы начнем рассматривать операции над векторами.

Предыдущий шаг Содержание Следующий шаг