tree implementation in buffer of fixed size
Which open source implementations of a tree (with arbitrary number of children per node; nodes containing a small data type l开发者_运维知识库ike int or a pointer (additional to the implementation-specific indexing data, of course)) in a (linear) buffer do exist? (Obviously, the maximum number of tree nodes is bounded by the buffer size)
(Graph instead of tree would also be okay).
You can take any implementation of a tree that allows a stateful allocator, and implement a custom allocator on top of your fixed size buffer.
Though the C++ standard doesn't guarantee support for stateful allocators, they work "with most STL implementations most of the time". Allocator state is usually only a problem when moving nodes between containers.
If you can live with one instance, the buffer can also be a template parameter.
精彩评论