Data structure for tree (List-like, inverted-index-like, contiguous-like)
Dear C++ experts,
I have learned there are various data structures to realize tree data structure, such as List-like (each node has pointers to parent/children), inverted-index-like (like graph data structure), contiguous-like (in array like).
Probably, there are their pros and cons for Individual purposes.
(c.f. applicable algorithm, dynamic/static, memory efficiency etc)
If you know if there is some document about it,
I would appreciate it if you could tell me.
Kind regards
I have learned there are various data structures to realize tree data structure, such as List-like (each node has pointers to parent/children), inverted-index-like (like graph data structure), contiguous-like (in array like).
Probably, there are their pros and cons for Individual purposes.
(c.f. applicable algorithm, dynamic/static, memory efficiency etc)
If you know if there is some document about it,
I would appreciate it if you could tell me.
Kind regards
dynamic memory constructs risk constant page faults, which are often a notable performance hit. They are a pain to save and load, and a pain to iterate all nodes. You can mitigate page faults with a light hand rolled memory manager for it, but that is extra work.
shoveling them into vectors lets you iterate easier if you just want to touch all nodes, and its easier to save them, by saving the vector, with just a binary file write (and read() to fetch). It reduces the page fault issue (eliminated for small data). All the tree algorithms work fine on it; you really just swap the 'pointers' for 'array indexes' and its the same old same old.
The biggest impact of vectorized is deletion -- you need a way to reclaim unused cells in your vector, often an extra 'i am deleted' bool flag in your data object.
graphs can be done many ways. Depending on what you need, one of the schemes could be useful, but IMHO a tree belongs in a vector more than 99% of the time.
shoveling them into vectors lets you iterate easier if you just want to touch all nodes, and its easier to save them, by saving the vector, with just a binary file write (and read() to fetch). It reduces the page fault issue (eliminated for small data). All the tree algorithms work fine on it; you really just swap the 'pointers' for 'array indexes' and its the same old same old.
The biggest impact of vectorized is deletion -- you need a way to reclaim unused cells in your vector, often an extra 'i am deleted' bool flag in your data object.
graphs can be done many ways. Depending on what you need, one of the schemes could be useful, but IMHO a tree belongs in a vector more than 99% of the time.
Last edited on
Topic archived. No new replies allowed.