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

Latest revision as of 14:26, 1 November 2024

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).

[edit] Iterator invalidation

std::inplace_vector iterator invalidation guarantees differ from std::vector:

• moving an inplace_vector invalidates all iterators;
• swapping two inplace_vectors 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: operator=, assign, assign_range, clear, emplace, erase, insert, insert_range, pop_back, resize, and swap.

The following member functions potentially invalidate end iterator only: append_range, emplace_back, push_back, try_append_range, try_emplace_back, try_push_back, unchecked_emplace_back, and unchecked_push_back.

[edit] Template parameters

[edit] Member types

[edit] Member functions

[edit] Non-member functions

[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.

[edit] Example

#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

[edit] External links