Difference between revisions of "cpp/container/inplace vector"

Latest revision as of 14:26, 1 November 2024

Defined in header `<inplace_vector>`
template< class T, std::size_t N > struct inplace_vector;		(since C++26)

inplace_vector is a dynamically-resizable array with contiguous inplace storage. The elements of type T are stored and properly aligned within the object itself. The capacity of internal storage is fixed at compile-time and is equal to N.

The elements are stored contiguously, which means that elements can be accessed not only through iterators or random-access operator[], but also using offsets to regular pointers to elements. A pointer to an element of an inplace_vector may be passed to any function that expects a pointer to an element of a C-array.

The inplace_vector models Container, ReversibleContainer, ContiguousContainer, and SequenceContainer, including most of the optional sequence container requirements, except that the push_front, emplace_front, pop_front, and prepend_range member functions are not provided.

For any N, std::inplace_vector<T, N>::iterator and std::inplace_vector<T, N>::const_iterator meet the ConstexprIterator requirements.

If N > 0 and std::is_trivial_v<T> is false, then member functions of inplace_vector are not usable in constant expressions.

The specialization std::inplace_vector<T, 0> is a TrivialType and is empty.

Any member function of std::inplace_vector<T, N> that would cause insertion beyond the capacity N throws std::bad_alloc.

The complexity of common operations on inplace_vectors is as follows:

Random access to an element via operator[] or at() – constant: $𝓞(1)$ .
Insertion or removal of an element at the end – constant: $𝓞(1)$ .
Insertion or removal of elements at the end – linear in the number of elements inserted/removed: $𝓞(n)$ .
Insertion or removal of elements in the beginning or in the middle – linear in the number of elements inserted/removed plus the distance to the end of the vector: $𝓞(n)$ .

Type	Definition
`value_type`	`T`[edit]
`size_type`	std::size_t[edit]
`difference_type`	std::ptrdiff_t[edit]
`reference`	value_type&[edit]
`const_reference`	const value_type&[edit]
`pointer`	value_type*[edit]
`const_pointer`	const value_type*[edit]
`iterator`	implementation-defined LegacyRandomAccessIterator and `random_access_iterator` to `value_type`[edit]
`const_iterator`	implementation-defined LegacyRandomAccessIterator and `random_access_iterator` to const value_type[edit]
`reverse_iterator`	std::reverse_iterator<iterator>[edit]
`const_reverse_iterator`	std::reverse_iterator<const_iterator>[edit]

[edit] Member functions

(constructor)	constructs the `inplace_vector` (public member function) [edit]
(destructor)	destructs the `inplace_vector` (public member function) [edit]
operator=	assigns values to the container (public member function) [edit]
assign	assigns values to the container (public member function) [edit]
assign_range	assigns a range of values to the container (public member function) [edit]
Element access
at	access specified element with bounds checking (public member function) [edit]
operator[]	access specified element (public member function) [edit]
front	access the first element (public member function) [edit]
back	access the last element (public member function) [edit]
data	direct access to the underlying contiguous storage (public member function) [edit]
Iterators
begincbegin	returns an iterator to the beginning (public member function) [edit]
endcend	returns an iterator to the end (public member function) [edit]
rbegincrbegin	returns a reverse iterator to the beginning (public member function) [edit]
rendcrend	returns a reverse iterator to the end (public member function) [edit]
Size and capacity
empty	checks whether the container is empty (public member function) [edit]
size	returns the number of elements (public member function) [edit]
max_size [static]	returns the maximum possible number of elements (public static member function) [edit]
capacity [static]	returns the number of elements that can be held in currently allocated storage (public static member function) [edit]
resize	changes the number of elements stored (public member function) [edit]
reserve [static]	reserves storage (public static member function) [edit]
shrink_to_fit [static]	reduces memory usage by freeing unused memory (public static member function) [edit]
Modifiers
insert	inserts elements (public member function) [edit]
insert_range	inserts a range of elements (public member function) [edit]
emplace	constructs element in-place (public member function) [edit]
emplace_back	constructs an element in-place at the end (public member function) [edit]
try_emplace_back	tries to construct an element in-place at the end (public member function) [edit]
unchecked_emplace_back	unconditionally constructs an element in-place at the end (public member function) [edit]
push_back	adds an element to the end (public member function) [edit]
try_push_back	tries to add an element to the end (public member function) [edit]
unchecked_push_back	unconditionally adds an element to the end (public member function) [edit]
pop_back	removes the last element (public member function) [edit]
append_range	adds a range of elements to the end (public member function) [edit]
try_append_range	tries to add a range of elements to the end (public member function) [edit]
clear	clears the contents (public member function) [edit]
erase	erases elements (public member function) [edit]
swap	swaps the contents (public member function) [edit]

[edit] Non-member functions

std::swap(std::inplace_vector) (C++26)	specializes the std::swap algorithm (function template) [edit]
erase(std::inplace_vector)erase_if(std::inplace_vector) (C++26)	erases all elements satisfying specific criteria (function template) [edit]
operator==operator<=> (C++26)	lexicographically compares the values of two `inplace_vector`s (function template) [edit]

[edit] Notes

The number of elements in a inplace_vector may vary dynamically up to a fixed capacity because elements are stored within the object itself similarly to std::array. However, objects are initialized as they are inserted into inplace_vector unlike C arrays or std::array , which must construct all elements on instantiation.

inplace_vector is useful in environments where dynamic memory allocations are undesired.

Feature-test macro	Value	Std	Feature
`__cpp_lib_inplace_vector`	202406L	(C++26)	`std::inplace_vector`: dynamically-resizable vector with fixed capacity inplace storage

[edit] Example

Run this code

#include <algorithm>
#include <array>
#include <cassert>
#include <inplace_vector>
 
int main()
{
    std::inplace_vector<int, 4> v1{0, 1, 2};
    assert(v1.max_size() == 4);
    assert(v1.capacity() == 4);
    assert(v1.size() == 3);
    assert(std::ranges::equal(v1, std::array{0, 1, 2}));
    assert(v1[0] == 0);
    assert(v1.at(0) == 0);
    assert(v1.front() == 0);
    assert(*v1.begin() == 0);
    assert(v1.back() == 2);
    v1.push_back(3);
    assert(v1.back() == 3);
    assert(std::ranges::equal(v1, std::array{0, 1, 2, 3}));
    v1.resize(3);
    assert(std::ranges::equal(v1, std::array{0, 1, 2}));
    assert(v1.try_push_back(3) != nullptr);
    assert(v1.back() == 3);
    assert(v1.size() == 4);
    assert(v1.try_push_back(13) == nullptr); // no place
    assert(v1.back() == 3);
    assert(v1.size() == 4);
    v1.clear();
    assert(v1.size() == 0);
    assert(v1.empty());
}

[edit] See also

vector	dynamic contiguous array (class template) [edit]
array (C++11)	fixed-sized inplace contiguous array (class template) [edit]
deque	double-ended queue (class template) [edit]

[edit] External links

	`inplace_vector` — A reference implementation of P0843R14 (`std::inplace_vector`).
	`static_vector` — Boost.Container implements inplace vector as a standalone type with its own guarantees.
	`fixed_vector` — EASTL implements inplace vector via an extra template parameter.
	`small_vector` — Folly also implements inplace vector via an extra template parameter.
	`stack_alloc` — Howard Hinnant's Custom allocators that emulate `std::inplace_vector` on top of std::vector.

@@ Line 8: / Line 8: @@
 }}
-{{tt|inplace_vector}} is a dynamically-resizable array with contiguous inplace storage (that is, the elements of type {{tt|T}} are stored within the object itself) and with fixed at compile-time capacity {{tt|N}}.
+{{tt|inplace_vector}} is a dynamically-resizable array with contiguous inplace storage. The elements of type {{tt|T}} are stored and properly aligned within the object itself. The capacity of internal storage is fixed at compile-time and is equal to {{tt|N}}.
-{{tt|inplace_vector}} is useful in environments where dynamic memory allocations are undesired.
+The elements are stored contiguously, which means that elements can be accessed not only through iterators or random-access {{c/core|operator[]}}, but also using offsets to regular pointers to elements. A pointer to an element of an {{tt|inplace_vector}} may be passed to any function that expects a pointer to an element of a C-array.
-<!--DONE-->
-{{todo}}
-<!--TODO: Below is a mere copy from std::array. REPLACE!
-{{tt|std::inplace_vector}} is a container that encapsulates fixed size inplace_vectors.
+The {{tt|inplace_vector}} models {{named req|Container}}, {{named req|ReversibleContainer}}, {{named req|ContiguousContainer}}, and {{named req|SequenceContainer}}, including most of the [[cpp/named_req/SequenceContainer#Optional operations|optional sequence container requirements]], except that the {{tt|push_front}}, {{tt|emplace_front}}, {{tt|pop_front}}, and {{tt|prepend_range}} member functions are not provided.
-This container is an aggregate type with the same semantics as a struct holding a [[cpp/language/inplace_vector|C-style inplace_vector]] {{c|T[N]}} as its only non-static data member. Unlike a C-style inplace_vector, it doesn't decay to {{c|T*}} automatically. As an aggregate type, it can be initialized with [[cpp/language/aggregate initialization|aggregate-initialization]] given at most {{tt|N}} initializers that are convertible to {{tt|T}}: {{c|1=std::inplace_vector<int, 3> a = {1, 2, 3};}}.
+For any {{tt|N}}, {{c|std::inplace_vector<T, N>::iterator}} and {{c|std::inplace_vector<T, N>::const_iterator}} meet the {{named req|ConstexprIterator}} requirements.
-The struct combines the performance and accessibility of a C-style inplace_vector with the benefits of a standard container, such as knowing its own size, supporting assignment, random access iterators, etc.
+If {{c|N > 0}} and {{c|std::is_trivial_v<T>}} is {{c|false}}, then member functions of {{tt|inplace_vector}} are not {{lsd|cpp/language/constant expression#Usable in constant expressions}}.
-{{tt|std::inplace_vector}} satisfies the requirements of {{named req|Container}} and {{named req|ReversibleContainer}} except that default-constructed inplace_vector is not empty and that the complexity of swapping is linear, {{rev inl|since=c++17|satisfies the requirements of {{named req|ContiguousContainer}},}} and partially satisfies the requirements of {{named req|SequenceContainer}}.
+The specialization {{c|std::inplace_vector<T, 0>}} is a {{named req|TrivialType}} and is empty.
-There is a special case for a zero-length inplace_vector ({{tt|1=N == 0}}). In that case, {{c|
+Any member function of {{c|std::inplace_vector<T, N>}} that would cause insertion beyond the capacity {{tt|N}} throws {{lc|std::bad_alloc}}.
-=inplace_vector.begin() == inplace_vector.end()}}, which is some unique value. The effect of calling {{c|front()}} or {{c|back()}} on a zero-sized inplace_vector is undefined.
-An inplace_vector can also be used as a tuple of {{tt|N}} elements of the same type.
+The complexity of common operations on {{tt|inplace_vector}}s is as follows:
--->
+* Random access to an element via {{rlt|operator at|operator[]}} or {{rlt|at|at()}} &ndash; constant: {{math|𝓞(1)}}.
+* Insertion or removal of an element at the end &ndash; constant: {{math|𝓞(1)}}.
+* Insertion or removal of elements at the end &ndash; linear in the number of elements inserted/removed: {{math|𝓞(n)}}.
+* Insertion or removal of elements in the beginning or in the middle &ndash; linear in the number of elements inserted/removed plus the distance to the end of the vector: {{math|𝓞(n)}}.
 ===Iterator invalidation===
-{{todo}}
+{{tt|std::inplace_vector}} iterator invalidation guarantees differ from {{lc|std::vector}}:
-<!--TODO: A COPY from std::array
+* moving an {{tt|inplace_vector}} invalidates all iterators;
-As a rule, iterators to an inplace_vector are never invalidated throughout the lifetime of the inplace_vector. One should take note, however, that during {{rl|swap}}, the iterator will continue to point to the same inplace_vector element, and will thus change its value.
+* swapping two {{tt|inplace_vector}}s invalidates all iterators (during swap, the iterator will continue to point to the same array element, and may thus change its value).
--->
+The following member functions potentially invalidate iterators:
+{{rlt|operator{{=}}}},
+{{rlt|assign}},
+{{rlt|assign_range}},
+{{rlt|clear}},
+{{rlt|emplace}},
+{{rlt|erase}},
+{{rlt|insert}},
+{{rlt|insert_range}},
+{{rlt|pop_back}},
+{{rlt|resize}}, and
+{{rlt|swap}}.
+The following member functions potentially invalidate {{rlt|end}} iterator only:
+{{rlt|append_range}},
+{{rlt|emplace_back}},
+{{rlt|push_back}},
+{{rlt|try_append_range}},
+{{rlt|try_emplace_back}},
+{{rlt|try_push_back}},
+{{rlt|unchecked_emplace_back}}, and
+{{rlt|unchecked_push_back}}.
 ===Template parameters===
 {{par begin}}
-{{par|T|element type.<!--Must be a complete object type that is not an abstract class type.--> Must be {{named req|MoveConstructible}} and {{named req|MoveAssignable}}.}}
+{{par|T|element type. Must be {{named req|MoveConstructible}} and {{named req|MoveAssignable}}.}}
 {{par|N|capacity, i.e. the maximum number of elements in the {{tt|inplace_vector}} (might be {{c|0}}).}}
 {{par end}}
-{{todo|Complete the descriptions of template parameters.}}
 ===Member types===
 {{dsc begin}}
-{{dsc hitem|Member type|Definition}}
+{{dsc hitem|Type|Definition}}
 {{dsc inc|cpp/container/dsc value_type|inplace_vector}}
 {{dsc inc|cpp/container/dsc size_type|inplace_vector}}
@@ Line 102: / Line 120: @@
 {{dsc inc|cpp/container/dsc append_range|inplace_vector}}
 {{dsc inc|cpp/container/dsc try_append_range|inplace_vector}}
-{{dsc inc|cpp/container/dsc resize|inplace_vector}}
 {{dsc inc|cpp/container/dsc clear|inplace_vector}}
 {{dsc inc|cpp/container/dsc erase|inplace_vector}}
@@ Line 116: / Line 133: @@
 ===Notes===
-<!--TODO: Add motivation for inclusion of inplace_vector into the C++ standard. -->
+The number of elements in a {{tt|inplace_vector}} may vary dynamically up to a fixed capacity because elements are stored within the object itself similarly to {{lc|std::array}}. However, objects are initialized as they are inserted into {{tt|inplace_vector}} unlike C arrays or {{lc|std::array}} , which must construct all elements on instantiation.
+{{tt|inplace_vector}} is useful in environments where dynamic memory allocations are undesired.
-<!--CHECK, this is from `set#Notes`
-The member types iterator and const_iterator may be aliases to the same type. This means defining a pair of function overloads using the two types as parameter types may violate the One Definition Rule. Since iterator is convertible to const_iterator, a single function with a const_iterator as parameter type will work instead.
--->
 {{feature test macro|__cpp_lib_inplace_vector|std=C++26|value=202406L|{{tt|std::inplace_vector}}: dynamically-resizable vector with fixed capacity inplace storage}}
 ===Example===
-{{example}}<!--
 {{example
 |code=
+#include <algorithm>
+#include <array>
+#include <cassert>
 #include <inplace_vector>
-#include <iostream>
 int main()
 {
+    std::inplace_vector<int, 4> v1{0, 1, 2};
+    assert(v1.max_size() == 4);
+    assert(v1.capacity() == 4);
+    assert(v1.size() == 3);
+    assert(std::ranges::equal(v1, std::array{0, 1, 2}));
+    assert(v1[0] == 0);
+    assert(v1.at(0) == 0);
+    assert(v1.front() == 0);
+    assert(*v1.begin() == 0);
+    assert(v1.back() == 2);
+    v1.push_back(3);
+    assert(v1.back() == 3);
+    assert(std::ranges::equal(v1, std::array{0, 1, 2, 3}));
+    v1.resize(3);
+    assert(std::ranges::equal(v1, std::array{0, 1, 2}));
+    assert(v1.try_push_back(3) != nullptr);
+    assert(v1.back() == 3);
+    assert(v1.size() == 4);
+    assert(v1.try_push_back(13) == nullptr); // no place
+    assert(v1.back() == 3);
+    assert(v1.size() == 4);
+    v1.clear();
+    assert(v1.size() == 0);
+    assert(v1.empty());
 }
-|output=
+}}
-}}-->
 ===See also===
@@ Line 145: / Line 185: @@
 ===External links===
 {{elink begin}}
-{{elink|[https://www.boost.org/doc/libs/release/doc/html/boost/container/static_vector.html Boost.Container: {{tt|static_vector}}] implements inplace vector as a standalone type with its own guarantees.}}
+{{elink|[https://godbolt.org/z/5P78aG5xE {{tt|inplace_vector}}] &mdash; A reference implementation of {{stddoc|P0843R14}} ({{tt|std::inplace_vector}}).}}
-{{elink|[https://github.com/questor/eastl/blob/master/fixed_vector.h#L71 EASTL: {{tt|fixed_vector}}] implements inplace vector via an extra template parameter.}}
+{{elink|[https://www.boost.org/doc/libs/release/doc/html/container/non_standard_containers.html#container.non_standard_containers.static_vector {{tt|static_vector}}] &mdash; Boost.Container implements inplace vector as a standalone type with its own guarantees.}}
-{{elink|[https://github.com/facebook/folly/blob/master/folly/docs/small_vector.md Folly: {{tt|small_vector}}] also implements inplace vector via an extra template parameter.}}
+{{elink|[https://github.com/questor/eastl/blob/master/fixed_vector.h#L71 {{tt|fixed_vector}}] &mdash; EASTL implements inplace vector via an extra template parameter.}}
-{{elink|[https://godbolt.org/z/5P78aG5xE Compiler Explorer] &mdash; A reference implementation of {{stddoc|P0843R14}} ({{tt|std::inplace_vector}}).}}
+{{elink|[https://github.com/facebook/folly/blob/master/folly/docs/small_vector.md {{tt|small_vector}}] &mdash; Folly also implements inplace vector via an extra template parameter.}}
+{{elink|[https://howardhinnant.github.io/stack_alloc.html {{tt|stack_alloc}}] &mdash; Howard Hinnant's Custom allocators that emulate {{tt|std::inplace_vector}} on top of {{lc|std::vector}}.}}
 {{elink end}}
 {{langlinks|de|es|fr|it|ja|pl|pt|ru|zh}}

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Metaprogramming library (C++11)
Diagnostics library
General utilities library
Strings library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Numerics library
Localizations library
Input/output library
Filesystem library (C++17)
Regular expressions library (C++11)
Concurrency support library (C++11)
Execution support library (C++26)
Technical specifications
Symbols index
External libraries

Sequence
array (C++11)
vector
vector<bool>
inplace_vector (C++26)
deque
forward_list (C++11)
list
Associative
set
multiset
map
multimap
Unordered associative
unordered_set (C++11)
unordered_multiset (C++11)
unordered_map (C++11)
unordered_multimap (C++11)
Adaptors
stack
queue
priority_queue
flat_set (C++23)
flat_multiset (C++23)
flat_map (C++23)
flat_multimap (C++23)
Views
span (C++20)
mdspan (C++23)
Tables
Iterator invalidation
Member function table
Non-member function table

cppreference.com

Namespaces

Variants

Views

Actions

Difference between revisions of "cpp/container/inplace vector"

Latest revision as of 14:26, 1 November 2024

Contents

[edit] Iterator invalidation

[edit] Template parameters

[edit] Member types

[edit] Member functions

Element access

Iterators

Size and capacity

Modifiers

[edit] Non-member functions

[edit] Notes

[edit] Example

[edit] See also

[edit] External links

Navigation

Toolbox

T	-	element type. Must be MoveConstructible and MoveAssignable.
N	-	capacity, i.e. the maximum number of elements in the `inplace_vector` (might be 0).