Язык C++
Контейнеры стандартной библиотеки C++
При написании почти любой программы возникает необходимость работы с набором объектов. К набору объектов можно добавлять объекты, удалять из него объекты, искать определенный объект и т.д. В любом высокоуровневом языке программирования реализованы классические структуры данных (контейнеры), позволяющие решать часто возникающие задачи по работе с наборами объектов. Умение использовать подходящие структуры данных является базовым навыком разработчика.
Стандартная библиотека C++ содержит контейнеры двух типов:
- Последовательные контейнеры обеспечивают эффективный последовательный доступ к элементам. Примерами последовательных структур данных являются двусвязный список и массив, которые в C++ представлены типами
list
иvector
, соответственно. Вероятно, читатель уже знаком с этими структурами. - Ассоциативные контейнеры обеспечивают быстрый поиск элементов. Примером ассоциативных структур данных являются множество и словарь, которым соответствуют типы
set
иmap
. Типset
позволяет хранить уникальные объекты различных типов, эффективно добавлять, удалять объекты и выполнять поиск. Типmap
позволяет хранить пары ключ-значение, причем ключи должны быть уникальными.
Разные типы контейнеров C++ разработаны таким образом, чтобы работа с ними происходила единообразно. Во многих случаях можно изменить тип контейнера, не изменяя часть кода, в которой происходит работа с контейнером. Сейчас мы рассмотрим примеры работы с основными контейнерами и кратко обсудим их относительные преимущества и недостатки. В дальнейшем в ходе курса мы будем уточнять знания о контейнерах.
Контейнер vector
Контейнер vector
используется чаще всего. Чтобы создать объект типа vector
, необходимо в угловых скобках указать тип объектов, которые мы собираемся хранить. Вот несколько примеров создания объектов типа vector
:
#include <vector>
#include <string>
using namespace std;
// пустой вектор для объектов типа int
vector<int> v1;
// создание вектора с помощью списка инициализации
vector<int> v2 = {1,2,3};
// вектор размера 10 для хранения объектов типа double
vector<double> v3(10);
// вектор строк, который содержит три строки "vec"
vector<string> v4(3, "vec");
// вектор векторов для типа double
vector<vector<double>> v5;
Тип vector
может работать с любым типом данных, в том числе с самим собой, как показано в последнем примере. Это относится ко всем контейнерам C++ с некоторыми уточнениями.
Обращаться к элементу вектора можно по индексу:
vector<int> v{1,2,3};
int a = v[0]; // a = 1
int b = v.at(1); // b = 2
v[2] = 5; // v = [1,2,5]
v.at(0) = 0; // v = [0,2,5]
При вызове оператора []
не происходит проверка того, что индекс не превышает размер вектора, в то время как метод at()
выполняет такую проверку и в случае неудачи генерирует исключение.
Чтобы добавить один элемент в конец вектора, можно воспользоваться методом push_back()
. Метод insert()
позволяет вставить объект в произвольное место в векторе:
vector<int> v{1,2,4};
v.push_back(5); // v = [1,2,4,5]
v.insert(v.begin()+2, 3); // v = [1,2,3,4,5]
vector<int> w{6,7,8};
v.insert(v.end(), w.begin(), w.end()); // v = [1,2,3,4,5,6,7,8]
Методы begin()
и end()
позволяют получить объекты, которые указывают на начало и конец вектора, соответственно. Позже мы уточним более детально, что это за объекты.
Вставка объекта в конец вектора с помощью метода push_back()
происходит максимально эффективно, поскольку объекты хранятся последовательно в памяти. Вставка объекта в начало вектора методом insert()
приводит к необходимости перемещать все остальные объекты. Если в вашей программе происходит вставка в начало вектора в цикле, то скорее всего вы выбрали не самую подходящую структуру данных.
Метод size()
возвращает текущий размер вектора, метод empty()
возвращает true
, если размер равен нулю и false
в противном случае. Эти методы определены для всех стандартных контейнеров C++.
Прочитать последовательно все элементы вектора можно способом, который работает для всех стандартных контейнеров:
vector<int> v{1,2,3,4};
for (int item : v) {
cout << item << ' ';
}
Внимательный читатель заметил, что работа с векторами во многом похожа на работу с типом string
. Это не удивительно, ведь string
можно рассматривать в качестве специального последовательного контейнера. Также это сходство иллюстрирует стремление к единообразию в работе с различными контейнерами в C++.
Мы обсудили далеко не все возможности векторов, но этого достаточно для начала работы с ними. Более подробную информацию о типе vector
можно найти в документации.
Контейнер set
Тип set
реализует ассоциативный контейнер "множество". Объект типа set
хранит упорядоченное множество уникальных объектов. Операции добавления, удаления и поиска элемента в set
требуют количество вычислений, пропорциональное логарифму текущего размера множества. Эти характеристики достигаются специальным способом хранения объектов - в виде двоичного дерева поиска.
Создать объект set
можно различными способами:
#include <set>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
set<int> s1; // пустое множество для int
set<int> s2{1,3,5,2}; // инициализация из список объектов
vector<string> v{"frog", "dog", "cat", "dog"};
set<string> s3(v.begin(), v.end());
for (string item : s3) {
cout << item << ", ";
} // Выведет cat, dog, frog
Добавление элементов в set
выполняется с помощью метода insert
set<int> s{1,3,1,1}; // s = {1, 3}
s.insert(2); // s = {1,2,3}
s.insert({1,2,3,4,5}); // s = {1,2,3,4,5}
vector<int> v{1,80,82};
s.insert(v.begin(), v.end()); // s = {1,2,3,4,5,80,82}
Рассмотрим несколько методов для поиска элементов в set
:
find
позволяет найти элемент, если он есть вset
. Метод возвращает итератор на найденный элемент. Если элемент не найден, возвращается специальный итератор, указывающий в никуда (возвращается методомend()
);lower_bound
возвращает итератор на первый элемент, который не меньше данного;upper_bound
возвращает итератор на первый элемент, который больше данного.
Про итераторы мы будем говорить отдельно. Сейчас достаточно знать, что это некоторый объект, который указывает на элемент в контейнере. Незнание некоторых деталей не мешает нам начать их использовать:
set<int> s{1,3,4,5};
set<int>::iterator it = s.find(2);
if (it == s.end()) {
cout << "Not found\n";
} else {
int val = *it;
cout << "Found " << val << endl;
}
if (auto it2 = s.lower_bound(3); it2 != s.end()) {
cout << "Lower bound is " << *it2 << endl; // Lower bound is 3
}
if (auto it3 = s.upper_bound(2); it3 != s.end()) {
cout << "Upper bound is " << *it3 << endl; // Lower bound is 3
}
Из этого примера мы видим, что итератор для типа set<int>
имеет тип set<int>::iterator
. Ключевое слово auto
позволяет не набирать длинные названия типов каждый раз, когда мы имеем дело с итераторами. Также мы использовали операцию разыменовывания итератора int val = *it;
, которая по форме очень похожа на разыменовывание указателей в C.
Наконец, в этом примере использован прием, который стал доступен, начиная со стандарта C++ 2017 года: мы инициализировали итераторы it2
и it3
в теле условного оператора if
. Конструкция с инициализацией переменной в теле оператора if
позволяет явно указать, что переменная не будет использоваться за пределами условного оператора. Этот прием позволяет писать более выразительный код и не держать в области видимости лишние объекты.
Объекты типа set
хранят упорядоченные наборы объектов. Это накладывает некоторые требования на тип этих объектов: для типа должен быть определен оператор меньше <
. Именно он используется для поддержания правильной структуры.
Контейнер map
Еще один очень полезный ассоциативный контейнер — тип map
. Он позволяет хранить пары ключ-значение и эффективно находить объекты по ключу. Все очень похоже на тип set
, только с каждым уникальным ключом связано некоторые значение. Большинство методов типа map
аналогичны методам типа set
. Следующий пример показывает основные приемы работы с контейнером map
:
map<string, int> m1; // ключ типа string, значение типа int
m1.insert({"NSU", 257});
map<string, int> m2 {
{"NSU", 257},
{"MSU", 150},
{"MIPT", 230},
{"Stanford U", 1}
};
if (auto it = m2.find("NSU"); it != m2.end()) {
string university = it->first;
int rank = it->second;
cout << "University " << university << " has rank " << rank << endl;
}
if (auto it2 = m2.find("Stanford U"); it2 != m2.end()) {
m2.erase(it2); // удаляем пару ключ-значение из словаря
}
for (auto& [key, val] : m2) {
cout << key << ": " << val << endl;
}
// Вывод будет упорядочен по ключам
// MIPT: 230
// MSU: 150
// NSU: 257
Неупорядоченные ассоциативные контейнеры
В стандартной библиотеке реализованы неупорядоченные версии контейнеров unordered_set
и unordered_map
, которые гарантируют сложность добавления, удаления и поиска элементов за константное время. Это означает, что количество выполняемых операций не зависит от количества элементов в контейнере. Эти гарантии достигаются благодаря хранению объектов в виде хэш-таблиц.
Резюме
Мы обсудили два типа контейнеров из стандартной библиотеки C++: последовательные и ассоциативные. Рассмотрели логику работы с наиболее часто используемыми контейнерами vector
, set
и map
. Выбор подходящих структур данных является одним из ключевых умений грамотного разработчика программного обеспечения. Мы призываем вас продолжать самостоятельно изучать различные структуры данных.