std::vector

Vector — это динамический массив, основной контейнер для последовательного хранения данных.

▸Создание и базовые операции

cpp

1#include <vector>
2#include <algorithm>
3
4std::vector<int> v1;              // Пустой
5std::vector<int> v2(10, 42);     // 10 элементов со значением 42
6std::vector<int> v3 = {1, 2, 3}; // Инициализация списком
7
8// Добавление
9v1.push_back(1);
10v1.emplace_back(2); // Конструирование на месте
11
12// Доступ
13int first = v1[0];      // Без проверки границ
14int safe = v1.at(0);    // С проверкой (бросает std::out_of_range)
15
16// Итераторы
17for (auto it = v1.begin(); it != v1.end(); ++it) {
18    std::cout << *it << " ";
19}
20
21// Range-based for
22for (const auto& elem : v1) {
23    std::cout << elem << " ";
24}

▸Временная сложность vector

| Операция | Сложность |

|----------|-----------|

| Доступ по индексу | O(1) |

| push_back (amortized) | O(1) |

| Вставка в середину | O(n) |

| Удаление в середине | O(n) |

| Поиск | O(n) |

▸Эмпирическое правило

Vector выделяет память с коэффициентом роста 2. При добавлении N элементов происходит O(log N) реаллокаций. Используйте reserve() если знаете примерный размер.

cpp

1std::vector<int> v;
2v.reserve(1000); // Предварительное выделение
3for (int i = 0; i < 1000; ++i) {
4    v.push_back(i); // Без реаллокаций
5}

std::map

Map — это упорядоченный ассоциативный контейнер, основанный на красно-чёрном дереве.

▸Создание и использование

cpp

1#include <map>
2#include <string>
3
4std::map<std::string, int> ages;
5ages["Alice"] = 30;
6ages["Bob"] = 25;
7
8// Вставка
9auto [it, inserted] = ages.insert({"Charlie", 35});
10if (inserted) {
11    std::cout << "Inserted\n";
12}
13
14// Поиск
15auto found = ages.find("Alice");
16if (found != ages.end()) {
17    std::cout << "Alice: " << found->second << "\n";
18}
19
20// Оператор []
21int age = ages["Unknown"]; // Создаёт запись со значением 0!

▸Кастомный компаратор

cpp

1struct CaseInsensitiveCompare {
2    bool operator()(const std::string& a, const std::string& b) const {
3        return std::lexicographical_compare(
4            a.begin(), a.end(),
5            b.begin(), b.end(),
6            [](char c1, char c2) { return std::tolower(c1) < std::tolower(c2); }
7        );
8    }
9};
10
11std::map<std::string, int, CaseInsensitiveCompare> ci_map;
12ci_map["Hello"] = 1;
13ci_map["hello"] = 2; // Перезапишет предыдущее

std::unordered_map

Unordered_map — это хеш-таблица с амортизированным O(1) для всех операций.

▸Сравнение с map

| Операция | map | unordered_map |

|----------|-----|---------------|

| Поиск | O(log n) | O(1) amortized |

| Вставка | O(log n) | O(1) amortized |

| Удаление | O(log n) | O(1) amortized |

| Порядок | Отсортирован | Не определён |

| Память | Больше (дерево) | Меньше (хеш-таблица) |

▸Кастомный хеш

cpp

1struct Point {
2    int x, y;
3};
4
5struct PointHash {
6    size_t operator()(const Point& p) const {
7        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 16);
8    }
9};
10
11struct PointEqual {
12    bool operator()(const Point& a, const Point& b) const {
13        return a.x == b.x && a.y == b.y;
14    }
15};
16
17std::unordered_set<Point, PointHash, PointEqual> points;
18points.insert({1, 2});
19points.insert({3, 4});

Выбор контейнера

vector — последовательный доступ, частый доступ по индексу

map — когда нужен отсортированный порядок

unordered_map — максимальная скорость поиска

set — уникальные элементы в отсортированном порядке

deque — частые вставки/удаления в начале и конце

Заключение

STL-контейнеры — это основа эффективной C++-разработки. Правильный выбор контейнера определяет производительность и удобство кода. Используйте vector по умолчанию, unordered_map для быстрого поиска и map когда нужна сортировка.

#c++#stl#vector#map#unordered-map#контейнеры

C++≈ 12 мин чтения5 апреля 2024 г.

STL контейнеры: vector, map, unordered_map

Детальный обзор основных STL-контейнеров: когда использовать vector, map или unordered_map, их временная сложность и особенности.

std::vector

Vector — это динамический массив, основной контейнер для последовательного хранения данных.

▸Создание и базовые операции

cpp

1#include <vector>
2#include <algorithm>
3
4std::vector<int> v1;              // Пустой
5std::vector<int> v2(10, 42);     // 10 элементов со значением 42
6std::vector<int> v3 = {1, 2, 3}; // Инициализация списком
7
8// Добавление
9v1.push_back(1);
10v1.emplace_back(2); // Конструирование на месте
11
12// Доступ
13int first = v1[0];      // Без проверки границ
14int safe = v1.at(0);    // С проверкой (бросает std::out_of_range)
15
16// Итераторы
17for (auto it = v1.begin(); it != v1.end(); ++it) {
18    std::cout << *it << " ";
19}
20
21// Range-based for
22for (const auto& elem : v1) {
23    std::cout << elem << " ";
24}

▸Временная сложность vector

| Операция | Сложность |

|----------|-----------|

| Доступ по индексу | O(1) |

| push_back (amortized) | O(1) |

| Вставка в середину | O(n) |

| Удаление в середине | O(n) |

| Поиск | O(n) |

▸Эмпирическое правило

cpp

1std::vector<int> v;
2v.reserve(1000); // Предварительное выделение
3for (int i = 0; i < 1000; ++i) {
4    v.push_back(i); // Без реаллокаций
5}

std::map

Map — это упорядоченный ассоциативный контейнер, основанный на красно-чёрном дереве.

▸Создание и использование

cpp

1#include <map>
2#include <string>
3
4std::map<std::string, int> ages;
5ages["Alice"] = 30;
6ages["Bob"] = 25;
7
8// Вставка
9auto [it, inserted] = ages.insert({"Charlie", 35});
10if (inserted) {
11    std::cout << "Inserted\n";
12}
13
14// Поиск
15auto found = ages.find("Alice");
16if (found != ages.end()) {
17    std::cout << "Alice: " << found->second << "\n";
18}
19
20// Оператор []
21int age = ages["Unknown"]; // Создаёт запись со значением 0!

▸Кастомный компаратор

cpp

1struct CaseInsensitiveCompare {
2    bool operator()(const std::string& a, const std::string& b) const {
3        return std::lexicographical_compare(
4            a.begin(), a.end(),
5            b.begin(), b.end(),
6            [](char c1, char c2) { return std::tolower(c1) < std::tolower(c2); }
7        );
8    }
9};
10
11std::map<std::string, int, CaseInsensitiveCompare> ci_map;
12ci_map["Hello"] = 1;
13ci_map["hello"] = 2; // Перезапишет предыдущее

std::unordered_map

Unordered_map — это хеш-таблица с амортизированным O(1) для всех операций.

▸Сравнение с map

| Операция | map | unordered_map |

|----------|-----|---------------|

| Поиск | O(log n) | O(1) amortized |

| Вставка | O(log n) | O(1) amortized |

| Удаление | O(log n) | O(1) amortized |

| Порядок | Отсортирован | Не определён |

| Память | Больше (дерево) | Меньше (хеш-таблица) |

▸Кастомный хеш

cpp

1struct Point {
2    int x, y;
3};
4
5struct PointHash {
6    size_t operator()(const Point& p) const {
7        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 16);
8    }
9};
10
11struct PointEqual {
12    bool operator()(const Point& a, const Point& b) const {
13        return a.x == b.x && a.y == b.y;
14    }
15};
16
17std::unordered_set<Point, PointHash, PointEqual> points;
18points.insert({1, 2});
19points.insert({3, 4});

Выбор контейнера

vector — последовательный доступ, частый доступ по индексу

map — когда нужен отсортированный порядок

unordered_map — максимальная скорость поиска

set — уникальные элементы в отсортированном порядке

deque — частые вставки/удаления в начале и конце

Заключение

#c++#stl#vector#map#unordered-map#контейнеры

🛠

Попробуйте наш инструмент

Закрепите знания с помощью интерактивных упражнений

Перейти →

STL контейнеры: vector, map, unordered_map

std::vector

▸Создание и базовые операции

▸Временная сложность vector

▸Эмпирическое правило

std::map

▸Создание и использование

▸Кастомный компаратор

std::unordered_map

▸Сравнение с map

▸Кастомный хеш

Выбор контейнера

Заключение

Попробуйте наш инструмент

Похожие статьи

React: полное руководство для собеседования

JavaScript: глубокий анализ для собеседования

Node.js и backend: что спрашивают на собеседовании

DevOps: от основ до продвинутого уровня

STL контейнеры: vector, map, unordered_map

std::vector

▸Создание и базовые операции

▸Временная сложность vector

▸Эмпирическое правило

std::map

▸Создание и использование

▸Кастомный компаратор

std::unordered_map

▸Сравнение с map

▸Кастомный хеш

Выбор контейнера

Заключение

Попробуйте наш инструмент

Похожие статьи

React: полное руководство для собеседования

JavaScript: глубокий анализ для собеседования

Node.js и backend: что спрашивают на собеседовании

DevOps: от основ до продвинутого уровня