Библиотека стандартных шаблонов (STL) (англ. Standard Template Library) — набор согласованных обобщённых алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций в C++.
Библиотека стандартных шаблонов до включения в стандарт C++ была сторонней разработкой, вначале — фирмы HP, а затем SGI. Стандарт языка не называет её «STL», так как эта библиотека стала неотъемлемой частью языка, однако многие люди до сих пор используют это название, чтобы отличать её от остальной части стандартной библиотеки (потоки ввода-вывода (iostream), подраздел Си и др.).
Vector
Vector - C-подобный динамический массив произвольного доступа с автоматическим изменением размера при добавлении/удалении элемента. Доступ по индексу за O(1). Добавление-удаление элемента в конец vector занимает амортизированное O(1) время, та же операция в начале или середине vector — O(n).
Контейнер vector -- единственный в STL обратно-совместимый с чистым C контейнер. Это означает, что vector по сути дела и является обычным динамическим массивом, но с рядом дополнительных функций.
Знакомство с vector имеет смысл начать с примеров, что бы можно было установить аналогии между массивом и контейнером:
- Код: выделить все
#include <vector>
using namespace std;
int main() {
int size = 10;
vector<int> arr(size);
for(int i = 0; i < size; i++) {
arr[i] = (i+1)*(i+1);
}
for(int i = size-1; i > 0; i--) {
arr[i] -= arr[i-1];
}
return 0;
}
Мы видим, что при описании контейнера типа vector сразу после ключевого слова vector в угловых скобках -- в качестве шаблонного параметра -- указывается тип данных. Сам класс vector подключается через использование заголовочного файла с аналогичным названием.
Когда в программе встречается описание следующего вида
- Код: выделить все
vector<int> arr;
на самом деле создаётся пустой вектор. Будьте внимательны с конструкциями вроде
- Код: выделить все
vector<int> arr[10];
В данном коде переменная v описывается как массив из десяти векторов целых чисел, каждый из которых изначально пуст. Для размещения в памяти вектора ненулевого начального размера следует использовать конструктор, т. е. писать круглые скобки вместо квадратных.
Размер объекта класса vector всегда можно узнать с помощью метода size():
- Код: выделить все
size_t elementsCount = arr.size();
Здесь следует сделать два замечания. Первое заключается в том, что согласно стандарту STL все методы, возвращающие размер контейнера, имеют беззнаковый тип.
Второе замечание состоит в следующем: конструкция вида c.size() == 0 является признаком дурного тона в STL. Если следует определить, не пуст ли контейнер, следует использовать специальный метод empty(), который определен возвращает true в случае, если контейнер пуст и false в обратном случае, определённый для каждого контейнера.
- Код: выделить все
bool isNonemptyNotGood = (container.size() > 0); //Некрасиво
bool isNonemptyOk = !container.empty(); //Красиво
Добавление в вектор и очистка
Для добавления элемента в вектор широко используется функция push_back(x). Метод push_back(x) добавляет элемент в конец вектора, расширяя его на один элемент. Поясним это на примере:
- Код: выделить все
vector<int> arr;
for(int i = 1; i < 1000; i *= 2) {
arr.push_back(i);
}
size_t elementsCount = arr.size();
Для того, что бы изменить размер вектора, используется метод resize(n):
- Код: выделить все
vector<int> arr(20);
for(int i = 0; i < 20; i++) {
arr[i] = i+1;
}
arr.resize(25);
for(int i = 20; i < 25; i++) {
arr[i] = i*2;
}
После вызова метода resize(n) вектор будет содержать ровно n элементов. Если параметр n меньше, чем размер вектора до вызова resize(n), то вектор уменьшится и «лишние» элементы будут удалены. Если же n больше, чем размер вектора, то вектор увеличит свой размер и заполнит появившиеся элементы нулями. Если хранимым типом данных является более сложный объект, нежели стандартный тип данных новые элементы будут инициализированы конструктором по умолчанию.
Важно помнить, что если использовать push_back(x) после resize(n), то элементы будут добавлены после области, выделенной resize(n), а не в неё. В нижеприведённом примере, после выполнения данного фрагмента кода, размер вектора будет равен 30, а не 25.
- Код: выделить все
vector<int> arr(20);
for(int i = 0; i < 20; i++) {
arr[i] = i+1;
}
arr.resize(25);
for(int i = 20; i < 25; i++) {
arr.push_back(i*2); // Запись производится в элементы
// [25..30), а не [20..25) !
}
Для очистки вектора (как и любого другого контейнера STL) предназначен метод clear(). После вызова clear() контейнер окажется пустым, т. е. будет содержать ноль элементов. Будьте аккуратны: clear() не обнуляет все элементы контейнера, но освобождает весь контейнер целиком.
Инциализация
Существует много способов инициализировать вектор при создании.
Вектор можно создать как копию другого вектора:
vector<int> arr1;
...
vector<int> arr2 = arr1;
vector<int> arr3(arr1);
Можно создать вектор желаемого размера:
- Код: выделить все
vector<int> data(1000);
В данном примере data будет содержать тысячу нулей. Не забывайте об использовании круглых, а не квадратных скобок.
Для того, чтобы проинициализировать все элементы вектора при создании значениями по умолчанию, следует передать конструктору второй параметр:
- Код: выделить все
vector<string> names(20, "Unknown");
Вектор может содержать любой тип данных, а не только int.
Также очень важно бывает создать многомерный массив. Сделать это с использованием векторов можно при помощи следующей конструкции:
- Код: выделить все
vector< vector<int> > matrix;
На примере должно быть понятно, как указать размер матрицы при создании:
- Код: выделить все
size_t rowsNum, colsNum;
...
vector< vector<int> > matrix(rowsNum, vector<int>(colsNum, 10));
Вышеприведённая конструкция создаёт матрицу с rowsNum строками и colsNum столбцами. Изначально матрица будет заполнена значениями 10.
Стоит отметить, что пробел между двумя знаками больше (>) в объявлении двухмерного вектора - обязателен. Его отсутствие вызовет ошибку компиляции. Компилятор рассмотрит два знака больше как один оператор чтения из потока.
Контейнеры при передаче в функцию
При использовании векторов следует помнить об одной очень важной особенности работы с памятью в STL. Основное правило здесь можно сформулировать таким образом: контейнеры STL всегда копируются при любых попытках передать их в качестве параметра.
Таким образом, если вы передаёте вектор из миллиона элементов функции, описанной следующим образом:
- Код: выделить все
void someFunction(vector<int> arr) {
}
то весь миллион элементов будет скопирован в другой, временный, вектор, который будет освобождён при выходе их функции someFunction. Если эта функция вызывается в цикле, то производительности программы можно забыть сразу.
Если вы не хотите, чтобы контейнер создавал клон себя каждый раз при вызове функции, используйте передачу параметра по ссылке. Хорошим тоном считается использование при этом модификатора const, если функция не намерена изменять содержимое контейнера.
- Код: выделить все
void someFunction(const vector<int>& arr) {
...
}
Возвращение контейнеров из функции
Из функции можно вернуть любой контейнер, так же как и стандартный тип, или структуру.
- Код: выделить все
vector<int> readInput() {
fstream fIn("input.txt", ios_base::in);
if(!fIn.is_open()) {
cerr << "Error openning input file" << endl;
exit(1);
}
size_t size;
fIn >> size;
vector<int> res(size);
for(size_t i=0; i<size; i++) {
fIn >> res[i];
}
fIn.close();
return res;
}
При этом беспокоиться о производительности не стоит потому что, хоть формально объекты внутри функции, и вне – это два разных объекта, но копирования не будет, компилятор этот момент оптимизирует.