Re: [boost] [containers] Clarifications on incomplete type support?

Subject: Re: [boost] [containers] Clarifications on incomplete type support?
From: Mikael Persson (mikael.s.persson_at_[hidden])
Date: 2014-09-22 13:34:32

Thanks for the reply.

> I didn't have that need in the past, I used containers of incomplete to
define recursive containers or like PIMPL-like idiom.

My intended application is part of a complete re-write of the
adjacency_list class template of the Boost.Graph library, and especially,
it's new little cousin, a linked-tree implementation (which are both
working wonderfully on version 1.54). Using the guarantees on incomplete
types from Boost.Container, it allows for a great number of simplifications
(less indirections) under the hood, unlike the existing adjacency_list
implementation which relies on STL containers and is forced to make many
contortions (including void* style type-erasure) to avoid instantiating
containers of incomplete types.

What my problem basically boils down to is being able to have a recursive
data structure with "back-pointers" (as iterators). Like this:

struct vertex;

struct edge {
  T value;
  containerA<vertex>::iterator target_vertex;
}

struct vertex {
  T value;
  containerB<edge> out_edges;
  containerB<edge>::iterator in_edge;
}

I hope you can see how crucial it is to have this support, and how it is an
integral part of supporting recursive data structures (where such
"back-pointers" are very commonly needed or used). Without incomplete type
support for iterators, the options to solve this problem are:

1. assume that "container<int>::iterator" has the same layout as any
"container<T>::iterator" and simply do reinterpret-casts on the iterators,
which is obvious dirty and unsafe, but works in practice.
2. do "container<T*>", which fundamentally changes the nature of the
container and the performance characteristics.
3. dynamically allocate the iterators and cast them to void* or using a
similar type-erasure technique.

All three of these tricks are used at one point or another in the current
BGL adjacency_list implementation, and I consider all of them to be
unacceptable (too much indirection, sacrificing performance, and a general
violation of the end-user's choice of container options (if you choose a
vector storage, you don't expect it will be a vector of pointers!! That
makes a huge difference!)). With incomplete type support for iterators,
none of these tricks are needed, and a much leaner implementation can be
achieved.

Thanks,
Mikael.