CODEWITHSUNDEEP
c++oopstlc++17incomplete-type
Tomilov Anatoliy
Tomilov Anatoliy

Reputation: 16741

STL way to represent data structures that implies cross-referencing

Often I faced the following situation. (Without loss of generality: I use for the following example a simpliest possible case of two containers, but in an implementations of geometrical algorithms there are a plenty of them needed to describe an interconnected graphs data structures.)

I have a plenty values of two data types A and B which references to each other (not one-to-one generally), say, at first by means of (native) pointers or references. Both of them are emplaced into containers using CA = std::container1< A >; and using CB = std::container2< B >;. A result of some function is a pair of CA and CB instances. Having an element of CA instance I want to remove referenced element in CB instance and vice versa.

struct A;
struct B;

using CA = std::container1< A >;
using CB = std::container2< B >;

I want to define A and B as following:

struct A
{
    int payload;
    typename CB::iterator pb; // hard error here in general case of choosing `std:container2`
};

struct B
{
    double payload;
    typename CA::iterator pa;
};

// ...
PA a;
PB b;
// ...
assert(!a.empty());
assert(a.begin()->pb != b.end()); // and pb is not default-constructed
b.erase(a.begin()->pb);

Live example.

But currently I can't declare typename CB::iterator pb; in general case, just only B /*const*/ * pb; or B /*const*/ & pb;, because type B, which is the part of CB declaration, is incomplete at point of using member typedef iterator of container CB into definition of aggregate A.

There is a proposal of a containers of an incomplete types, but it is not currently a part of the Standard.

For the current implementation of non-debug versions of containers in libstdc++ and libc++ the code above may be compiled fine by chance, but it is not mandatory at all. In case of success a definitions of iterators does not contain anything except pointers or references to the value_type for sure. But there is no requirement for that in the Standard.

As you can see in live example there is hard error for std::unordered_set, due to its iterator requires std::hash of value_type to be complete type.

Double indirection proposed into comments may be not to good solution due to architecture (OOP) and performance reasons. At least it looks ugly to define std::container3< B * > along with std::container2< B > and track the validity of a resulting zoo of a different cross-referenced containers.

Iterators have pointer semantics by nature. And they shouldn't demand completeness of referenced type.

How to deal with the problem in C++14 and previous?

Upvotes: 4

Views: 327

Answers (3)

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275936

An insane solution would be to store aligned storage and manually manage the object lifetime of the iterator, static asserting you made the storage the right size.

It is a real pain and quite unsafe (easy to make mistakes), but it works.

Use the size/alignment of boring container iterators. Access iterator using free function via adl.

std tends to over require fully defined types.

A careful use of crtp and tags might let you automate the dangerous code, but tricky.

Upvotes: 1

Mircea Baja
Mircea Baja

Reputation: 473

In your live example, fundamentally what you have is: an int and a double with a 1:1 relationship, the ints are stored in a vector<int> and the doubles in a unordered_set<double>.

One path could be to simplify the problem e.g. would you be able to put data into an unordered_map<double, int>? Sometimes that might be true and will solve a lot of effort. Sometimes that might not be true e.g. you might need to sort data by the ints.

I think the path of using std 2 containers is riddled with difficulties of which your compilation error is just the tip of the iceberg e.g.:

  • for a 1:1 relationship, when you add an entry you need to insert into two containers, so maybe you need to handle the case when you insert into one, but the other fails
  • the iterators might get invalidated (e.g. if you have a iterator to a vector element and you sort the vector)
  • the values in [unordered_]sets (and the [unordered_]keys in maps) are const (so you can't change them after you added them)

The other path could be: consider using something like boost bimap or multi_index. They take advantage of the fact that if say you want two node based structures (e.g. two sets) with a 1:1 relationship, then for an insert it only needs to make one allocation containing both nodes

Upvotes: -1

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 123431

I tried your second example with vector, list, deque, set and unordered_set. Only for unordered_set I got a compiler error that I could fix by using container of pointers:

 using CA = std::unordered_set< A* >;
 using CB = std::unordered_set< B* >;

See here (Ideone.com C++14).

Upvotes: 2

Related Questions