Основы программирования на C++: Последовательные контейнеры⁠⁠

Прежде чем читать мою статью - реши для себя, зачем ты это делаешь. Даже если ты просто нормальный человек, лишним не будет.

Если вы настоящий профессионал программирования, то зачем вы тут сидите и читайте статью на пикабу? Если вы ради интереса зашли почитать, то претензий ноль, но если вы просто захотели задушить нового пользователя Пикабу минусами, то немедленно покиньте статью, вам однозначно интересно не будет.

Здравствуйте, мои маленькие любители программирования!

Последовательные контейнеры

Стандартная библиотека C++ предлагает набор шаблонных контейнеров, с некоторыми из которых вы уже знакомы: это std::vector и std::string. Эти два контейнера гарантируют, что элементы (или символы в случае строки) будут храниться в непрерывном участке памяти. Они эффективно добавляют элементы в конец, при необходимости делая реаллокацию, но не могут обеспечить эффективную вставку или удаление элементов в других местах.

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

Контейнер std::array

Если вам нужен массив фиксированного размера, известного на этапе компиляции, используйте std::array. Вот пример объявления array из трёх элементов:

#include <array>

int main() {

std::array<int, 3> point = {1, 2, -3};

}

std::array является обёрткой над низкоуровневым массивом T[N], предоставляя интерфейс стандартного контейнера: он знает свой размер, умеет присваиваться, предоставляет итераторы и т.д. Как и у вектора, элементы array располагаются в памяти непрерывно, но хранятся не в динамической памяти, а на стеке. Размер array должен быть задан на этапе компиляции и не может изменяться во время выполнения программы.

Контейнер std::deque

Deque расшифровывается как double-ended queue (двусторонняя очередь). В отличие от вектора, который размещает элементы в памяти непрерывно, std::deque размещает их кусочно-непрерывно, в отдельных страницах (непрерывных блоках) памяти фиксированного размера. Даже для одного элемента в деке будет выделена целая страница. Сами страницы не обязательно расположены в памяти подряд. Отдельно поддерживается список указателей на начала страниц. Размеры страниц зависят от sizeof(T) и от конкретной реализации дека.

Дек эффективно добавляет и удаляет элементы в начале и в конце без необходимости реаллокации и копирования старых элементов. Вставка по краям в деке эффективнее, чем в векторе. Однако вставка в середину и удаление из неё требуют сдвига элементов. Обращение к элементу по индексу происходит за O(1), но требует двух разыменований указателей, в то время как вектору достаточно одного.

Пример использования deque:

#include <deque>

#include <iostream>

int main() {

std::deque<int> d = {1, 2, 3, 4};

d.push_back(5); // добавление в конец

d.push_back(6);

d.pop_back(); // удаление из конца

d.push_front(0); // добавление в начало

d.push_front(-1);

d.pop_front(); // удаление из начала

for (size_t i = 0; i != d.size(); ++i) {

std::cout << d[i] << "\n";

}

for (int x : d) {

std::cout << x << "\n";

}

}

Контейнер std::list

Двусвязный список std::list хранит элементы в отдельных узлах, которые могут располагаться в разных местах памяти. Узлы содержат указатели на предыдущий и следующий узлы. Пройтись по списку можно только с помощью range-based for или итераторов.

Пример использования list:

#include <list>

#include <iostream>

int main() {

std::list<int> l = {10, 15, 20};

l.push_front(5);

l.push_front(0);

l.push_back(25);

l.push_back(30);

l.pop_front();

l.pop_back();

for (int x : l) {

std::cout << x << "\n"; // 5 10 15 20 25

}

}

Итераторы списка

Итераторы — это объекты для навигации по контейнеру. Они позволяют обращаться к текущему элементу и сдвигаться к соседним. Функция begin возвращает итератор, указывающий на начальный элемент контейнера.

Пример использования итераторов:

#include <list>

#include <iostream>

int main() {

std::list<int> l = {10, 15, 20};

auto iter = l.begin();

std::cout << *iter << "\n"; // печатаем начальный элемент

++iter; // сдвигаемся к следующему элементу

--iter; // возвращаемся назад

}

Функция end возвращает итератор, указывающий за последний элемент контейнера. Этот итератор нельзя разыменовывать, но можно сравнивать с ним.

Пример прохода по списку:

#include <list>

#include <iostream>

int main() {

std::list<int> l = {10, 15, 20};

for (auto iter = l.begin(); iter != l.end(); ++iter) {

std::cout << *iter << "\n"; // печатаем элементы списка через итератор

}

for (auto iter = l.rbegin(); iter != l.rend(); ++iter) {

std::cout << *iter << "\n"; // проход по списку в обратном порядке

}

}

С итераторами можно вставлять или удалять элементы в любом месте списка.

Пример вставки и удаления элементов:

#include <list>

#include <iostream>

int main() {

std::list<int> l = {0, 10, 15, 20};

auto iter = l.begin();

++iter;

l.insert(iter, 5); // вставляем на эту позицию элемент

for (auto iter = l.begin(); iter != l.end(); ) {

if (*iter % 2 == 0) {

iter = l.erase(iter); // возвращается итератор на элемент, следующий за удалённым

} else {

++iter;

}

}

}

Контейнер std::forward_list

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

Пример использования forward_list:

#include <forward_list>

#include <iostream>

int main() {

std::forward_list<int> fl = {3, 42, 5};

fl.push_front(2);

auto iter = std::next(fl.begin());

iter = fl.erase_after(iter);

fl.insert_after(iter, 4);

for (int x : fl) {

std::cout << x << "\n"; // 2 3 5 4

}

}

Инвалидация итераторов и ссылок

При изменении контейнера итераторы и ссылки на элементы могут стать невалидными. Например, если у вектора произошла реаллокация, все итераторы и ссылки инвалидируются. В std::array ничего вставить нельзя, его размер фиксирован. В std::deque инвалидируются итераторы, но не инвалидируются ссылки и указатели. В std::list и std::forward_list ни итераторы, ни ссылки не инвалидируются.

Пример инвалидации итераторов:

#include <vector>

#include <iostream>

int main() {

std::vector<int> v = {1, 2, 3, 4};

auto iter = v.begin(); // итератор

int* ptr = &v.front(); // указатель

int& ref = v.front(); // ссылка

std::cout << *iter << " " << *ptr << " " << ref << "\n"; // 1 1 1

v.push_back(5); // происходит реаллокация

// обращаться к старым итераторам, указателям и ссылкам больше нельзя:

std::cout << *iter << " " << *ptr << " " << ref << "\n"; // неопределённое поведение!

}

Ассоциативные контейнеры в C++

Ассоциативные контейнеры в C++ позволяют хранить данные в виде пар "ключ-значение". Они обеспечивают быстрый доступ к значениям по ключу. В стандартной библиотеке C++ есть два основных типа ассоциативных контейнеров:

1. Контейнеры на основе сбалансированных деревьев:

- `std::map` — хранит пары "ключ-значение" в отсортированном порядке.

- `std::set` — хранит только уникальные ключи в отсортированном порядке.

2. Контейнеры на основе хеш-таблиц:

- `std::unordered_map` — хранит пары "ключ-значение" без гарантии порядка.

- `std::unordered_set` — хранит только уникальные ключи без гарантии порядка.

Также существуют "мульти" версии этих контейнеров (`multimap`, `multiset`, `unordered_multimap`, `unordered_multiset`), которые позволяют хранить несколько значений для одного ключа.

---

Контейнер `std::map`

`std::map` — это ассоциативный контейнер, который хранит пары "ключ-значение" в отсортированном порядке. Он реализован как красно-чёрное дерево, что обеспечивает логарифмическое время выполнения операций поиска, вставки и удаления.

Пример использования `std::map`:

#include <iostream>

#include <map>

#include <string>

int main() {

std::map<std::string, int> years = {

{"Moscow", 1147},

{"Rome", -753},

{"London", 47},

};

// Добавление элемента

years["Paris"] = 52;

// Итерация по элементам

for (const auto& [city, year] : years) {

std::cout << city << ": " << year << "\n";

}

// Поиск элемента

if (auto it = years.find("Rome"); it != years.end()) {

std::cout << "Found: " << it->first << " -> " << it->second << "\n";

}

// Удаление элемента

years.erase("London");

}

Основные операции:

- Вставка: `years[key] = value` или `years.insert({key, value})`.

- Поиск: `years.find(key)`.

- Удаление: `years.erase(key)`.

Контейнер `std::unordered_map`

`std::unordered_map` — это ассоциативный контейнер, основанный на хеш-таблицах. Он обеспечивает среднее время выполнения операций O(1), но не гарантирует порядок элементов.

Пример использования `std::unordered_map`:

#include <iostream>

#include <unordered_map>

#include <string>

int main() {

std::unordered_map<std::string, int> freqs;

std::string word;

// Подсчёт частот слов

while (std::cin >> word) {

++freqs[word];

}

// Вывод результатов

for (const auto& [word, freq] : freqs) {

std::cout << word << ": " << freq << "\n";

}

}

Основные операции:

- Вставка: `freqs[key] = value` или `freqs.insert({key, value})`.

- Поиск: `freqs.find(key)`.

- Удаление: `freqs.erase(key)`.

Контейнеры `std::set` и `std::unordered_set`

Эти контейнеры хранят только уникальные ключи. Они полезны, когда нужно проверить наличие элемента в коллекции.

Пример использования `std::set`:

#include <iostream>

#include <set>

#include <string>

int main() {

std::set<std::string> unique_words;

std::string word;

// Сбор уникальных слов

while (std::cin >> word) {

unique_words.insert(word);

}

// Вывод уникальных слов

for (const auto& word : unique_words) {

std::cout << word << "\n";

}

}

Мультиконтейнеры (`multimap`, `multiset`, `unordered_multimap`, `unordered_multiset`) позволяют хранить несколько значений для одного ключа.

Пример использования `std::multimap`:

#include <iostream>

#include <map>

#include <string>

int main() {

std::multimap<std::string, int> positions;

std::string word;

int position = 0;

// Сохранение позиций слов

while (std::cin >> word) {

positions.insert({word, position});

++position;

}

// Вывод всех позиций для слова "hello"

auto range = positions.equal_range("hello");

for (auto it = range.first; it != range.second; ++it) {

std::cout << "Position: " << it->second << "\n";

}

}

Итераторы ассоциативных контейнеров

Итераторы позволяют обходить элементы контейнера. Для `map` и `set` итераторы двусторонние, а для `unordered_map` и `unordered_set` — однонаправленные.

Пример работы с итераторами:

#include <iostream>

#include <map>

int main() {

std::map<int, std::string> numbers = {

{1, "one"},

{2, "two"},

{3, "three"},

};

auto it = numbers.find(2);

if (it != numbers.end()) {

std::cout << "Found: " << it->first << " -> " << it->second << "\n";

}

}

Ассоциативные контейнеры в C++ — это мощный инструмент для работы с данными, организованными по принципу "ключ-значение". Выбор между `map` и `unordered_map` зависит от требований к порядку элементов и производительности. Для хранения уникальных ключей используйте `set` или `unordered_set`, а для работы с дубликатами — мультиконтейнеры.