10
\$\begingroup\$

I decided to write my own vector class template for learning purposes. My main goal was a correct interpretation of C++20 standard (as of n4810).

I took some liberties and decided to use concepts instead of plain typenames for iterators instead of SFINAE. On the other hand, I decided against Empty Base Class optimization of allocator for the sake of simplicity.

I think I managed to get most things right. The thing that bothers me the most is exception safety. Most of it is implemented inside Move and Rollback member functions. The standardese there was really hard to parse so you may want to inspect them more closely.

In the future I plan to port all named requirements to concepts, if anyone has suggestions which ones can be swapped for concepts that are already in C++20, you're welcome.

Body is limited to 65536 characters; you entered 66294. Ugh, gotta trim stuff. Removed repeating wording in [vector.modifiers].

Vector.h

/// \file
/// \brief Header file that describes the Vector class template.
/// \author Lyberta
/// \copyright GNU GPLv3 or any later version.

#pragma once

#include <memory>

#include "Iterator.h" // For iterator concepts

namespace ftz::General
{

/// \brief A vector class template compatible with std::vector.
/// \details Vector is a sequence container that stores its elements
/// contiguously.
/// \tparam T Type of elements in a vector.
/// \tparam Allocator Allocator used to manage memory.

template <typename T, typename Allocator = std::allocator<T>>
class Vector final
{
public:
    /// \brief Type of elements in a vector.
    using value_type = T;

    /// \brief Type of the allocator used to manage memory.
    using allocator_type = Allocator;

    /// \brief Type of pointers used by the allocator.
    using pointer = typename std::allocator_traits<Allocator>::pointer;

    /// \brief Type of pointers to const used by the allocator.
    using const_pointer =
        typename std::allocator_traits<Allocator>::const_pointer;

    /// \brief Type of references to elements of a vector.
    using reference = value_type&;

    /// \brief Type of references to constant elements of a vector.
    using const_reference = const value_type&;

    /// \brief Type used to hold the size of the vector.
    using size_type = typename std::allocator_traits<Allocator>::size_type;

    /// \brief Type used to hold the difference between iterators.
    using difference_type =
        typename std::allocator_traits<Allocator>::difference_type;

    /// \brief Forward iterator type.
    using iterator = pointer;

    /// \brief Constant forward iterator type.
    using const_iterator = const_pointer;

    /// \brief Reverse iterator type.
    using reverse_iterator = std::reverse_iterator<iterator>;

    /// \brief Constant reverse iterator type.
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    /// \brief Default constructor.
    /// \pre Allocator is Cpp17DefaultConstructible.
    Vector() noexcept(noexcept(Allocator{}));

    /// \brief Constructors an empty vector using the specified allocator.
    /// \param[in] allocator Allocator to copy.
    explicit Vector(const Allocator& allocator);

    /// \brief Constructs a vector with the specified amount of default
    /// inserted elements using the specified allocator.
    /// \pre [vector.cons] T is Cpp17DefaultInsertable into Vector.
    /// \param[in] amount Amount of elements to construct.
    /// \param[in] allocator Allocator to copy.
    explicit Vector(size_type amount, const Allocator& allocator = Allocator{});

    /// \brief Constructs a vector with the specified amount of the given value.
    /// \pre [sequence.reqmts] T is Cpp17CopyInsertable into Vector.
    /// \param[in] amount Amount of values to construct.
    /// \param[in] value Value to fill the vector with.
    /// \param[in] allocator Allocator to copy.
    Vector(size_type amount, const T& value, const Allocator& allocator =
        Allocator{});

    /// \brief Constructs a vector from values pointed to by the range [first,
    /// last).
    /// \pre [sequence.reqmts] T is Cpp17EmplaceConstructible and
    /// Cpp17MoveInsertable into Vector.
    /// \tparam I Input iterator type.
    /// \param[in] first Iterator to the beginning of the range.
    /// \param[in] last Iterator past the end of the range.
    /// \param[in] allocator Allocator to copy.
    template <InputIterator I>
    Vector(I first, I last, const Allocator& allocator = Allocator{});

    /// \brief Constructs a vector from values pointed to by the range [first,
    /// last).
    /// \pre [sequence.reqmts] T is Cpp17EmplaceConstructible into Vector.
    /// \tparam I Forward iterator type.
    /// \param[in] first Iterator to the beginning of the range.
    /// \param[in] last Iterator past the end of the range.
    /// \param[in] allocator Allocator to copy.
    template <ForwardIterator I>
    Vector(I first, I last, const Allocator& allocator = Allocator{});

    /// \brief Copy constructor.
    /// \pre [container.requirements.general] T is Cpp17CopyInsertable into
    /// Vector.
    /// \param[in] other Vector to copy from.
    Vector(const Vector& other);

    /// \brief Move constructor.
    /// \param[in] other Vector to move from.
    Vector(Vector&& other) noexcept;

    /// \brief Constructs a vector with the copies of elements from the other
    /// vector using the specified allocator.
    /// \pre [container.requirements.general] T is Cpp17CopyInsertable into
    /// Vector.
    /// \param[in] other Vector to copy from.
    /// \param[in] allocator Allocator to copy.
    Vector(const Vector& other, const Allocator& allocator);

    /// \brief Constructs a vector by moving elements from the other vector
    /// using the specified allocator.
    /// \pre [container.requirements.general] T is Cpp17MoveInsertable into
    /// Vector.
    /// \param[in] other Vector to move from.
    /// \param[in] allocator Allocator to copy.
    Vector(Vector&& other, const Allocator& new_allocator);

    /// \brief Constructs a vector from the list of values using the specified
    /// allocator.
    /// \pre [sequence.reqmts] T is Cpp17EmplaceConstructible into Vector.
    /// \param[in] values Values to copy.
    /// \param[in] allocator Allocator to copy.
    Vector(std::initializer_list<T> values, const Allocator& allocator =
        Allocator{});

    /// \brief Copy assignment operator.
    /// \pre [container.requirements.general] T is Cpp17CopyInsertable into
    /// Vector and Cpp17CopyAssignable.
    /// \param[in] other Vector to copy from.
    /// \return Reference to this vector.
    Vector& operator=(const Vector& other);

    /// \brief Move assignment operator.
    /// \pre [container.requirements.general] If std::allocator_traits<
    /// allocator_type>::propagate_on_container_move_assignment::value is false,
    /// T is Cpp17MoveInsertable into Vector and Cpp17MoveAssignable.
    /// \param[in,out] other Vector to move from.
    /// \return Reference to this vector.
    Vector& operator=(Vector&& other) noexcept(
        std::allocator_traits<Allocator>::
        propagate_on_container_move_assignment::value ||
        std::allocator_traits<Allocator>::is_always_equal::value);

    /// \brief Assigns a list of values to the vector.
    /// \pre [sequence.reqmts] T is Cpp17CopyInsertable into Vector and
    /// Cpp17CopyAssignable.
    /// \param[in] values Values to assign.
    /// \return Reference to this vector.
    Vector& operator=(std::initializer_list<T> values);

    /// \brief Destructor.
    ~Vector();

    /// \brief Assigns values pointed to by the range [first, last) to the
    /// vector.
    /// \pre [sequence.reqmts] T is Cpp17EmplaceConstructible, assignable from
    /// *first and Cpp17MoveInsertable into Vector.
    /// \tparam I Input iterator type.
    /// \param[in] first Iterator to the beginning of the range.
    /// \param[in] last Iterator past the end of the range.
    template <InputIterator I>
    void assign(I first, I last);

    /// \brief Assigns values pointed to by the range [first, last) to the
    /// vector.
    /// \pre [sequence.reqmts] T is Cpp17EmplaceConstructible into Vector and
    /// assignable from *first.
    /// \tparam I Forward iterator type.
    /// \param[in] first Iterator to the beginning of the range.
    /// \param[in] last Iterator past the end of the range.
    template <ForwardIterator I>
    void assign(I first, I last);

    /// \brief Assings the specified amount of the given value to the vector.
    /// \pre [sequence.reqmts] T is Cpp17CopyInsertable into Vector and
    /// Cpp17CopyAssignable.
    /// \param[in] amount Amount of values to assign.
    /// \param[in] value Value to fill the vector with.
    void assign(size_type amount, const T& value);

    /// \brief Assigns a list of values to the vector.
    /// \pre [sequence.reqmts] T is Cpp17EmplaceConstructible into Vector and
    /// assignable from T&.
    /// \param[in] values Values to assign.
    void assign(std::initializer_list<T> values);

    /// \brief Returns the allocator of the vector.
    /// \return Allocator of the vector.
    allocator_type get_allocator() const noexcept;

    // Iterators

    /// \brief Returns an iterator to the first element in the vector.
    /// \return Iterator to the first element in the vector.
    iterator begin() noexcept;

    /// \brief Returns a constant iterator to the first element in the vector.
    /// \return Constant iterator to the first element in the vector.
    const_iterator begin() const noexcept;

    /// \brief Returns an iterator to the position after the last element in the
    /// vector.
    /// \return Iterator to the position after the last element in the vector.
    iterator end() noexcept;

    /// \brief Returns a constant iterator to the position after the last
    /// element in the vector.
    /// \return Constant iterator to the position after the last element in the
    /// vector.
    const_iterator end() const noexcept;

    /// \brief Returns a reverse iterator to the first element in the reversed
    /// vector.
    /// \return Reverse iterator to the first element in the reversed vector.
    reverse_iterator rbegin() noexcept;

    /// \brief Returns a constant reverse iterator to the first element in the
    /// reversed vector.
    /// \return Constant reverse iterator to the first element in the reversed
    /// vector.
    const_reverse_iterator rbegin() const noexcept;

    /// \brief Returns a reverse iterator to the position after the last element
    /// in the reversed vector.
    /// \return Reverse iterator to the position after the last element in the
    /// reversed vector.
    reverse_iterator rend() noexcept;

    /// \brief Returns a constant reverse iterator to the position after the
    /// last element in the reversed vector.
    /// \return Constant reverse iterator to the position after the last element
    /// in the reversed vector.
    const_reverse_iterator rend() const noexcept;

    /// \brief Returns a constant iterator to the first element in the vector.
    /// \return Constant iterator to the first element in the vector.
    const_iterator cbegin() const noexcept;

    /// \brief Returns a constant iterator to the position after the last
    /// element in the vector.
    /// \return Constant iterator to the position after the last element in the
    /// vector.
    const_iterator cend() const noexcept;

    /// \brief Returns a constant reverse iterator to the first element in the
    /// reversed vector.
    /// \return Constant reverse iterator to the first element in the reversed
    /// vector.
    const_reverse_iterator crbegin() const noexcept;

    /// \brief Returns a constant reverse iterator to the position after the
    /// last element in the reversed vector.
    /// \return Constant reverse iterator to the position after the last element
    /// in the reversed vector.
    const_reverse_iterator crend() const noexcept;

    // Capacity

    /// \brief Checks if the vector contains any elements.
    /// \return True if there are no elements, false otherwise.
    [[nodiscard]] bool empty() const noexcept;

    /// \brief Returns the amount of elements in the vector.
    /// \return Amount of elements in the vector.
    size_type size() const noexcept;

    /// \brief Returns the maximum possible size of the vector.
    /// \return Maximum possible size of the vector.
    size_type max_size() const noexcept;

    /// \brief Returns the capacity of the vector.
    /// \return Capacity of the vector.
    size_type capacity() const noexcept;

    /// \brief Changes the amount of elements in the vector.
    /// \pre [vector.capacity] T is Cpp17MoveInsertable and
    /// Cpp17DefaultInsertable into Vector.
    /// \param[in] new_size Amount of elements to contain.
    /// \throw std::length_error If new size is greater than max_size().
    /// \note Exception safety: [vector.capacity] If an exception is thrown
    /// other than by the move constructor of a non-Cpp17CopyInsertable T there
    /// are no effects.
    void resize(size_type new_size);

    /// \brief Changes the amount of elements in the vector.
    /// \pre [vector.capacity] T is Cpp17CopyInsertable into Vector.
    /// \param[in] new_size Amount of elements to contain.
    /// \param[in] value Value to initialize new elements with.
    /// \throw std::length_error If new size is greater than max_size().
    /// \note Exception safety: [vector.capacity] Requires strong exception
    /// safety guarantee.
    void resize(size_type new_size, const T& value);

    /// \brief Reserves the space for new elements.
    /// \pre [vector.capacity] T is Cpp17MoveInsertable into Vector.
    /// \param[in] new_capacity Amount of elements to reserve space for.
    /// \throw std::length_error If requested capacity is greater than
    /// max_size().
    /// \note Exception safety: [vector.capacity] If an exception is thrown
    /// other than by the move constructor of a non-Cpp17CopyInsertable type,
    /// there are no effects.
    void reserve(size_type new_capacity);

    /// \brief Requests the removal of unused capacity.
    /// \pre [vector.capacity] T is Cpp17MoveInsertable into Vector.
    /// \note Exception safety: If an exception is thrown other than by the move
    /// constructor of a non-Cpp17CopyInsertable T there are no effects.
    void shrink_to_fit();

    // Element access

    /// \brief Returns a reference to the element at the specified index.
    /// \param[in] index Index of the element.
    /// \return Reference to the element at the specified index.
    /// \note If the index is greater than or equal to size(), the behavior is
    /// undefined.
    reference operator[](size_type index);

    /// \brief Returns a reference to the constant element at the specified
    /// index.
    /// \param[in] index Index of the element.
    /// \return Reference to the constant element at the specified index.
    /// \note If the index is greater than or equal to size(), the behavior is
    /// undefined.
    const_reference operator[](size_type index) const;

    /// \brief Returns a reference to the element at the specified index.
    /// \param[in] index Index of the element.
    /// \return Reference to the element at the specified index.
    /// \throw std::out_of_range If the index is greater than or equal to
    /// size().
    reference at(size_type index);

    /// \brief Returns a reference to the constant element at the specified
    /// index.
    /// \param[in] index Index of the element.
    /// \return Reference to the constant element at the specified index.
    /// \throw std::out_of_range If the index is greater than or equal to
    /// size().
    const_reference at(size_type index) const;

    /// \brief Returns a reference to the first element in the vector.
    /// \return Reference to the first element in the vector.
    reference front();

    /// \brief Returns a reference to the constant first element in the vector.
    /// \return Reference to the constant first element in the vector.
    const_reference front() const;

    /// \brief Returns a reference to the last element in the vector.
    /// \return Reference to the last element in the vector.
    reference back();

    /// \brief Returns a reference to the constant last element in the vector.
    /// \return Reference to the constant last element in the vector.
    const_reference back() const;

    // Data access

    /// \brief Returns a pointer to the elements of the vector.
    /// \return Pointer to the elements of the vector.
    T* data() noexcept;

    /// \brief Returns a pointer to the constant elements of the vector.
    /// \return Pointer to the constant elements of the vector.
    const T* data() const noexcept;

    // Modifiers

    /// \brief Constructs the element in-place with the given arguments at the
    /// end of the vector.
    /// \pre [sequence.reqmts] T is Cpp17EmplaceConstructible and
    /// Cpp17MoveInsertable into Vector.
    /// \tparam Args Types of the arguments to the constructor.
    /// \param[in,out] args Arguments to construct element with.
    /// \return Reference to the constructed element.
    /// \note Exception safety: [vector.modifiers] If an exception is thrown
    /// other than by the copy constructor, move constructor, assignment
    /// operator, or move assignment operator of T or by any InputIterator
    /// operation there are no effects. If an exception is thrown while
    /// inserting a single element at the end and T is Cpp17CopyInsertable or
    /// std::is_nothrow_move_constructible_v<T> is true, there are no effects.
    /// Otherwise, if an exception is thrown by the move constructor of a
    /// non-Cpp17CopyInsertable T, the effects are unspecified. This overrides
    /// the strong exception safety guarantee in
    /// [container.requirements.general].
    template <typename... Args>
    reference emplace_back(Args&&... args);

    /// \brief Copies the given value to the end of the vector.
    /// \pre [sequence.reqmts] T is Cpp17CopyInsertable into Vector.
    /// \param[in] value Value to copy.
    /// \note Exception safety: [vector.modifiers] SNIP
    void push_back(const T& value);

    /// \brief Moves the given value to the end of the vector.
    /// \pre [sequence.reqmts] T is Cpp17MoveInsertable into Vector.
    /// \param[in] value Value to move.
    /// \note Exception safety: [vector.modifiers] SNIP
    void push_back(T&& value);

    /// \brief Removes the last element from the vector.
    /// \throws [vector.modifiers] Nothing unless an exception is thrown by the
    /// assignment operator or move assignment operator of T. This overrides the
    /// noexcept guarantee in [container.requirements.general].
    void pop_back();

    /// \brief Constructs the element in-place with the given arguments before
    /// the position pointed to by the iterator.
    /// \pre [sequence.reqmts] T is Cpp17EmplaceConstructible and
    /// Cpp17MoveInsertable into Vector and Cpp17MoveAssignable.
    /// \tparam Args Types of the arguments to the constructor.
    /// \param[in] position Iterator pointing to the position of insertion.
    /// \param[in,out] args Arguments to construct element with.
    /// \return Iterator pointing to the constructed element.
    /// \note Exception safety: [vector.modifiers] SNIP
    template <typename... Args>
    iterator emplace(const_iterator position, Args&&... args);

    /// \brief Inserts the given value before the position pointed to by the
    /// iterator via copying.
    /// \pre [sequence.reqmts] T is Cpp17CopyInsertable into Vector and
    /// Cpp17CopyAssignable.
    /// \param[in] position Iterator pointing to the position of insertion.
    /// \param[in] value Value to insert.
    /// \return Iterator pointing to the inserted element.
    /// \note Exception safety: [vector.modifiers] SNIP
    iterator insert(const_iterator position, const T& value);

    /// \brief Inserts the given value before the position pointed to by the
    /// iterator via moving.
    /// \pre [sequence.reqmts] T is Cpp17MoveInsertable into Vector and
    /// Cpp17MoveAssignable.
    /// \param[in] position Iterator pointing to the position of insertion.
    /// \param[in] value Value to insert.
    /// \return Iterator pointing to the inserted element.
    /// \note Exception safety: [vector.modifiers] SNIP
    iterator insert(const_iterator position, T&& value);

    /// \brief Inserts the specified amount of the given value before the
    /// position pointed to by the iterator.
    /// \pre [sequence.reqmts] T is Cpp17CopyInsertable into Vector and
    /// Cpp17CopyAssignable.
    /// \param[in] position Iterator pointing to the position of insertion.
    /// \param[in] amount Amount to insert.
    /// \param[in] value Value to insert.
    /// \return Iterator pointing to first inserted element or provided iterator
    /// if no elements were inserted.
    /// \note Exception safety: [vector.modifiers] SNIP
    iterator insert(const_iterator position, size_type amount, const T& value);

    /// \brief Inserts values pointed to by the range [first, last) before the
    /// position pointed to by the iterator.
    /// \pre [sequence.reqmts] T is Cpp17EmplaceConstructible and
    /// Cpp17MoveInsertable into Vector, Cpp17MoveConstructible,
    /// Cpp17MoveAssignable and swappable.
    /// \tparam I Input iterator type.
    /// \param[in] position Iterator pointing to the position of insertion.
    /// \param[in] first Iterator to the beginning of the range.
    /// \param[in] last Iterator past the end of the range.
    /// \return Iterator pointing to first inserted element or provided iterator
    /// if no elements were inserted.
    /// \note Exception safety: [vector.modifiers] SNIP
    template <InputIterator I>
    iterator insert(const_iterator position, I first, I last);

    /// \brief Inserts values pointed to by the range [first, last) before the
    /// position pointed to by the iterator.
    /// \pre [sequence.reqmts] T is Cpp17EmplaceConstructible and
    /// Cpp17MoveInsertable into Vector, Cpp17MoveConstructible,
    /// Cpp17MoveAssignable and swappable.
    /// \tparam I Forward iterator type.
    /// \param[in] position Iterator pointing to the position of insertion.
    /// \param[in] first Iterator to the beginning of the range.
    /// \param[in] last Iterator past the end of the range.
    /// \return Iterator pointing to first inserted element or provided iterator
    /// if no elements were inserted.
    /// \note Exception safety: [vector.modifiers] SNIP
    template <ForwardIterator I>
    iterator insert(const_iterator position, I first, I last);

    /// \brief Inserts a list of values before the position pointed to by the
    /// iterator.
    /// \pre [sequence.reqmts] T is Cpp17EmplaceConstructible and
    /// Cpp17MoveInsertable into Vector, Cpp17MoveConstructible,
    /// Cpp17MoveAssignable and swappable.
    /// \param[in] position Iterator pointing to the position of insertion.
    /// \param[in] list List of values to insert.
    /// \return Iterator pointing to the the first inserted element or provided
    /// iterator if no elements were inserted.
    /// \note Exception safety: [vector.modifiers] SNIP
    iterator insert(const_iterator position, std::initializer_list<T> values);

    /// \brief Erases the element at the position pointed to by the iterator.
    /// \pre [sequence.reqmts] T is Cpp17MoveAssignable.
    /// \param[in] position Iterator pointing to the element to be removed.
    /// \return Iterator pointing to the position after the removed element.
    /// \throw [vector.modifiers] Nothing unless an exception is thrown by the
    /// assignment operator or move assignment operator of T. This overrides the
    /// noexcept guarantee in [container.requirements.general].
    iterator erase(const_iterator position);

    /// \brief Erases elements pointed to by the range [first, last) in the
    /// vector.
    /// \pre [sequence.reqmts] T is Cpp17MoveAssignable.
    /// \param[in] first Iterator to the beginning of the range.
    /// \param[in] last Iterator past the end of the range.
    /// \return Iterator pointing to the position after the last removed
    /// element.
    /// \throw [vector.modifiers] Nothing unless an exception is thrown by the
    /// assignment operator or move assignment operator of T. This overrides the
    /// noexcept guarantee in [container.requirements.general].
    iterator erase(const_iterator first, const_iterator last);

    /// \brief Exchanges the contents and capacity with another vector.
    /// \param[in,out] other Vector to swap with.
    void swap(Vector& other) noexcept(
        std::allocator_traits<Allocator>::propagate_on_container_swap::value ||
        std::allocator_traits<Allocator>::is_always_equal::value);

    /// \brief Removes all elements from the vector without affecting capacity.
    /// \note Exception safety: [container.requirements.general] Requires
    /// noexcept.
    void clear() noexcept;
private:
    pointer m_elements; ///< Holds all elements.
    size_type m_buffer_capacity; ///< Capacity of the vector.
    size_type m_buffer_size; ///< Amount of constructed elements.
    Allocator m_allocator; ///< Allocator used to manage memory.

    /// \brief Returns capacity that will be enough to store given amount of
    /// elements.
    /// \param[in] amount Amount of elements that need to be stored.
    /// \return Capacity that is enough to store given amount of elements.
    /// \throw std::length_error If amount is greater than the maximum
    /// allocation size.
    size_type GetSufficientCapacity(size_type amount) const;

    /// \brief Allocates the space for the given amount of the elements.
    /// \param[in] new_capacity Amount of elements to allocate for.
    /// \warning If the buffer is already allocated, a memory leak will occur.
    void Allocate(size_type new_capacity);

    /// \brief Destructs all constructed elements and deallocates the
    /// buffer.
    void Deallocate();

    /// \brief Constructs a new element at the end of the buffer.
    /// \tparam Args Types of the arguments to the constructor of the element.
    /// \param[in, out] args Arguments to the constructor of the element.
    /// \warning If the buffer is full, the behavior is undefined.
    template <typename... Args>
    void Construct(Args&&... args);

    /// \brief Destroys the element at the end of the buffer.
    /// \warning If the buffer is empty, the behavior is undefined.
    void Destroy();

    /// \brief Allocates new vector with the exact given capacity and the given
    /// allocator.
    /// \param[in] new_capacity Capacity to allocate.
    /// \param[in] new_allocator Allocator to use.
    /// \return New vector with the given capacity and allocator.
    static Vector CreateNewBuffer(size_type new_capacity,
        const Allocator& new_allocator);

    /// \brief Moves the elements pointed to by the range [first, last) to the
    /// end of the given vector. Used during reallocations.
    /// \param[in] first Iterator to the beginning of the range.
    /// \param[in] last Iterator past the end of the range.
    /// \param[in,out] buffer Vector to move elements to.
    /// \note If the elements have throwing move constructor, this function will
    /// actually try to copy them. This is used to preserve strong exception
    /// safety.
    static void Move(iterator first, iterator last, Vector& buffer);

    /// \brief Moves all elements to the given vector. Used during
    /// reallocations.
    /// \param[in,out] buffer Vector to move elements to.
    /// \note If the elements have throwing move constructor, this function will
    /// actually try to copy them. This is used to preserve strong exception
    /// safety.
    void MoveAll(Vector& buffer);

    /// \brief Moves elements pointed to by the range [std::begin(other), last)
    /// back to this vector. Used to implement strong exception safety
    /// guarantee.
    /// \param[in,out] other Vector to move elements from.
    /// \param[in] last Iterator past the last element to be moved.
    /// \note This function does nothing if elements were copied.
    void Rollback(Vector& other, iterator last) noexcept;

    /// \brief Assumes the state of the given vector.
    /// \param[in,out] other Vector to assume the state of.
    void Commit(Vector&& other) noexcept;

    /// \brief Checks if the given iterator is valid.
    /// \param[in] it Iterator to check.
    /// \throw std::out_of_range If iterator is invalid.
    void ValidateIterator(const_iterator it) const;
};

/// \brief Compares two vectors.
/// \pre [container.requirements.general] T is Cpp17EqualityComparable.
/// \param[in] lhs First vector.
/// \param[in] rhs Second vector.
/// \return True if vectors are equal, false otherwise.
template <typename T, typename Allocator>
bool operator==(const Vector<T, Allocator>& lhs,
    const Vector<T, Allocator>& rhs);

/// \brief Compares two vectors.
/// \pre [container.requirements.general] T is Cpp17EqualityComparable.
/// \param[in] lhs First vector.
/// \param[in] rhs Second vector.
/// \return True if vectors are not equal, false otherwise.
template <typename T, typename Allocator>
bool operator!=(const Vector<T, Allocator>& lhs,
    const Vector<T, Allocator>& rhs);

/// \brief Compares two vectors.
/// \pre [container.requirements.general] operator< is defined, producing total
/// order.
/// \param[in] lhs First vector.
/// \param[in] rhs Second vector.
/// \return True when first vector is less than the second one, false otherwise.
template <typename T, typename Allocator>
bool operator<(const Vector<T, Allocator>& lhs,
    const Vector<T, Allocator>& rhs);

/// \brief Compares two vectors.
/// \pre [container.requirements.general] operator< is defined, producing total
/// order.
/// \param[in] lhs First vector.
/// \param[in] rhs Second vector.
/// \return True when first vector is greater than the second one, false
/// otherwise.
template <typename T, typename Allocator>
bool operator>(const Vector<T, Allocator>& lhs,
    const Vector<T, Allocator>& rhs);

/// \brief Compares two vectors.
/// \pre [container.requirements.general] operator< is defined, producing total
/// order.
/// \param[in] lhs First vector.
/// \param[in] rhs Second vector.
/// \return True when first vector is less than or equal to the second one,
/// false otherwise.
template <typename T, typename Allocator>
bool operator<=(const Vector<T, Allocator>& lhs,
    const Vector<T, Allocator>& rhs);

/// \brief Compares two vectors.
/// \pre [container.requirements.general] operator< is defined, producing total
/// order.
/// \param[in] lhs First vector.
/// \param[in] rhs Second vector.
/// \return True when first vector is greater than or equal to the second one,
/// false otherwise.
template <typename T, typename Allocator>
bool operator>=(const Vector<T, Allocator>& lhs,
    const Vector<T, Allocator>& rhs);

}

#include "Vector.hpp"

Vector.hpp

/// \file
/// \brief Internal header file that contains implementation of the Vector class
/// template.
/// \author Lyberta
/// \copyright GNU GPLv3 or any later version.

#pragma once

namespace ftz::General
{

template <typename T, typename Allocator>
Vector<T, Allocator>::Vector() noexcept(noexcept(Allocator{}))
    : Vector{Allocator{}}
{
}

template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(const Allocator& allocator)
    : m_elements{nullptr},
    m_buffer_capacity{0},
    m_buffer_size{0},
    m_allocator{allocator}
{
}

template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(size_type amount, const Allocator& allocator)
    : Vector{allocator}
{
    this->resize(amount);
}

template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(size_type amount, const T& value,
    const Allocator& allocator)
    : Vector{allocator}
{
    this->resize(amount, value);
}

template <typename T, typename Allocator> template <InputIterator I>
Vector<T, Allocator>::Vector(I first, I last, const Allocator& allocator)
    : Vector{allocator}
{
    this->assign(first, last);
}

template <typename T, typename Allocator> template <ForwardIterator I>
Vector<T, Allocator>::Vector(I first, I last, const Allocator& allocator)
    : Vector{allocator}
{
    this->assign(first, last);
}

template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(const Vector& other)
    : Vector{other,
        std::allocator_traits<Allocator>::select_on_container_copy_construction(
        other.m_allocator)}
{
}

template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(Vector&& other) noexcept
    : m_elements{other.m_elements},
    m_buffer_capacity{other.m_buffer_capacity},
    m_buffer_size{other.m_buffer_size},
    m_allocator{other.m_allocator}
{
    other.m_elements = nullptr;
    other.m_buffer_capacity = 0;
    other.m_buffer_size = 0;
}

template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(const Vector& other, const Allocator& allocator)
    : Vector{allocator}
{
    this->assign(std::begin(other), std::end(other));
}

template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(Vector&& other, const Allocator& new_allocator)
    : Vector{new_allocator}
{
    if (m_allocator == other.m_allocator)
    {
        m_elements = other.m_elements;
        m_buffer_capacity = other.m_buffer_capacity;
        m_buffer_size = other.m_buffer_size;
        other.m_elements = nullptr;
        other.m_buffer_capacity = 0;
        other.m_buffer_size = 0;
        return;
    }
    this->Allocate(this->GetSufficientCapacity(other.m_buffer_size));
    std::move(std::begin(other), std::end(other), std::back_inserter(*this));
}

template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(std::initializer_list<T> values,
    const Allocator& allocator)
    : Vector{allocator}
{
    this->assign(values);
}

template <typename T, typename Allocator>
Vector<T, Allocator>& Vector<T, Allocator>::operator=(const Vector& other)
{
    if (std::allocator_traits<Allocator>::
        propagate_on_container_copy_assignment::value == false)
    {
        Vector new_buffer{other, m_allocator};
        this->Commit(std::move(new_buffer));
        return *this;
    }
    Vector new_buffer{other};
    this->Commit(std::move(new_buffer));
    return *this;
}

template <typename T, typename Allocator>
Vector<T, Allocator>& Vector<T, Allocator>::operator=(Vector&& other) noexcept(
    std::allocator_traits<Allocator>::propagate_on_container_move_assignment::
        value || std::allocator_traits<Allocator>::is_always_equal::value)
{
    if (std::allocator_traits<Allocator>::
        propagate_on_container_move_assignment::value == true)
    {
        this->Commit(std::move(other));
        return *this;
    }
    if (m_allocator == other.m_allocator)
    {
        this->Deallocate();
        m_elements = other.m_elements;
        m_buffer_capacity = other.m_buffer_capacity;
        m_buffer_size = other.m_buffer_size;
        // No allocator assignment.
        other.m_elements = nullptr;
        other.m_buffer_capacity = 0;
        other.m_buffer_size = 0;
        return *this;
    }
    Vector new_buffer{this->GetSufficientCapacity(other.m_buffer_size),
        m_allocator};
    this->MoveAll(new_buffer);
    this->Commit(std::move(new_buffer));
    return *this;
}

template <typename T, typename Allocator>
Vector<T, Allocator>& Vector<T, Allocator>::operator=(
    std::initializer_list<T> values)
{
    this->assign(values);
    return *this;
}

template <typename T, typename Allocator>
Vector<T, Allocator>::~Vector()
{
    if (m_elements == nullptr)
    {
        return;
    }
    this->Deallocate();
}

template <typename T, typename Allocator> template <InputIterator I>
void Vector<T, Allocator>::assign(I first, I last)
{
    if (m_buffer_size == 0)
    {
        try
        {
            std::copy(first, last, std::back_inserter(*this));
        }
        catch (...)
        {
            this->clear();
            throw;
        }
        return;
    }
    Vector new_buffer{m_allocator};
    this->Commit(std::move(new_buffer));
}

template <typename T, typename Allocator> template <ForwardIterator I>
void Vector<T, Allocator>::assign(I first, I last)
{
    if (first == last)
    {
        this->clear();
        return;
    }
    if (m_buffer_size == 0)
    {
        if (m_buffer_capacity == 0)
        {
            this->Allocate(this->GetSufficientCapacity(
                std::distance(first, last)));
        }
        try
        {
            std::copy(first, last, std::back_inserter(*this));
        }
        catch (...)
        {
            this->clear();
            throw;
        }
        return;
    }
    auto new_buffer = CreateNewBuffer(this->GetSufficientCapacity(
        std::distance(first, last)), m_allocator);
    std::copy(first, last, std::back_inserter(new_buffer));
    this->Commit(std::move(new_buffer));
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::assign(size_type amount, const T& value)
{
    if (m_buffer_size == 0)
    {
        try
        {
            std::fill_n(std::back_inserter(*this), amount, value);
        }
        catch (...)
        {
            this->clear();
            throw;
        }
        return;
    }
    Vector new_buffer{amount, value, m_allocator};
    this->Commit(std::move(new_buffer));
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::assign(std::initializer_list<T> values)
{
    this->assign(std::begin(values), std::end(values));
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::allocator_type Vector<T, Allocator>::
    get_allocator() const noexcept
{
    return m_allocator;
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::iterator Vector<T, Allocator>::begin() noexcept
{
    return m_elements;
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::const_iterator Vector<T, Allocator>::begin()
    const noexcept
{
    return m_elements;
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::iterator Vector<T, Allocator>::end() noexcept
{
    return m_elements + m_buffer_size;
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::const_iterator Vector<T, Allocator>::end() const
    noexcept
{
    return m_elements + m_buffer_size;
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::reverse_iterator Vector<T, Allocator>::rbegin()
    noexcept
{
    return reverse_iterator{this->end()};
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::const_reverse_iterator Vector<T, Allocator>::
    rbegin() const noexcept
{
    return const_reverse_iterator{this->end()};
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::reverse_iterator Vector<T, Allocator>::rend()
    noexcept
{
    return reverse_iterator{this->begin()};
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::const_reverse_iterator Vector<T, Allocator>::
    rend() const noexcept
{
    return const_reverse_iterator{this->begin()};
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::const_iterator Vector<T, Allocator>::cbegin()
    const noexcept
{
    return m_elements;
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::const_iterator Vector<T, Allocator>::cend() const
    noexcept
{
    return m_elements + m_buffer_size;
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::const_reverse_iterator Vector<T, Allocator>::
    crbegin() const noexcept
{
    return const_reverse_iterator{this->end()};
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::const_reverse_iterator Vector<T, Allocator>::
    crend() const noexcept
{
    return const_reverse_iterator{this->begin()};
}

template <typename T, typename Allocator>
[[nodiscard]] bool Vector<T, Allocator>::empty() const noexcept
{
    return m_buffer_size == 0;
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::size_type Vector<T, Allocator>::size() const
    noexcept
{
    return m_buffer_size;
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::size_type Vector<T, Allocator>::max_size() const
    noexcept
{
    return std::allocator_traits<Allocator>::max_size(m_allocator);
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::size_type Vector<T, Allocator>::capacity() const
    noexcept
{
    return m_buffer_capacity;
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::resize(size_type new_size)
{
    if (new_size == m_buffer_size)
    {
        return;
    }
    if (new_size < m_buffer_size)
    {
        while (m_buffer_size != new_size)
        {
            this->pop_back();
        }
        return;
    }
    if (m_buffer_capacity == 0)
    {
        this->Allocate(this->GetSufficientCapacity(new_size));
    }
    if (new_size <= m_buffer_capacity)
    {
        size_type amount_to_construct = new_size - m_buffer_size;
        for (size_type i = 0; i < amount_to_construct; ++i)
        {
            this->Construct();
        }
        return;
    }
    auto new_buffer = CreateNewBuffer(this->GetSufficientCapacity(new_size),
        m_allocator);
    this->MoveAll(new_buffer);
    try
    {
        size_type amount_to_construct = new_size - m_buffer_size;
        auto old_buffer_size = m_buffer_size;
        try
        {
            for (size_type i = 0; i < amount_to_construct; ++i)
            {
                this->Construct();
            }
        }
        catch (...)
        {
            while (m_buffer_size != old_buffer_size)
            {
                this->Destroy();
            }
            throw;
        }
    }
    catch (...)
    {
        this->Rollback(new_buffer, std::begin(new_buffer) + m_buffer_size);
        throw;
    }
    this->Commit(std::move(new_buffer));
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::resize(size_type new_size, const T& value)
{
    if (new_size == m_buffer_size)
    {
        return;
    }
    if (new_size < m_buffer_size)
    {
        while (m_buffer_size != new_size)
        {
            this->pop_back();
        }
        return;
    }
    if (m_buffer_capacity == 0)
    {
        this->Allocate(this->GetSufficientCapacity(new_size));
    }
    if (new_size <= m_buffer_capacity)
    {
        size_type amount_to_construct = new_size - m_buffer_size;
        auto old_buffer_size = m_buffer_size;
        try
        {
            for (size_type i = 0; i < amount_to_construct; ++i)
            {
                this->Construct(value);
            }
        }
        catch (...)
        {
            while (m_buffer_size != old_buffer_size)
            {
                this->Destroy();
            }
            throw;
        }
        return;
    }
    auto new_buffer = CreateNewBuffer(this->GetSufficientCapacity(new_size),
        m_allocator);
    this->MoveAll(new_buffer);
    try
    {
        size_type amount_to_construct = new_size - m_buffer_size;
        for (size_type i = 0; i < amount_to_construct; ++i)
        {
            new_buffer.Construct(value);
        }
    }
    catch (...)
    {
        this->Rollback(new_buffer, std::begin(new_buffer) + m_buffer_size);
        throw;
    }
    this->Commit(std::move(new_buffer));
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::reserve(size_type new_capacity)
{
    if (new_capacity <= m_buffer_capacity)
    {
        return;
    }
    if (m_buffer_capacity == 0)
    {
        this->Allocate(new_capacity);
        return;
    }
    auto new_buffer = CreateNewBuffer(this->GetSufficientCapacity(new_capacity),
        m_allocator);
    this->MoveAll(new_buffer);
    this->Commit(std::move(new_buffer));
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::shrink_to_fit()
{
    if (m_buffer_size == m_buffer_capacity)
    {
        return;
    }
    auto new_buffer = CreateNewBuffer(m_buffer_size, m_allocator);
    this->MoveAll(new_buffer);
    this->Commit(std::move(new_buffer));
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::reference Vector<T, Allocator>::operator[](
    size_type index)
{
    return m_elements[index];
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::const_reference Vector<T, Allocator>::operator[](
    size_type index) const
{
    return m_elements[index];
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::reference Vector<T, Allocator>::at(
    size_type index)
{
    if (index >= m_buffer_size)
    {
        throw std::out_of_range{"Vector::at: Index is out of range."};
    }
    return m_elements[index];
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::const_reference Vector<T, Allocator>::at(
    size_type index) const
{
    if (index >= m_buffer_size)
    {
        throw std::out_of_range{"Vector::at: Index is out of range."};
    }
    return m_elements[index];
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::reference Vector<T, Allocator>::front()
{
    return *m_elements;
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::const_reference Vector<T, Allocator>::front()
    const
{
    return *m_elements;
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::reference Vector<T, Allocator>::back()
{
    return *(m_elements + m_buffer_size - 1);
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::const_reference Vector<T, Allocator>::back()
    const
{
    return *(m_elements + m_buffer_size - 1);
}

template <typename T, typename Allocator>
T* Vector<T, Allocator>::data() noexcept
{
    return std::to_address(m_elements);
}

template <typename T, typename Allocator>
const T* Vector<T, Allocator>::data() const noexcept
{
    return std::to_address(m_elements);
}

template <typename T, typename Allocator> template <typename... Args>
typename Vector<T, Allocator>::reference Vector<T, Allocator>::emplace_back(
    Args&&... args)
{
    if (m_buffer_capacity == 0)
    {
        this->Allocate(this->GetSufficientCapacity(1));
    }
    if (m_buffer_size < m_buffer_capacity)
    {
        this->Construct(std::forward<Args>(args)...);
        return this->back();
    }
    auto new_buffer = CreateNewBuffer(this->GetSufficientCapacity(
        m_buffer_size + 1), m_allocator);
    this->MoveAll(new_buffer);
    try
    {
        new_buffer.Construct(std::forward<Args>(args)...);
    }
    catch (...)
    {
        this->Rollback(new_buffer, std::end(new_buffer));
        throw;
    }
    this->Commit(std::move(new_buffer));
    return this->back();
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::push_back(const T& value)
{
    if (m_buffer_capacity == 0)
    {
        this->Allocate(this->GetSufficientCapacity(1));
    }
    if (m_buffer_size < m_buffer_capacity)
    {
        this->Construct(value);
        return;
    }
    auto new_buffer = CreateNewBuffer(this->GetSufficientCapacity(
        m_buffer_size + 1), m_allocator);
    this->MoveAll(new_buffer);
    try
    {
        new_buffer.Construct(value);
    }
    catch (...)
    {
        this->Rollback(new_buffer, std::end(new_buffer));
        throw;
    }
    this->Commit(std::move(new_buffer));
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::push_back(T&& value)
{
    if (m_buffer_capacity == 0)
    {
        this->Allocate(this->GetSufficientCapacity(1));
    }
    if (m_buffer_size < m_buffer_capacity)
    {
        this->Construct(std::move(value));
        return;
    }
    auto new_buffer = CreateNewBuffer(this->GetSufficientCapacity(
        m_buffer_size + 1), m_allocator);
    this->MoveAll(new_buffer);
    try
    {
        new_buffer.Construct(std::move(value));
    }
    catch (...)
    {
        this->Rollback(new_buffer, std::end(new_buffer));
        throw;
    }
    this->Commit(std::move(new_buffer));
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::pop_back()
{
    if (m_buffer_size == 0)
    {
        return;
    }
    this->Destroy();
}

template <typename T, typename Allocator> template <typename... Args>
typename Vector<T, Allocator>::iterator Vector<T, Allocator>::emplace(
    const_iterator position, Args&&... args)
{
    this->ValidateIterator(position);
    auto pos = const_cast<iterator>(position);
    if (m_buffer_size < m_buffer_capacity)
    {
        if (pos == std::end(*this))
        {
            this->Construct(std::forward<Args>(args)...);
            return pos;
        }
        this->Construct(std::move(this->back()));
        std::move_backward(pos, std::end(*this) - 1, std::end(*this));
        pos = T(std::forward<Args>(args)...);
        return pos;
    }
    auto new_buffer = CreateNewBuffer(this->GetSufficientCapacity(
        m_buffer_size + 1), m_allocator);
    Move(std::begin(*this), pos, new_buffer);
    try
    {
        new_buffer.Construct(std::forward<Args>(args)...);
    }
    catch (...)
    {
        this->Rollback(new_buffer, std::end(new_buffer));
        throw;
    }
    Move(pos, std::end(*this), new_buffer);
    auto offset = pos - std::begin(*this);
    this->Commit(std::move(new_buffer));
    return std::begin(*this) + offset;
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::iterator Vector<T, Allocator>::insert(
    const_iterator position, const T& value)
{
    this->ValidateIterator(position);
    auto pos = const_cast<iterator>(position);
    if (m_buffer_size < m_buffer_capacity)
    {
        if (pos == std::end(*this))
        {
            this->Construct(value);
            return pos;
        }
        this->Construct(std::move(this->back()));
        std::move_backward(pos, std::end(*this) - 1, std::end(*this));
        pos = value;
        return pos;
    }
    auto new_buffer = CreateNewBuffer(this->GetSufficientCapacity(
        m_buffer_size + 1), m_allocator);
    Move(std::begin(*this), pos, new_buffer);
    try
    {
        new_buffer.Construct(value);
    }
    catch (...)
    {
        this->Rollback(new_buffer, std::end(new_buffer));
        throw;
    }
    Move(pos, std::end(*this), new_buffer);
    auto offset = pos - std::begin(*this);
    this->Commit(std::move(new_buffer));
    return std::begin(*this) + offset;
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::iterator Vector<T, Allocator>::insert(
    const_iterator position, T&& value)
{
    this->ValidateIterator(position);
    auto pos = const_cast<iterator>(position);
    if (m_buffer_size < m_buffer_capacity)
    {
        if (pos == std::end(*this))
        {
            this->Construct(std::move(value));
            return pos;
        }
        this->Construct(std::move(this->back()));
        std::move_backward(pos, std::end(*this) - 1, std::end(*this));
        *pos = std::move(value);
        return pos;
    }
    auto new_buffer = CreateNewBuffer(this->GetSufficientCapacity(
        m_buffer_size + 1), m_allocator);
    Move(std::begin(*this), pos, new_buffer);
    try
    {
        new_buffer.Construct(std::move(value));
    }
    catch (...)
    {
        this->Rollback(new_buffer, std::end(new_buffer));
        throw;
    }
    Move(pos, std::end(*this), new_buffer);
    auto offset = pos - std::begin(*this);
    this->Commit(std::move(new_buffer));
    return std::begin(*this) + offset;
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::iterator Vector<T, Allocator>::insert(
    const_iterator position, size_type amount, const T& value)
{
    this->ValidateIterator(position);
    auto pos = const_cast<iterator>(position);
    if (amount == 0)
    {
        return pos;
    }
    if (m_buffer_size + amount <= capacity)
    {
        if (pos == std::end(*this))
        {
            auto old_buffer_size = m_buffer_size;
            try
            {
                for (size_type i = 0; i < amount; ++i)
                {
                    this->Construct(value);
                }
            }
            catch (...)
            {
                while (m_buffer_size != old_buffer_size)
                {
                    this->Destroy();
                }
                throw;
            }
            return pos;
        }
        auto last_move = std::end(*this);
        for (auto i = std::end(*this) - amount, end = std::end(*this); i != end;
            ++i)
        {
            this->Construct(std::move(*i));
        }
        std::move_backward(pos, pos + amount, last_move);
        std::fill_n(pos, amount, value);
        return pos;
    }
    auto new_buffer = CreateNewBuffer(this->GetSufficientCapacity(
        m_buffer_size + amount), m_allocator);
    Move(std::begin(*this), pos, new_buffer);
    auto offset = pos - std::begin(*this);
    try
    {
        for (size_type i = 0; i < amount; ++i)
        {
            new_buffer.Construct(value);
        }
    }
    catch (...)
    {
        this->Rollback(new_buffer, std::begin(new_buffer) + offset);
        throw;
    }
    Move(pos, std::end(*this), new_buffer);
    this->Commit(std::move(new_buffer));
    return std::begin(*this) + offset;
}

template <typename T, typename Allocator> template <InputIterator I>
typename Vector<T, Allocator>::iterator Vector<T, Allocator>::insert(
    const_iterator position, I first, I last)
{
    this->ValidateIterator(position);
    auto pos = const_cast<iterator>(position);
    if (first == last)
    {
        return pos;
    }
    auto new_buffer = CreateNewBuffer(this->GetSufficientCapacity(
        m_buffer_size + 1), m_allocator);
    Move(std::begin(*this), pos, new_buffer);
    auto offset = pos - std::begin(*this);
    try
    {
        while (first != last)
        {
            new_buffer.Construct(*first);
            ++first;
        }
    }
    catch (...)
    {
        this->Rollback(new_buffer, std::begin(new_buffer) + offset);
        throw;
    }
    Move(pos, std::end(*this), new_buffer);
    this->Commit(std::move(new_buffer));
    return std::begin(*this) + offset;
}

template <typename T, typename Allocator> template <ForwardIterator I>
typename Vector<T, Allocator>::iterator Vector<T, Allocator>::insert(
    const_iterator position, I first, I last)
{
    this->ValidateIterator(position);
    auto pos = const_cast<iterator>(position);
    if (first == last)
    {
        return pos;
    }
    auto amount = std::distance(first, last);
    if (m_buffer_size + amount <= capacity)
    {
        if (pos == std::end(*this))
        {
            auto old_buffer_size = m_buffer_size;
            try
            {
                while (first != last)
                {
                    this->Construct(*first);
                    ++first;
                }
            }
            catch (...)
            {
                while (m_buffer_size != old_buffer_size)
                {
                    this->Destroy();
                }
                throw;
            }
            return pos;
        }
        auto last_move = std::end(*this);
        for (auto i = std::end(*this) - amount, end = std::end(*this); i != end;
            ++i)
        {
            this->Construct(std::move(*i));
        }
        std::move_backward(pos, pos + amount, last_move);
        std::copy(first, last, pos);
        return pos;
    }
    auto new_buffer = CreateNewBuffer(this->GetSufficientCapacity(
        m_buffer_size + amount), m_allocator);
    Move(std::begin(*this), pos, new_buffer);
    auto offset = pos - std::begin(*this);
    try
    {
        while (first != last)
        {
            new_buffer.Construct(*first);
            ++first;
        }
    }
    catch (...)
    {
        this->Rollback(new_buffer, std::begin(new_buffer) + offset);
        throw;
    }
    Move(pos, std::end(*this), new_buffer);
    this->Commit(std::move(new_buffer));
    return std::begin(*this) + offset;
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::iterator Vector<T, Allocator>::insert(
    const_iterator position, std::initializer_list<T> values)
{
    return this->insert(position, std::begin(values), std::end(values));
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::iterator Vector<T, Allocator>::erase(
    const_iterator position)
{
    this->ValidateIterator(position);
    auto pos = const_cast<iterator>(position);
    std::move(pos + 1, std::end(*this), pos);
    this->Destroy();
    return pos;
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::iterator Vector<T, Allocator>::erase(
    const_iterator first, const_iterator last)
{
    this->ValidateIterator(first);
    this->ValidateIterator(last);
    std::move(const_cast<iterator>(last), std::end(*this),
        const_cast<iterator>(first));
    iterator pos = first;
    while (first != last)
    {
        this->Destroy();
        ++first;
    }
    return pos;
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::swap(Vector& other) noexcept(
    std::allocator_traits<Allocator>::propagate_on_container_swap::value ||
    std::allocator_traits<Allocator>::is_always_equal::value)
{
    using std::swap;
    swap(m_elements, other.m_elements);
    std::swap(m_buffer_capacity, other.m_buffer_capacity);
    std::swap(m_buffer_size, other.m_buffer_size);
    if (std::allocator_traits<Allocator>::propagate_on_container_swap::value
        == true)
    {
        swap(m_allocator, other.m_allocator);
    }
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::clear() noexcept
{
    for (auto i = m_elements, end = i + m_buffer_size; i != end; ++i)
    {
        try
        {
            this->Destroy();
        }
        catch (...)
        {
        }
    }
    m_buffer_size = 0;
}

template <typename T, typename Allocator>
typename Vector<T, Allocator>::size_type Vector<T, Allocator>::
    GetSufficientCapacity(size_type amount) const
{
    auto max_size = std::allocator_traits<Allocator>::max_size(m_allocator);
    if (amount > max_size)
    {
        throw std::length_error{"Vector::GetSufficientCapacity: "
            "The requested amount is bigger than the maximum supported by the "
            "allocator."};
    }
    size_type new_capacity = std::ceil2(amount);
    if (new_capacity > max_size)
    {
        throw std::length_error{"Vector::GetSufficientCapacity: "
            "The requested amount is bigger than the maximum supported by the "
            "allocator."};
    }
    return new_capacity;
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::Allocate(size_type new_capacity)
{
    m_elements = std::allocator_traits<Allocator>::allocate(m_allocator,
        new_capacity);
    m_buffer_capacity = new_capacity;
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::Deallocate()
{
    this->clear();
    std::allocator_traits<Allocator>::deallocate(m_allocator, m_elements,
        m_buffer_capacity);
    m_elements = nullptr;
    m_buffer_capacity = 0;
}

template <typename T, typename Allocator> template <typename... Args>
void Vector<T, Allocator>::Construct(Args&&... args)
{
    std::allocator_traits<Allocator>::construct(m_allocator,
        std::to_address(m_elements + m_buffer_size),
        std::forward<Args>(args)...);
    ++m_buffer_size;
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::Destroy()
{
    std::allocator_traits<Allocator>::destroy(m_allocator,
        std::to_address(m_elements + m_buffer_size) - 1);
    --m_buffer_size;
}

template <typename T, typename Allocator>
Vector<T, Allocator> Vector<T, Allocator>::CreateNewBuffer(
    size_type new_capacity, const Allocator& new_allocator)
{
    Vector new_buffer{new_allocator};
    new_buffer.Allocate(new_capacity);
    return new_buffer;
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::Move(iterator first, iterator last, Vector& buffer)
{
    if constexpr (std::is_nothrow_move_constructible_v<T> ||
        !std::is_copy_constructible_v<T>)
    {
        std::move(first, last, std::back_inserter(buffer));
    }
    else
    {
        std::copy(first, last, std::back_inserter(buffer));
    }
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::MoveAll(Vector& buffer)
{
    Move(std::begin(*this), std::end(*this), buffer);
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::Rollback(Vector& other, iterator last) noexcept
{
    if constexpr (!std::is_nothrow_move_constructible_v<T> &&
        std::is_copy_constructible_v<T>)
    {
        // The elements were copied during the Move() call so the destructor of
        // temporary vector will take care of them.
        return;
    }
    else if constexpr (std::is_nothrow_move_assignable_v<T>)
    {
        // Just move assign them back.
        std::move(std::begin(other), last, std::begin(*this));
        return;
    }
    else if constexpr (std::is_nothrow_move_constructible_v<T>)
    {
        // Hard case. Non-noexcept-move-assignable type. But since move ctor is
        // noexcept, we just destroy and construct them back.
        auto source = std::begin(other);
        auto destination = m_elements;
        while (source != last)
        {
            std::allocator_traits<Allocator>::destroy(m_allocator,
                std::to_address(destination));
            std::allocator_traits<Allocator>::construct(m_allocator,
                std::to_address(destination), std::move(*source));
            ++source;
            ++destination;
        }
        return;
    }
    else if constexpr (std::is_move_assignable_v<T>)
    {
        // Entering "unspecified" territory. We can just try to move assign some
        // of them back and swallow any exceptions. If an exception is thrown
        // here, some elements are lost.
        try
        {
            std::move(std::begin(other), last, std::begin(*this));
        }
        catch (...)
        {
        }
        return;
    }
    // The type is non-move-assignable and has throwing move ctor. Just give up.
    // We haven't invalidated any invariants so destructors will do their job.
    // Just elements that have been moved are lost. Meh.
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::Commit(Vector&& other) noexcept
{
    this->Deallocate();
    m_elements = other.m_elements;
    m_buffer_capacity = other.m_buffer_capacity;
    m_buffer_size = other.m_buffer_size;
    m_allocator = other.m_allocator;
    other.m_elements = nullptr;
    other.m_buffer_capacity = 0;
    other.m_buffer_size = 0;
}

template <typename T, typename Allocator>
void Vector<T, Allocator>::ValidateIterator(const_iterator it) const
{
    if ((it < std::begin(*this)) || it > std::end(*this))
    {
        throw std::out_of_range{"Vector::ValidateIterator: Invalid iterator."};
    }
}

template <typename T, typename Allocator>
bool operator==(const Vector<T, Allocator>& lhs,
    const Vector<T, Allocator>& rhs)
{
    return std::equal(std::begin(lhs), std::end(lhs), std::begin(rhs),
        std::end(rhs));
}

template <typename T, typename Allocator>
bool operator!=(const Vector<T, Allocator>& lhs,
    const Vector<T, Allocator>& rhs)
{
    return !(lhs == rhs);
}

template <typename T, typename Allocator>
bool operator<(const Vector<T, Allocator>& lhs,
    const Vector<T, Allocator>& rhs)
{
    return std::lexicographical_compare(std::begin(lhs), std::end(lhs),
        std::begin(rhs), std::end(rhs));
}

template <typename T, typename Allocator>
bool operator>(const Vector<T, Allocator>& lhs,
    const Vector<T, Allocator>& rhs)
{
    return rhs < lhs;
}

template <typename T, typename Allocator>
bool operator<=(const Vector<T, Allocator>& lhs,
    const Vector<T, Allocator>& rhs)
{
    return !(lhs > rhs);
}

template <typename T, typename Allocator>
bool operator>=(const Vector<T, Allocator>& lhs,
    const Vector<T, Allocator>& rhs)
{
    return !(lhs < rhs);
}

}
\$\endgroup\$
  • 2
    \$\begingroup\$ Note that by posting it here, the code is also licensed under CC BY-SA 3.0: codereview.stackexchange.com/help/licensing \$\endgroup\$ – user673679 May 18 at 10:52
  • 1
    \$\begingroup\$ Still copyleft - good enough. \$\endgroup\$ – Lyberta May 18 at 11:02
  • \$\begingroup\$ @L.F. Move-semantics are quite foreign to allocators, which are generally either trivially copyable (and likely empty) or at least extremely cheaply... \$\endgroup\$ – Deduplicator May 19 at 13:43
  • \$\begingroup\$ Please see What to do when someone answers. I have rolled back Rev 2 → 1 \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ May 31 at 15:31
  • 1
    \$\begingroup\$ @coderodde Are you talking about the Doxygen code? It is a document generator for C++ code. \$\endgroup\$ – L. F. Sep 14 at 2:01
8
\$\begingroup\$

Non-conformance:

  1. [Derivation].4: All types specified in the C++ standard library shall be non-final types unless otherwise specified.

    std::vector is not an exception, and thus must not be final.

  2. You forgot to implement support for hashing by specializing std::hash.

  3. You don't add the necessary typedef to sub-namepspace pmr for polymorphic allocator support.

  4. You don't implement the ill-fated specialization for bool.

  5. #pragma once is not strictly conforming C++, though numerous compilers implement it.

Efficiency:

  1. It is understandable that you would prefer not using EBO, as many think it clunky. For this reason, C++20 section [dcl.attr.nouniqueaddr] introduces the attribute [[no_unique_address]] for member-variables. Use either.

  2. You are using a growth-factor of 2. That means you will never re-use any previous allocation when consecutively growing your vector, as all previous allocations together will never suffice. Consider a smaller factor.

  3. Yes, you can safely measure the distance between two ForwardIterators for pre-sizing. An InputIterator might support subtracting to get the difference despite only allowing a single traversal though. If you have the choice, go by available operations, not fully implemented concepts.

Form:

  1. Consider using in-class initializers to simplify your ctors.

  2. this is implicit, always using it is useless clutter.

  3. There is no use to special-casing ForwardIterators if you don't actually treat them differently in your own code. The code you call from there does all that magic on its own.

  4. Consider reading up on the copy-and-swap-idiom, for efficient simpler code.

  5. Choose the target-ctor a bit more carefully, and you can more frequently have an empty body.

  6. The ternary operator is very useful for efficient and more flexible constructor-chaining.

  7. Consider using std::make_move_iterator() where appropriate.

template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(Vector&& other, const Allocator& new_allocator)
: Vector{new_allocator == other.m_allocator
    ? Vector{other}
    : Vector{std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()), new_allocator}}
{}
  1. If someone has the effrontery to use an element-type which can throw on destruction, and that happened, all bets are off as far as the standard is concerned. Even if it wasn't, swallowing exceptions generally only makes bugs harder to treat.

  2. Explicit comparison against true and false is needless verbosity. If you disagree, why not add a few extra-comparisons? Also, you might fall afoul of subtleties especially if comparing to true.

  3. Generally, pre-testing whether something is already null is both verbose and inefficient, as it duplicates work.

  4. Try to avoid conditional execution, especially if it is not expected to save more than an insignificant amount and that only in rare cases, inviting branch-misprediction.

  5. I would expect use or omission of the two-step for swap to be consistent, at least in a single function.

\$\endgroup\$
  • \$\begingroup\$ 9. If I don't explicitly type type it always looks like a random non-member function. 10. InputIterator is one pass so you can't preallocate and have to use inefficient algorithm. I split those to have more efficient one for ForwardIterators. 13. Ternary operator is really hard to read. 16. if (foo) is really hard to read unless it is very explicit. \$\endgroup\$ – Lyberta May 19 at 0:31
  • \$\begingroup\$ @Lyberta re 9: It Looks like a random non-member? Well, I don't concurr, but whatever. re 10: As you have the same code for both ctors, you don't take advantage of separating them there already. The callee does. re 13: Ehm, no. re 16: "if the vector is empty is true" is a very convoluted way to say "if the vector is empty". Dito for the moral equivalent in C++. It's somewhat hard to understand how anyone could disagree there. Of course, comparison against true is far more error-prone and alien to C and C++ than against false, which is also generally bad. \$\endgroup\$ – Deduplicator May 19 at 1:00
3
\$\begingroup\$

(Note: I am referring to the newest draft, so some of the points below may be due to the changes in the standard draft. I will list them for the sake of completeness and also to help you adapt to the newest drafts.)

Here's some more suggestions not covered by Deduplicator's answer:

Non-conformance

  1. Per [vector.syn], the header <initializer_list> should be included by <vector>. You are using the identifier std::initializer_list without including the appropriate header.

  2. std::vector is constexpr-friendly in C++20 thanks to allocation/deallocation and construction/destruction being allowed in constexpr.

  3. The standard std::vector constructs default allocators with Allocator() instead of Allocator{}. This can cause a difference. See Are there any difference in empty parentheses (T()) and empty braces (T{}) when used as initializers?.

  4. The (alloc) constructor is noexcept.

  5. Per [container.requirements.general]/8, the move constructor should move construct from the allocator.

  6. The assign(inputit, inputit) function doesn't look right. It seems that it clears the vector if size != 0.

Missing functionality

  1. Free function swap.

  2. Uniform erasure (erase, erase_if).

  3. In C++20, the three-comparison operator <=> is introduced. You may want to change the comparison operators to operator<=>.

Other

  1. The type std::allocator_traits<Allocator> is used numerous times in the class. I suggest introducing a type alias for it. For example:

    using A_Tr = std::allocator_traits<Allocator>;
    
  2. Since your (it, it) constructor delegates to assign inside, there is no need to provide a separate version for forward iterators.

  3. You always call your constructor parameter allocator except for the (vector&&, alloc) version, in which it is new_allocator. It is probably a good idea to keep consistent.

  4. I have to say this again: don't use this-> everywhere. It automatically makes me think of dependent base classes and etc. Just remove them.

  5. The move constructor can be simplified with some swap_content function.

  6. You can avoid writing the template parameters twice by using a trailing return type. For example:

    template <typename T, typename A>
    auto Vector<T, A>::operator(std::initializer_list<T> values)
        -> Vector&
    {
        // ...
    }
    

    And use auto as appropriate:

    template <typename T, typename A>
    auto Vector<T, A>::get_allocator() const noexcept
    {
        return m_allocator;
    }
    

    (This one should really be implemented directly in the class.)

  7. The assign(In, In) function can be simplified if the (In, In) constructor doesn't depend on it:

    template <typename T, typename A>
    template <InputIterator I>
    void Vector<T, A>::assign(I first, I last)
    {
        Vector vec(first, last, m_allocator);
        swap(vec);
    }
    

    To me, it seems more logical to make the constructor depend on insert.

    Similarly, the assign(For, For) function is way too complicated. Let the (For, For) constructor depend on insert instead.

  8. The assign(count, value) function should use the (count, value) constructor because the latter does not depend on the former.

  9. The c iterator functions can delegate to the other functions.

  10. To be honest, my sanity dropped by ~4.2% when I saw the resize functions. Their sheer size makes comprehension difficult. Here's how I'll write the whole function: (just the idea, not tested)

    template <typename T, typename A>
    void Vector<T, A>::resize(size_type new_size)
    {
        while (size() > new_size) {
            pop_back();
        }
        reserve(new_size);
        while (size() < new_size) {
            emplace_back();
        }
    }
    

    and

    template <typename T, typename A>
    void Vector<T, A>::resize(size_type new_size, const T& value)
    {
        while (size() > new_size) {
            pop_back();
        }
        if (size() < new_size) {
            insert(end(), new_size - size(), value);
        }
    }
    
  11. The push_back function should delegate to emplace_back. Two insert functions should delegate to emplace.

  12. pop_back has undefined behavior on empty vectors, so there's no need to handle the empty case specially. An assertion will be enough. Likewise, clear() doesn't need to check exceptions.

  13. Do you know std::move_if_noexcept? You can simplify Move like this:

    template <typename T, typename Allocator>
    void Vector<T, Allocator>::Move(iterator first, iterator last, Vector& buffer)
    {
        std::transform(first, last, std::back_inserter(buffer),
            [](auto&& value) -> decltype(auto) { return std::move_if_noexcept(value); });
    }
    
\$\endgroup\$
  • \$\begingroup\$ .resize() must work even if passed an element of the vector and reallocation is done. \$\endgroup\$ – Deduplicator Sep 13 at 20:08
  • \$\begingroup\$ @Deduplicator That's logical. I genuinely failed to consider that edge case ... Does the insert(it, count, value) version allow value to be an element of the vector too? \$\endgroup\$ – L. F. Sep 14 at 1:58
  • \$\begingroup\$ If it's a value instead of an xvalue, it might just be an element, yes. At least none of the emplace-functions must take that into account AFAICR. \$\endgroup\$ – Deduplicator Sep 14 at 2:25
2
\$\begingroup\$

First, I would like to mention, that defining the constructors out of class adds a lot of unnecessary clutter in the form of template <typename T, typename Allocator> and Vector<T, Allocator>

You should use explicit member initialization rather than repeating yourself in the constructors.

pointer m_elements{nullptr};
std::size_t m_buffer_capacity{0};
std::size_t m_buffer_size{0};
Allocator m_allocator{Allocator()};

Also note that in that case you explicitly default the default constructor as it will deduce the correct exception specification itself.

Vector() = default;

Vector(const Allocator& allocator)
    : m_allocator{allocator}
{}

I am skeptical of your move constructor:

template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(Vector&& other) noexcept
    : m_elements{other.m_elements},
    m_buffer_capacity{other.m_buffer_capacity},
    m_buffer_size{other.m_buffer_size},
    m_allocator{other.m_allocator}
{
    other.m_elements = nullptr;
    other.m_buffer_capacity = 0;
    other.m_buffer_size = 0;
}

For one thing it does unnecessary work, as other is defined as in an unspecified state, so resetting can be skipped. Also you are copying the allocator of other. That should (regardless whether the allocator is movable or not) be

m_allocator{std::move(other.m_allocator)} 

I have to object to @Deduplicator comment 12. Using the copy and swap idiom requires default construction of the allocator which might or might not be expensive. A fundamental workhorse such as vector can bear that few extra lines. Also note that adding the linebreak before the commata increases alignment and therewith readability:

template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(Vector&& other) noexcept
    : m_elements{other.m_elements}
    , m_buffer_capacity{other.m_buffer_capacity},
    , m_buffer_size{other.m_buffer_size}
    , m_allocator{std::move(other.m_allocator)}
{
}

The other move constructor also does more than it should. Even worse it is inconsistent as other is in a different state depending on which branch is taken

template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(Vector&& other, const Allocator& new_allocator)
    : Vector{new_allocator}
{
    if (m_allocator == other.m_allocator)
    {
        m_elements = other.m_elements;
        m_buffer_capacity = other.m_buffer_capacity;
        m_buffer_size = other.m_buffer_size;
        other.m_elements = nullptr;
        other.m_buffer_capacity = 0;
        other.m_buffer_size = 0;
        return;
    }
    Allocate(GetSufficientCapacity(other.m_buffer_size));
    std::move(std::begin(other), std::end(other), std::back_inserter(*this));
}

The first thing is not using the initializer list for the trivial members. Second you are using std::back_inserter which falls back to individual push_backs. Rather you should directly use the begin()/end() methods.

template <typename T, typename Allocator>
Vector<T, Allocator>::Vector(Vector&& other, const Allocator& allocator)
    : m_buffer_capacity{other.m_buffer_capacity},
    , m_buffer_size{other.m_buffer_size}
    , m_allocator{allocator}
{
    if (m_allocator == other.m_allocator)
    {
        m_elements = other.m_elements;
    } 
    else 
    {
        Allocate(GetSufficientCapacity(other.m_buffer_size));
        std::move(other.begin(), other.end(), begin());
    }
}

EDIT

I checked libc++ and they indeed reset the values of the vector: https://github.com/llvm-mirror/libcxx/blob/8c84318aad43620024310db6c1fe75c0c1706ead/include/vector#L1279

Note that it still moves the allocator of other.

\$\endgroup\$
  • 1
    \$\begingroup\$ Not "unspecified" but "unspecified but valid". Thus, resetting the source on move-construction is necessary. As an aside, move-assignment also always destroys all the targets elements, even for self-assignment. Regarding your comment to my point 12, copy-and-swap does no default-construction. \$\endgroup\$ – Deduplicator Sep 13 at 21:26
  • \$\begingroup\$ @Deduplicator: That is factually wrong. The unspecified but valid is the phrasing that is done because it must not be resetted. The vector vas in a valid state before so no resetting is required. The reason why copy-and-swap is not used universally is that it indeed implies a measurable overhead in default constructing the members before swapping them. Note that in the move constructor after the initializer list of the constructor m_allocator is default constructed and then swapped afterwards. In contrast by writing it out m_allocator is directly move constructed. \$\endgroup\$ – miscco Sep 14 at 6:13
  • 1
    \$\begingroup\$ @miscco If you don't reset the source, it is left in an invalid state. Any decent compiler should optimize out the overhead caused by default construction + swapping over move + resetting. The m_allocator problem can be (and should be) addressed by having a separate swap_contents function. \$\endgroup\$ – L. F. Sep 14 at 8:32
  • \$\begingroup\$ @L.F. It is not about what acompiler could do but what it is allowed to do. It is not allowed to remove any observable behavior. So for example if you have an allocator that allocates a certain amount of storage during default construction the compiler cannot simply remove that allocation. This is analogous to the push for relocatable wrt move construction + destruction. \$\endgroup\$ – miscco Sep 14 at 18:32
  • \$\begingroup\$ @miscco Actually, allocating and deallocating is not per se observable behavior. There is even explicit license in the standard to coalesce allocations, as well as to omit allocation + deallocation pairs in many cases. \$\endgroup\$ – Deduplicator Sep 14 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.