/src/immer/immer/flex_vector.hpp

Source
//
// immer: immutable data structures for C++
// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
//
// This software is distributed under the Boost Software License, Version 1.0.
// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
//

#pragma once

#include <immer/detail/rbts/rrbtree.hpp>
#include <immer/detail/rbts/rrbtree_iterator.hpp>
#include <immer/memory_policy.hpp>

namespace immer {

template <typename T,
          typename MP,
          detail::rbts::bits_t B,
          detail::rbts::bits_t BL>
class vector;

template <typename T,
          typename MP,
          detail::rbts::bits_t B,
          detail::rbts::bits_t BL>
class flex_vector_transient;

/*!
 * Immutable sequential container supporting both random access,
 * structural sharing and efficient concatenation and slicing.
 *
 * @tparam T The type of the values to be stored in the container.
 * @tparam MemoryPolicy Memory management policy. See @ref
 *         memory_policy.
 *
 * @rst
 *
 * This container is very similar to `vector`_ but also supports
 * :math:`O(log(size))` *concatenation*, *slicing* and *insertion* at
 * any point. Its performance characteristics are almost identical
 * until one of these operations is performed.  After that,
 * performance is degraded by a constant factor that usually oscilates
 * in the range :math:`[1, 2)` depending on the operation and the
 * amount of flexible operations that have been performed.
 *
 * .. tip:: A `vector`_ can be converted to a `flex_vector`_ in
 *    constant time without any allocation.  This is so because the
 *    internal structure of a *vector* is a strict subset of the
 *    internal structure of a *flexible vector*.  You can take
 *    advantage of this property by creating normal vectors as long as
 *    the flexible operations are not needed, and convert later in
 *    your processing pipeline once and if these are needed.
 *
 * @endrst
 */
template <typename T,
          typename MemoryPolicy  = default_memory_policy,
          detail::rbts::bits_t B = default_bits,
          detail::rbts::bits_t BL =
              detail::rbts::derive_bits_leaf<T, MemoryPolicy, B>>
class flex_vector
{
    using impl_t = detail::rbts::rrbtree<T, MemoryPolicy, B, BL>;

    using move_t =
        std::integral_constant<bool, MemoryPolicy::use_transient_rvalues>;

public:
    static constexpr auto bits      = B;
    static constexpr auto bits_leaf = BL;
    using memory_policy             = MemoryPolicy;

    using value_type      = T;
    using reference       = const T&;
    using size_type       = detail::rbts::size_t;
    using difference_type = std::ptrdiff_t;
    using const_reference = const T&;

    using iterator = detail::rbts::rrbtree_iterator<T, MemoryPolicy, B, BL>;
    using const_iterator   = iterator;
    using reverse_iterator = std::reverse_iterator<iterator>;

    using transient_type = flex_vector_transient<T, MemoryPolicy, B, BL>;

    /*!
     * Returns the maximum theoretical size supported by the internal structure
     * given the current B, BL.
     */
    constexpr static size_type max_size() { return impl_t::max_size(); }

    /*!
     * Default constructor.  It creates a flex_vector of `size() == 0`.
     * It does not allocate memory and its complexity is @f$ O(1) @f$.
     */
    flex_vector() = default;

    /*!
     * Constructs a flex_vector containing the elements in `values`.
     */
    flex_vector(std::initializer_list<T> values)
        : impl_{impl_t::from_initializer_list(values)}
    {
    }

    /*!
     * Constructs a flex_vector containing the elements in the range
     * defined by the input iterator `first` and range sentinel `last`.
     */
    template <typename Iter,
              typename Sent,
              std::enable_if_t<detail::compatible_sentinel_v<Iter, Sent>,
                               bool> = true>
    flex_vector(Iter first, Sent last)
        : impl_{impl_t::from_range(first, last)}
    {
    }

    /*!
     * Constructs a vector containing the element `val` repeated `n`
     * times.
     */
    flex_vector(size_type n, T v = {})
        : impl_{impl_t::from_fill(n, v)}
    {
    }

    /*!
     * Default constructor.  It creates a flex_vector with the same
     * contents as `v`.  It does not allocate memory and is
     * @f$ O(1) @f$.
     */
    flex_vector(vector<T, MemoryPolicy, B, BL> v)
        : impl_{v.impl_.size,
                v.impl_.shift,
                v.impl_.root->inc(),
                v.impl_.tail->inc()}
    {
    }

    /*!
     * Returns an iterator pointing at the first element of the
     * collection. It does not allocate memory and its complexity is
     * @f$ O(1) @f$.
     */
    IMMER_NODISCARD iterator begin() const { return {impl_}; }

    /*!
     * Returns an iterator pointing just after the last element of the
     * collection. It does not allocate and its complexity is @f$ O(1) @f$.
     */
    IMMER_NODISCARD iterator end() const
    {
        return {impl_, typename iterator::end_t{}};
    }

    /*!
     * Returns an iterator that traverses the collection backwards,
     * pointing at the first element of the reversed collection. It
     * does not allocate memory and its complexity is @f$ O(1) @f$.
     */
    IMMER_NODISCARD reverse_iterator rbegin() const
    {
        return reverse_iterator{end()};
    }

    /*!
     * Returns an iterator that traverses the collection backwards,
     * pointing after the last element of the reversed collection. It
     * does not allocate memory and its complexity is @f$ O(1) @f$.
     */
    IMMER_NODISCARD reverse_iterator rend() const
    {
        return reverse_iterator{begin()};
    }

    /*!
     * Returns the number of elements in the container.  It does
     * not allocate memory and its complexity is @f$ O(1) @f$.
     */
    IMMER_NODISCARD size_type size() const { return impl_.size; }

    /*!
     * Returns `true` if there are no elements in the container.  It
     * does not allocate memory and its complexity is @f$ O(1) @f$.
     */
    IMMER_NODISCARD bool empty() const { return impl_.size == 0; }

    /*!
     * Access the last element.
     */
    IMMER_NODISCARD const T& back() const { return impl_.back(); }

    /*!
     * Access the first element.
     */
    IMMER_NODISCARD const T& front() const { return impl_.front(); }

    /*!
     * Returns a `const` reference to the element at position `index`.
     * It is undefined when @f$ 0 index \geq size() @f$.  It does not
     * allocate memory and its complexity is *effectively* @f$ O(1)
     * @f$.
     */
    IMMER_NODISCARD reference operator[](size_type index) const
    {
        return impl_.get(index);
    }

    /*!
     * Returns a `const` reference to the element at position
     * `index`. It throws an `std::out_of_range` exception when @f$
     * index \geq size() @f$.  It does not allocate memory and its
     * complexity is *effectively* @f$ O(1) @f$.
     */
    reference at(size_type index) const { return impl_.get_check(index); }

    /*!
     * Returns whether the vectors are equal.
     */
    IMMER_NODISCARD bool operator==(const flex_vector& other) const
    {
        return impl_.equals(other.impl_);
    }
    IMMER_NODISCARD bool operator!=(const flex_vector& other) const
    {
        return !(*this == other);
    }

    /*!
     * Returns a flex_vector with `value` inserted at the end.  It may
     * allocate memory and its complexity is *effectively* @f$ O(1) @f$.
     *
     * @rst
     *
     * **Example**
     *   .. literalinclude:: ../example/flex-vector/flex-vector.cpp
     *      :language: c++
     *      :dedent: 8
     *      :start-after: push-back/start
     *      :end-before:  push-back/end
     *
     * @endrst
     */
    IMMER_NODISCARD flex_vector push_back(value_type value) const&
    {
        return impl_.push_back(std::move(value));
    }

    IMMER_NODISCARD decltype(auto) push_back(value_type value) &&
    {
        return push_back_move(move_t{}, std::move(value));
    }

    /*!
     * Returns a flex_vector with `value` inserted at the front.  It may
     * allocate memory and its complexity is @f$ O(log(size)) @f$.
     *
     * @rst
     *
     * **Example**
     *   .. literalinclude:: ../example/flex-vector/flex-vector.cpp
     *      :language: c++
     *      :dedent: 8
     *      :start-after: push-front/start
     *      :end-before:  push-front/end
     *
     * @endrst
     */
    IMMER_NODISCARD flex_vector push_front(value_type value) const
    {
        return flex_vector{}.push_back(value) + *this;
    }

    /*!
     * Returns a flex_vector containing value `value` at position `index`.
     * Undefined for `index >= size()`.
     * It may allocate memory and its complexity is
     * *effectively* @f$ O(1) @f$.
     *
     * @rst
     *
     * **Example**
     *   .. literalinclude:: ../example/flex-vector/flex-vector.cpp
     *      :language: c++
     *      :dedent: 8
     *      :start-after: set/start
     *      :end-before:  set/end
     *
     * @endrst
     */
    IMMER_NODISCARD flex_vector set(size_type index, value_type value) const&
    {
        return impl_.assoc(index, std::move(value));
    }

    IMMER_NODISCARD decltype(auto) set(size_type index, value_type value) &&
    {
        return set_move(move_t{}, index, std::move(value));
    }

    /*!
     * Returns a vector containing the result of the expression
     * `fn((*this)[idx])` at position `idx`.
     * Undefined for `index >= size()`.
     * It may allocate memory and its complexity is
     * *effectively* @f$ O(1) @f$.
     *
     * @rst
     *
     * **Example**
     *   .. literalinclude:: ../example/flex-vector/flex-vector.cpp
     *      :language: c++
     *      :dedent: 8
     *      :start-after: update/start
     *      :end-before:  update/end
     *
     * @endrst

     */
    template <typename FnT>
    IMMER_NODISCARD flex_vector update(size_type index, FnT&& fn) const&
    {
        return impl_.update(index, std::forward<FnT>(fn));
    }

    template <typename FnT>
    IMMER_NODISCARD decltype(auto) update(size_type index, FnT&& fn) &&
    {
        return update_move(move_t{}, index, std::forward<FnT>(fn));
    }

    /*!
     * Returns a vector containing only the first `min(elems, size())`
     * elements. It may allocate memory and its complexity is
     * *effectively* @f$ O(1) @f$.
     *
     * @rst
     *
     * **Example**
     *   .. literalinclude:: ../example/flex-vector/flex-vector.cpp
     *      :language: c++
     *      :dedent: 8
     *      :start-after: take/start
     *      :end-before:  take/end
     *
     * @endrst
     */
    IMMER_NODISCARD flex_vector take(size_type elems) const&
    {
        return impl_.take(elems);
    }

    IMMER_NODISCARD decltype(auto) take(size_type elems) &&
    {
        return take_move(move_t{}, elems);
    }

    /*!
     * Returns a vector without the first `min(elems, size())`
     * elements. It may allocate memory and its complexity is
     * *effectively* @f$ O(1) @f$.
     *
     * @rst
     *
     * **Example**
     *   .. literalinclude:: ../example/flex-vector/flex-vector.cpp
     *      :language: c++
     *      :dedent: 8
     *      :start-after: drop/start
     *      :end-before:  drop/end
     *
     * @endrst
     */
    IMMER_NODISCARD flex_vector drop(size_type elems) const&
    {
        return impl_.drop(elems);
    }

    IMMER_NODISCARD decltype(auto) drop(size_type elems) &&
    {
        return drop_move(move_t{}, elems);
    }

    /*!
     * Concatenation operator. Returns a flex_vector with the contents
     * of `l` followed by those of `r`.  It may allocate memory
     * and its complexity is @f$ O(log(max(size_r, size_l))) @f$
     *
     * @rst
     *
     * **Example**
     *   .. literalinclude:: ../example/flex-vector/flex-vector.cpp
     *      :language: c++
     *      :dedent: 8
     *      :start-after: concat/start
     *      :end-before:  concat/end
     *
     * @endrst
     */
    IMMER_NODISCARD friend flex_vector operator+(const flex_vector& l,
                                                 const flex_vector& r)
    {
        return l.impl_.concat(r.impl_);
    }

    IMMER_NODISCARD friend decltype(auto) operator+(flex_vector&& l,
                                                    const flex_vector& r)
    {
        return concat_move(move_t{}, std::move(l), r);
    }

    IMMER_NODISCARD friend decltype(auto) operator+(const flex_vector& l,
                                                    flex_vector&& r)
    {
        return concat_move(move_t{}, l, std::move(r));
    }

    IMMER_NODISCARD friend decltype(auto) operator+(flex_vector&& l,
                                                    flex_vector&& r)
    {
        return concat_move(move_t{}, std::move(l), std::move(r));
    }

    /*!
     * Returns a flex_vector with the `value` inserted at index
     * `pos`. It may allocate memory and its complexity is @f$
     * O(log(size)) @f$
     *
     * @rst
     *
     * **Example**
     *   .. literalinclude:: ../example/flex-vector/flex-vector.cpp
     *      :language: c++
     *      :dedent: 8
     *      :start-after: insert/start
     *      :end-before:  insert/end
     *
     * @endrst
     */
    IMMER_NODISCARD flex_vector insert(size_type pos, T value) const&
    {
        return take(pos).push_back(std::move(value)) + drop(pos);
    }
    IMMER_NODISCARD decltype(auto) insert(size_type pos, T value) &&
    {
        using std::move;
        auto rs = drop(pos);
        return std::move(*this).take(pos).push_back(std::move(value)) +
               std::move(rs);
    }

    IMMER_NODISCARD flex_vector insert(size_type pos, flex_vector value) const&
    {
        return take(pos) + std::move(value) + drop(pos);
    }
    IMMER_NODISCARD decltype(auto) insert(size_type pos, flex_vector value) &&
    {
        using std::move;
        auto rs = drop(pos);
        return std::move(*this).take(pos) + std::move(value) + std::move(rs);
    }

    /*!
     * Returns a flex_vector without the element at index `pos`. It
     * may allocate memory and its complexity is @f$ O(log(size)) @f$
     *
     * @rst
     *
     * **Example**
     *   .. literalinclude:: ../example/flex-vector/flex-vector.cpp
     *      :language: c++
     *      :dedent: 8
     *      :start-after: erase/start
     *      :end-before:  erase/end
     *
     * @endrst
     */
    IMMER_NODISCARD flex_vector erase(size_type pos) const&
    {
        return take(pos) + drop(pos + 1);
    }
    IMMER_NODISCARD decltype(auto) erase(size_type pos) &&
    {
        auto rs = drop(pos + 1);
        return std::move(*this).take(pos) + std::move(rs);
    }

    IMMER_NODISCARD flex_vector erase(size_type pos, size_type lpos) const&
    {
        return lpos > pos ? take(pos) + drop(lpos) : *this;
    }
    IMMER_NODISCARD decltype(auto) erase(size_type pos, size_type lpos) &&
    {
        if (lpos > pos) {
            auto rs = drop(lpos);
            return std::move(*this).take(pos) + std::move(rs);
        } else {
            return std::move(*this);
        }
    }

    /*!
     * Returns an @a transient form of this container, an
     * `immer::flex_vector_transient`.
     */
    IMMER_NODISCARD transient_type transient() const& { return impl_; }
    IMMER_NODISCARD transient_type transient() && { return std::move(impl_); }

    /*!
     * Returns a value that can be used as identity for the container.  If two
     * values have the same identity, they are guaranteed to be equal and to
     * contain the same objects.  However, two equal containers are not
     * guaranteed to have the same identity.
     */
    std::pair<void*, void*> identity() const
    {
        return {impl_.root, impl_.tail};
    }

    // Semi-private
    const impl_t& impl() const { return impl_; }

#if IMMER_DEBUG_PRINT
    void debug_print(std::ostream& out = std::cerr) const
    {
        impl_.debug_print(out);
    }
#endif

private:
    friend transient_type;

public:
    flex_vector(impl_t impl)
        : impl_(std::move(impl))
    {
#if IMMER_DEBUG_PRINT
        // force the compiler to generate debug_print, so we can call
        // it from a debugger
        [](volatile auto) {}(&flex_vector::debug_print);
#endif
    }

private:
    flex_vector&& push_back_move(std::true_type, value_type value)
    {
        impl_.push_back_mut({}, std::move(value));
        return std::move(*this);
    }
    flex_vector push_back_move(std::false_type, value_type value)
    {
        return impl_.push_back(std::move(value));
    }

    flex_vector&& set_move(std::true_type, size_type index, value_type value)
    {
        impl_.assoc_mut({}, index, std::move(value));
        return std::move(*this);
    }
    flex_vector set_move(std::false_type, size_type index, value_type value)
    {
        return impl_.assoc(index, std::move(value));
    }

    template <typename Fn>
    flex_vector&& update_move(std::true_type, size_type index, Fn&& fn)
    {
        impl_.update_mut({}, index, std::forward<Fn>(fn));
        return std::move(*this);
    }
    template <typename Fn>
    flex_vector update_move(std::false_type, size_type index, Fn&& fn)
    {
        return impl_.update(index, std::forward<Fn>(fn));
    }

    flex_vector&& take_move(std::true_type, size_type elems)
    {
        impl_.take_mut({}, elems);
        return std::move(*this);
    }
    flex_vector take_move(std::false_type, size_type elems)
    {
        return impl_.take(elems);
    }

    flex_vector&& drop_move(std::true_type, size_type elems)
    {
        impl_.drop_mut({}, elems);
        return std::move(*this);
    }
    flex_vector drop_move(std::false_type, size_type elems)
    {
        return impl_.drop(elems);
    }

    static flex_vector&&
    concat_move(std::true_type, flex_vector&& l, const flex_vector& r)
    {
        concat_mut_l(l.impl_, {}, r.impl_);
        return std::move(l);
    }
    static flex_vector&&
    concat_move(std::true_type, const flex_vector& l, flex_vector&& r)
    {
        concat_mut_r(l.impl_, r.impl_, {});
        return std::move(r);
    }
    static flex_vector&&
    concat_move(std::true_type, flex_vector&& l, flex_vector&& r)
    {
        concat_mut_lr_l(l.impl_, {}, r.impl_, {});
        return std::move(l);
    }
    static flex_vector
    concat_move(std::false_type, const flex_vector& l, const flex_vector& r)
    {
        return l.impl_.concat(r.impl_);
    }

    impl_t impl_ = {};
};

static_assert(std::is_nothrow_move_constructible<flex_vector<int>>::value,
              "flex_vector is not nothrow move constructible");
static_assert(std::is_nothrow_move_assignable<flex_vector<int>>::value,
              "flex_vector is not nothrow move assignable");

} // namespace immer

Coverage Report

Created: 2026-02-26 06:19

Line	Count	Source
1		//
2		// immer: immutable data structures for C++
3		// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
4		//
5		// This software is distributed under the Boost Software License, Version 1.0.
6		// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
7		//
8
9		#pragma once
10
11		#include <immer/detail/rbts/rrbtree.hpp>
12		#include <immer/detail/rbts/rrbtree_iterator.hpp>
13		#include <immer/memory_policy.hpp>
14
15		namespace immer {
16
17		template <typename T,
18		typename MP,
19		detail::rbts::bits_t B,
20		detail::rbts::bits_t BL>
21		class vector;
22
23		template <typename T,
24		typename MP,
25		detail::rbts::bits_t B,
26		detail::rbts::bits_t BL>
27		class flex_vector_transient;
28
29		/*!
30		* Immutable sequential container supporting both random access,
31		* structural sharing and efficient concatenation and slicing.
32		*
33		* @tparam T The type of the values to be stored in the container.
34		* @tparam MemoryPolicy Memory management policy. See @ref
35		* memory_policy.
36		*
37		* @rst
38		*
39		* This container is very similar to `vector`_ but also supports
40		* :math:`O(log(size))` concatenation, slicing and insertion at
41		* any point. Its performance characteristics are almost identical
42		* until one of these operations is performed. After that,
43		* performance is degraded by a constant factor that usually oscilates
44		* in the range :math:`[1, 2)` depending on the operation and the
45		* amount of flexible operations that have been performed.
46		*
47		* .. tip:: A `vector`_ can be converted to a `flex_vector`_ in
48		* constant time without any allocation. This is so because the
49		* internal structure of a vector is a strict subset of the
50		* internal structure of a flexible vector. You can take
51		* advantage of this property by creating normal vectors as long as
52		* the flexible operations are not needed, and convert later in
53		* your processing pipeline once and if these are needed.
54		*
55		* @endrst
56		*/
57		template <typename T,
58		typename MemoryPolicy = default_memory_policy,
59		detail::rbts::bits_t B = default_bits,
60		detail::rbts::bits_t BL =
61		detail::rbts::derive_bits_leaf<T, MemoryPolicy, B>>
62		class flex_vector
63		{
64		using impl_t = detail::rbts::rrbtree<T, MemoryPolicy, B, BL>;
65
66		using move_t =
67		std::integral_constant<bool, MemoryPolicy::use_transient_rvalues>;
68
69		public:
70		static constexpr auto bits = B;
71		static constexpr auto bits_leaf = BL;
72		using memory_policy = MemoryPolicy;
73
74		using value_type = T;
75		using reference = const T&;
76		using size_type = detail::rbts::size_t;
77		using difference_type = std::ptrdiff_t;
78		using const_reference = const T&;
79
80		using iterator = detail::rbts::rrbtree_iterator<T, MemoryPolicy, B, BL>;
81		using const_iterator = iterator;
82		using reverse_iterator = std::reverse_iterator<iterator>;
83
84		using transient_type = flex_vector_transient<T, MemoryPolicy, B, BL>;
85
86		/*!
87		* Returns the maximum theoretical size supported by the internal structure
88		* given the current B, BL.
89		*/
90	1.20M	constexpr static size_type max_size() { return impl_t::max_size(); }
91
92		/*!
93		* Default constructor. It creates a flex_vector of `size() == 0`.
94		* It does not allocate memory and its complexity is @f$ O(1) @f$.
95		*/
96	68.9k	flex_vector() = default;
97
98		/*!
99		* Constructs a flex_vector containing the elements in `values`.
100		*/
101		flex_vector(std::initializer_list<T> values)
102		: impl_{impl_t::from_initializer_list(values)}
103		{
104		}
105
106		/*!
107		* Constructs a flex_vector containing the elements in the range
108		* defined by the input iterator `first` and range sentinel `last`.
109		*/
110		template <typename Iter,
111		typename Sent,
112		std::enable_if_t<detail::compatible_sentinel_v<Iter, Sent>,
113		bool> = true>
114		flex_vector(Iter first, Sent last)
115		: impl_{impl_t::from_range(first, last)}
116		{
117		}
118
119		/*!
120		* Constructs a vector containing the element `val` repeated `n`
121		* times.
122		*/
123		flex_vector(size_type n, T v = {})
124		: impl_{impl_t::from_fill(n, v)}
125		{
126		}
127
128		/*!
129		* Default constructor. It creates a flex_vector with the same
130		* contents as `v`. It does not allocate memory and is
131		* @f$ O(1) @f$.
132		*/
133		flex_vector(vector<T, MemoryPolicy, B, BL> v)
134		: impl_{v.impl_.size,
135		v.impl_.shift,
136		v.impl_.root->inc(),
137		v.impl_.tail->inc()}
138		{
139		}
140
141		/*!
142		* Returns an iterator pointing at the first element of the
143		* collection. It does not allocate memory and its complexity is
144		* @f$ O(1) @f$.
145		*/
146		IMMER_NODISCARD iterator begin() const { return {impl_}; }
147
148		/*!
149		* Returns an iterator pointing just after the last element of the
150		* collection. It does not allocate and its complexity is @f$ O(1) @f$.
151		*/
152		IMMER_NODISCARD iterator end() const
153		{
154		return {impl_, typename iterator::end_t{}};
155		}
156
157		/*!
158		* Returns an iterator that traverses the collection backwards,
159		* pointing at the first element of the reversed collection. It
160		* does not allocate memory and its complexity is @f$ O(1) @f$.
161		*/
162		IMMER_NODISCARD reverse_iterator rbegin() const
163		{
164		return reverse_iterator{end()};
165		}
166
167		/*!
168		* Returns an iterator that traverses the collection backwards,
169		* pointing after the last element of the reversed collection. It
170		* does not allocate memory and its complexity is @f$ O(1) @f$.
171		*/
172		IMMER_NODISCARD reverse_iterator rend() const
173		{
174		return reverse_iterator{begin()};
175		}
176
177		/*!
178		* Returns the number of elements in the container. It does
179		* not allocate memory and its complexity is @f$ O(1) @f$.
180		*/
181	2.78M	IMMER_NODISCARD size_type size() const { return impl_.size; }
182
183		/*!
184		* Returns `true` if there are no elements in the container. It
185		* does not allocate memory and its complexity is @f$ O(1) @f$.
186		*/
187		IMMER_NODISCARD bool empty() const { return impl_.size == 0; }
188
189		/*!
190		* Access the last element.
191		*/
192		IMMER_NODISCARD const T& back() const { return impl_.back(); }
193
194		/*!
195		* Access the first element.
196		*/
197		IMMER_NODISCARD const T& front() const { return impl_.front(); }
198
199		/*!
200		* Returns a `const` reference to the element at position `index`.
201		* It is undefined when @f$ 0 index \geq size() @f$. It does not
202		* allocate memory and its complexity is effectively @f$ O(1)
203		* @f$.
204		*/
205		IMMER_NODISCARD reference operator[](size_type index) const
206		{
207		return impl_.get(index);
208		}
209
210		/*!
211		* Returns a `const` reference to the element at position
212		* `index`. It throws an `std::out_of_range` exception when @f$
213		* index \geq size() @f$. It does not allocate memory and its
214		* complexity is effectively @f$ O(1) @f$.
215		*/
216		reference at(size_type index) const { return impl_.get_check(index); }
217
218		/*!
219		* Returns whether the vectors are equal.
220		*/
221		IMMER_NODISCARD bool operator==(const flex_vector& other) const
222	33.9k	{
223	33.9k	return impl_.equals(other.impl_);
224	33.9k	}
225		IMMER_NODISCARD bool operator!=(const flex_vector& other) const
226		{
227		return !(*this == other);
228		}
229
230		/*!
231		* Returns a flex_vector with `value` inserted at the end. It may
232		* allocate memory and its complexity is effectively @f$ O(1) @f$.
233		*
234		* @rst
235		*
236		* Example
237		* .. literalinclude:: ../example/flex-vector/flex-vector.cpp
238		* :language: c++
239		* :dedent: 8
240		* :start-after: push-back/start
241		* :end-before: push-back/end
242		*
243		* @endrst
244		*/
245		IMMER_NODISCARD flex_vector push_back(value_type value) const&
246	353k	{
247	353k	return impl_.push_back(std::move(value));
248	353k	}
249
250		IMMER_NODISCARD decltype(auto) push_back(value_type value) &&
251	32.6k	{
252	32.6k	return push_back_move(move_t{}, std::move(value));
253	32.6k	}
254
255		/*!
256		* Returns a flex_vector with `value` inserted at the front. It may
257		* allocate memory and its complexity is @f$ O(log(size)) @f$.
258		*
259		* @rst
260		*
261		* Example
262		* .. literalinclude:: ../example/flex-vector/flex-vector.cpp
263		* :language: c++
264		* :dedent: 8
265		* :start-after: push-front/start
266		* :end-before: push-front/end
267		*
268		* @endrst
269		*/
270		IMMER_NODISCARD flex_vector push_front(value_type value) const
271		{
272		return flex_vector{}.push_back(value) + *this;
273		}
274
275		/*!
276		* Returns a flex_vector containing value `value` at position `index`.
277		* Undefined for `index >= size()`.
278		* It may allocate memory and its complexity is
279		* effectively @f$ O(1) @f$.
280		*
281		* @rst
282		*
283		* Example
284		* .. literalinclude:: ../example/flex-vector/flex-vector.cpp
285		* :language: c++
286		* :dedent: 8
287		* :start-after: set/start
288		* :end-before: set/end
289		*
290		* @endrst
291		*/
292		IMMER_NODISCARD flex_vector set(size_type index, value_type value) const&
293		{
294		return impl_.assoc(index, std::move(value));
295		}
296
297		IMMER_NODISCARD decltype(auto) set(size_type index, value_type value) &&
298		{
299		return set_move(move_t{}, index, std::move(value));
300		}
301
302		/*!
303		* Returns a vector containing the result of the expression
304		* `fn((*this)[idx])` at position `idx`.
305		* Undefined for `index >= size()`.
306		* It may allocate memory and its complexity is
307		* effectively @f$ O(1) @f$.
308		*
309		* @rst
310		*
311		* Example
312		* .. literalinclude:: ../example/flex-vector/flex-vector.cpp
313		* :language: c++
314		* :dedent: 8
315		* :start-after: update/start
316		* :end-before: update/end
317		*
318		* @endrst
319
320		*/
321		template <typename FnT>
322		IMMER_NODISCARD flex_vector update(size_type index, FnT&& fn) const&
323	154k	{
324	154k	return impl_.update(index, std::forward<FnT>(fn));
325	154k	}
326
327		template <typename FnT>
328		IMMER_NODISCARD decltype(auto) update(size_type index, FnT&& fn) &&
329	35.2k	{
330	35.2k	return update_move(move_t{}, index, std::forward<FnT>(fn));
331	35.2k	}
332
333		/*!
334		* Returns a vector containing only the first `min(elems, size())`
335		* elements. It may allocate memory and its complexity is
336		* effectively @f$ O(1) @f$.
337		*
338		* @rst
339		*
340		* Example
341		* .. literalinclude:: ../example/flex-vector/flex-vector.cpp
342		* :language: c++
343		* :dedent: 8
344		* :start-after: take/start
345		* :end-before: take/end
346		*
347		* @endrst
348		*/
349		IMMER_NODISCARD flex_vector take(size_type elems) const&
350	25.7k	{
351	25.7k	return impl_.take(elems);
352	25.7k	}
353
354		IMMER_NODISCARD decltype(auto) take(size_type elems) &&
355	39.1k	{
356	39.1k	return take_move(move_t{}, elems);
357	39.1k	}
358
359		/*!
360		* Returns a vector without the first `min(elems, size())`
361		* elements. It may allocate memory and its complexity is
362		* effectively @f$ O(1) @f$.
363		*
364		* @rst
365		*
366		* Example
367		* .. literalinclude:: ../example/flex-vector/flex-vector.cpp
368		* :language: c++
369		* :dedent: 8
370		* :start-after: drop/start
371		* :end-before: drop/end
372		*
373		* @endrst
374		*/
375		IMMER_NODISCARD flex_vector drop(size_type elems) const&
376	26.1k	{
377	26.1k	return impl_.drop(elems);
378	26.1k	}
379
380		IMMER_NODISCARD decltype(auto) drop(size_type elems) &&
381	31.1k	{
382	31.1k	return drop_move(move_t{}, elems);
383	31.1k	}
384
385		/*!
386		* Concatenation operator. Returns a flex_vector with the contents
387		* of `l` followed by those of `r`. It may allocate memory
388		* and its complexity is @f$ O(log(max(size_r, size_l))) @f$
389		*
390		* @rst
391		*
392		* Example
393		* .. literalinclude:: ../example/flex-vector/flex-vector.cpp
394		* :language: c++
395		* :dedent: 8
396		* :start-after: concat/start
397		* :end-before: concat/end
398		*
399		* @endrst
400		*/
401		IMMER_NODISCARD friend flex_vector operator+(const flex_vector& l,
402		const flex_vector& r)
403	806k	{
404	806k	return l.impl_.concat(r.impl_);
405	806k	}
406
407		IMMER_NODISCARD friend decltype(auto) operator+(flex_vector&& l,
408		const flex_vector& r)
409	304k	{
410	304k	return concat_move(move_t{}, std::move(l), r);
411	304k	}
412
413		IMMER_NODISCARD friend decltype(auto) operator+(const flex_vector& l,
414		flex_vector&& r)
415	3.24k	{
416	3.24k	return concat_move(move_t{}, l, std::move(r));
417	3.24k	}
418
419		IMMER_NODISCARD friend decltype(auto) operator+(flex_vector&& l,
420		flex_vector&& r)
421	24.6k	{
422	24.6k	return concat_move(move_t{}, std::move(l), std::move(r));
423	24.6k	}
424
425		/*!
426		* Returns a flex_vector with the `value` inserted at index
427		* `pos`. It may allocate memory and its complexity is @f$
428		* O(log(size)) @f$
429		*
430		* @rst
431		*
432		* Example
433		* .. literalinclude:: ../example/flex-vector/flex-vector.cpp
434		* :language: c++
435		* :dedent: 8
436		* :start-after: insert/start
437		* :end-before: insert/end
438		*
439		* @endrst
440		*/
441		IMMER_NODISCARD flex_vector insert(size_type pos, T value) const&
442	20.0k	{
443	20.0k	return take(pos).push_back(std::move(value)) + drop(pos);
444	20.0k	}
445		IMMER_NODISCARD decltype(auto) insert(size_type pos, T value) &&
446		{
447		using std::move;
448		auto rs = drop(pos);
449		return std::move(*this).take(pos).push_back(std::move(value)) +
450		std::move(rs);
451		}
452
453		IMMER_NODISCARD flex_vector insert(size_type pos, flex_vector value) const&
454		{
455		return take(pos) + std::move(value) + drop(pos);
456		}
457		IMMER_NODISCARD decltype(auto) insert(size_type pos, flex_vector value) &&
458		{
459		using std::move;
460		auto rs = drop(pos);
461		return std::move(*this).take(pos) + std::move(value) + std::move(rs);
462		}
463
464		/*!
465		* Returns a flex_vector without the element at index `pos`. It
466		* may allocate memory and its complexity is @f$ O(log(size)) @f$
467		*
468		* @rst
469		*
470		* Example
471		* .. literalinclude:: ../example/flex-vector/flex-vector.cpp
472		* :language: c++
473		* :dedent: 8
474		* :start-after: erase/start
475		* :end-before: erase/end
476		*
477		* @endrst
478		*/
479		IMMER_NODISCARD flex_vector erase(size_type pos) const&
480	3.02k	{
481	3.02k	return take(pos) + drop(pos + 1);
482	3.02k	}
483		IMMER_NODISCARD decltype(auto) erase(size_type pos) &&
484		{
485		auto rs = drop(pos + 1);
486		return std::move(*this).take(pos) + std::move(rs);
487		}
488
489		IMMER_NODISCARD flex_vector erase(size_type pos, size_type lpos) const&
490		{
491		return lpos > pos ? take(pos) + drop(lpos) : *this;
492		}
493		IMMER_NODISCARD decltype(auto) erase(size_type pos, size_type lpos) &&
494		{
495		if (lpos > pos) {
496		auto rs = drop(lpos);
497		return std::move(*this).take(pos) + std::move(rs);
498		} else {
499		return std::move(*this);
500		}
501		}
502
503		/*!
504		* Returns an @a transient form of this container, an
505		* `immer::flex_vector_transient`.
506		*/
507		IMMER_NODISCARD transient_type transient() const& { return impl_; }
508		IMMER_NODISCARD transient_type transient() && { return std::move(impl_); }
509
510		/*!
511		* Returns a value that can be used as identity for the container. If two
512		* values have the same identity, they are guaranteed to be equal and to
513		* contain the same objects. However, two equal containers are not
514		* guaranteed to have the same identity.
515		*/
516		std::pair<void, void> identity() const
517		{
518		return {impl_.root, impl_.tail};
519		}
520
521		// Semi-private
522		const impl_t& impl() const { return impl_; }
523
524		#if IMMER_DEBUG_PRINT
525		void debug_print(std::ostream& out = std::cerr) const
526		{
527		impl_.debug_print(out);
528		}
529		#endif
530
531		private:
532		friend transient_type;
533
534		public:
535		flex_vector(impl_t impl)
536	1.36M	: impl_(std::move(impl))
537	1.36M	{
538		#if IMMER_DEBUG_PRINT
539		// force the compiler to generate debug_print, so we can call
540		// it from a debugger
541		[](volatile auto) {}(&flex_vector::debug_print);
542		#endif
543	1.36M	}
544
545		private:
546		flex_vector&& push_back_move(std::true_type, value_type value)
547	32.6k	{
548	32.6k	impl_.push_back_mut({}, std::move(value));
549	32.6k	return std::move(*this);
550	32.6k	}
551		flex_vector push_back_move(std::false_type, value_type value)
552		{
553		return impl_.push_back(std::move(value));
554		}
555
556		flex_vector&& set_move(std::true_type, size_type index, value_type value)
557		{
558		impl_.assoc_mut({}, index, std::move(value));
559		return std::move(*this);
560		}
561		flex_vector set_move(std::false_type, size_type index, value_type value)
562		{
563		return impl_.assoc(index, std::move(value));
564		}
565
566		template <typename Fn>
567		flex_vector&& update_move(std::true_type, size_type index, Fn&& fn)
568	35.2k	{
569	35.2k	impl_.update_mut({}, index, std::forward<Fn>(fn));
570	35.2k	return std::move(*this);
571	35.2k	}
572		template <typename Fn>
573		flex_vector update_move(std::false_type, size_type index, Fn&& fn)
574		{
575		return impl_.update(index, std::forward<Fn>(fn));
576		}
577
578		flex_vector&& take_move(std::true_type, size_type elems)
579	39.1k	{
580	39.1k	impl_.take_mut({}, elems);
581	39.1k	return std::move(*this);
582	39.1k	}
583		flex_vector take_move(std::false_type, size_type elems)
584		{
585		return impl_.take(elems);
586		}
587
588		flex_vector&& drop_move(std::true_type, size_type elems)
589	31.1k	{
590	31.1k	impl_.drop_mut({}, elems);
591	31.1k	return std::move(*this);
592	31.1k	}
593		flex_vector drop_move(std::false_type, size_type elems)
594		{
595		return impl_.drop(elems);
596		}
597
598		static flex_vector&&
599		concat_move(std::true_type, flex_vector&& l, const flex_vector& r)
600	304k	{
601	304k	concat_mut_l(l.impl_, {}, r.impl_);
602	304k	return std::move(l);
603	304k	}
604		static flex_vector&&
605		concat_move(std::true_type, const flex_vector& l, flex_vector&& r)
606	3.24k	{
607	3.24k	concat_mut_r(l.impl_, r.impl_, {});
608	3.24k	return std::move(r);
609	3.24k	}
610		static flex_vector&&
611		concat_move(std::true_type, flex_vector&& l, flex_vector&& r)
612	24.6k	{
613	24.6k	concat_mut_lr_l(l.impl_, {}, r.impl_, {});
614	24.6k	return std::move(l);
615	24.6k	}
616		static flex_vector
617		concat_move(std::false_type, const flex_vector& l, const flex_vector& r)
618		{
619		return l.impl_.concat(r.impl_);
620		}
621
622		impl_t impl_ = {};
623		};
624
625		static_assert(std::is_nothrow_move_constructible<flex_vector<int>>::value,
626		"flex_vector is not nothrow move constructible");
627		static_assert(std::is_nothrow_move_assignable<flex_vector<int>>::value,
628		"flex_vector is not nothrow move assignable");
629
630		} // namespace immer