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/memory_policy.hpp> |
12 | #include <immer/detail/arrays/with_capacity.hpp> |
13 | |
14 | namespace immer { |
15 | |
16 | template <typename T, typename MemoryPolicy> |
17 | class array_transient; |
18 | |
19 | /*! |
20 | * Immutable container that stores a sequence of elements in |
21 | * contiguous memory. |
22 | * |
23 | * @tparam T The type of the values to be stored in the container. |
24 | * |
25 | * @rst |
26 | * |
27 | * It supports the most efficient iteration and random access, |
28 | * equivalent to a ``std::vector`` or ``std::array``, but all |
29 | * manipulations are :math:`O(size)`. |
30 | * |
31 | * .. tip:: Don't be fooled by the bad complexity of this data |
32 | * structure. It is a great choice for short sequence or when it |
33 | * is seldom or never changed. This depends on the ``sizeof(T)`` |
34 | * and the expensiveness of its ``T``'s copy constructor, in case |
35 | * of doubt, measure. For basic types, using an `array` when |
36 | * :math:`n < 100` is a good heuristic. |
37 | * |
38 | * @endrst |
39 | */ |
40 | template <typename T, typename MemoryPolicy = default_memory_policy> |
41 | class array |
42 | { |
43 | using impl_t = std::conditional_t< |
44 | MemoryPolicy::use_transient_rvalues, |
45 | detail::arrays::with_capacity<T, MemoryPolicy>, |
46 | detail::arrays::no_capacity<T, MemoryPolicy>>; |
47 | |
48 | using move_t = |
49 | std::integral_constant<bool, MemoryPolicy::use_transient_rvalues>; |
50 | |
51 | public: |
52 | using value_type = T; |
53 | using reference = const T&; |
54 | using size_type = std::size_t; |
55 | using difference_type = std::ptrdiff_t; |
56 | using const_reference = const T&; |
57 | |
58 | using iterator = const T*; |
59 | using const_iterator = iterator; |
60 | using reverse_iterator = std::reverse_iterator<iterator>; |
61 | |
62 | using memory_policy = MemoryPolicy; |
63 | using transient_type = array_transient<T, MemoryPolicy>; |
64 | |
65 | /*! |
66 | * Default constructor. It creates an array of `size() == 0`. It |
67 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
68 | */ |
69 | array() = default; |
70 | |
71 | /*! |
72 | * Constructs an array containing the elements in `values`. |
73 | */ |
74 | array(std::initializer_list<T> values) |
75 | : impl_{impl_t::from_initializer_list(values)} |
76 | {} |
77 | |
78 | /*! |
79 | * Constructs a array containing the elements in the range |
80 | * defined by the forward iterator `first` and range sentinel `last`. |
81 | */ |
82 | template <typename Iter, typename Sent, |
83 | std::enable_if_t |
84 | <detail::compatible_sentinel_v<Iter, Sent> |
85 | && detail::is_forward_iterator_v<Iter>, bool> = true> |
86 | array(Iter first, Sent last) |
87 | : impl_{impl_t::from_range(first, last)} |
88 | {} |
89 | |
90 | /*! |
91 | * Constructs a array containing the element `val` repeated `n` |
92 | * times. |
93 | */ |
94 | array(size_type n, T v = {}) |
95 | : impl_{impl_t::from_fill(n, v)} |
96 | {} |
97 | |
98 | /*! |
99 | * Returns an iterator pointing at the first element of the |
100 | * collection. It does not allocate memory and its complexity is |
101 | * @f$ O(1) @f$. |
102 | */ |
103 | IMMER_NODISCARD iterator begin() const { return impl_.data(); } |
104 | |
105 | /*! |
106 | * Returns an iterator pointing just after the last element of the |
107 | * collection. It does not allocate and its complexity is @f$ O(1) @f$. |
108 | */ |
109 | IMMER_NODISCARD iterator end() const { return impl_.data() + impl_.size; } |
110 | |
111 | /*! |
112 | * Returns an iterator that traverses the collection backwards, |
113 | * pointing at the first element of the reversed collection. It |
114 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
115 | */ |
116 | IMMER_NODISCARD reverse_iterator rbegin() const { return reverse_iterator{end()}; } |
117 | |
118 | /*! |
119 | * Returns an iterator that traverses the collection backwards, |
120 | * pointing after the last element of the reversed collection. It |
121 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
122 | */ |
123 | IMMER_NODISCARD reverse_iterator rend() const { return reverse_iterator{begin()}; } |
124 | |
125 | /*! |
126 | * Returns the number of elements in the container. It does |
127 | * not allocate memory and its complexity is @f$ O(1) @f$. |
128 | */ |
129 | IMMER_NODISCARD std::size_t size() const { return impl_.size; } |
130 | |
131 | /*! |
132 | * Returns `true` if there are no elements in the container. It |
133 | * does not allocate memory and its complexity is @f$ O(1) @f$. |
134 | */ |
135 | IMMER_NODISCARD bool empty() const { return impl_.size == 0; } |
136 | |
137 | /*! |
138 | * Access the raw data. |
139 | */ |
140 | IMMER_NODISCARD const T* data() const { return impl_.data(); } |
141 | |
142 | /*! |
143 | * Access the last element. |
144 | */ |
145 | IMMER_NODISCARD const T& back() const { return data()[size() - 1]; } |
146 | |
147 | /*! |
148 | * Access the first element. |
149 | */ |
150 | IMMER_NODISCARD const T& front() const { return data()[0]; } |
151 | |
152 | /*! |
153 | * Returns a `const` reference to the element at position `index`. |
154 | * It is undefined when @f$ 0 index \geq size() @f$. It does not |
155 | * allocate memory and its complexity is *effectively* @f$ O(1) |
156 | * @f$. |
157 | */ |
158 | IMMER_NODISCARD reference operator[] (size_type index) const |
159 | { return impl_.get(index); } |
160 | |
161 | /*! |
162 | * Returns a `const` reference to the element at position |
163 | * `index`. It throws an `std::out_of_range` exception when @f$ |
164 | * index \geq size() @f$. It does not allocate memory and its |
165 | * complexity is *effectively* @f$ O(1) @f$. |
166 | */ |
167 | reference at(size_type index) const |
168 | { return impl_.get_check(index); } |
169 | |
170 | /*! |
171 | * Returns whether the vectors are equal. |
172 | */ |
173 | IMMER_NODISCARD bool operator==(const array& other) const |
174 | { return impl_.equals(other.impl_); } |
175 | IMMER_NODISCARD bool operator!=(const array& other) const |
176 | { return !(*this == other); } |
177 | |
178 | /*! |
179 | * Returns an array with `value` inserted at the end. It may |
180 | * allocate memory and its complexity is @f$ O(size) @f$. |
181 | * |
182 | * @rst |
183 | * |
184 | * **Example** |
185 | * .. literalinclude:: ../example/array/array.cpp |
186 | * :language: c++ |
187 | * :dedent: 8 |
188 | * :start-after: push-back/start |
189 | * :end-before: push-back/end |
190 | * |
191 | * @endrst |
192 | */ |
193 | IMMER_NODISCARD array push_back(value_type value) const& |
194 | { return impl_.push_back(std::move(value)); } |
195 | |
196 | IMMER_NODISCARD decltype(auto) push_back(value_type value) && |
197 | { return push_back_move(move_t{}, std::move(value)); } |
198 | |
199 | /*! |
200 | * Returns an array containing value `value` at position `idx`. |
201 | * Undefined for `index >= size()`. |
202 | * It may allocate memory and its complexity is @f$ O(size) @f$. |
203 | * |
204 | * @rst |
205 | * |
206 | * **Example** |
207 | * .. literalinclude:: ../example/array/array.cpp |
208 | * :language: c++ |
209 | * :dedent: 8 |
210 | * :start-after: set/start |
211 | * :end-before: set/end |
212 | * |
213 | * @endrst |
214 | */ |
215 | IMMER_NODISCARD array set(std::size_t index, value_type value) const& |
216 | { return impl_.assoc(index, std::move(value)); } |
217 | |
218 | IMMER_NODISCARD decltype(auto) set(size_type index, value_type value) && |
219 | { return set_move(move_t{}, index, std::move(value)); } |
220 | |
221 | /*! |
222 | * Returns an array containing the result of the expression |
223 | * `fn((*this)[idx])` at position `idx`. |
224 | * Undefined for `index >= size()`. |
225 | * It may allocate memory and its complexity is @f$ O(size) @f$. |
226 | * |
227 | * @rst |
228 | * |
229 | * **Example** |
230 | * .. literalinclude:: ../example/array/array.cpp |
231 | * :language: c++ |
232 | * :dedent: 8 |
233 | * :start-after: update/start |
234 | * :end-before: update/end |
235 | * |
236 | * @endrst |
237 | */ |
238 | template <typename FnT> |
239 | IMMER_NODISCARD array update(std::size_t index, FnT&& fn) const& |
240 | { return impl_.update(index, std::forward<FnT>(fn)); } |
241 | |
242 | template <typename FnT> |
243 | IMMER_NODISCARD decltype(auto) update(size_type index, FnT&& fn) && |
244 | { return update_move(move_t{}, index, std::forward<FnT>(fn)); } |
245 | |
246 | /*! |
247 | * Returns a array containing only the first `min(elems, size())` |
248 | * elements. It may allocate memory and its complexity is |
249 | * *effectively* @f$ O(1) @f$. |
250 | * |
251 | * @rst |
252 | * |
253 | * **Example** |
254 | * .. literalinclude:: ../example/array/array.cpp |
255 | * :language: c++ |
256 | * :dedent: 8 |
257 | * :start-after: take/start |
258 | * :end-before: take/end |
259 | * |
260 | * @endrst |
261 | */ |
262 | IMMER_NODISCARD array take(size_type elems) const& |
263 | { return impl_.take(elems); } |
264 | |
265 | IMMER_NODISCARD decltype(auto) take(size_type elems) && |
266 | { return take_move(move_t{}, elems); } |
267 | |
268 | /*! |
269 | * Returns an @a transient form of this container, an |
270 | * `immer::array_transient`. |
271 | */ |
272 | IMMER_NODISCARD transient_type transient() const& |
273 | { return transient_type{ impl_ }; } |
274 | IMMER_NODISCARD transient_type transient() && |
275 | { return transient_type{ std::move(impl_) }; } |
276 | |
277 | // Semi-private |
278 | const impl_t& impl() const { return impl_; } |
279 | |
280 | private: |
281 | friend transient_type; |
282 | |
283 | array(impl_t impl) : impl_(std::move(impl)) {} |
284 | |
285 | array&& push_back_move(std::true_type, value_type value) |
286 | { impl_.push_back_mut({}, std::move(value)); return std::move(*this); } |
287 | array push_back_move(std::false_type, value_type value) |
288 | { return impl_.push_back(std::move(value)); } |
289 | |
290 | array&& set_move(std::true_type, size_type index, value_type value) |
291 | { impl_.assoc_mut({}, index, std::move(value)); return std::move(*this); } |
292 | array set_move(std::false_type, size_type index, value_type value) |
293 | { return impl_.assoc(index, std::move(value)); } |
294 | |
295 | template <typename Fn> |
296 | array&& update_move(std::true_type, size_type index, Fn&& fn) |
297 | { impl_.update_mut({}, index, std::forward<Fn>(fn)); return std::move(*this); } |
298 | template <typename Fn> |
299 | array update_move(std::false_type, size_type index, Fn&& fn) |
300 | { return impl_.update(index, std::forward<Fn>(fn)); } |
301 | |
302 | array&& take_move(std::true_type, size_type elems) |
303 | { impl_.take_mut({}, elems); return std::move(*this); } |
304 | array take_move(std::false_type, size_type elems) |
305 | { return impl_.take(elems); } |
306 | |
307 | impl_t impl_ = impl_t::empty(); |
308 | }; |
309 | |
310 | } /* namespace immer */ |
311 | |