Doc. no.: N3890
Date: 2014-01-19
Project: Programming Language C++, Library Evolution Working Group
Reply-to: Zhihao Yuan <zy at miator dot net>

Container<Incomplete Type>

Overview

struct Entry
{
    std::deque<Entry> messages;
    // ...
};

The goal of this paper is to allow recursive data structure definitions with STL containers, while to make the STL container instantiations well-formed even when some of the template arguments are incomplete types (in contrast to 17.6.4.8/2) is an approach to achieve the goal without breaking any language restrictions or existing practices.

The approach, namely “Containers of Incomplete Types”, was well-known shortly after the C++98 standard being shipped[1], is one of the main features provided by Boost.Container[2] and libstdc++, and is receiving increasing interest in libc++.

Some workarounds have been discussed, including using a container of smart pointers. However, the proposed solution has the following significant advantages:

  1. The value semantics of value_type is well-preserved;
  2. scoped allocators work out-of-box;
  3. such a container can be used in type erasure.

Impact on the Standard

  1. An additional “Completeness” requirement for each category of the containers – Sequence, Associative, Unordered associative, and Container adaptors, plus the Hash requirements and Allocator requirements.

  2. Require the unspecialized and transparent function objects (std::less<T> and std::less<>, for example, respectively) to be complete types unconditionally.

  3. Require std::allocator<T> to unconditionally satisfy the “Allocator completeness requirements” in 1).

2) and 3) are trivial to the existing implementations, but not 1). Some changes involve ABI breakages, and some changes result in less compile-time checking; but run-time performance will not be affected (interestingly, the situation is similar to that of the SCARY iterators, as well as some techniques we are using, plus some goals we want to achieve from a type system’s point of view).

Currently,

Design Decisions

The proposed feature set is chosen in a “least common multiple” (of the existing implementations) manner. All the possible (no std::array) and useful cases are conditionally covered, so that only the standard library implementations may be affected, but not existing user code. For example, if a customized MyLess is not a complete type, the whole std::set<T, MyLess> specialization is not well-formed.

Technical Specifications

This specification only covers 1) in Impact on the Standard; 2) and 3) are merely wording details.

Hash completeness requirements

A type H satisfies the Hash completeness requirements if:

[Just a note: h and k are defined in 17.6.3.4 –end note]

Allocator completeness requirements

A type X satisfies the Allocator completeness requirements if:

[Just a note: If LWG 2311 is applied, this section may no longer be needed. –end note]

Sequence containers

A sequence container with an Allocator template parameter is a complete type if:

Associative containers

An associative container is a complete type if:

Unordered associative containers

An unordered associative container is a complete type if:

Container adaptors

Sample Implementation

The proposed solution has been implemented (as an llvm/libc++ fork) and well- tested: https://github.com/lichray/libcxx/tree/container_incomplete

References

[1] Austern, Matthew H. The Standard Librarian: Containers of Incomplete Types. http://www.drdobbs.com/the-standard-librarian-containers-of-inc/184403814

[2] Main features: Containers of Incomplete Types. “Boost.Container” http://www.boost.org/doc/libs/1_55_0/doc/html/container/main_features.html#container.main_features.containers_of_incomplete_types

Acknowledgments

Thanks to the library implementers who helped refine the idea, run my crappy test code, and review the patches publicly and/or privately.