Are C++ Recursive Type Definitions Possible, in Particular How to Put a Vector<T> Within the Definition of T

Are C++ recursive type definitions possible, in particular can I put a vector T within the definition of T?

The C++ Standard (2003) clearly says that instantiating a standard container with an incomplete type invokes undefined-behavior.

The spec says in §17.4.3.6/2,

In particular, the effects are undefined in the following cases:

__ [..]

— if an incomplete type (3.9) is used as a template argument when instantiating a template component.

__ [..]

Things have changed with the C++17 standard, which explicitely allows this types of recursion for std::list, std::vector and std::forward_list. For reference, see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4510.html and this answer: How can I declare a member vector of the same class?

C++ recursive type definition

This boils down to vector<T> not needing to know the size a value of type T occupies, which allows T to be an incomplete type. Essentially, the mechanism in play here is the same as in this declaration:

struct test {
    test* start;
    test* end;
};

The compiler has no problem declaring pointers to any type, as long as you promise to define it at some later point.

This behavior changes based on the template: you have no problem defining test with a vector<T>, but an array<T,Size> or even a pair<T,K> would be problematic:

struct broken1 {
    array<broken1,3> a; // Does not compile
};
struct broken2 {
    pair<broken2,broken2> p; // Does not compile
};

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

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.

How can I declare a member vector of the same class?

This paper was adopted into C++17 which allows incomplete types to be used in certain STL containers. Prior to that, it was Undefined Behavior. To quote from the paper:

Based on the discussion on the Issaquah meeting, we achieved the
consensus to proceed* with the approach – “Containers of Incomplete
Types”, but limit the scope to std::vector, std::list, and
std::forward_list, as the first step.

And as for the changes in the standard (emphasis mine):

An incomplete type T may be used when instantiating vector if the
allocator satisfies the allocator-completeness-requirements
(17.6.3.5.1). T shall be complete before any member of the resulting
specialization of vector is referenced.

So, there you have it, if you leave the default std::allocator<T> in place when instantiating the std::vector<T, Allocator>, then it will always work with an incomplete type T according to the paper; otherwise, it depends on your Allocator being instantiable with an incomplete type T.

---

A is an incomplete type, right? If there was a vector of A*s I would understand. But here I don't understand how it works. It seems to be a recursive definition.

There is no recursion there. In an extremely simplified form, it's similar to:

class A{
    A* subAs;
};

Technically, apart from size, capacity and possibly allocator, std::vector only needs to hold a pointer to a dynamic array of A it manages via its allocator. (And the size of a pointer is known at compile time.)

So, an implementation may look like this:

namespace std{

    template<typename T, typename Allocator = std::allocator<T>>
    class vector{

        ....

        std::size_t m_capacity;
        std::size_t m_size;
        Allocator m_allocator;
        T* m_data;
    };

}

How to define a recursive concept?

Concepts can always defer to a type trait:

template <typename T> concept C = some_trait<T>::value;

And that trait can be recursive:

template <typename T>
struct some_trait : std::false_type { };

template <std::Integral T>
struct some_trait<T> : std::true_type { };

template <typename T, typename A>
struct some_trait<std::vector<T, A>> : some_trait<T> { };

If you don't mean just vector, then the last partial specialization can be generalized to:

template <std::Range R>
struct some_trait<R> : some_trait<std::range_value_t<R>> { };

C++ template recursively print a vector of vector using template

What should struct is_vector looks like to do this?

It looks like what template partial specialization looks like

template<class T>
struct is_vector : std::false_type {};

template<class T, class Alloc>
struct is_vector<std::vector<T, Alloc>> : std::true_type {};

Demo

putting iterator on a container inside it

Here is a solution to what I think is the problem you're trying to solve.

vec is the original immutable vector of Something objects (this is like your T, above).

weightedIndex is a vector of interators into vec which in this case has been ordered by ascending Something.weight() (but it could be any predicate)

#include <iostream>
#include <vector>
#include <algorithm>

struct Something
{
    Something(int weight)
    : _creationOrder { _createCount++ }
    , _weight { weight }
    {}

    int weight() const { return _weight; }

    std::ostream& write(std::ostream& os) const {
        os << "Something { createOrder=" 
        << _creationOrder 
        << ", weight=" << _weight << "}";
        return os;
    }
private:
    int _creationOrder;
    int _weight;
    static int _createCount;
};

std::ostream& operator<<(std::ostream& os, const Something& st) {
    return st.write(os);
}

int Something::_createCount { 0 };

using namespace std;

int main()
{
    vector<Something> vec { 10, 23, 76, 12, 98, 11, 34 };
    cout << "original list:";
    for(const auto& item : vec) {
        cout << "\n" << item;
    }

    using iter = decltype(vec)::const_iterator;
    vector<iter> weightIndex;
    weightIndex.reserve(vec.size());
    for(auto i = vec.begin() ; i != vec.end() ; ++i) {
        weightIndex.push_back(i);
    }
    sort(weightIndex.begin(), weightIndex.end() , [](const iter& i1, const iter& i2) {
       return i1->weight() < i2->weight(); 
    });

    // weightIndex is now a vector of pointers to the Something elements, but the pointers
    // are ordered by weight of each Something

    cout << "\nSorted index:";
    for(const auto p : weightIndex) {
        cout << "\n" << *p;
    }

    cout << endl;

    // find the mid-weight
    auto ii = next(weightIndex.begin(), 3);

    // next one in list is
    auto next_ii = next(ii, 1);

    // find previous in weighted order
    auto prev_ii = prev(ii, 1);
    cout << "Selection:\n";
    cout << "Current = " << **ii << endl;
    cout << "Next = " << **next_ii << endl;
    cout << "Previous = " << **prev_ii << endl;

   return 0;
}

Output:

original list:
Something { createOrder=0, weight=10}
Something { createOrder=1, weight=23}
Something { createOrder=2, weight=76}
Something { createOrder=3, weight=12}
Something { createOrder=4, weight=98}
Something { createOrder=5, weight=11}
Something { createOrder=6, weight=34}
Sorted index:
Something { createOrder=0, weight=10}
Something { createOrder=5, weight=11}
Something { createOrder=3, weight=12}
Something { createOrder=1, weight=23}
Something { createOrder=6, weight=34}
Something { createOrder=2, weight=76}
Something { createOrder=4, weight=98}
Selection:
Current = Something { createOrder=1, weight=23}
Next = Something { createOrder=6, weight=34}
Previous = Something { createOrder=3, weight=12}

---

Related Topics