Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/named req/AllocatorAwareContainer"

From cppreference.com
< cpp‎ | named req
(P1072R10. Removed some wording seems misleading to me, restoration is welcome if you can clarify them.)
m (→‎Standard library: P0843)
 
(9 intermediate revisions by 5 users not shown)
Line 1: Line 1:
−
{{cpp/named req/title|AllocatorAwareContainer}}
+
{{cpp/named req/title|AllocatorAwareContainer|notes={{mark since c++11}}}}
 
{{cpp/named req/navbar}}
 
{{cpp/named req/navbar}}
  
 
An {{named req|AllocatorAwareContainer}} is a {{named req|Container}} that holds an instance of an {{named req|Allocator}} and uses that instance in all its member functions to allocate and deallocate memory and to construct and destroy objects in that memory (such objects may be container elements, nodes, or, for unordered containers, bucket arrays){{rev inl|since=c++23|, except that {{lc|std::basic_string}} specializations do not use the allocators for construction/destruction of their elements}}.
 
An {{named req|AllocatorAwareContainer}} is a {{named req|Container}} that holds an instance of an {{named req|Allocator}} and uses that instance in all its member functions to allocate and deallocate memory and to construct and destroy objects in that memory (such objects may be container elements, nodes, or, for unordered containers, bucket arrays){{rev inl|since=c++23|, except that {{lc|std::basic_string}} specializations do not use the allocators for construction/destruction of their elements}}.
  
−
The following rules apply to container construction
+
The following rules apply to container construction:
−
 
+
 
* Copy constructors of {{named req/core|AllocatorAwareContainer}}s obtain their instances of the allocator by calling {{c|std::allocator_traits<allocator_type>::select_on_container_copy_construction}} on the allocator of the container being copied.
 
* Copy constructors of {{named req/core|AllocatorAwareContainer}}s obtain their instances of the allocator by calling {{c|std::allocator_traits<allocator_type>::select_on_container_copy_construction}} on the allocator of the container being copied.
 
* Move constructors obtain their instances of allocators by move-constructing from the allocator belonging to the old container.
 
* Move constructors obtain their instances of allocators by move-constructing from the allocator belonging to the old container.
−
* All other constructors take a {{c|const allocator_type&}} parameter.
+
* All other constructors take a {{c/core|const allocator_type&}} parameter.
  
 +
{{anchor|Replacing allocator}}
 
The only way to replace an allocator is copy-assignment, move-assignment, and swap:
 
The only way to replace an allocator is copy-assignment, move-assignment, and swap:
−
 
+
* Copy-assignment will replace the allocator only if {{c|std::allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value}} is {{c|true}}.
−
* Copy-assignment will replace the allocator only if {{c|std::allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value}} is {{c|true}}
+
* Move-assignment will replace the allocator only if {{c|std::allocator_traits<allocator_type>::propagate_on_container_move_assignment::value}} is {{c|true}}.
−
* Move-assignment will replace the allocator only if {{c|std::allocator_traits<allocator_type>::propagate_on_container_move_assignment::value}} is {{c|true}}
+
 
* Swap will replace the allocator only if {{c|std::allocator_traits<allocator_type>::propagate_on_container_swap::value}} is {{c|true}}. Specifically, it will exchange the allocator instances through an unqualified call to the non-member function swap, see {{named req|Swappable}}.
 
* Swap will replace the allocator only if {{c|std::allocator_traits<allocator_type>::propagate_on_container_swap::value}} is {{c|true}}. Specifically, it will exchange the allocator instances through an unqualified call to the non-member function swap, see {{named req|Swappable}}.
  
−
Note: swapping two containers with unequal allocators if {{tt|propagate_on_container_swap}} is {{c|false}} is undefined behavior.
+
Note: The behavior of swapping two containers with unequal allocators if {{tt|propagate_on_container_swap}} is {{c|false}} is undefined.
  
 
* The accessor {{tt|get_allocator()}} obtains a copy of the allocator that was used to construct the container or installed by the most recent allocator replacement operation.
 
* The accessor {{tt|get_allocator()}} obtains a copy of the allocator that was used to construct the container or installed by the most recent allocator replacement operation.
  
 
===Requirements===
 
===Requirements===
−
====Legend====
+
A type satisfies {{named req/core|AllocatorAwareContainer}} if it satisfies {{named req|Container}} and, given the following types and values, the semantic and complexity requirements in the tables below are satisfied:
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc|{{ttb|X}}|Container type}}
+
{{dsc hitem|Type|Definition}}
−
{{dsc|{{ttb|T}}|Element type}}
+
{{dsc|{{tt|X}}|an {{named req/core|AllocatorAwareContainer}} type}}
−
{{dsc|{{ttb|A}}|Allocator for {{ttb|T}} }}
+
{{dsc|{{tt|T}}|the {{tt|value_type}} of {{tt|X}}}}
−
{{dsc|{{ttb|a}}, {{ttb|b}}|Objects of type {{ttb|X}} (non-const lvalue)}}
+
{{dsc|{{tt|A}}|the allocator type used by {{tt|X}}}}
−
{{dsc|{{ttb|t}}|Object of type {{ttb|X}} (lvalue or const rvalue) }}
+
{{dsc hitem|Value|Definition}}
−
{{dsc|{{ttb|rv}}|Object of type {{ttb|X}} (non-const rvalue) }}
+
{{dsc|{{c|a}}, {{c|b}}|non-const lvalues of type {{tt|X}}}}
−
{{dsc|{{ttb|m}}|Object of type {{ttb|A}} }}
+
{{dsc|{{c|c}}|an lvalue of type {{c/core|const X}}}}
−
{{dsc|{{ttb|Q}}| Allocator type }}
+
{{dsc|{{c|t}}|an lvalue or a const rvalue of type {{tt|X}}}}
 +
{{dsc|{{c|rv}}|a non-const rvalue of type {{tt|X}}}}
 +
{{dsc|{{c|m}}|a value of type {{tt|A}}}}
 
{{dsc end}}
 
{{dsc end}}
  
 +
====Types====
 
{|class=wikitable
 
{|class=wikitable
−
!expression||return type||pre/requirements||post/effects||complexity
+
!Name
 +
!{{nbsp}}Type{{nbsp}}
 +
!Requirement
 
|-
 
|-
−
|{{c|allocator_type}}||{{ttb|A}}||{{c|allocator_type::value_type}} must be the same as {{c|X::value_type}} || || compile-time
+
|{{c/core|typename X::allocator_type}}{{nbsp}}
 +
|{{tt|A}}
 +
|{{tt|X::allocator_type::value_type}} and {{tt|X::value_type}} are the same.
 +
|}
 +
 
 +
====Statements====
 +
{|class=wikitable
 +
!Statement
 +
!colspan=2|Semantics
 +
!Complexity
 
|-
 
|-
−
|{{c|get_allocator()}}||{{ttb|A}}|| || || constant
+
|rowspan=2|{{c|X u;}}<br>{{c|1=X u = X();}}
 +
|Precondition
 +
|{{tt|A}} is {{named req|DefaultConstructible}}.
 +
|rowspan=2|Constant
 
|-
 
|-
−
|{{c|X u;}} || ||{{ttb|A}} is {{named req|DefaultConstructible}}|| {{c|u.empty() {{==}} true && u.get_allocator() {{==}} A()}} || constant
+
|Postcondition{{nbsp}}
 +
|{{c|u.empty()}} and {{c|1=u.get_allocator() == A()}} are both {{c|true}}.
 
|-
 
|-
−
|{{c|X u(m);}} || || || {{c|u.empty() {{==}} true && u.get_allocator() {{==}} m}} || constant
+
|{{c|X u(m);}}
 +
|Postcondition
 +
|{{c|u.empty()}} and {{c|1=u.get_allocator() == m}} are both {{c|true}}.
 +
|Constant
 +
|-
 +
|rowspan=2|{{c|X u(t, m);}}
 +
|Precondition
 +
|{{tt|T}} is {{named req|CopyInsertable}} into {{tt|X}}.
 +
|rowspan=2|Linear
 +
|-
 +
|Postcondition
 +
|{{c|1=u == t}} and {{c|1=u.get_allocator() == m}} are both {{c|true}}.
 +
|-
 +
|{{c|X u(rv);}}
 +
|Postcondition
 +
|
 +
* {{c|u}} has the same elements as {{c|rv}} had before this construction.
 +
* The value of {{c|u.get_allocator()}} is the same as the value of {{c|rv.get_allocator()}} before this construction.
 +
|Constant
 +
|-
 +
|rowspan=2|{{c|X u(rv, m);}}
 +
|Precondition
 +
|{{tt|T}} is {{named req|MoveInsertable}} into {{tt|X}}.
 +
|rowspan=2|
 +
* Constant if {{c|1=m == rv.get_allocator()}} is {{c|true}}.
 +
* Otherwise linear.
 +
|-
 +
|Postcondition
 +
|
 +
* {{c|u}} has the same elements, or copies of the elements, that {{c|rv}} had before this construction.
 +
* {{c|1=u.get_allocator() == m}} is {{c|true}}.
 +
|}
 +
 
 +
====Expressions====
 +
{|class=wikitable
 +
!Expression
 +
!{{nbsp}}Type{{nbsp}}
 +
!colspan=2|Semantics
 +
!{{nbsp}}Complexity{{nbsp}}
 
|-
 
|-
−
|{{c|X u(t,m);}} ||
+
|{{c|c.get_allocator()}}
−
| {{ttb|T}} is {{named req|CopyInsertable}} into {{ttb|X}}
+
|{{tt|A}}
−
|{{c|u {{==}} t && u.get_allocator() {{==}} m}} || linear
+
|colspan=2|No direct semantic requirement.
 +
|Constant
 
|-
 
|-
−
|{{c|X u(rv);}} ||
+
|rowspan=2|{{c|1=a = t}}
−
| Move constructor of {{ttb|A}} must not throw exceptions
+
|rowspan=2|{{tt|X&}}
−
| {{ttb|u}} has the same elements and an equal allocator as {{ttb|rv}} had before the construction || constant
+
|Precondition
 +
|{{tt|T}} is {{named req|CopyInsertable}} into {{tt|X}} and {{named req|CopyAssignable}}.
 +
|rowspan=2|Linear
 
|-
 
|-
−
|{{c|X u(rv,m);}}||
+
|Postcondition{{nbsp}}
−
|{{ttb|T}} is {{named req|MoveInsertable}} into {{ttb|X}}
+
|{{c|1=a == t}} is {{c|true}}.
−
| The elements of {{ttb|u}} are the same or copies of those of {{ttb|rv}} and {{c|u.get_allocator() {{==}} m}}
+
−
| constant if {{c|m {{==}} rv.get_allocator()}}, otherwise linear
+
 
|-
 
|-
−
|{{c|a {{=}} t}}||{{c|X&}}
+
|rowspan=3|{{c|1=a = rv}}
−
|{{c|{{ttb|T}} is {{named req|CopyInsertable}} into {{ttb|X}} and {{named req|CopyAssignable}} ||{{c|a {{==}} t}} || linear
+
|rowspan=3|{{tt|X&}}
 +
|Precondition
 +
|If the allocator will '''not''' be replaced by move-assignment (see [[#Replacing allocator|above]]), then {{tt|T}} is {{named req|MoveInsertable}} into {{tt|X}} and {{named req|MoveAssignable}}.
 +
|rowspan=3|Linear
 
|-
 
|-
−
|{{c|a {{=}} rv}}||{{c|X&}}
+
|Effect
−
|If the allocator will <i>not</i> be replaced by move-assignment (see above), then {{ttb|T}} is {{named req|MoveInsertable}} into {{ttb|X}} and {{named req|MoveAssignable}}
+
|All existing elements of {{c|a}} are either move assigned to or destroyed.
−
|All existing elements of {{ttb|a}} are either move assigned to or destroyed; if {{ttb|a}} and {{ttb|rv}} do not refer the same object, {{ttb|a}} is equal to the value that {{ttb|rv}} had before the assignment|| linear
+
 
|-
 
|-
−
|{{c|a.swap(b)}}||void|| || Exchanges the contents of {{ttb|a}} and {{ttb|b}} || constant
+
|Postcondition
 +
|If {{c|a}} and {{c|rv}} do not refer the same object, {{c|a}} is equal to the value that {{c|rv}} had before the assignment.
 
|-
 
|-
 +
|{{c|a.swap(b)}}
 +
|{{c/core|void}}
 +
|Effect
 +
|Exchanges the contents of {{c|a}} and {{c|b}}.
 +
|Constant
 
|}
 
|}
  
 
===Notes===
 
===Notes===
−
Allocator-aware containers always call {{c|std::allocator_traits<A>::construct(m, p, args)}} to construct an object of type {{tt|T}} at {{tt|p}} using {{tt|args}}, with {{c|1=m == get_allocator()}}. {{rev inl|until=c++20|The default {{tt|construct}} in {{lc|std::allocator}} calls {{c|::new((void*)p) T(args)}}}}{{rev inl|since=c++20|{{lc|std::allocator}} has no {{tt|construct}} member and {{c|std::construct_at(p, args)}} is called when constructing elements}}, but specialized allocators may choose a different definition
+
Allocator-aware containers always call {{c|std::allocator_traits<A>::construct(m, p, args)}} to construct an object of type {{tt|T}} at {{c|p}} using {{c|args}}, with {{c|1=m == get_allocator()}}. {{rev inl|until=c++20|The default {{tt|construct}} in {{lc|std::allocator}} calls {{c|::new((void*)p) T(args)}}}}{{rev inl|since=c++20|{{lc|std::allocator}} has no {{tt|construct}} member and {{c|std::construct_at(p, args)}} is called when constructing elements}}, but specialized allocators may choose a different definition.
  
 
===Standard library===
 
===Standard library===
−
All standard library containers except {{lc|std::array}} are {{named req/core|AllocatorAwareContainer}}s:
+
All standard library string types and containers (except {{lc|std::array}} and {{lc|std::inplace_vector}}) are {{named req/core|AllocatorAwareContainer}}s:
 
* {{lc|std::basic_string}}
 
* {{lc|std::basic_string}}
 
* {{lc|std::deque}}
 
* {{lc|std::deque}}
Line 89: Line 153:
 
===Defect reports===
 
===Defect reports===
 
{{dr list begin}}
 
{{dr list begin}}
−
{{dr list item|wg=lwg|dr=2839|std=C++11|before=self move assignment of standard containers was not allowed|after=allowed but the result is unspecifed}}
+
{{dr list item|wg=lwg|dr=2839|std=C++11|before=self move assignment of standard containers was not allowed|after=allowed but the result is unspecified}}
 
{{dr list end}}
 
{{dr list end}}
  
 
{{langlinks|de|es|ja|ru|zh}}
 
{{langlinks|de|es|ja|ru|zh}}

Latest revision as of 22:18, 3 August 2024

 
C++
 
C++ named requirements
 

An AllocatorAwareContainer is a Container that holds an instance of an Allocator and uses that instance in all its member functions to allocate and deallocate memory and to construct and destroy objects in that memory (such objects may be container elements, nodes, or, for unordered containers, bucket arrays), except that std::basic_string specializations do not use the allocators for construction/destruction of their elements(since C++23).

The following rules apply to container construction:

  • Copy constructors of AllocatorAwareContainers obtain their instances of the allocator by calling std::allocator_traits<allocator_type>::select_on_container_copy_construction on the allocator of the container being copied.
  • Move constructors obtain their instances of allocators by move-constructing from the allocator belonging to the old container.
  • All other constructors take a const allocator_type& parameter.

The only way to replace an allocator is copy-assignment, move-assignment, and swap:

  • Copy-assignment will replace the allocator only if std::allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value is true.
  • Move-assignment will replace the allocator only if std::allocator_traits<allocator_type>::propagate_on_container_move_assignment::value is true.
  • Swap will replace the allocator only if std::allocator_traits<allocator_type>::propagate_on_container_swap::value is true. Specifically, it will exchange the allocator instances through an unqualified call to the non-member function swap, see Swappable.

Note: The behavior of swapping two containers with unequal allocators if propagate_on_container_swap is false is undefined.

  • The accessor get_allocator() obtains a copy of the allocator that was used to construct the container or installed by the most recent allocator replacement operation.

Contents

[edit] Requirements

A type satisfies AllocatorAwareContainer if it satisfies Container and, given the following types and values, the semantic and complexity requirements in the tables below are satisfied:

Type Definition
X an AllocatorAwareContainer type
T the value_type of X
A the allocator type used by X
Value Definition
a, b non-const lvalues of type X
c an lvalue of type const X
t an lvalue or a const rvalue of type X
rv a non-const rvalue of type X
m a value of type A

[edit] Types

Name  Type  Requirement
typename X::allocator_type  A X::allocator_type::value_type and X::value_type are the same.

[edit] Statements

Statement Semantics Complexity
X u;
X u = X(); 		Precondition A is DefaultConstructible. Constant
Postcondition  u.empty() and u.get_allocator() == A() are both true.
X u(m); Postcondition u.empty() and u.get_allocator() == m are both true. Constant
X u(t, m); Precondition T is CopyInsertable into X. Linear
Postcondition u == t and u.get_allocator() == m are both true.
X u(rv); Postcondition
  • u has the same elements as rv had before this construction.
  • The value of u.get_allocator() is the same as the value of rv.get_allocator() before this construction.
Constant
X u(rv, m); Precondition T is MoveInsertable into X.
  • Constant if m == rv.get_allocator() is true.
  • Otherwise linear.
Postcondition
  • u has the same elements, or copies of the elements, that rv had before this construction.
  • u.get_allocator() == m is true.

[edit] Expressions

Expression  Type  Semantics  Complexity 
c.get_allocator() A No direct semantic requirement. Constant
a = t X& Precondition T is CopyInsertable into X and CopyAssignable. Linear
Postcondition  a == t is true.
a = rv X& Precondition If the allocator will not be replaced by move-assignment (see above), then T is MoveInsertable into X and MoveAssignable. Linear
Effect All existing elements of a are either move assigned to or destroyed.
Postcondition If a and rv do not refer the same object, a is equal to the value that rv had before the assignment.
a.swap(b) void Effect Exchanges the contents of a and b. Constant

[edit] Notes

Allocator-aware containers always call std::allocator_traits<A>::construct(m, p, args) to construct an object of type T at p using args, with m == get_allocator(). The default construct in std::allocator calls ::new((void*)p) T(args)(until C++20)std::allocator has no construct member and std::construct_at(p, args) is called when constructing elements(since C++20), but specialized allocators may choose a different definition.

[edit] Standard library

All standard library string types and containers (except std::array and std::inplace_vector) are AllocatorAwareContainers:

[edit] Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR Applied to Behavior as published Correct behavior
LWG 2839 C++11 self move assignment of standard containers was not allowed allowed but the result is unspecified
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/named_req/AllocatorAwareContainer&oldid=174063"