Without any (manual) heap allocation[1]:
struct NodeInfo {
int id;
};
using Tree = boost::make_recursive_variant<
NodeInfo,
std::vector<boost::recursive_variant_>
>::type;
I know variants come with their own "complexity", but memory locality is preserved and manual memory management avoided.
Now to get closer to your stated optimization goals, you could use std::array<T, 8>
instead of the std::vector
, or perhaps just make the vector
use a custom allocator
to allocate from a memory pool.
Sample program (see it Live on Coliru):
#include <iostream>
#include <boost/variant.hpp>
#include <vector>
struct NodeInfo {
int id;
};
using Tree = boost::make_recursive_variant<
NodeInfo,
std::vector<boost::recursive_variant_>
>::type;
// for nicer code:
using Branch = std::vector<Tree>;
using Leaf = NodeInfo;
static std::ostream& operator<<(std::ostream& os, Leaf const& ni) {
return os << ni.id;
}
static std::ostream& operator<<(std::ostream& os, Branch const& b) {
os << "{ ";
for (auto& child: b) os << child << " ";
return os << "}";
}
int main()
{
Branch branch1 {
Leaf { 2 },
Leaf { 1 },
Branch {
Leaf { 42 },
Leaf { -42 },
}
};
Tree tree = Branch { branch1, Leaf { 0 }, branch1 };
std::cout << tree << "\n";
}
Prints:
{ { 2 1 { 42 -42 } } 0 { 2 1 { 42 -42 } } }
[1] (outside the use of std::vector)