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

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

https://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0#%D0%9E%D1%82%D0%BA%D1%80%D1%8B%D1%82%D0%B0%D1%8F_%D0%B0%D0%B4%D1%80%D0%B5%D1%81%D0%B0%D1%86%D0%B8%D1%8F

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

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

https://learnc.info/adt/hashmap_open_addressing.html

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

У меня есть просто дерево. Без всяких ключей. То есть просто корневая нода, у нее дети и так рекурсивно. Ноды создает корень в любом случае, но при создании ноды указывается id родителя ноды. И создание ноды возвращает этот самый id. Вот по этому id и нужен О(1) доступ. Все делается через корень.

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

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

H>У меня есть просто дерево. Без всяких ключей. То есть просто корневая нода, у нее дети и так рекурсивно. Ноды создает корень в любом случае, но при создании ноды указывается id родителя ноды.

Почему ид а не указатель?

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

TB>Почему ид а не указатель?

Потому что внутри нод есть некие пути к неким параметрам внутри других нод. И эти пути задаются именно через последовательность id-шников и так и сохраняются в файлы и загружаются из файлов. Сохранять в файл значение указателя, сам понимаешь, такое себе

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

H>Потому что внутри нод есть некие пути к неким параметрам внутри других нод. И эти пути задаются именно через последовательность id-шников

Не помню такой способ хранению путей, кроме как префиксные деревья. А эта последовательность — это именно последовательность вложенных нод? Тогда достаточно LRLRLRRRRLLRLR, если дерево бинарное ну или другого компактного способа, если хранить только внутренний индекс потомка

H>Сохранять в файл значение указателя, сам понимаешь, такое себе

На самом деле так тоже можно, но для этого тебе придётся решить задачу эквивалентную дефрагментации

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

H>У меня есть просто дерево. Без всяких ключей. То есть просто корневая нода, у нее дети и так рекурсивно. Ноды создает корень в любом случае, но при создании ноды указывается id родителя ноды. И создание ноды возвращает этот самый id. Вот по этому id и нужен О(1) доступ. Все делается через корень.

OK. Допустим, у тебя есть O(1) по этому самому ID. Зачем тебе еще и дерево? Вернее, если за какой-то надобностью ноды у тебя логически объединены в дерево, устроит ли тебя, что ссылаться друг на друга они будут не по прямому указателю, а по ID?

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

Да, id в рамках сессии однозначно идентифицирует ноды. И они активно друг на друга ссылаются именно по id. И эти же id сериализуются и отдаются наружу пользователю.

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

H>Да, id в рамках сессии однозначно идентифицирует ноды. И они активно друг на друга ссылаются именно по id. И эти же id сериализуются и отдаются наружу пользователю.

Еще два вопроса:
1) ID выделяются последовательно?
2) Надо ли их удалять?

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

Pzz>Еще два вопроса:
Pzz>1) ID выделяются последовательно?

Неважно. Наверное, при создании — удобно последовательно , но если в предшествующих номерах после удаленных остались дыры, то можно их занимать. То есть родитель может быть с Id=9, а внутри него ребенок может быть вполне с id = 4. Это неважно. Главное — уникальность и однозначность в поиске

Pzz>2) Надо ли их удалять?

Да. Причем с удалением всех детей ноды, разумеется

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

M>...

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

M>ЗЫ А в эмбеде обычно нет вообще никакого кеша.
Ну смотря что вы понимаете под эмбеддед. Для меня всякие малинки, броадкомы, телеприставки и т.п. — это эмбеддед, хотя может я слишком широко беру.

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

Pzz>>Еще два вопроса:
Pzz>>1) ID выделяются последовательно?

H>Неважно. Наверное, при создании — удобно последовательно , но если в предшествующих номерах после удаленных остались дыры, то можно их занимать. То есть родитель может быть с Id=9, а внутри него ребенок может быть вполне с id = 4. Это неважно. Главное — уникальность и однозначность в поиске

Ну, как вариант, можно хранить массив (вектор), в котором ID — это индекс, а значение — указатель на ноду. Расширять его по мере надобности и переиспользовать дырки по мере возможности.

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

В принципе, эта структура напоминает FAT из MS-DOS, примерно так организованы списки свободных/занятых блоков.

Потери твои — если ты навыделял много нор, а потом много освободил, то их позиции в индексном массиве остаются в оперативной памяти до тех пор, пока опять не понадобятся. Но я б на эту тему особо не переживал. Всё равно сишное освобождение памяти (free/delete) довольно маловероятно, что вернёт память системе, скорее, оставит её, как свободную область в куче.

Pzz>>2) Надо ли их удалять?

H>Да. Причем с удалением всех детей ноды, разумеется

Еще один вариант — использовать структуру, напоминающую page directory у x86. Кажется, это называется radix tree. Такая штука работает хорошо, когда у тебя ID в принципе ложатся кучно, но возможно, что с дырками между кучками. И плохо работает, когда они случайно распределены.

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

Ну BlackEric выше по сути и привел это решение

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

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

Ничего кривого я тут не вижу.

1. Есть некая структура из элементов (пусть дерево, а впрочем, любая) организованная на каком-то принципе, не привязанном к ID.

2. Есть необходимость доступа по ID, причем O(1)

3. Делаем массив, где ID — индекс, а элемент — указатель на элемент из (1). При удалении элемента заносим туда null. Вот и все.

Вот пример аналогичного класса, внутри которого 2 структуры

https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html

Внутри hashmap для доступа по ключу и linkedlist — список по порядку добавления.

This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).

Не совсем то, конечно, но очень похоже. Вместо "insrtion order" тебе нужен "ID order", ну а коль нужен O(1) — массив, а не список.

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

Криво то, что и удаление и создание нод идет по сути через два контейнера. Нельзя например просто грохнуть ноду и он автоматически грохнет детей. Надо id и самой ноды и ее детей рекурсивно вычищать из другого контейнера.

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

H>Криво то, что и удаление и создание нод идет по сути через два контейнера. Нельзя например просто грохнуть ноду и он автоматически грохнет детей. Надо id и самой ноды и ее детей рекурсивно вычищать из другого контейнера.

Если метод удаления ноды (самой) вызывает себя для детей, то достаточно при удалении ноды ставить в массив null. При удалении детей он сделает то же самое для детей

Примерно так.

void deleteNode (Node node) {
foreach(child in node) {
deleteNode(child);
}
array[node.id] = null;
// удаление самой ноды
}

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

H>Ну BlackEric выше по сути и привел это решение

Угу. А я объяснил, откуда оно берётся.

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

M>>ЗЫ А в эмбеде обычно нет вообще никакого кеша.
SaZ>Ну смотря что вы понимаете под эмбеддед. Для меня всякие малинки, броадкомы, телеприставки и т.п. — это эмбеддед, хотя может я слишком широко беру.

Ну это такой себе эмбед, там обычно вполне полноценная ОС. Обычно же эмбед — это микроконтроллер, ОС там нет или что-то типа FreeRTOS, и тайминги там критические

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

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

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

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

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

Проще пареной репы.

using TreeNode = int;
static constexpr TreeNode none = -1;

struct TreeItem
{
  TreeNode parent;
  TreeNode next;
  TreeNode child;
};

std::vector<TreeItem> treeItems;
TreeNode deletedItems = none;

Вместо указателей — индексы. Индексы знаковые, невалидное значение — отрицательное. Помимо none можно использовать спецзначения в отрицательном диапазоне.
При удалении элементов ссылка устанавливается в none. Удалённые элементы остаются в массиве, но включаются в список deletedItems, для переиспользования.

Работает с сотнями МБ данных.