Why on earth does the following piece of code work?
struct A {
std::vector<A> subAs;
};
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.
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;
};
}