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

Boost tree has a constructor that takes a user-provided allocator object: https://www.boost.org/doc/libs/1_70_0/libs/geometry/doc/html/geometry/reference/spatial_indexes/boost__geometry__index__rtree/rtree_parameters_type_const____indexable_getter_const____value_equal_const____allocator_type_const___.html — Ilya Popov, Aug 06 '19 at 08:09

Jeff Garrett · Accepted Answer · 2019-08-06T19:25:15.223

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.

Yeah, the circular dependency was/is the issue. I attempted to workaround it with tricks like [here](https://stackoverflow.com/questions/47462707/static-class-template-member-invalid-application-of-sizeof-to-incomplete-type) and forward declarations to no avail. Using `short_alloc` and the constructor I had previously missed lead to a working solution! This is probably better anyway since `short_alloc` is conformant, whereas `stack_alloc` is not ([1](https://stackoverflow.com/questions/11648202/questions-about-hinnants-stack-allocator/11652436#11652436)). Thanks! — Alexander Karatarakis, Aug 08 '19 at 01:03

Hinnant's stack allocator with boost rtrees: compilation failure

1 Answers1