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

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是我用来管理树的私有(private)结构，它有 T data;然而，在其成员中，如果T是非法的是不完整的。奇怪的是，当我使用std::list时相反，不存在这样的问题，我理解这是未定义的行为。

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

<小时/>

结构概述:

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)。因此，在实例化节点根时，您会遇到错误，编译器不知道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 是 节点，C 是迭代器。而且错误是一样的

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

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

A<D*>::C ad;

但是正如您所提到的，STL(或 vector )中的list不存在这样的问题。事情是这样的，A 中的 root 类型应该是 B* 或 B&，而不是 B。但如果您要使用 B*，您将需要注意内存分配。