Template map

Контейнер map<> это гибрид hash-table + bidirectional linked list. 

Ключами могут быть любые простые скалярные типы для которых определена специализация вычислителя хеша UniversalHashKey<>. Как правило это текстовые строки, key, type<> или широко разбросанные целые числа.

Все ключи уникальны в рамках одного map<>.

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

Как array. Иногда может применяться вместе с array как индекс для ускорения выборки. Всегда private. При передаче через return и параметры происходит присваивание с полным медленным копированием содержимого. Обойти это нельзя, как и с array, специально чтобы отбить желание делать неинкапсулированные хаки.

Применяется для осмысленной оптимизации при практически наблюдаемой по факту неэффективности поиска в array<> перебором его элементов.

Нужно понимать, что существенные накладные расходы на поддержания списков и хеш таблиц для маленького количества элементов будут только хуже чем применение array и Find.

Перед применением для оптимизации изучить реализацию хеш таблицы, ее эффективного предаллокирования и учесть расходы времени на поддержание списков по сравнению с тривиальным array<>. Проверить профайлером быстродействие на правките и для больших объемов данных сверить изменения в расходе памяти по сравнению с разумно предаллокированным array.

Учесть возможные проблемы с итераторами если публикуется метод Iterate и есть возможность удаления ключей из мапа.

Небольшие маппинги из которых никогда ничего не удаляется (в т.ч. константные) могут быть полезны и безвредны там где быстродествие не нужно. Не забывать что map<> не экспозабелен автоматической экспозицией и для постоянного хранения более пригодны array и Udb.

    VALUE& operator [] (const KEY& key);
    map& operator << (const KEY& k);

Запись mapXxx[key] = value не может завершится отказом (пока достаточно памяти) ни при каком значении key (в отличие от array).

Запись mapXxx << key1 << key2 << ... оставляет все value в соответствующих null() значениях. Если map<> требуется только для хранения ключей, то для значений следует объявить тип unused (map<str, unused>)

    // Delete a mapping, return true if was found
    bool RemoveAtKey(
            const KEY& key);
 
    // Delete items, free hashtable, preserve reusable blocks
    void RemoveAll();
 
    // Remove only first or last mapped value
    void RemoveHead();
    void RemoveTail();

Удаление конфликтует с итераторами. Изучить Безопасный итератор для map и приватность POS указателей. Рекомендуется избегать map<> там где требуется и удаление элементов и публичные итераторы.

    // Size
    int GetCount()
            const;
 
    // Check key presence
    bool IsIn(
            const KEY& key)
            const;
 
    // Get value if mapped
    bool LookupExisting(
            const KEY& key,
            out VALUE& rValue)
            const;
 
    // With default return
    VALUE GetValueOr(
            const KEY& key,
            const VALUE& def)
            const;
 
    // nullable<> pointer support
    nullable<VALUE> LookupOrNull(
            const KEY& key)
            const;
 
    // Relative Lookup by Key
    VALUE GetValueNextToKeyOr(
            const KEY& key,
            const VALUE& def)
            const;
    VALUE GetValuePrevToKeyOr(
            const KEY& key,
            const VALUE& def)
            const;
    VALUE GetValueNextOrPrevToKeyOr(
            EMapNextPrev dir,
            const KEY& key,
            const VALUE& def)
            const;

Итерация всегда происходит гарантированно в последовательности добавления элементов. Это в отличие от hashmaps/dictionaries/etc в дефективных популярных системах, где порядок перебора "non-deterministic" и приложения традиционно сталкиваются с абсурдным, бугным-по-определению итератором по хешам.

    bool Iterate(
            out iter& out_i,
            out VALUE& out_value)
            const;
    bool IterateBackwards(
            out iter& out_i,
            out VALUE& out_value)
            const;
 
    bool IterateKeys(
            out iter& out_i,
            out KEY& out_key,
            out VALUE& out_value)
            const;
    bool IterateKeysBackwards(
            out iter& out_i,
            out KEY& out_key,
            out VALUE& out_value)
            const;

При удалении элементов итератор нужно прервать. Изучить Безопасный итератор для map и приватность POS указателей.

В новых проектах пока не требовалась. Старая опасная функция с POS закрыта. Возможна реализация на ее основе безопасной функции перемещающей элемент по ключу.

    // for values
    VALUE GetHeadValue()
            const;
    VALUE GetTailValue()
            const;
    VALUE GetHeadValueOr(
            const VALUE& def)
            const;
    VALUE GetTailValueOr(
            const VALUE& def)
            const;
 
    // for keys
    KEY GetHeadKey()
            const;
    KEY GetTailKey()
            const;
    KEY GetHeadKeyOr(
            const KEY& or_return_key)
            const;
    KEY GetTailKeyOr(
            const KEY& or_return_key)
            const;

    // Hash Table
    int GetHashTableSize()
            const;
    void RebuildHashTable(...);
 
    // Hash Statistics
    DMapHashStats GetHashStats()
            const;

Это замена автоматическому адаптивному механизму которая как правило не требуется.

Сначала изучить теорию. Потом реализацию. Хэш таблица классическая. При оптимизации размер задавать немного больший чем предполагаемое количество элементов, использовать prime number который ни на что не делится.

Я реализовал автоматическое адаптивное переаллокирование хеш таблицы при росте числа элементов. Оно происходит с упреждением, по тестам достаточно быстро так что на практике в ручную управлять динамическим переаллокированием пока не требовалось.

B-tree не поддерживается. Для этого есть Udb.

Только для частного случая:

    // Assuming KEY is str and the VALUE is ref<>
    void ExposeMapStrToRef(
            ref_arg<CExpose> rExpose,
            str sKey);

map<> сейчас может декларироваться только как не экспозабельный.

Ряд функций разрабатываются для эффективного превращения ключей и значений в форме array<>.

Эта категория в данный момент пуста.