В чем разница между std::map и std::vector?

Разница между std::map и std::vector

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

Структурные различия

std::vector:

std::vector<int> vec = {1, 2, 3, 4, 5};
// Структура: связный массив в памяти
// [1] [2] [3] [4] [5] <- все рядом (cache-friendly)

std::map:

std::map<std::string, int> dict;  // {ключ: значение}
dict["apple"] = 5;
dict["banana"] = 3;
// Структура: красно-чёрное дерево
//       [apple]
//      /        \
//  [banana]   [cherry]

1. Сложность операций

Vector:

std::vector<int> vec;

vec.push_back(10);           // O(1) амортизировано
vec.pop_back();              // O(1)
vec.insert(vec.begin(), 5);  // O(n) - ДОРОГО!
vec.erase(vec.begin());      // O(n) - ДОРОГО!
vec[2] = 100;                // O(1) - случайный доступ

// Поиск элемента
auto it = std::find(vec.begin(), vec.end(), 10);  // O(n)

Map:

std::map<std::string, int> map;

map["key"] = 10;             // O(log n)
map.insert({"key", 10});     // O(log n)
map.erase("key");            // O(log n)
int val = map["key"];        // O(log n)
auto it = map.find("key");   // O(log n)
map.count("key");            // O(log n)

Таблица сложности:

2. Использование памяти

Vector:

std::vector<int> vec;
vec.reserve(1000);  // Выделяет память на 1000 элементов

// Использует: 1000 * sizeof(int) = 4000 байт
// Никакого overhead на структуру данных

Map:

std::map<int, std::string> dict;
dict[1] = "hello";
dict[2] = "world";

// На каждый элемент: узел дерева (ключ, значение, 3 указателя, цвет)
// Overhead: ~48 байт на элемент (даже для простых типов)
// Для 1000 элементов: ~48000 байт extra overhead

Вывод: vector экономнее по памяти, map требует больше памяти но имеет логику.

3. Cache-friendliness

Vector (отлично):

std::vector<int> vec(1000000);

// Элементы идут подряд в памяти
// CPU cache hits: почти 100%
// Линейный обход - молниеносно

for (int x : vec) {
    process(x);  // Cache miss почти не бывает
}

Map (плохо):

std::map<int, int> map;
for (int i = 0; i < 1000000; i++) {
    map[i] = i;
}

// Элементы разбросаны по памяти (дерево)
// CPU cache misses: частые
// Обход медленнее, чем у vector

for (auto& [key, val] : map) {
    process(val);  // Cache misses часто
}

Бенчмарк линейного обхода 1М элементов:

vector: 10ms
map:    100ms  ← в 10x медленнее!

4. Практические примеры

Когда использовать Vector:

// 1. Последовательность данных
std::vector<int> scores = {10, 20, 30, 40};

// 2. Когда нужна производительность
std::vector<Point> vertices = loadMesh();
for (auto& p : vertices) renderPoint(p);  // Fast!

// 3. Динамический массив с добавлением в конец
std::vector<Event> log;
while (true) {
    log.push_back(getNextEvent());  // O(1)
}

// 4. Когда нужен случайный доступ
for (int i = 0; i < vec.size(); i++) {
    vec[i] = i;  // O(1)
}

Когда использовать Map:

// 1. Словарь: быстрый поиск по ключу
std::map<std::string, int> userScores;
userScores["Alice"] = 100;
int aliceScore = userScores["Alice"];  // O(log n)

// 2. Конфигурационные данные
std::map<std::string, std::string> config;
config["database_host"] = "localhost";
config["database_port"] = "5432";

// 3. Индексирование by ID
std::map<int, User> usersById;
for (const auto& user : loadUsers()) {
    usersById[user.id] = user;
}
User user = usersById[123];  // O(log n)

// 4. Подсчет частот
std::map<char, int> frequency;
for (char c : "hello world") {
    frequency[c]++;
}

// 5. Отсортированное хранилище
std::map<int, std::string> orderedData;  // Автоматически отсортирован по ключу
for (const auto& [key, val] : orderedData) {
    std::cout << key << ": " << val << "\n";  // Гарантирован порядок
}

5. Iterator invalidation

Vector:

std::vector<int> vec = {1, 2, 3};
auto it = vec.begin();

vec.push_back(4);  // Может инвалидировать ALL итераторы!
vec.erase(it);     // Инвалидирует итераторы от it и дальше

// Опасно в многопоточности

Map:

std::map<int, int> map;
auto it = map.find(1);

map[2] = 20;      // НЕ инвалидирует итератор it!
map.erase(it);    // Инвалидирует только удаляемый элемент

// Безопаснее для многопоточности

6. Альтернативы

unordered_map (хеш-таблица):

std::unordered_map<std::string, int> dict;
dict["apple"] = 5;
dict["banana"] = 3;

// Средняя сложность: O(1)
// Худшая сложность: O(n) - при коллизиях хеша
// НЕ отсортирован

// Vs map:
// - unordered_map быстрее в среднем
// - map медленнее но гарантирует O(log n)
// - map отсортирован

7. Как выбрать

Алгоритм выбора:

1. Нужен быстрый поиск по ключу?
   ДА → unordered_map (если НЕ нужна сортировка)
   ДА → map (если нужна сортировка или O(log n) гарантия)
   НЕТ → vector

2. Нужна сортировка ключей?
   ДА → map
   НЕТ → unordered_map или vector

3. Производительность критична?
   ДА → vector (cache-friendly)
   НЕТ → map или unordered_map

4. Нужна безопасность итераторов?
   ДА → map
   НЕТ → vector

Best Practices

✓ Правила:

• Vector по умолчанию - это самый быстрый и экономный контейнер
• Map для словарей - быстрый поиск по строковому ключу
• unordered_map для спида - если не нужна сортировка
• Профилируй - не угадывай, измеряй!
• Избегай resize vector в цикле - используй reserve()
• Предпочитай emplace вместо insert - меньше копирований

Заключение

Vector и map решают разные задачи:

• Vector = быстрый, экономный, cache-friendly массив
• Map = логическая структура для быстрого поиска по ключу

Выбор зависит от:

1. Нужен ли быстрый поиск (O(log n) vs O(n))
2. Нужна ли сортировка
3. Критична ли производительность
4. Как часто будут вставки/удаления

Для большинства случаев - начни с vector, перейди на map только если нужен поиск!