Сколько требуется памяти для хранения map?

Сколько требуется памяти для хранения map?

Ответ зависит от типа map и структуры данных. Давайте разберёмся подробно:

std::map (Red-Black Tree)

Структура узла:

struct Node {
    KeyType key;          // Размер ключа
    ValueType value;      // Размер значения
    Node* left;           // Указатель (8 байт на 64-bit)
    Node* right;          // Указатель (8 байт)
    Node* parent;         // Указатель (8 байт)
    bool is_red;          // Цвет для Red-Black дерева (1 байт)
    // padding: 7 байт (для alignment)
};

Память на один элемент:

• 8 байт (left pointer)
• 8 байт (right pointer)
• 8 байт (parent pointer)
• 1 байт (color)
• 7 байт (padding)
• sizeof(KeyType) + sizeof(ValueType)

Итого: 32 + sizeof(Key) + sizeof(Value) байт на элемент

Пример:

std::map<int, std::string> m; // int=4, std::string~56 (с SSO)
// Per element: 32 + 4 + 56 = 92 байта
// Для 1,000,000 элементов: ~92 MB

std::unordered_map (Hash Table)

Структура:

┌─────────────────────┐
│  Bucket array       │  (buckets.size() * 8 байт)
│  [ptr] [ptr] [ptr]  │
└─────────────────────┘
       ↓      ↓      ↓
    [Node]→[Node]→[Node]  (chaining for collisions)

Память:

• Bucket array: bucket_count * 8 байт
• Узлы: size * (32 + sizeof(Key) + sizeof(Value))
• Load factor обычно ~0.75 → buckets ≈ size / 0.75

Итого: ~10.7 * sizeof(Key) + sizeof(Value) + 32 байта на элемент

std::unordered_map<int, std::string> m;
// Per element: ~10.7 * 4 + 56 + 32 = ~130 байт
// Для 1,000,000 элементов: ~130 MB

std::flat_map (C++23)

Структура:

struct FlatMap {
    std::vector<KeyType> keys;      // Отсортированные ключи
    std::vector<ValueType> values;  // Соответствующие значения
};

Память:

• Keys: size * sizeof(Key) + vector overhead (~24 байта)
• Values: size * sizeof(Value) + vector overhead (~24 байта)
• Capacity обычно ~1.5x size для избежания реаллокаций

Итого: ~1.5 * (sizeof(Key) + sizeof(Value)) + 48 байт на элемент

std::map<int, std::string> m;
// Per element: 1.5 * (4 + 56) + 48 = ~138 байт
// Но лучше cache locality!

Сравнение памяти

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

Случай 1: map<uint32_t, uint64_t>

std::map<uint32_t, uint64_t> m;
// Per element: 32 + 4 + 8 = 44 байта
// 1M элементов: 44 MB

Случай 2: map<string, vector<int>>

std::map<std::string, std::vector<int>> m;
// Key: ~56 байт (с SSO)
// Value: ~24 + 1000*4 = ~4024 байта (для вектора из 1000 int)
// Per element: 32 + 56 + 4024 = ~4112 байт
// 1000 элементов: ~4 MB

Оптимизация памяти

1. Используй меньшие типы:

std::map<uint16_t, uint8_t> m;  // Намного компактнее

2. Выбери правильный контейнер:

// Если нужен частый поиск — unordered_map
std::unordered_map<int, int> fast_lookup;

// Если нужен порядок — map
std::map<int, int> ordered;

// Если нет вставок/удалений — flat_map
std::vector<std::pair<int, int>> immutable;

3. Используй std::string_view для ключей:

std::map<std::string_view, int> m;  // Избегает копирования

4. Reserve для unordered_map:

std::unordered_map<int, int> m;
m.reserve(1000000);  // Избегает реаллокаций

Эмпирическое измерение

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> m;
    
    auto before = m.capacity();  // 0
    
    m[1] = "test";
    m[2] = "hello";
    m[3] = "world";
    
    // sizeof(m) даст размер самого контейнера (~48 байт)
    std::cout << "Container size: " << sizeof(m) << " bytes\n";
    std::cout << "Elements: " << m.size() << "\n";
    std::cout << "Per-element overhead: ~32 bytes (Red-Black tree)\n";
    
    return 0;
}

Практический совет

Для production backend систем:

• Small N (<1000): используй std::map — простой и понятный
• Large N (>100K): используй unordered_map или flat_map в зависимости от нужд
• Memory-critical: профилируй реальные данные, не гадай
• Cache-sensitive: используй flat_map для лучшей локальности

Память это деньги в облаке. Выбор контейнера может сэкономить 30-40% памяти в large-scale приложениях.