Линейный контейнер vector

Простейшим контейнером STL является vector. Это всего лишь обычный (C-like) массив с расширенной функциональностью. Контейнер vector -- единственный в STL обратно-совместимый с чистым C контейнер. Это означает, что vector по сути дела и является обычным динамическим массивом, но с рядом дополнительных функций.

Знакомство с vector начнём с примеров:

#include <vector>

using namespace std;

vector<int> v(10);

for(int i = 0; i < 10; i++) {
   v[i] = (i+1)*(i+1);
}

for(int i = 9; i > 0; i--) {
   v[i] -= v[i-1];
}

Далее в этом тексте директивы #include и using будут опускаться.

Мы видим, что при описании контейнера типа vector сразу после ключевого слова vector в угловых скобках -- в качестве шаблонного параметра -- указывается тип данных.

Когда в программе встречается описание следующего вида

vector<int> v;

на самом деле создаётся пустой вектор. Будьте внимательны с конструкциями вроде

vector<int> v[10];

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

Вектор всегда может сказать свой текущий размер:

int elements_count = v.size();

Здесь следует сделать два замечания. Первое заключается в том, что согласно стандарту STL все методы, возвращающие размер контейнера, имеют беззнаковый тип. Это чревато не только надоедливыми предупреждениями о приведении и сравнении знакового и беззнакового типов, но и более серьёзными проблемами. Поэтому, в экстремальном программировании, автор рекомендует использовать простой макрос, который возвращает тип контейнера в «обычном» знаковом целом типе.

#define sz(c) int((c).size())

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

Второе замечание состоит в следующем: конструкция вида c.size() == 0 является признаком дурного тона в STL. Если следует определить, не пуст ли контейнер, следует использовать специальный метод empty(), определённый для каждого контейнера.

// Подобного кода следует избегать.
bool is_nonempty_notgood = (Container.size() >= 0); 

// ОК 
bool is_nonempty_ok = ! Container.empty();

Дело в том, что не любой контейнер может узнать свой размер за O(1). А для того, чтобы узнать, к примеру, есть ли хотя бы один элемент в двусвязном списке, определённо не имеет смысла пробегаться по всем его элементам и подсчитывать их количество, не так ли?

Также с векторами широко используется функция push_back(x). Метод push_back(x) добавляет элемент в конец вектора, расширяя его на один элемент. Поясним это на примере:

vector<int> v;
for(int i = 1; i < 1000000; i *= 2) {
    v.push_back(i);
}
int elements_count = v.size(); 
// Здесь, кстати, мы получим предупреждение 
// о signed/unsigned mismatch

При использовании метода push_back(x) не следует беспокоиться за лишние операции выделения памяти. Конечно же, вектор не будет расширяться на один элемент при вызове push_back(x). Если о чём и следует беспокоиться при использовании push_back(x) -- так это об объёме используемой памяти. В большинстве реализаций STL использование push_back(x) может привести к тому, что занятый вектором объём памяти будет в два раза превосходить реальную потребность. О методах работы с памятью для векторов и о способах эффективного их использования мы ещё поговорим ниже.

Если хочется изменить размер вектора, используется метод resize(n):

vector<int> v(20);

for(int i = 0; i < 20; i++) {
    v[i] = i+1;
}

v.resize(25);

for(int i = 20; i < 25; i++) {
    v[i] = i*2;
}

После вызова метода resize(n) вектор будет содержать ровно n элементов. Если параметр n меньше, чем размер вектора до вызова resize(n), то вектор уменьшится и «лишние» элементы будут удалены. Если же n больше, чем размер вектора, то вектор увеличит свой размер и заполнит появившиеся элементы нулями. Если хранимым типом данных является более сложный объект, нежели стандартный тип данных новые элементы будут инициализированы конструктором по умолчанию.

Важно помнить, что если использовать push_back(x) после resize(n), то элементы будут добавлены после области, выделенной resize(n), а не в неё. В нижеприведённом примере, после выполнения данного фрагмента кода, размер вектора будет равен 30, а не 25.

vector<int> v(20);
for(int i = 0; i < 20; i++) {
	v[i] = i+1;
}
v.resize(25);
for(int i = 20; i < 25; i++) {
    v.push_back(i*2); // Запись производится в элементы 
                      // [25..30), а не [20..25) !
}

Для очистки вектора (как и любого другого контейнера STL) предназначен метод clear(). После вызова clear() контейнер окажется пустым, т. е. будет содержать ноль элементов. Будьте аккуратны: clear() не обнуляет все элементы контейнера, но освобождает весь контейнер целиком.

Существует много способов инициализировать вектор при создании.

Вектор можно создать как копию другого вектора:

vector<int> v1;
...
vector<int> v2 = v1;
vector<int> v3(v1);

Если вы хорошо знакомы с C++, то понимаете, что v2 и v3 инициализируются абсолютно идентично.

Как мы уже говорили, можно создать вектор желаемого размера:

vector<int> Data(1000);

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

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

vector<string> names(20, "Unknown");

Как вы, конечно, помните, вектор может содержать любой тип данных, а не только int. string -- это стандартный контейнер для строки в STL, о нём мы поговорим чуть позже.

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

vector< vector<int> > Matrix; 
// Помните о лишних пробелах между угловыми скобками!

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

int N, M;
...
vector< vector<int> > Matrix(N, vector<int>(M, -1));

Вышеприведённая конструкция создаёт матрицу с N строками и M столбцами. Изначально матрица будет заполнена значениями -1.

При использовании векторов следует помнить об одной очень важной особенности работы с памятью в STL. Основное правило здесь можно сформулировать таким образом: контейнеры STL всегда копируются при любых попытках передать их в качестве параметра.

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

void some_function(vector<int> v) { 
   // Старайтесь никогда так не делать
   ...
}

то весь миллион элементов будет скопирован в другой, временный, вектор, который будет освобождён при выходе их функции some_function. Если эта функция вызывается в цикле, о производительности программы можно забыть сразу.

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

void some_function(const vector<int>& v) { 
   // OK
   ...
}

Если содержимое контейнера может измениться по ходу работы функции, то модификатор const писать не следует:

int modify_vector(vector<int>& v) { 
   // Так держать
   v[0]++;
}

Правило копирования данных применимо ко всем контейнерам STL без исключения.

Также следует отметить, что если объекты, хранимые в контейнере, имеют некоторый физический смысл и/или связаны с другими объектами, следует задуматься об использовании не контейнера из объектов, а контейнера из указателей на объекты. Хорошим критерием здесь может служить следующее правило: всегда ли можно создать новый экземпляр моего класса при помощи конструктора по умолчанию? В случае любых сомнений при ответе на этот вопрос не следует «разбрасываться» объектами. Следует пользоваться контейнерами из указателей. Хорошим решением при этом будет использование контейнеров, содержащих умные указатели (smart pointers), но и поддержание отдельного массива (вектора) созданных объектов -- тоже достаточно грамотное решение.

Часто используется функция vector::reserve(n). Как уже было сказано, вектор не выделяет по одному новому элементу в памяти на каждый вызов push_back(). Вместо этого, при вызове push_back(), вектор выделяет больше памяти, чем реально требуется. В большинстве реализаций при необходимости выделить лишнюю память, vector увеличивает объём выделенной памяти в два раза. На практике это бывает не очень удобно. Наиболее простой способ обойти эту проблему заключается в использовании метода reserve. Вызов метода vector::reserve(size_t n) выделяет дополнительную память в будущее пользование vector. Параметр n имеет следующий смысл: вектор должен выделить столько памяти, чтобы вплоть до размера в n элементов дополнительных операций выделения памяти не потребовалось.

Рассмотрим следующий пример. Пусть имеется vector из 1 000 элементов, и пусть объём выделенной им памяти составляет 1 024 элемента. Мы собираемся добавить в него 50 элементов при помощи метода push_back(). Если вектор расширяется в два раза, его размер в памяти по завершении этой операции будет составлять 2 048 элементов, т. е. почти в два раза больше, чем это реально необходимо. Однако, если перед серией вызовов метода v.push_back(x) добавить вызов

v.reserve(1050);

то память будет использоваться эффективно. Если вы активно используете push_back(), то reserve() -- ваш друг.

Итак, мы умеем создавать вектора, добавлять в них данные и работать с этими данными. Хочется двигаться дальше: например, научиться манипулировать блоками данных внутри самого вектора. Однако, прежде чем мы перейдём к рассмотрению соответствующего инструментария STL, познакомимся с другими аспектами программирования в STL.