|
Boost : |
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk