Namespaces
Variants
Views
Actions

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

From cppreference.com
< cpp‎ | named req
m (→‎Methods and operators: fmt)
(Added LWG issue #276 DR (part 1/2).)
Line 5: Line 5:
  
 
===Requirements===
 
===Requirements===
−
* {{ttb|C}} container type;
+
* {{tt|T}}, an element type;
−
* {{ttb|T}} element type;
+
* {{tt|C}}, a {{named req/core|Container}} type containing elements of type {{tt|T}};
−
* {{ttb|a}}, {{ttb|b}} objects of type {{ttb|C}}.
+
* {{tt|a}} and {{tt|b}}, objects of type {{tt|C}};
−
* {{ttb|rv}} a prvalue expression of type {{ttb|C}}.
+
* {{tt|rv}}, a prvalue expression of type {{tt|C}}.
  
 
====Types====
 
====Types====
 
{|class=wikitable
 
{|class=wikitable
−
!name||type||notes
+
!Name||Type||Requirements
 
|-
 
|-
−
|{{tt|value_type}}||T||{{named req|Erasable}}
+
|{{tt|value_type}}||{{tt|T}}||{{rev inl|until=c++11|{{named req|CopyConstructible}}}}{{rev inl|since=c++11|{{named req|Erasable}}}}
 
|-
 
|-
−
|{{tt|reference}}||T&||
+
|{{tt|reference}}||{{tt|T&}}||
 
|-
 
|-
−
|{{tt|const_reference}}||const T&||
+
|{{tt|const_reference}}||{{tt|const T&}}||
 
|-
 
|-
−
|{{tt|iterator}}||iterator pointing to T||{{named req|ForwardIterator}}<br/>convertible to {{ttb|const_iterator}}
+
|{{tt|iterator}}||iterator pointing to {{tt|T}}||{{named req|ForwardIterator}}<br/>convertible to {{tt|const_iterator}}
 
|-
 
|-
−
|{{tt|const_iterator}}||constant iterator pointing to T||{{named req|ForwardIterator}}
+
|{{tt|const_iterator}}||constant iterator pointing to {{tt|T}}||{{named req|ForwardIterator}}
 
|-
 
|-
 
|{{tt|difference_type}}||signed integer
 
|{{tt|difference_type}}||signed integer
−
|must be the same as {{ttb|[[cpp/iterator/iterator_traits|iterator_traits]]::difference_type}} for {{ttb|iterator}} and {{ttb|const_iterator}}
+
|must be the same as {{tt|[[cpp/iterator/iterator_traits|iterator_traits]]::difference_type}} for {{tt|iterator}} and {{tt|const_iterator}}
 
|-
 
|-
−
|{{tt|size_type}}||unsigned integer||large enough to represent all positive values of {{ttb|difference_type}}
+
|{{tt|size_type}}||unsigned integer||large enough to represent all positive values of {{tt|difference_type}}
 
|}
 
|}
  
 
====Methods and operators====
 
====Methods and operators====
 
{|class=wikitable
 
{|class=wikitable
−
!expression||return type||semantics||conditions||complexity
+
!Expression||Return type||Semantics||Conditions||Complexity
 
|-
 
|-
−
|{{c|C()}}||C||creates an empty container|| Post: {{tt|1=C().empty() == true}}||Constant
+
|{{c|C()}}||{{tt|C}}||creates an empty container|| Post: {{c|C().empty()}}<br>{{c|1=== true}}||Constant
 
|-
 
|-
−
|{{c|C(a)}}||C||creates a copy of {{ttb|a}}||Pre: T must be {{named req|CopyInsertable}}<br/>Post: {{tt|1=a == C(a)}}||Linear
+
|{{c|C(a)}}||{{tt|C}}||creates a copy of {{c|a}}||Pre: T must be {{named req|CopyInsertable}}<br/>Post: {{c|1=a == C(a)}}||Linear
 
|-
 
|-
−
|{{c|C(rv)}}<br>{{mark since c++11}}||C||moves {{ttb|rv}}||Post: equal to the value {{ttb|rv}} had before this construction||Constant<ref name="array">Linear for {{lc|std::array}}</ref>
+
|{{c|C(rv)}}<br>{{mark since c++11}}||C||moves {{c|rv}}||Post: equal to the value {{c|rv}} had before this construction||Constant<ref name="array">Linear for {{lc|std::array}}</ref>
 
|-
 
|-
−
|{{c|1=a = b}}||C&||destroys or copy-assigns all elements of {{ttb|a}} from elements of {{ttb|b}}||Post: {{tt|1=a == b}}||Linear
+
|{{c|1=a = b}}||{{tt|C&}}||destroys or copy-assigns all elements of {{c|a}} from elements of {{c|b}}||Post: {{c|1=a == b}}||Linear
 
|-
 
|-
−
|{{c|1=a = rv}}||C&||destroys or move-assigns all elements of {{ttb|a}} from elements of {{ttb|rv}}||Post: if {{ttb|a}} and {{ttb|rv}} do not refer the same object, {{ttb|a}} is equal to the value {{ttb|rv}} had before this assignment||Linear
+
|{{c|1=a = rv}}||{{tt|C&}}||destroys or move-assigns all elements of {{c|a}} from elements of {{c|rv}}||Post: if {{c|a}} and {{c|rv}} do not refer the same object, {{c|a}} is equal to the value {{c|rv}} had before this assignment||Linear
 
|-
 
|-
−
|{{c|a.~C()}}||{{tt|void}}||destroys all elements of {{ttb|a}} and frees all memory||  ||Linear
+
|{{c|a.~C()}}||{{c|void}}||destroys all elements of {{c|a}} and frees all memory||  ||Linear
 
|-
 
|-
−
|{{c|a.begin()}}||{{tt|(const_)iterator}}||Iterator to the first element of {{ttb|a}}|| ||Constant
+
|{{c|a.begin()}}||{{tt|(const_)iterator}}||Iterator to the first element of {{c|a}}|| ||Constant
 
|-
 
|-
−
|{{c|a.end()}}||{{tt|(const_)iterator}}||Iterator to one past the last element of {{ttb|a}}||  ||Constant
+
|{{c|a.end()}}||{{tt|(const_)iterator}}||Iterator to one past the last element of {{c|a}}||  ||Constant
 
|-
 
|-
 
|{{c|a.cbegin()}}<br>{{mark since c++11}}||{{tt|const_iterator}}||{{c|const_cast<const C&>(a).begin()}}|| ||Constant
 
|{{c|a.cbegin()}}<br>{{mark since c++11}}||{{tt|const_iterator}}||{{c|const_cast<const C&>(a).begin()}}|| ||Constant
Line 54: Line 54:
 
|{{c|a.cend()}}<br>{{mark since c++11}}||{{tt|const_iterator}}||{{c|const_cast<const C&>(a).end()}}|| ||Constant
 
|{{c|a.cend()}}<br>{{mark since c++11}}||{{tt|const_iterator}}||{{c|const_cast<const C&>(a).end()}}|| ||Constant
 
|-
 
|-
−
|{{c|1=a == b}} || convertible to {{c|bool}} || {{rev inl|until=c++14|noborder=true|{{c|1=a.size() == b.size() &&
+
|{{c|1=a == b}} || convertible to {{c|bool}} || {{rev begin}}
−
std::equal(a.begin(), a.end(), b.begin())}}<br>}}{{rev inl|since=c++14|noborder=true|{{c|std::equal(a.begin(), a.end(), b.begin(), b.end())}}<br>}} ||Pre: {{tt|T}} must be {{named req|EqualityComparable}} || Constant<ref>always linear for {{lc|std::forward_list}}</ref> if {{tt|1=a.size() != b.size()}}, linear otherwise<!-- LWG2257 -->
+
{{rev|until=c++14|{{c|1=a.size() == b.size() &&
 +
    std::equal(a.begin(),
 +
        a.end(), b.begin())}}}}
 +
{{rev|since=c++14|{{c|std::equal(a.begin(), a.end(),
 +
    b.begin(), b.end())}}}}
 +
{{rev end}}
 +
|| Pre: {{tt|T}} must be {{named req|EqualityComparable}} || Constant<ref>always linear for {{lc|std::forward_list}}</ref> if {{c|1=a.size() !=}}<br>{{c|b.size()}}, linear otherwise<!-- LWG2257 -->
 
|-
 
|-
 
|{{c|1=a != b}} || convertible to {{c|bool}} || {{c|1=!(a == b)}} || || Linear
 
|{{c|1=a != b}} || convertible to {{c|bool}} || {{c|1=!(a == b)}} || || Linear
 
|-
 
|-
−
|{{c|a.swap(b)}} || {{tt|void}} || exchanges the values of {{ttb|a}} and {{ttb|b}} ||  
+
|{{c|a.swap(b)}} || {{c|void}} || exchanges the values of {{c|a}} and {{c|b}} ||  
 
| Constant<ref name="array">{{mark since c++11}} Linear for {{lc|std::array}}</ref><ref name="should">{{mark until c++11}} Not strictly constant</ref>
 
| Constant<ref name="array">{{mark since c++11}} Linear for {{lc|std::array}}</ref><ref name="should">{{mark until c++11}} Not strictly constant</ref>
 
|-
 
|-
−
|{{c|swap(a, b)}} || {{tt|void}} || {{c|a.swap(b)}} || || Constant<ref name="array"/>
+
|{{c|swap(a, b)}} || {{c|void}} || {{c|a.swap(b)}} || || Constant<ref name="array"/>
 
|-
 
|-
 
|{{c|a.size()}} || {{tt|size_type}} || {{c|std::distance(a.begin(), a.end())}} || || Constant<ref name="should" />
 
|{{c|a.size()}} || {{tt|size_type}} || {{c|std::distance(a.begin(), a.end())}} || || Constant<ref name="should" />
 
|-
 
|-
−
|{{c|a.max_size()}} || {{tt|size_type}} || {{c|b.size()}} where {{ttb|b}} is the largest possible container || || Constant<ref name="should" />
+
|{{c|a.max_size()}} || {{tt|size_type}} || {{c|b.size()}} where {{c|b}} is the largest possible container || || Constant<ref name="should" />
 
|-
 
|-
 
|{{c|a.empty()}} || convertible to {{c|bool}} || {{c|1=a.begin() == a.end()}} || || Constant
 
|{{c|a.empty()}} || convertible to {{c|bool}} || {{c|1=a.begin() == a.end()}} || || Constant
Line 80: Line 86:
  
 
===Container data races===
 
===Container data races===
−
see [[cpp/container#Thread_safety|container thread safety]]
+
see [[cpp/container#Thread safety|container thread safety]]
  
 
===Other requirements===
 
===Other requirements===
Line 96: Line 102:
 
{{dr list begin}}
 
{{dr list begin}}
 
{{dr list item|wg=lwg|dr=179|std=C++98|before={{tt|iterator}} and {{tt|const_iterator}} types might be incomparable|after=required to be comparable}}
 
{{dr list item|wg=lwg|dr=179|std=C++98|before={{tt|iterator}} and {{tt|const_iterator}} types might be incomparable|after=required to be comparable}}
−
{{dr list item|wg=lwg|dr=2263|std=C++11|before=resolution of LWG179 was accidentally dropped in C++11|after=restored}}
+
{{dr list item|wg=lwg|dr=276|std=C++98|before={{tt|T}} was required to be {{named req|CopyAssignable}}|after={{tt|T}} is required to be {{named req|CopyConstructible}}}}
 +
{{dr list item|wg=lwg|dr=2263|std=C++11|before=the resolution of {{lwg|179}} was accidentally dropped in C++11|after=restored}}
 
{{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 unspecifed}}
 
{{dr list end}}
 
{{dr list end}}
  
 
===See also===
 
===See also===
−
 
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc see cpp | cpp/container | Containers library}}
+
{{dsc see cpp|cpp/container|Containers library}}
 
{{dsc end}}
 
{{dsc end}}
  
 
{{langlinks|de|es|fr|it|ja|pt|ru|zh}}
 
{{langlinks|de|es|fr|it|ja|pt|ru|zh}}

Revision as of 21:41, 7 November 2022

 
C++
 
C++ named requirements
 

A Container is an object used to store other objects and taking care of the management of the memory used by the objects it contains.

Contents

Requirements

  • T, an element type;
  • C, a Container type containing elements of type T;
  • a and b, objects of type C;
  • rv, a prvalue expression of type C.

Types

Name Type Requirements
value_type T CopyConstructible(until C++11)Erasable(since C++11)
reference T&
const_reference const T&
iterator iterator pointing to T LegacyForwardIterator
convertible to const_iterator
const_iterator constant iterator pointing to T LegacyForwardIterator
difference_type signed integer must be the same as iterator_traits::difference_type for iterator and const_iterator
size_type unsigned integer large enough to represent all positive values of difference_type

Methods and operators

Expression Return type Semantics Conditions Complexity
C() C creates an empty container Post: C().empty()
== true		 Constant
C(a) C creates a copy of a Pre: T must be CopyInsertable
Post: a == C(a)		 Linear
C(rv)
(since C++11)		 C moves rv Post: equal to the value rv had before this construction Constant[1]
a = b C& destroys or copy-assigns all elements of a from elements of b Post: a == b Linear
a = rv C& destroys or move-assigns all elements of a from elements of rv Post: if a and rv do not refer the same object, a is equal to the value rv had before this assignment Linear
a.~C() void destroys all elements of a and frees all memory Linear
a.begin() (const_)iterator Iterator to the first element of a Constant
a.end() (const_)iterator Iterator to one past the last element of a Constant
a.cbegin()
(since C++11)		 const_iterator const_cast<const C&>(a).begin() Constant
a.cend()
(since C++11)		 const_iterator const_cast<const C&>(a).end() Constant
a == b convertible to bool
a.size() == b.size() &&

    std::equal(a.begin(),

        a.end(), b.begin())		 (until C++14)
std::equal(a.begin(), a.end(),
    b.begin(), b.end())		 (since C++14)
 Pre: T must be EqualityComparable Constant[2] if a.size() !=
b.size(), linear otherwise
a != b convertible to bool !(a == b) Linear
a.swap(b) void exchanges the values of a and b Constant[1][3]
swap(a, b) void a.swap(b) Constant[1]
a.size() size_type std::distance(a.begin(), a.end()) Constant[3]
a.max_size() size_type b.size() where b is the largest possible container Constant[3]
a.empty() convertible to bool a.begin() == a.end() Constant
notes
  1. ↑ 1.0 1.1 1.2 Linear for std::array
  2. ↑ always linear for std::forward_list
  3. ↑ 3.0 3.1 3.2 (until C++11) Not strictly constant

Given

  • i and j, objects of a container's iterator type,

in the expressions i == j, i != j, i < j, i <= j, i >= j, i > j, i - j, either or both may be replaced by an object of the container's const_iterator type referring to the same element with no change in semantics.

Container data races

see container thread safety

Other requirements

C
T

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 179 C++98 iterator and const_iterator types might be incomparable required to be comparable
LWG 276 C++98 T was required to be CopyAssignable T is required to be CopyConstructible
LWG 2263 C++11 the resolution of LWG issue 179 was accidentally dropped in C++11 restored
LWG 2839 C++11 self move assignment of standard containers was not allowed allowed but the result is unspecifed

See also

C++ documentation for Containers library
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/named_req/Container&oldid=144875"