3 ms·

You could use id/vec indices, instead of directly pointing to your e.g. sucessors: "struct Node { successors: Vec<usize> }". This has the obvious disadvantage t

You could use id/vec indices, instead of directly pointing to your e.g. sucessors: "struct Node { successors: Vec<usize> }". This has the obvious disadvantage that deleting nodes is quite hard though.

mtanski 10y ago
> This has the obvious disadvantage that deleting nodes is quite hard though It's hard because now you're in charge of building a malloc(3) implementation. Depending how important this data structure is you might need to worry about 1. about fragmentation 2. free space managment 3. adjacency and cache effects So you've traded on hard problem for another hard problem. Not something I'd call a win.
- pcwalton 10y ago
  Just use petgraph. It manages all of this for you.
  - dman 10y ago
    I work on databases and I ran into similar problems implementing index data structures. While I understand petgraph solves some/all of these problems completely - it would be great if the barrier to writing trees / graphs from scratch in Rust would be lower than it is currently.
    - mtanski 10y ago
      Same problem. Working on an OLAP database toolkit (tried to in Rust)... writing typical database data structures is excruciating painful in Rust. Trees, indexes (including bitmaps), buffer allocators and even just keeping state in streaming cursors (Volcano model). Are all pain in the ass in to implement. In fact implementing a Cursor trait for like 10 different Cursor (SrcView, Join, Project, Compute, ...) became painful because each cursor struct has it's own complex lifetime params and those lifetimes were trying to leak into the main Cursor trait. Right now I can't do that without resolving to runtime using RefCell. In my case the plans could be entirely materialized at compile time, so not really a win. The situation won't get better until there's some kind of abstraction over lifetimes (HKT?).
- readittwice 10y ago
  Sure, I wouldn't recommend that solution if you have to delete single nodes a lot. But it is quite convenient if you don't need to do that.

mtanski 10y ago

> This has the obvious disadvantage that deleting nodes is quite hard though It's hard because now you're in charge of building a malloc(3) implementation. Depending how important this data structure is you might need to worry about 1. about fragmentation 2. free space managment 3. adjacency and cache effects So you've traded on hard problem for another hard problem. Not something I'd call a win.

pcwalton 10y ago
Just use petgraph. It manages all of this for you.
- dman 10y ago
  I work on databases and I ran into similar problems implementing index data structures. While I understand petgraph solves some/all of these problems completely - it would be great if the barrier to writing trees / graphs from scratch in Rust would be lower than it is currently.
  - mtanski 10y ago
    Same problem. Working on an OLAP database toolkit (tried to in Rust)... writing typical database data structures is excruciating painful in Rust. Trees, indexes (including bitmaps), buffer allocators and even just keeping state in streaming cursors (Volcano model). Are all pain in the ass in to implement. In fact implementing a Cursor trait for like 10 different Cursor (SrcView, Join, Project, Compute, ...) became painful because each cursor struct has it's own complex lifetime params and those lifetimes were trying to leak into the main Cursor trait. Right now I can't do that without resolving to runtime using RefCell. In my case the plans could be entirely materialized at compile time, so not really a win. The situation won't get better until there's some kind of abstraction over lifetimes (HKT?).
readittwice 10y ago
Sure, I wouldn't recommend that solution if you have to delete single nodes a lot. But it is quite convenient if you don't need to do that.