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

Question

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?

Answer 1

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.