std::vector::iterator inside said structure causes "error: invalid use of incomplete type"

Question

I have a C11 std::vector of structures. The structure contains an iterator to another structure of the same type, describing a tree.

Using a forward declaration doesn't work, because vector needs to have the full definition of the structure, but vector can't have the full definition of the structure until definition is complete.

#include <vector>

template <class Payload>
class Tree
{
    public:
        typedef struct _Node Node;
        struct _Node
        {
            Payload t_payload;
            //error: invalid use of incomplete type '_Value_type {aka struct _Node}'
            std::vector<Node>::iterator pst_father;
        };

        std::vector<Node> gast_tree;
};

int main()
{
    Tree<int> my_tree;
    return 0;
}

in instantiation of 'void std::_Destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = _Node*]':
required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator, std::allocator<_T2>&) [with _ForwardIterator = _Node*; _Tp = _Node]'
required from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = _Node; _Alloc = std::allocator<_Node>]'
required from here
error: invalid use of incomplete type '_Value_type {aka struct _Node}'

I want std::vector to serve as container for the Node structure, and I want Node(s) to link with each others to build a tree. It would be trivial using int indexes instead of iterators and resolving the reference later, but I'm trying to learn std::vector<>::iterators. This compiles just fine:

#include <vector>

template <class Payload>
class Tree
{
    public:
        typedef struct _Node
        {
            Payload t_payload;
            //use a dumb index
            int s32_father_index;
        } Node;

        std::vector<Node> gast_tree;
};

int main()
{
    Tree<int> my_tree;
    return 0;
}

I tried several ways, but I can't get the iterator to compile. Is it possible to have an iterator to an object inside the object?

SOLUTION

The keyword typedef is redundant in C++. The keyword typename can be used in this scenario where the definition for the template is still incomplete. Details.

#include <vector>

template <class Payload>
class Tree
{
    public:
        struct Node
        {
            Payload t_payload;
            typename std::vector<Node>::iterator pst_father;
        };
        std::vector<Node> gast_tree;
};

int main()
{
    Tree<int> my_tree;
    return 0;
}

Why are you using `typedef struct` in the first place? That is redundant in C++ — UnholySheep, Aug 24 '22 at 14:41
Because I didn't know. I tried removing typedef and the example that compiles still compiles. Thanks for the tip! — 05032 Mendicant Bias, Aug 24 '22 at 14:42
And in the example that didn't compile before you will get a different error, about missing `typename` before a dependent type. Which can be fixed by adding exactly that before `std::vector` — UnholySheep, Aug 24 '22 at 14:44
It's exactly as you said! It even look cleaner without the typedef boilerplate. typename doesn't work if I use it at the same time as typedef. If you post it as an answer, i can accept it, thanks. — 05032 Mendicant Bias, Aug 24 '22 at 14:49
There's a cannonical answer for the `typename` problem already though: https://stackoverflow.com/questions/610245/where-and-why-do-i-have-to-put-the-template-and-typename-keywords - which is a lot more detailed than what I could possibly write for an answer here — UnholySheep, Aug 24 '22 at 14:50
Your link is very through indeed. It was to give you the points for the valid answer. Thanks for the help. — 05032 Mendicant Bias, Aug 24 '22 at 14:52

score 0 · Answer 1 · answered Aug 25 '22 at 06:45

SOLUTION

The keyword typedef is redundant in C++. The keyword typename can be used in this scenario where the definition for the template is still incomplete.

#include <vector>

template <class Payload>
class Tree
{
    public:
        struct Node
        {
            Payload t_payload;
            typename std::vector<Node>::iterator pst_father;
        };
        std::vector<Node> gast_tree;
};

int main()
{
    Tree<int> my_tree;
    return 0;
}

std::vector::iterator inside said structure causes "error: invalid use of incomplete type"

SOLUTION

1 Answers1

SOLUTION