Глава 6. Стандартная библиотека #

6.1 Контейнеры STL #

Контейнеры стандартной библиотеки C++ (STL) — это шаблонные классы, которые предоставляют эффективные структуры данных для хранения и организации объектов. Каждый контейнер имеет свои уникальные характеристики и области применения.

1. Вектор (std::vector) #

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

Основные характеристики: #

• Непрерывное хранение элементов
• Быстрый доступ по индексу (O(1))
• Динамическое изменение размера
• Эффективное добавление элементов в конец

#include <vector>
#include <iostream>

std::vector<int> numbers = {1, 2, 3, 4, 5};
numbers.push_back(6);  // Добавление элемента в конец
std::cout << numbers[2] << std::endl;  // Доступ по индексу
numbers.pop_back();    // Удаление последнего элемента

Сложность основных операций: #

• Случайный доступ: O(1)
• Вставка/удаление в конце: O(1)
• Вставка/удаление в середине: O(n)

2. Список (std::list) #

Двусвязный список, позволяющий эффективно вставлять и удалять элементы в любом месте.

Основные характеристики: #

• Нет непрерывного хранения
• Эффективные вставка и удаление в любом месте
• Двусторонняя навигация

#include <list>
#include <iostream>

std::list<std::string> names = {"Alice", "Bob"};
names.push_front("Charlie");  // Вставка в начало
names.push_back("David");     // Вставка в конец
names.insert(++names.begin(), "Eve");  // Вставка в середину

Сложность основных операций: #

• Вставка/удаление в любом месте: O(1)
• Случайный доступ: O(n)

3. Двустороння очередь (std::deque) #

Контейнер, позволяющий эффективно добавлять и удалять элементы с обоих концов.

Основные характеристики: #

• Быстрое добавление/удаление с начала и конца
• Случайный доступ
• Меньшие накладные расходы, чем у vector

#include <deque>
#include <iostream>

std::deque<int> numbers = {1, 2, 3};
numbers.push_front(0);    // Добавление в начало
numbers.push_back(4);     // Добавление в конец
numbers.pop_front();      // Удаление из начала

4. Множества (std::set и std::multiset) #

std::set #

• Упорядоченное множество уникальных элементов
• Автоматическая сортировка
• Быстрый поиск

#include <set>
#include <iostream>

std::set<int> unique_numbers = {5, 2, 8, 1, 5};
// В set будет: {1, 2, 5, 8}
unique_numbers.insert(3);
auto it = unique_numbers.find(5);  // Быстрый поиск

std::multiset #

• Упорядоченное множество с возможностью повторения элементов

#include <set>
#include <iostream>

std::multiset<int> numbers = {5, 2, 5, 8, 1};
// В multiset будет: {1, 2, 5, 5, 8}
numbers.insert(5);  // Можно добавить повторяющийся элемент

Сложность основных операций: #

• Вставка: O(log n)
• Поиск: O(log n)

5. Отображения (std::map и std::multimap) #

std::map #

• Контейнер “ключ-значение” с уникальными ключами
• Автоматическая сортировка по ключу

#include <map>
#include <string>
#include <iostream>

std::map<std::string, int> ages = {
    {"Alice", 30},
    {"Bob", 25}
};
ages["Charlie"] = 35;  // Добавление или изменение
std::cout << ages["Alice"] << std::endl;  // Доступ по ключу

std::multimap #

• Отображение с возможностью повторения ключей

#include <map>
#include <string>

std::multimap<std::string, int> scores = {
    {"Alice", 95},
    {"Alice", 97},
    {"Bob", 92}
};

6. Стек (std::stack) #

Контейнер с дисциплиной “последним вошел - первым вышел” (LIFO).

#include <stack>
#include <iostream>

std::stack<int> numbers;
numbers.push(1);
numbers.push(2);
std::cout << numbers.top() << std::endl;  // 2
numbers.pop();

7. Очередь (std::queue) #

Контейнер с дисциплиной “первым вошел - первым вышел” (FIFO).

#include <queue>
#include <iostream>

std::queue<std::string> tasks;
tasks.push("Task 1");
tasks.push("Task 2");
std::cout << tasks.front() << std::endl;  // "Task 1"
tasks.pop();

8. Приоритетная очередь (std::priority_queue) #

Очередь с упорядочиванием элементов по приоритету.

#include <queue>
#include <iostream>

std::priority_queue<int> priorities;
priorities.push(3);
priorities.push(1);
priorities.push(4);
std::cout << priorities.top() << std::endl;  // 4

Рекомендации по выбору контейнера #

1. std::vector:

   • Когда нужен быстрый доступ по индексу
   • Частые операции в конце контейнера

2. std::list:

   • Частые вставки и удаления в середине
   • Не требуется случайный доступ

3. std::set/map:

   • Необходима сортировка
   • Быстрый поиск
   • Уникальные ключи

4. std::deque:

   • Частые операции с началом и концом
   • Меньше накладных расходов, чем vector

Заключение #

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