Hinnant's stack allocator with boost rtrees: compilation failure

Question

I am trying to use Howard Hinnant's stack_alloc with boost rtrees, as in the following example:

#include "stack_alloc.h"
#include <boost/geometry/index/rtree.hpp>

using NodePoint = boost::geometry::model::point<double, 2, boost::geometry::cs::cartesian>;
using Linear = boost::geometry::index::linear<8, 2>;
using RTree =
    boost::geometry::index::rtree<NodePoint, Linear, boost::geometry::index::indexable<NodePoint>,
                                  boost::geometry::index::equal_to<NodePoint>,
                                  stack_alloc<NodePoint, 100>>;

int main()
{
    RTree my_tree{};

    return 0;
}

This fails to compile with a fairly sizeable template error stack. I think the heart of the issue is:

/usr/local/include/boost/geometry/index/detail/rtree/node/variant_static.hpp:26:7: error: invalid use of incomplete type 'class boost::geometry::index::detail::rtree::allocators, 100>, boost::geometry::model::point, boost::geometry::index::linear<8, 2>, boost::geometry::model::box >, boost::geometry::index::detail::rtree::node_variant_static_tag>'

Here is the full example on coliru with the full error.

What is wrong here?

I tried using stack_alloc with various boost collections, like boost::container::static_vector and boost::container::map and those worked fine. I also tried using another stack_allocator implementation from this SO reply and got the same error.

Furthermore, I am aware that there is an updated implementation from Howard Hinnant, namely short_alloc. I tried using it, but this implementation has no default ctor and requires us to provide the storage at construction time. Since boost takes the allocator as a template parameter and instantiates it internally, I could not find a way to make this work, but will happily use it if there is a way. Further info for stack_alloc and/vs short_alloc: 1, 2, 3

Answer 1

The heart of the issue is essentially a circular dependency.

Constructing the RTree causes the rtree<...> template instantiation which includes a typedef node_pointer = allocators_type::node_pointer, which triggers the instantiation of allocators_type, i.e. detail::rtree::allocators<...>, which has a base class of detail::rtree::node_alloc<...>, which in its definition rebinds the allocator to the node type. The node type is a variant of detail::rtree::variant_leaf<...> and detail::rtree::variant_internal_node<...>.

But stack_alloc needs the sizeof(T), so both templates included in the variant types get instantiated, and when instantiating variant_internal_node, it needs Allocators::node_pointer, so Allocators must be instantiated, but isn't that what we're in the middle of instantiating!

I suggest trying short_alloc and passing the allocator to the container. Because it separates the storage from the allocator type, it should not require completeness of the template type, breaking the circle.