STL: std::vector

Vector это стандартный шаблонный контейнер STL. Элементы в std::vector располагаются в том порядке, в котором они добавлялись в вектор. Vector представляет из себя массив данных (объектов одного типа), который может динамически изменять свой размер – увеличиваться по мере добавления данных и уменьшаться при их удалении. При этом, хочу заметить, он чаще всего не освобождает память при удалении элементов из него – он её резервирует на тот случай, если данные снова будут добавляться и размер std::vector снова нужно будет увеличивать. Обычно при создании объекта вектора, он сразу резервирует некоторое количество памяти под размещение новых элементов. Если же места под размещение новых элементов не хватает – вектор сам выделит новую память, но, опять же, с некоторым запасом. Эти оптимизации сделаны для того, что бы вектор постоянно не занимался выделением/удалением памяти, ибо это операции не быстрые.

Вектор хранит элементы в виде линейного массива – потому обращаться к его элементам можно не только по итераторам и/или с использованием at() или operator[], но и просто по указателю, как к обычному массиву. Но, как я уже сказал выше, в отличие от обычных массивов, в вектор можно добавлять или удалять данные, т.е. менять количество элементов в массиве.

Когда использовать vector?

Vector стоит использовать если :

• есть необходимость обращаться к элементам массива по их номеру (индексу) – std::vector позволяет делать это практически без потерь скорости.
• последовательно обрабатывать (или посматривать) элементы массива – аналогично, вектор оптимизирован для таких операций и существенной разницы с обычными массивами наблюдаться не будет.
• добавление элементов в ваш массив будет происходить только в конец массива, тогда скажутся те самые оптимизации, о которых я писал выше и скорость будет почти равна обычным массивам
• вообще вектор это хорошая замена обычным массивам – обычно скорость работы std::vector не ниже, а качество кода при этом заметно выше

vector vs. массив

В общем, если проводить параллели с обычным массивом, то vector будет иметь примерно такую же скорость (чуть-чуть медленнее местами, но не существенно), но зато в вектор можно добавлять элементы, не задумываясь есть ли место для их размещения (при разумном количестве добавляемых элементов, конечно же), он сам подчистит за собой память, когда вы перестанете его использовать и он (в режиме отладки) будет проверять что вы случайно не вышли за пределы массива (например, если вы пытаетесь получить 100ый элемент из массива, где всего 90 элементов). Последний пункт, кстати, особенно важен и позволяет отловить достаточно большое количество багов, которые иначе могли бы жить в программе месяцами.

Недостатки std::vector

Но у std::vector есть и некоторые недостатки, по сравнению с обычными массивами: обычно он чуть-чуть медленнее (но это не повод его не использовать!!!!) и он требует немного больше памяти, чем обычные массивы (поскольку обычно резервирует память для быстрой вставки новых элементов).

Как правило, следует заранее обдумывать то, какие элементы и в каком количестве будут храниться в std::vector. Если Вы планируете часто добавлять в него данные, то имеет смысл зарезервировать некоторый объём памяти заранее – тогда vector::push_back и прочие операции будут работать быстрее, т.к. им не придётся постоянно выделять память. Естественно, вектор старается оптимизировать количество выделений памяти, но если Вы так же задумаетесь об этом – хуже-то точно не станет.

Кроме того, не забывайте, что std::vector может расширять количество потребляемой им памяти, но он никогда не уменьшает её. Из этого следует, что если вы добавите в вектор, скажем, миллион объектов, а потом удалите их из него – вектор по прежнему будет потреблять столько памяти, сколько требовалось для хранения того самого миллиона объектов. Для того, что бы освободить эту память – придётся приложить некоторые усилия. Обычно это называют “фокус с перестановкой std::vector”:

vector<ТипДанныхВВекторе>(ваш_вектор).swap(ваш_вектор);

Что бы немного поразмять свою голову – попробуйте самостоятельно понять, как это работает.

Функционал vector

Как и любой контейнер STL, std::vector позволяет получить текущее количество элементов ( функция vector::size() ). Кроме того, он позволяет узнать сколько он распределил места для добавления новых элементов (функция vector::capacity() ). Позволяет проверить, есть ли в нём элементы или он пустой, узнать сколько максимум элементов можно в него “положить”, удалить все элементы одной командой.

Шаблон std::vector

В Standard Template Library шаблон std::vector определён как принимающий два параметра, один из которых необязательный:

template < class T, class Allocator = allocator<T> > class vector;

Первый параметр определяет тип (class) элементов, которые будет содержать в себе вектор, а второй – это аллокатор (распределитель памяти). По умолчанию использует дефолтный аллокатор и этого практически всегда достаточно. Однако, при необходимости, вы можете указать своё собственный алокатор, который будет выделять память так, как надо вам – иногда (хоть и очень-очень редко) это бывает полезно.

Пример использования vector.

Мы уже использовали шаблон вектор в разрабатываемой нами игре, но, для большей понятности, приведу ещё один пример использования контейнера std::vector для хранения объектов:

#include <string>
#include <vector>
#include <iostream>
 
class Foo
{
   public:
      Foo(const std::string& n):
         name(n)
      { std::cout << "Foo(const std::string&)(" << name << ")" << std::endl; }
 
      ~Foo()
      { std::cout << "~Foo(" << name << ")" << std::endl; }
 
   private:
      std::string name;
};
 
int main(int argc, char* argv[])
{
   std::vector<Foo> v;
 
   v.push_back(Foo("a"));
   v.push_back(Foo("b"));
   v.push_back(Foo("c"));
 
   return 0;
}

Более подробно почитать о векторе можно, например, на MSDN.