C++ и Python

Язык 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. Выбор подходящих структур данных является одним из ключевых умений грамотного разработчика программного обеспечения. Мы призываем вас продолжать самостоятельно изучать различные структуры данных.

Источники