Можно ли организовать хранение древовидной структуры, чтобы все узлы плоско

Question

Можно ли организовать хранение древовидной структуры, чтобы все узлы плоско

хранились в векторе и у каждого был номер, но у каждого узла мог быть набор ссылок на потомков? Узлы только добавляются, не удаляются. То есть примерно
struct Node {
/*some payload*/
children: Vec<&??? Node>
}

struct Tree {
nodes: Vec<Node>
}

impl Tree {
fn size(&self) -> usize {self.nodes.len()}
fn get(&self, i: usize) -> &Node {&self.nodes[i]}
fn add_root(&mut self, node: Node) {self.nodes.push(node)}
fn add_child(&mut self, parent: usize, node: Node) {
self.nodes.push(node);
self.nodes[parent].children.push(nodes.last().unwrap())
}

#backend #embedded #programming #russian #rust

0

09.05.2021

3 ответов

9 просмотров

Эрик

Если узлы никогда не удаляются, то тут и обычная арена подойдёт: https://docs.rs/typed-arena/2.0.1/typed_arena/ Сорцы у этой либы достаточно простые, если хочешь посмотреть как оно сделано, ансейфа там минимум.

0

09.05.2021

Юльвёнок Чувствительная Автор вопроса

Эрик
Если узлы никогда не удаляются, то тут и обычная а...

Спасибо

0

09.05.2021

Денис · Accepted Answer

Денис

обычно в таких случаях хорошо подходит slab, и вместо ссылок хранятся идентификаторы

0

09.05.2021

172 похожих чатов

Можно ли организовать хранение древовидной структуры, чтобы все узлы плоско

3 ответов

Похожие вопросы