集合迭代器中的不完整类型

Question

我自己编写了一个自定义的 STL 样式容器，它在内部使用 AVL 树来组织数据。现在，在一个项目中，我想有一个迭代器作为它的成员：

class vertex {
    ...
    avl_tree<vertex>::iterator partner;
    ...
}

但是，我收到错误消息：

error: ‘avl_tree<T, A>::node::data’ has incomplete type
         T data;
           ^

根据我在 SO 和其他网站上阅读的内容，vertex 在完全定义之前是不完整的类型。 avl_tree<T,A>::node 是我用来管理树的私有结构，它的成员中有 T data;，但是如果 T 不完整，这是非法的。奇怪的是，当我改用 std::list 时，没有这样的问题，我理解这是未定义的行为。

有没有解决这个问题的简单方法？ avl_tree<T,A>::iterator 内部仅维护一个指针 node *ptr ，这对于不完整的类型应该不是问题，因为指针具有固定大小。但是我不想将 node class 暴露给 public，我想使用 iterator。尽管如此，iterator 将始终具有相同的大小，而不管模板参数如何，那么有没有办法强制编译器承认这一事实？

结构概述：

template <typename T, typename A = std::allocator<T> >
class avl_tree {
private:
    class node {
    public:
        T data;
        avl_tree *tree;
        short depth;
        size_type n;
        node *parent;
        node *left_child;
        node *right_child;
    };
public:
    class iterator {
    private:
        node *ptr;
    };
private:
    using NodeAlloc = typename std::allocator_traits<A>::template rebind_alloc<node>;
    NodeAlloc alloc;
    node root;
};

完整代码可在 GitHub 上找到。

Answer 1

我猜node或iterator类型没有问题。问题是你使用递归类型定义

class vertex {
    ...
    avl_tree<vertex>::iterator partner;
    ...
}

您正在尝试使用尚未完全定义的类型 (vertex)。因此，在 node root 的实例化时出现错误，编译器不知道 T 的大小。

这是模拟您的问题的小例子

template<typename T>
struct A {

    struct B {

        T data;

    };

    struct C {

        B* b;

    };

    B root;
};

struct D {

    A<D>::C ad;

};

int main() {
    D d;
}

A 是您的 avl_tree，B 是 node，C 是 iterator。错误是一样的

error: ‘A::B::data’ has incomplete type

现在有多种方法可以修复它。第一个是将 D 类型中的 ad 类型更改为

A<D*>::C ad;

但是正如您所说，STL 的list（或vector）没有这样的问题。而且这里是交易，A 中的 root 的类型应该是 B* 或 B&，而不是 B。但是，如果您将使用 B*，则需要注意内存分配。

Answer 2

类型齐全

首先，让我们看一个简单的示例，说明定义 UDT（用户定义类型）所需的内容。

struct Foo
{
     struct Bar bar;
};

鉴于上面的代码，编译器只有在理解 struct Bar 的定义的情况下才能正确构建它。否则它不知道如何对齐此 bar 数据成员以及结构实际有多大（以及添加多少填充以确保其正确对齐）。

因此，要能够以这种方式定义 Foo，同样需要定义 Bar。类型依赖性如下所示：

Foo->Bar

如果我们将上面的代码改成这样：

struct Foo
{
     struct Bar* bar;
};

...突然之间，我们看到了一个截然不同的场景。在这种情况下，Bar 可以是不完整的类型（已声明但未定义），因为 Foo 仅存储指向它的指针。指针实际上是 POD（普通旧数据类型）。无论是指向 Bar 还是 Baz，它的大小和对齐要求都不会改变。结果，这里的类型依赖基本上是：

Foo->POD

因此，即使 Bar 的定义未知，我们也可以编译这段代码。当然，如果编译器遇到试图访问 Bar 成员或构造它或做任何需要有关 Bar 信息的代码，具体来说，它会生成错误，除非 Bar 的定义=] 届时可用。

Circular/Recursive 类型依赖关系

让我们看一个递归类型依赖的简单例子：

struct Foo
{
    struct Foo next;
};

对于这种情况，为了正确定义Foo，我们必须正确定义Foo。糟糕——无限递归。即使以某种方式允许这样做，系统也会为 Foo 分配无限量的内存。在这种情况下，类型依赖性如下所示：

Foo->Foo->Foo->...

即使我们在中间引入一个新类型，同样的问题仍然存在：

struct Foo
{
     struct Node next;
};

struct Node
{
     struct Foo element;
};

由于类型依赖的循环性质，我们仍然会遇到编译器错误，如下所示：

Foo->Node->Foo->Node->Foo->...

除此之外，我们还有先有鸡还是先有蛋的问题。如果 Foo 先于 Node，则 Node 不可能在当时定义 Foo，并且 Node 不可能在 Foo 时定义如果 Node 在 Foo.

之前定义

为了打破循环，我们可以添加一个间接：

struct Foo
{
    struct Node* next;
};

struct Node
{
    struct Foo element;
};

现在我们有：

Foo->POD
Node->Foo->POD

...这是有效的，避免了循环类型依赖，并且编译得很好。

树示例

更接近您的树示例，让我们看一个这样的案例：

template <class T>
struct Tree
{
     struct Node
     {
         T element;
     };
     Node root;
};

在这种情况下，类型依赖性如下所示：

Tree->Node->T->...

如果 T 不依赖于 Tree 或 Node.

的定义，这将编译良好

然而，在您的情况下，T 是一个 vertex，它取决于存储节点的树的类型定义，该节点存储顶点。结果，我们有这样的场景：

avl_tree<vertex>->node->vertex->avl_tree<vertex>->node->vertex->...

... 因此我们再次具有循环类型依赖性。切断这种依赖关系的最简单方法之一，也许是像这样的链接结构最常用的方法，就是将 root/head/tail 存储为指针。

template <class T>
struct Tree
{
     struct Node
     {
         T element;
     };
     Node* root;
};

这样，我们就切断了类型依赖性：

Tree->POD
Node->T->...

... 或者，根据您的示例进行调整：

avl_tree<vertex>->POD
node->vertex->avl_tree<vertex>->POD

...完全可以打破循环。

您可能想知道为什么从概念上讲，这需要完整的 avl_tree 类型定义：

avl_tree<vertex>::iterator partner;

这里的迭代器很好，因为它存储了指向作为 POD 的节点的指针。然而这里的问题是我们正在尝试访问 avl_tree 的成员，即使它只是一个类型名，这要求编译器具有 avl_tree 的完整类型定义（它不在我们可能喜欢的理想粒度级别上工作）。这递归需要 node 的完整定义，然后需要 vertex.

的完整定义

Oddly enough, when I use std::list instead, there is no such problem

这是因为 std::list 通常看起来像这样（提供或采取一些微小的变化）：

template <class T, ...>
class list
{
public:
    ...

private:
    struct node
    {
         node* next;
         node* prev;
         T element;
    };
    ...
    node* head;
    node* tail;
};

此处相关的类型依赖如下所示：

list<T>->POD
node->T->...

打破类型依赖

从上面我们可以看出，我们可以通过指针引入间接来sever/break类型依赖。这样做时，我们不再需要用户定义的类型定义，而是可以将 UDT 依赖项更改为简单的 POD 依赖项。

间接寻址可以放在任何你喜欢的地方，但对于链接结构，通常最方便的地方是结构的root/head/tail。这可以防止使用您的链接结构的客户端不必担心这些 recursive/circular 类型依赖性。

间接成本

我经常听到的一件事是 "the cost of indirection"，好像这很贵。这完全取决于内存访问模式以及它们如何与内存层次结构相关，从寄存器一直到二级阶段的内存分页。虽然将此视为 "cost of indirection" 是一种简单而通用的查看方式，因为指针可以指向内存中的所有位置，但真正不同的是我们如何访问内存尊重那些指针。

如果我们在连续内存中按顺序遍历链表 space，即使是链表也可能非常高效，其中多个节点适合缓存行并在逐出之前被访问。它们通常不那么快的地方是由于这样一个事实，即节点通常是由通用分配器分配的，而不是一次全部分配，将它们的内容分散并分散在内存中 space 并导致缓存未命中遍历。内存布局是这里最大的不同。

因此，如果您担心打破类型依赖性所需的间接成本，请不要担心。除非在非常精细的情况下仅仅是关于指针的内存大小，否则担心它通常是错误的。而是查看内存的分配方式，寻找引用的位置。使用正确的内存分配策略，即使是不可避免地依赖大量间接的链接结构也可以变得非常高效。

集合迭代器中的不完整类型

Incomplete types in collection iterators

c++

templates

stl

incomplete-type

类型齐全

Circular/Recursive 类型依赖关系

树示例

打破类型依赖

间接成本