Can't create recursive type `using T = vector<T::iterator>`-CodePudding

I'm trying to create a vector that contains its own iterators as elements, and I find it impossible to fully expand the type declaration.

using MyVectorType = std::vector<std::vector<...>::iterator>;
// Trying to fill in the ...                 ^^^

Another approach that fails is:

using MyVectorType = std::vector<MyVectorType::iterator>;

use of undeclared identifier 'MyVectorType' Trying to use an intermediate declaration also fails

template <class T>
using MyVectorType_incomplete = std::vector<T>;
using MyVectorType = MyVectorType_incomplete<MyVectorType_incomplete::iterator>;

error: 'MyVectorType_incomplete' is not a class,
namespace, or enumeration

Clearly using a pointer instead solves this issue.

struct It {
   It *iterator;
};
vector<It>;

However this means that you cannot use the iterator interface, and basically have to reimplement the iterator for the given class.

Is there a way to do this in C ?

More generally, is there a way to create recursive types like the above, where you refer to a type before it's created?

CodePudding user response：

I do not think that it is possible by the standard.

To achieve what you want you must be able to refer to std::vector<T>::iterator while T is incomplete.

Before C 17 T was required to be complete to instantiate std::vector<T> at all, so it cannot work there.

Since C 17 the standard allows instantiating std::vector<T> with incomplete types T, however only as long as the type is complete before any of its members are referenced, see [vector.overview]/4 of the post-C 20 draft.

However, if you want to achieve such a recursion, you need to be able to inherit or have a member of type std::vector<T>::iterator. Not only does this reference the ::iterator type, but it also requires it to be complete, which it is not guaranteed to be at this point.

struct MakeMyVectorType : std::vector<MakeMyVectorType>::iterator  {
};

using MyVectorType = std::vector<MakeMyVectorType>;

int main() {
    MyVectorType v1(10);
    MyVectorType v2(v1.begin(), v1.end());
    v2.push_back({v1.begin() 5});
    MyVectorType v3{{v2.begin()}, {v2.end()}};
    std::cout << v1.size() << "\n";  // 10
    std::cout << v2.size() << "\n";  // 11
    std::cout << v3.size() << "\n";  // 2
}

Instead of inheritance you can also make the iterator a member of the class. Either inheritance or member indirection is required though, since you cannot have the template arguments of the type be infinitely recursive.

I am also not really sure how you would use this type.

CodePudding user response：

using introduces a type alias. An alias is a name of some other thing. You can always replace the alias with that other thing. In fact you must do it in order to figure out properties of types that involve aliases, because aliases don't have properties of their own.

using MyVectorType = std::vector<MyVectorType::iterator>; // replace the name with the thing named
using MyVectorType = std::vector<std::vector<MyVectorType::iterator>::iterator>; // again
using MyVectorType = std::vector<std::vector<std::vector<std::vector<MyVectorType::iterator>::iterator>; ::iterator>::iterator>; // and again and again

So you cannot have a recursive type alias.

You can create a recursive type, but you cannot close the loop with a type alias. You can do it with a pointer or with a template. Something like this should be legal C :

struct my_vector : public std::vector<std::vector<my_vector>::iterator> {}

but I don't know how useful it is to you.