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

user_7697209 0
Viewed 91

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?

recursion type-systems templates c++ types
2 Answers

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.

user_7758060

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 instantiated, which is not guaranteed to work at this point.

Having the class inherit from std::vector<T::iterator> won't work either, since then T needs to be complete. Deferring T::iterator to another inherited class will also not work, since the classes then recursively depend on being completed before one another.

Depending on how the standard library is implementing std::vector<T>::iterator the following may work, although it is technically undefined behavior according to the standard:

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
}

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

user_177325220
Related