前書き
この記事はC++ Advent Calendar 2017 22日目の記事です
C++98/03時代のAllocator
C++98/03時代にはAllocator-aware Containerというコンセプトがありません。規格には[lib.container.requirements]に幾つかの文面しかありませんでした。
N1638 [lib.container.requirements/9]より
Copy constructors for all container types defined in this clause copy an allocator argument from their
respective first parameters. All other constructors for these container types take an Allocator& argument
(20.1.6), an allocator whose value type is the same as the container’s value type. A copy of this argument
is used for any memory allocation performed, by these constructors and by all member functions, during
the lifetime of each container object. In all container types defined in this clause, the member
get_allocator() returns a copy of the Allocator object used to construct the container.
それに対して、Allocatorのコンセプトの規定が以下のようになっています：
N1638 [lib.allocator.requirements]より
| Variables | Definition |
|---|---|
T, U |
any non-const, non-reference type |
X |
an Allocator class for type T
|
Y |
the corresponding Allocator class for type U
|
t |
a value of type const T&
|
a, a1, a2 |
values of type X&
|
b |
a value of type Y
|
p |
a value of type X::pointer, obtained by calling a1.allocate, where a1 == a. |
q |
a value of type X::const_pointer obtained by conversion from a value p. |
r |
a value of type X::reference obtained by the expression *p. |
s |
a value of type X::const_reference obtained by the expression *q or by conversion from a value r. |
u |
a value of type Y::const_pointer obtained by calling Y::allocate , or else 0. |
n |
a value of type X::size_type. |
| expression | return type | assertion/note pre/post-condition |
|---|---|---|
X::pointer |
Pointer to T. |
|
X::const_pointer |
Pointer to const T. |
|
X::reference |
T& |
|
X::const_reference |
const T& |
|
X::value_type |
Identical to T
|
|
X::size_type |
unsigned integral type | a type that can represent the size of the largest object in the allocation model. |
X::difference_type |
signed integral type | a type that can represent the difference between any two pointers in the allocation model. |
typename X::template rebind<U>::other |
Y |
For all U(including T), Y::template rebind<T>::other is X. |
a.address(r) |
X::pointer |
|
a.address(s) |
X::const_pointer |
|
a.allocate(n)a.allocate(n, u)
|
X::pointer |
Memory is allocated for n objects of type T but objects are not constructed. allocate may raise an appropriate exception. The result is a random access iterator. [Note: If n==0, the return value is unspecified.] |
a.deallocate(p, n) |
(not used) | All n T objects in the area pointed by p shall be destroyed prior to this call. n shall match the value passed to allocate to obtain this memory. Does not throw exceptions. [Note: p shall not be null.] |
a.max_size() |
X::size_type |
the largest value that can meaningfully be passed to X::allocate(). |
a1 == a2 |
bool |
returns true iff storage allocated from each can be deallocated via the other. |
a1 != a2 |
bool |
same as !(a1 == a2)
|
X() |
creates a default instance. Note: a destructor is assumed. | |
X a(b) |
post: Y(a) == b
|
|
a.construct(p, t) |
(not used) | Effect: ::new((void*)p) T(t)
|
a.destroy(p) |
(not used) | Effect: ((T*)p)-> ̃T()
|
見た目は厳しい制限ではなさそうですが、続きには以下の規定があります。
N1638 [lib.allocator.requirements/4]より
Implementations of containers described in this International Standard are permitted to assume that their
Allocator template parameter meets the following two additional requirements beyond those in Table 33.
— All instances of a given allocator type are required to be interchangeable and always compare equal to
each other.
— The typedef members pointer, const_pointer, size_type, and difference_type are
required to be T*, T const*, std::size_t, and std::ptrdiff_t, respectively.
つまり標準ライブラリの場合、最悪どのオブジェクトでも他のオブジェクトと等しくなるAllocator、或いは「Stateless Allocator」しか標準ライブラリのコンテナが受けられません。標準ライブラリのコンテナがAllocatorの型で区別している上にAllocatorのオブジェクトを格納していますが、Allocatorオブジェクトがお互い等しくない場合は当該のコンテナのコピー、ムーブとスワップを一体どう扱うべきだったのかはさすが定義できません。
C++11以降のAllocator
C++以降は、標準ライブラリのコンテナがお互い等しくない「Stateful Allocator」を使えるようになります。提案N2525によって、標準委員会は型でもインスタンスでも区別してるAllocatorの使用例をまず二つ考えてみました。
N2525より
The extremes of allocator usage patterns are:
Pattern A) The allocator instance is a configuration parameter of an object, indicating
where memory for this object should come from. The allocator should not
change during the object's lifetime. The allocator mechanism is sometimes
created in the same scope as the client object, requiring that the allocator
not be copied into an object that will outlive that scope (e.g. by copy-
construction of the client into a longer-lived object).
Pattern B) The allocator is used for tuning the performance of a (container) class.
The type of the allocator, not the instance, determines the characteristics.
For this reason, one doesn't care so much what allocator instance a
container is using, but there are performance benefits to having multiple
stateful allocators rather than having one big memory pool shared by any
number of stateless allocators. Otherwise, the allocators are more-or-less
equivalent, though they do not compare equal because they manage
different segments of memory. With this pattern, it is both safe and
correct to change the allocator instance during the lifetime of an object
whenever efficiency dictates that approach. The underlying memory
resources used by this type of allocator are either long-lived or reference-
counted so that one does not worry excessively about an object outliving
the memory resource.
そのような考えに従って、規格には前の「標準ライブラリのコンテナは『Stateless Allocator』しか使えない」的な規定は削除され、代わりにAllocatorの要件は以下のようになりました。
N3337 [allocator.requirements]より
The template struct allocator_traits (20.6.8) supplies a uniform interface to all allocator types. Table 27
describes the types manipulated through allocators. Table 28 describes the requirements on allocator types
and thus on types used to instantiate allocator_traits. A requirement is optional if the last column of
Table 28 specifies a default for a given expression. Within the standard library allocator_traits template,
an optional requirement that is not supplied by an allocator is replaced by the specified default expression.
A user specialization of allocator_traits may provide different defaults and may provide defaults for
different requirements than the primary template. Within Tables 27 and 28, the use of move and forward
always refers to std::move and std::forward, respectively.
| Variable | Definition |
|---|---|
T, U, C |
any non-const object type |
V |
a type convertible to T
|
X |
an Allocator class for type T
|
Y |
the corresponding Allocator class for type U
|
XX |
the type allocator_traits<X>
|
YY |
the type allocator_traits<Y>
|
t |
a value of type const T&
|
a, a1, a2 |
values of type X&
|
a3 |
an rvalue of type X
|
b |
a value of type Y
|
c |
a dereferenceable pointer of type C*
|
p |
a value of type XX::pointer, obtained by calling a1.allocate, where a1 == a
|
q |
a value of type XX::const_pointer obtained by conversion from a value p. |
w |
a value of type XX::void_pointer obtained by conversion from a value p
|
z |
a value of type XX::const_void_pointer obtained by conversion from a value q or a value w
|
r |
a value of type T&obtained by the expression *p. |
s |
a value of type const T& obtained by the expression *q or by conversion from a value r. |
u |
a value of type YY::const_pointer obtained by calling YY::allocate, or else nullptr. |
v |
a value of type V
|
n |
a value of type XX::size_type. |
Args |
a template parameter pack |
args |
a function parameter pack with the pattern Args&&
|
| Expression | Return type | Assertion/note pre-/post-condition |
Default |
|---|---|---|---|
X::pointer |
T* |
||
X::const_pointer |
X::pointer is convertible to X::const_pointer
|
pointer_traits<X::pointer>::rebind<const T> |
|
X::void_pointerY::void_pointer
|
X::pointer is convertible to X::void_pointer.X::void_pointer and Y::void_pointer are the same type. |
pointer_traits<X::pointer>::rebind<void> |
|
X::const_void_pointerY::const_void_pointer
|
X::pointer, X::const_pointer, and X::void_pointer are convertible to X::const_void_pointer.X::const_void_pointer and Y::const_void_pointer are the same type. |
pointer_traits<X::pointer>::rebind<const void> |
|
X::value_type |
Identical to T
|
||
X::size_type |
unsigned integer type | a type that can represent the size of the largest object in the allocation model. | make_unsigned<X::difference_type>::type |
X::difference_type |
signed integer type | a type that can represent the difference between any two pointers in the allocation model. | pointer_traits<X::pointer>::difference_type |
typename X::template rebind<U>::other |
Y |
For all U (including T), Y::template rebind<T>::other is X. |
See Note A, below. |
*p |
T& |
||
*q |
const T& |
*q refers to the same object as *p
|
|
p->m |
type of T::m
|
pre: (*p).m is well-defined.equivalent to (*p).m
|
|
q->m |
type of T::m
|
pre: (*q).m is well-defined.equivalent to (*q).m
|
|
static_cast<X::pointer>(w) |
X::pointer |
static_cast<X::pointer>(w) == p |
|
static_cast<X::const_pointer>(z) |
X::const_pointer |
static_cast<X::const_pointer>(z) == q |
|
a.allocate(n) |
X::pointer |
Memory is allocated for n objects of type T but objects are not constructed. allocate may raise an appropriate exception. [ Note: If n == 0, the return value is unspecified. —end note ] |
|
a.allocate(n, u) |
X::pointer |
Same as a.allocate(n). The use of u is unspecified, but it is intended as an aid to locality. |
a.allocate(n) |
a.deallocate(p, n) |
(not used) | All n T objects in the area pointed to by p shall be destroyed prior to this call. n shall match the value passed to allocate to obtain this memory. Does not throw exceptions. [ Note:p shall not be singular.—end note ] |
|
a.max_size() |
X::size_type |
the largest value that can meaningfully be passed to X::allocate()
|
numeric_limits<size_type>::max() |
a1 == a2 |
bool |
returns true only if storage allocated from each can be deallocated via the other.operator== shall be reflexive, symmetric, and transitive, and shall not exit via an exception. |
|
a1 != a2 |
bool |
same as !(a1 == a2)
|
|
a == b |
bool |
same as a == Y::rebind<T>::other(b)
|
|
a != b |
bool |
same as !(a == b)
|
|
X a1(a); |
Shall not exit via an exception. post: a1 == a
|
||
X a(b); |
Shall not exit via an exception. post: Y(a) == b, a == X(b)
|
||
X a1(move(a)); |
Shall not exit via an exception. post: a1 equals the prior value of a. |
||
X a(move(b)); |
Shall not exit via an exception. post: a equals the prior value of X(b). |
||
a.construct(c, args) |
(not used) | Effect: Constructs an object of type C at c
|
::new ((void*)c) C(forward<Args>(args)...) |
a.destroy(c) |
(not used) | Effect: Destroys the object at c
|
c->˜C() |
a.select_on_container_copy_construction() |
X |
Typically returns either a or X()
|
return a; |
X::propagate_on_container_copy_assignment |
Identical to or derived from true_type or false_type
|
true_type only if an allocator of type X should be copied when the client container is copy-assigned. |
false_type |
X::propagate_on_container_move_assignment |
Identical to or derived from true_type or false_type
|
true_type only if an allocator of type X should be moved when the client container is move-assigned. |
false_type |
X::propagate_on_container_swap |
Identical to or derived from true_type or false_type
|
true_type only if an allocator of type X should be swapped when the client container is swapped. |
false_type |
Note A: The member class template rebind in the table above is effectively a typedef template. [ Note: In
general, if the name Allocator is bound to SomeAllocator<T>, then Allocator::rebind<U>::other is the
same type as SomeAllocator<U>, where SomeAllocator<T>::value_type is T and SomeAllocator<U>::
value_type is U. —end note ] If Allocator is a class template instantiation of the form SomeAllocator<T,
Args>, where Args is zero or more type arguments, and Allocator does not supply a rebind member
template, the standard allocator_traits template uses SomeAllocator<U, Args> in place of Allocator::
rebind<U>::other by default. For allocator types that are not template instantiations of the above form,
no default is provided.
N1638の当該規定に対し、N3337はAllocatorの要件にpropagate_on_container_copy_assignment、propagate_on_container_move_assignmentとpropagate_on_container_swapという特性を追加しました。コンテナのオブジェクトをコピー代入、ムーブ代入とスワップの時、アロケータ型の当該特性がstd::true_typeになれば、コンテナ内のアロケータオブジェクトはコンテナと共にコピー代入、ムーブ代入とスワップを行います。
なお、コンテナがコピー初期化を行う時、select_on_container_copy_constructionを呼び出してアロケータオブジェクトをコピー初期化することになります。
以上のAllocator要件に対し、規格はAllocator-aware containerというコンセプトを導入しました。
N3337 [container.requirements.general]より
In Table 99, X denotes an allocator-aware container class with a value_type of T using allocator of type A,
u denotes a variable, a and b denote non-const lvalues of type X, t denotes an lvalue or a const rvalue of
type X, rv denotes a non-const rvalue of type X, m is a value of type A, and Q is an allocator type.
| Expression | Return type | Assertion/note pre-/post-condition |
Complexity |
|---|---|---|---|
allocator_type |
A |
Requires:allocator_type::value_type is the same as X::value_type. |
compile time |
get_allocator() |
A |
constant | |
X()X u;
|
Requires: A is DefaultConstructible.post: u.empty() returns true, u.get_allocator() == A()
|
constant | |
X(m)X u(m)
|
post: u.empty() returns true, u.get_allocator() == m
|
constant | |
X(t, m)X u(t, m);
|
Requires: T is CopyInsertable into X.post: u == t, get_allocator() == m
|
linear | |
X(rv)X u(rv)
|
Requires: move construction of A shall not exit via an exception.post: u shall have the same elements as rv had before this construction; the value of get_allocator() shall be the same as the value of rv.get_allocator() before this construction. |
constant | |
X(rv, m)X u(rv, m);
|
Requires: T is MoveInsertable into X.post: u shall have the same elements, or copies of the elements, that rv had before this construction, get_allocator() == m
|
constant if m == rv.get_allocator(), otherwise linear |
|
a = t |
X& |
Requires: T is CopyInsertable into X and CopyAssignable.post: a == t
|
linear |
a = rv |
X& |
Requires: If allocator_traits<allocator_type>::propagate_on_container_move_assignment::value is false, T is MoveInsertable into X and MoveAssignable. All existing elements of a are either move assigned to or destroyed.post: a shall be equal to the value that rv had before this assignment. |
linear |
a.swap(b) |
void |
exchanges the contents of a and b
|
constant |
これからC++17まではAllocator-aware containerの規定が殆ど変更かありません。Allocatorの規定にis_always_equalという特性が追加されていますが、大したことでもありません。
N4713 [allocator.requirements]より
| Expression | Return type | Assertion/note pre-/post-condition |
Default |
|---|---|---|---|
| X::is_always_equal | Identical to or derived from true_type or false_type
|
true_type only if the expression a1 == a2 is guaranteed to be true for any two (possibly const) values a1, a2 of type X. |
is_empty<X>::type |
C++17のstd::pmr::polymorphic_allocator
というわけでC++にはAllocatorとアロケータを使うAllocator-aware containerは以上です。が、見た目は一般通過兄貴の想定してるアロケータとかなり違いそうなのです。なにより、「アロケータ」を言うとメモリの確保と廃棄を司るオブジェクトを思い出すのが普通ので、C++のAllocatorの設計はさすが分かりやすいとは言えないなのでしょう。わざわざアロケータの型をコンテナの型に追加して、アロケータをコンセプトにするのは、明らかにアロケータの区別を型（つまり静的な多相）で行うということにほかならない。標準テンプレートライブラリがなぜ最初からそういう設計になっているのかは恐らくAlexander Stepanov氏のみぞ知る。
ともかく、その設計のせいで問題がもう一つがあります：もし標準ライブラリのコンテナを使う時動的多相なアロケータが使いたければどうすべきでしょう？
その問題を解決するため、C++17にはstd::pmr::polymorphic_allocatorというアロケータを追加してます。
詳しくのはC++17 [mem.res.syn]を参照。簡単に言うとstd::pmr::polymorphic_allocatorは内部にstd::pmr::memory_resourceの多相クラスの生ポインタを格納してます。標準ライブラリコンテナを使う時、アロケータ型を示すテンプレート引数をstd::pmr::polymorphic_allocatorに設定するとそのコンテナを使うどんな場合にもstd::pmr::memory_resourceの経由で動的多相になることができます。
なお、std::pmr::polymorphic_allocator自身も前に言った「Stateful Allocator」の素晴らしい例と言えます。
規格準拠のAllocator-aware containerの例が欲しい
あれは後で追加します。
後書き
日本語わからない。日本語の記事を書くのは英語でC++のproposalを書くより難しい。