STL表示数据结构的方式暗示交叉引用

Question

经常会遇到以下情况。（不失一般性：在下面的例子中，我使用最简单的两个容器情况，但在几何算法的实现中需要大量这样的容器来描述相互连接的图形数据结构。）

我有两种数据类型 A 和 B 的许多值相互引用（通常不是一对一的关系），例如通过（本机）指针或引用。它们都被放置在容器中，例如 using CA = std::container1< A >; 和 using CB = std::container2< B >;。某个函数的结果是一对 CA 和 CB 实例。当我有了一个 CA 实例的元素时，我想要删除 CB 实例中引用的元素，反之亦然。

struct A;
struct B;

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

我想定义A和B如下：

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);

点此查看实例

但是在一般情况下，我无法声明typename CB :: iterator pb;，只能声明B /*const*/ * pb;或B /*const*/ & pb;，因为类型B是CB声明的一部分，在使用容器CB的成员typedef iterator定义聚合体A时，该类型是不完整的。

有一个提案是使用不完整类型的容器，但它目前还不是标准的一部分。

对于libstdc++和libc++中非调试版本的容器的当前实现，上述代码可能会因为偶然性而编译成功，但这并不是必须的。如果成功，迭代器的定义肯定不包含除了指向value_type的指针或引用之外的任何内容。但是标准没有对此有要求。

正如您在实例中所看到的，对于std::unordered_set，存在严重错误，因为其迭代器要求value_type的std::hash是完整类型。

由于架构（OOP）和性能原因，注释中提出的双重间接可能不是很好的解决方案。至少定义std::container3< B * >以及std::container2< B >并跟踪不同交叉引用容器的有效性看起来很丑陋。

迭代器本质上具有指针语义。它们不应要求所引用的类型是完整的。

如何在C++14及之前解决这个问题？

- Tomilov Anatoliy

---

这是一个非常令人困惑的问题，难以理解。 - erip

@erip，为什么无法正确跟踪问题的源头？ - Tomilov Anatoliy

也许是因为我不知道 Voronoi 到底是什么，但我并没有看出问题在哪里？你的代码无法编译吗？ - erip

@Orient，我建议你删除问题的整个第一部分，然后按照你的“附加更新”所示创建一个可编译的示例，并显示编译器错误。具有相互引用（在面向对象编程意义上，而不是C++意义上）的容器的问题是一个有趣的问题。 - user3458

实际上你的第二个例子[可以在没有错误的情况下编译]（https://ideone.com/Roj21f） - 463035818_is_not_a_number

Answer 1

我尝试了您的第二个示例，使用了vector、list、deque、set和unordered_set。只有在使用unordered_set时，我遇到了编译错误，但通过使用指针容器可以解决该问题。

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

查看这里（Ideone.com C++14）。

- 463035818_is_not_a_number

---

我认为使用std::unique_ptr<A>而不是A*更好。 - user1887915

而且，在大多数情况下，需要提供Hash（第二个）和KeyEqual（第三个）模板参数才能使其正确。 - user1887915

@user1887915 大多数情况下是什么？我只是在参考问题中的示例。使用 unique_ptr<A> 还是其他智能指针更好可能取决于实际用例。 - 463035818_is_not_a_number

Answer 2

一个疯狂的解决方案是存储对齐的存储器，并手动管理迭代器的对象生命周期，静态断言您制作了正确大小的存储器。

这是真正的痛苦，而且相当不安全（容易犯错），但它能够工作。

使用无聊容器迭代器的大小/对齐方式。通过adl使用自由函数访问迭代器。

std往往会过度要求完全定义的类型。

CRTP和标签的谨慎使用可能会让您自动化危险代码，但很棘手。

- Yakk - Adam Nevraumont

Answer 3

在您的实例中，基本上您拥有的是：一个int和一个double之间的1:1关系，ints存储在vector<int>中，而doubles存储在unordered_set<double>中。

一种方法是简化问题，例如您能否将数据放入unordered_map<double, int>中？有时可能是这样，可以解决很多问题。有时可能不是这样，例如您可能需要按ints对数据进行排序。

我认为使用std 2个容器的路径充满了困难，其中编译错误只是冰山一角，例如：

• 对于1:1关系，当您添加条目时，您需要插入两个容器，因此可能需要处理插入到一个容器但另一个容器失败的情况
• 迭代器可能会失效（例如，如果您有一个迭代器指向向量元素并对向量进行排序）
• [unordered_]sets中的值（以及映射中的[unordered_]keys）是const的（因此您无法在添加它们后更改它们）

另一种方法可能是：考虑使用类似于boost bimap或multi_index的东西。它们利用了这样一个事实，即如果您想要两个基于节点的结构（例如两个集合）具有1:1的关系，则对于插入操作，它只需要进行一次分配，其中包含两个节点。

- Mircea Baja

---

payload只是一个例子。您可以通过问题的编辑看到，最初的问题表述不同。应该有许多相互连接的几何结构。 - Tomilov Anatoliy