У меня есть дерево. То есть нулевой узел с дочерними узлами и каждый дочерний содержит свои дочерние и так далее
При создании ноды пользователю отдается unsigned int ID. И вот по этому ID нужен доступ за константное время. Идеально было бы как-то отразить дерево в вектор и чтоб ID был номером элемента в векторе. Но как-то криво выходит. Две структуры для одного и того же. Криво.
Еще вариант, что ID — это собственно сам указатель, но не нравится он мне
Какие есть варианты?

Здравствуйте, Hоmunculus, Вы писали:

H>У меня есть дерево. То есть нулевой узел с дочерними узлами и каждый дочерний содержит свои дочерние и так далее
H>При создании ноды пользователю отдается unsigned int ID. И вот по этому ID нужен доступ за константное время. Идеально было бы как-то отразить дерево в вектор и чтоб ID был номером элемента в векторе. Но как-то криво выходит. Две структуры для одного и того же. Криво.
H>Еще вариант, что ID — это собственно сам указатель, но не нравится он мне
H>Какие есть варианты?

std::unordered_map?

Здравствуйте, Marty, Вы писали:

M>std::unordered_map?

ну там константа не всегда. Учитывая, что узлов, конечно, не миллионы, а меньше тысячи, то скорее всего более-менее решение, но вдруг что-то интереснее уже придумали.

Здравствуйте, Hоmunculus, Вы писали:

H>Здравствуйте, Marty, Вы писали:

M>>std::unordered_map?

H>ну там константа не всегда.

там есть метод reserve. Так что можно сказать, что всегда константа

Здравствуйте, sergii.p, Вы писали:

SP>Здравствуйте, Hоmunculus, Вы писали:

H>>Здравствуйте, Marty, Вы писали:

M>>>std::unordered_map?

H>>ну там константа не всегда.

SP>там есть метод reserve. Так что можно сказать, что всегда константа

Коллизии еще бывают

Здравствуйте, T4r4sB, Вы писали:

TB>Коллизии еще бывают

Сложность всё равно константная. Вряд ли у ТС подразумевалось именно константное время (не более XX микро/наносекунд), он, скорее всего, не совсем точно выразился

Здравствуйте, Marty, Вы писали:

M>Здравствуйте, T4r4sB, Вы писали:

TB>>Коллизии еще бывают

M>Сложность всё равно константная. Вряд ли у ТС подразумевалось именно константное время (не более XX микро/наносекунд), он, скорее всего, не совсем точно выразился

O(1) однозначно значит независимость от количества элементов. И если их станет миллиард, чтобы это не привело к просадкам. Разумеется, это не значит одно и то же количество миллисекунд на любой платформе

Здравствуйте, Hоmunculus, Вы писали:

TB>>>Коллизии еще бывают

M>>Сложность всё равно константная. Вряд ли у ТС подразумевалось именно константное время (не более XX микро/наносекунд), он, скорее всего, не совсем точно выразился

H>O(1) однозначно значит независимость от количества элементов. И если их станет миллиард, чтобы это не привело к просадкам. Разумеется, это не значит одно и то же количество миллисекунд на любой платформе

Именно это я и имел в виду. В хэш мапе, даже если есть коллизия это перебор нескольких элементов, и это всё равно O(1). Проблема может быть с рехэш при увеличении размера, но это можно решить, если это прям проблема.

Здравствуйте, Marty, Вы писали:

M>Сложность всё равно константная.

В среднем да, в худшем случае нет

Здравствуйте, T4r4sB, Вы писали:

M>>Сложность всё равно константная.

TB>В среднем да, в худшем случае нет

Скорее всего, ТСу нужна средняя сложность, вряд ли он делает систему жесткого реального времени. А резервирование/рехеширование можно делать по мере необходимости при вставке, или настроить max_load_factor, чтобы рехеши пореже происходили

Практические рекомендации

Всегда используйте reserve(), если знаете примерный размер

Оптимальный max_load_factor зависит от использования:

Для частых поисков: 0.7-0.8

Для экономии памяти: 1.0-1.5

Для минимизации рехеширования: 2.0-3.0

Профилируйте для нахождения оптимальных параметров

Рассмотрите альтернативные контейнеры, если рехеширование критично

Здравствуйте, Marty, Вы писали:

M>А резервирование/рехеширование можно делать по мере необходимости при вставке, или настроить max_load_factor, чтобы рехеши пореже происходили

Рехеши не помогут от коллизий

M>Скорее всего, ТСу нужна средняя сложность, вряд ли он делает систему жесткого реального времени.

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

Здравствуйте, T4r4sB, Вы писали:

M>>А резервирование/рехеширование можно делать по мере необходимости при вставке, или настроить max_load_factor, чтобы рехеши пореже происходили

TB>Рехеши не помогут от коллизий

При плохой хэш функции оно конечно может выродится в O(N), но на практике скорее будет O(1)/O(2)/O(3) или около того


M>>Скорее всего, ТСу нужна средняя сложность, вряд ли он делает систему жесткого реального времени.

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

Стандартного std::hash обычно хватает, чтобы коллизий было приемлемое количество

Здравствуйте, Hоmunculus, Вы писали:


Можно попробовать как-то так. Массив узлов + массив указателей.

struct Node {
    std::vector<size_t> children;
    // ... другие данные узла
};

class Tree {
private:
    std::vector<Node> nodes;           // Все узлы хранятся здесь
    std::vector<size_t> free_ids;      // Список свободных ID
    size_t next_id = 0;
    
public:
    // Создание узла возвращает ID
    size_t createNode() {
        size_t id;
        if (!free_ids.empty()) {
            id = free_ids.back();
            free_ids.pop_back();
        } else {
            id = next_id++;
            if (id >= nodes.size()) {
                nodes.resize(id + 1);
            }
        }
        return id;
    }
    
    // Доступ за O(1)
    Node& getNode(size_t id) {
        return nodes[id];
    }
    
    void deleteNode(size_t id) {
        // Очищаем узел
        nodes[id].children.clear();
        // Добавляем ID в список свободных
        free_ids.push_back(id);
    }

Здравствуйте, Marty, Вы писали:

M>Оптимальный max_load_factor зависит от использования:
M>...
M>Для экономии памяти: 1.0-1.5
M>Для минимизации рехеширования: 2.0-3.0

А вот тут я чёт не понял
Если мы экономим память, то адресация должна быть открытая, никаких нахрен связных списков, а тогда заполнение в принципе не может достигать 1.0

Здравствуйте, T4r4sB, Вы писали:

TB>А вот тут я чёт не понял
TB>Если мы экономим память, то адресация должна быть открытая, никаких нахрен связных списков, а тогда заполнение в принципе не может достигать 1.0

А вот тут я тебя не понял. Я не спец по устройству std::unordered_map, но, как я понимаю, чем меньше корзин, тем меньше требуется памяти, т.е., количество корзин влияет на размер занимаемой памяти больше, чем размер самих корзин.

Здравствуйте, Marty, Вы писали:

M>Здравствуйте, T4r4sB, Вы писали:

TB>>А вот тут я чёт не понял
TB>>Если мы экономим память, то адресация должна быть открытая, никаких нахрен связных списков, а тогда заполнение в принципе не может достигать 1.0

M>А вот тут я тебя не понял. Я не спец по устройству std::unordered_map, но, как я понимаю, чем меньше корзин, тем меньше требуется памяти, т.е., количество корзин влияет на размер занимаемой памяти больше, чем размер самих корзин.



Тут я вижу 2 случая
Элементы мапы имеют небольшой размер ну там это поды до 50 байт каждый
Тогда накладные расходы на хранение корзин, разбросанных по куче, настолько велики, что нет смысла говорить об экономии памяти, и открытая адресация с заполнением 90% выиграет по памяти
Если элементы мапы жирные то уже пофиг сколько корзин.
А еще в стдшной мапе все элементы живут в одном односвязном списке, а для корзин просто массив итераторов на начало блока с нужным хешем, то есть увеличивая процент заполнения ты просто эеономишь на длине этого массива указателей

Здравствуйте, T4r4sB, Вы писали:

TB>Тут я вижу 2 случая
TB>Элементы мапы имеют небольшой размер ну там это поды до 50 байт каждый
TB>Тогда накладные расходы на хранение корзин, разбросанных по куче, настолько велики, что нет смысла говорить об экономии памяти, и открытая адресация с заполнением 90% выиграет по памяти
TB>Если элементы мапы жирные то уже пофиг сколько корзин.
TB>А еще в стдшной мапе все элементы живут в одном односвязном списке, а для корзин просто массив итераторов на начало блока с нужным хешем, то есть увеличивая процент заполнения ты просто эеономишь на длине этого массива указателей

Я не очень понял, что такое "открытая адресация"?

Здравствуйте, Marty, Вы писали:

M>Здравствуйте, Hоmunculus, Вы писали:

H>>У меня есть дерево. То есть нулевой узел с дочерними узлами и каждый дочерний содержит свои дочерние и так далее
H>>При создании ноды пользователю отдается unsigned int ID. И вот по этому ID нужен доступ за константное время. Идеально было бы как-то отразить дерево в вектор и чтоб ID был номером элемента в векторе. Но как-то криво выходит. Две структуры для одного и того же. Криво.
H>>Еще вариант, что ID — это собственно сам указатель, но не нравится он мне
H>>Какие есть варианты?

M>std::unordered_map?

Без примерного понимания размера, реальных тестов и того, как мапа создаётся — не всегда. Во многих случаях, особенно на небольших наборах данных map / flat_map будет (внезапно) быстрее из-за особенностей работы кэша, даже при теоретической логарифмической сложности. Особенно на всяких embedded где нет L3 кэша.

Здравствуйте, SaZ, Вы писали:

M>>std::unordered_map?

SaZ>Без примерного понимания размера, реальных тестов и того, как мапа создаётся — не всегда. Во многих случаях, особенно на небольших наборах данных map / flat_map будет (внезапно) быстрее из-за особенностей работы кэша, даже при теоретической логарифмической сложности. Особенно на всяких embedded где нет L3 кэша.

Я в курсе, что иногда тупой перебор может работать быстрее. Но в вопросе ТС не было задано никаких ограничений.

ЗЫ А в эмбеде обычно нет вообще никакого кеша.

Здравствуйте, Hоmunculus, Вы писали:

H>У меня есть дерево. То есть нулевой узел с дочерними узлами и каждый дочерний содержит свои дочерние и так далее
H>При создании ноды пользователю отдается unsigned int ID. И вот по этому ID нужен доступ за константное время. Идеально было бы как-то отразить дерево в вектор и чтоб ID был номером элемента в векторе. Но как-то криво выходит. Две структуры для одного и того же. Криво.
H>Еще вариант, что ID — это собственно сам указатель, но не нравится он мне
H>Какие есть варианты?

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

Но если у тебя два ключа, и по обоим надо искать эффективно, то волей-неволей продётся строить две параллельные структуры, и поддерживать синхронность между ними (что само по себе неприятно).

Или же ты спрашиваешь, как организовать быстрый поиск по unsigned int?