]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Container varray |
2 | // | |
3 | // Copyright (c) 2012-2015 Adam Wulkiewicz, Lodz, Poland. | |
4 | // Copyright (c) 2011-2013 Andrew Hundt. | |
5 | // | |
6 | // Use, modification and distribution is subject to the Boost Software License, | |
7 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
8 | // http://www.boost.org/LICENSE_1_0.txt) | |
9 | ||
10 | #ifndef BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_HPP | |
11 | #define BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_HPP | |
12 | ||
13 | // TODO - REMOVE/CHANGE | |
14 | #include <boost/container/detail/config_begin.hpp> | |
15 | #include <boost/container/detail/workaround.hpp> | |
16 | ||
17 | #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
18 | #include <boost/move/detail/fwd_macros.hpp> | |
19 | #endif | |
20 | ||
21 | #include <boost/config.hpp> | |
22 | #include <boost/swap.hpp> | |
23 | #include <boost/integer.hpp> | |
24 | ||
25 | #include <boost/mpl/assert.hpp> | |
26 | ||
27 | #include <boost/type_traits/is_unsigned.hpp> | |
28 | #include <boost/type_traits/alignment_of.hpp> | |
29 | #include <boost/type_traits/aligned_storage.hpp> | |
30 | ||
31 | // TODO - use std::reverse_iterator and std::iterator_traits | |
32 | // instead Boost.Iterator to remove dependency? | |
33 | // or boost/detail/iterator.hpp ? | |
34 | #include <boost/iterator/reverse_iterator.hpp> | |
35 | #include <boost/iterator/iterator_concepts.hpp> | |
36 | ||
37 | #include <boost/geometry/index/detail/assert.hpp> | |
38 | #include <boost/geometry/index/detail/exception.hpp> | |
39 | ||
40 | #include <boost/geometry/index/detail/varray_detail.hpp> | |
41 | ||
42 | #include <boost/concept_check.hpp> | |
43 | ||
44 | /*! | |
45 | \defgroup varray_non_member varray non-member functions | |
46 | */ | |
47 | ||
48 | namespace boost { namespace geometry { namespace index { namespace detail { | |
49 | ||
50 | namespace varray_detail { | |
51 | ||
52 | template <typename Value, std::size_t Capacity> | |
53 | struct varray_traits | |
54 | { | |
55 | typedef Value value_type; | |
56 | typedef std::size_t size_type; | |
57 | typedef std::ptrdiff_t difference_type; | |
58 | typedef Value * pointer; | |
59 | typedef const Value * const_pointer; | |
60 | typedef Value & reference; | |
61 | typedef const Value & const_reference; | |
62 | ||
63 | typedef boost::false_type use_memop_in_swap_and_move; | |
64 | typedef boost::false_type use_optimized_swap; | |
65 | typedef boost::false_type disable_trivial_init; | |
66 | }; | |
67 | ||
68 | template <typename Varray> | |
69 | struct checker | |
70 | { | |
71 | typedef typename Varray::size_type size_type; | |
72 | typedef typename Varray::const_iterator const_iterator; | |
73 | ||
74 | static inline void check_capacity(Varray const& v, size_type s) | |
75 | { | |
76 | BOOST_GEOMETRY_INDEX_ASSERT(s <= v.capacity(), "size too big"); | |
77 | ||
78 | ::boost::ignore_unused_variable_warning(v); | |
79 | ::boost::ignore_unused_variable_warning(s); | |
80 | } | |
81 | ||
82 | static inline void throw_out_of_bounds(Varray const& v, size_type i) | |
83 | { | |
84 | if ( v.size() <= i ) | |
85 | throw_out_of_range("index out of bounds"); | |
86 | ||
87 | ::boost::ignore_unused_variable_warning(v); | |
88 | ::boost::ignore_unused_variable_warning(i); | |
89 | } | |
90 | ||
91 | static inline void check_index(Varray const& v, size_type i) | |
92 | { | |
93 | BOOST_GEOMETRY_INDEX_ASSERT(i < v.size(), "index out of bounds"); | |
94 | ||
95 | ::boost::ignore_unused_variable_warning(v); | |
96 | ::boost::ignore_unused_variable_warning(i); | |
97 | } | |
98 | ||
99 | static inline void check_not_empty(Varray const& v) | |
100 | { | |
101 | BOOST_GEOMETRY_INDEX_ASSERT(!v.empty(), "the container is empty"); | |
102 | ||
103 | ::boost::ignore_unused_variable_warning(v); | |
104 | } | |
105 | ||
106 | static inline void check_iterator_end_neq(Varray const& v, const_iterator position) | |
107 | { | |
108 | BOOST_GEOMETRY_INDEX_ASSERT(v.begin() <= position && position < v.end(), "iterator out of bounds"); | |
109 | ||
110 | ::boost::ignore_unused_variable_warning(v); | |
111 | ::boost::ignore_unused_variable_warning(position); | |
112 | } | |
113 | ||
114 | static inline void check_iterator_end_eq(Varray const& v, const_iterator position) | |
115 | { | |
116 | BOOST_GEOMETRY_INDEX_ASSERT(v.begin() <= position && position <= v.end(), "iterator out of bounds"); | |
117 | ||
118 | ::boost::ignore_unused_variable_warning(v); | |
119 | ::boost::ignore_unused_variable_warning(position); | |
120 | } | |
121 | }; | |
122 | ||
123 | } // namespace varray_detail | |
124 | ||
125 | /*! | |
126 | \brief A variable-size array container with fixed capacity. | |
127 | ||
128 | varray is a sequence container like boost::container::vector with contiguous storage that can | |
129 | change in size, along with the static allocation, low overhead, and fixed capacity of boost::array. | |
130 | ||
131 | A varray is a sequence that supports random access to elements, constant time insertion and | |
132 | removal of elements at the end, and linear time insertion and removal of elements at the beginning or | |
133 | in the middle. The number of elements in a varray may vary dynamically up to a fixed capacity | |
134 | because elements are stored within the object itself similarly to an array. However, objects are | |
135 | initialized as they are inserted into varray unlike C arrays or std::array which must construct | |
136 | all elements on instantiation. The behavior of varray enables the use of statically allocated | |
137 | elements in cases with complex object lifetime requirements that would otherwise not be trivially | |
138 | possible. | |
139 | ||
140 | \par Error Handling | |
141 | Insertion beyond the capacity and out of bounds errors result in undefined behavior unless | |
142 | otherwise specified. In this respect if size() == capacity(), then varray::push_back() | |
143 | behaves like std::vector pop_front() if size() == empty(). The reason for this difference | |
144 | is because unlike vectors, varray does not perform allocation. | |
145 | ||
146 | \par Advanced Usage | |
147 | Error handling behavior can be modified to more closely match std::vector exception behavior | |
148 | when exceeding bounds by providing an alternate Strategy and varray_traits instantiation. | |
149 | ||
150 | \tparam Value The type of element that will be stored. | |
151 | \tparam Capacity The maximum number of elements varray can store, fixed at compile time. | |
152 | \tparam Strategy Defines the public typedefs and error handlers, | |
153 | implements StaticVectorStrategy and has some similarities | |
154 | to an Allocator. | |
155 | */ | |
156 | template <typename Value, std::size_t Capacity> | |
157 | class varray | |
158 | { | |
159 | typedef varray_detail::varray_traits<Value, Capacity> vt; | |
160 | typedef varray_detail::checker<varray> errh; | |
161 | ||
162 | BOOST_MPL_ASSERT_MSG( | |
163 | ( boost::is_unsigned<typename vt::size_type>::value && | |
164 | sizeof(typename boost::uint_value_t<Capacity>::least) <= sizeof(typename vt::size_type) ), | |
165 | SIZE_TYPE_IS_TOO_SMALL_FOR_SPECIFIED_CAPACITY, | |
166 | (varray) | |
167 | ); | |
168 | ||
169 | typedef boost::aligned_storage< | |
170 | sizeof(Value[Capacity]), | |
171 | boost::alignment_of<Value[Capacity]>::value | |
172 | > aligned_storage_type; | |
173 | ||
174 | template <typename V, std::size_t C> | |
175 | friend class varray; | |
176 | ||
177 | BOOST_COPYABLE_AND_MOVABLE(varray) | |
178 | ||
179 | #ifdef BOOST_NO_CXX11_RVALUE_REFERENCES | |
180 | public: | |
181 | template <std::size_t C> | |
182 | varray & operator=(varray<Value, C> & sv) | |
183 | { | |
184 | typedef varray<Value, C> other; | |
185 | this->operator=(static_cast<const ::boost::rv<other> &>(const_cast<const other &>(sv))); | |
186 | return *this; | |
187 | } | |
188 | #endif | |
189 | ||
190 | public: | |
191 | //! @brief The type of elements stored in the container. | |
192 | typedef typename vt::value_type value_type; | |
193 | //! @brief The unsigned integral type used by the container. | |
194 | typedef typename vt::size_type size_type; | |
195 | //! @brief The pointers difference type. | |
196 | typedef typename vt::difference_type difference_type; | |
197 | //! @brief The pointer type. | |
198 | typedef typename vt::pointer pointer; | |
199 | //! @brief The const pointer type. | |
200 | typedef typename vt::const_pointer const_pointer; | |
201 | //! @brief The value reference type. | |
202 | typedef typename vt::reference reference; | |
203 | //! @brief The value const reference type. | |
204 | typedef typename vt::const_reference const_reference; | |
205 | ||
206 | //! @brief The iterator type. | |
207 | typedef pointer iterator; | |
208 | //! @brief The const iterator type. | |
209 | typedef const_pointer const_iterator; | |
210 | //! @brief The reverse iterator type. | |
211 | typedef boost::reverse_iterator<iterator> reverse_iterator; | |
212 | //! @brief The const reverse iterator. | |
213 | typedef boost::reverse_iterator<const_iterator> const_reverse_iterator; | |
214 | ||
215 | //! @brief Constructs an empty varray. | |
216 | //! | |
217 | //! @par Throws | |
218 | //! Nothing. | |
219 | //! | |
220 | //! @par Complexity | |
221 | //! Constant O(1). | |
222 | varray() | |
223 | : m_size(0) | |
224 | {} | |
225 | ||
226 | //! @pre <tt>count <= capacity()</tt> | |
227 | //! | |
228 | //! @brief Constructs a varray containing count default constructed Values. | |
229 | //! | |
230 | //! @param count The number of values which will be contained in the container. | |
231 | //! | |
232 | //! @par Throws | |
233 | //! If Value's default constructor throws. | |
234 | //! @internal | |
235 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
236 | //! @endinternal | |
237 | //! | |
238 | //! @par Complexity | |
239 | //! Linear O(N). | |
240 | explicit varray(size_type count) | |
241 | : m_size(0) | |
242 | { | |
243 | this->resize(count); // may throw | |
244 | } | |
245 | ||
246 | //! @pre <tt>count <= capacity()</tt> | |
247 | //! | |
248 | //! @brief Constructs a varray containing count copies of value. | |
249 | //! | |
250 | //! @param count The number of copies of a values that will be contained in the container. | |
251 | //! @param value The value which will be used to copy construct values. | |
252 | //! | |
253 | //! @par Throws | |
254 | //! If Value's copy constructor throws. | |
255 | //! @internal | |
256 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
257 | //! @endinternal | |
258 | //! | |
259 | //! @par Complexity | |
260 | //! Linear O(N). | |
261 | varray(size_type count, value_type const& value) | |
262 | : m_size(0) | |
263 | { | |
264 | this->resize(count, value); // may throw | |
265 | } | |
266 | ||
267 | //! @pre | |
268 | //! @li <tt>distance(first, last) <= capacity()</tt> | |
269 | //! @li Iterator must meet the \c ForwardTraversalIterator concept. | |
270 | //! | |
271 | //! @brief Constructs a varray containing copy of a range <tt>[first, last)</tt>. | |
272 | //! | |
273 | //! @param first The iterator to the first element in range. | |
274 | //! @param last The iterator to the one after the last element in range. | |
275 | //! | |
276 | //! @par Throws | |
277 | //! If Value's constructor taking a dereferenced Iterator throws. | |
278 | //! @internal | |
279 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
280 | //! @endinternal | |
281 | //! | |
282 | //! @par Complexity | |
283 | //! Linear O(N). | |
284 | template <typename Iterator> | |
285 | varray(Iterator first, Iterator last) | |
286 | : m_size(0) | |
287 | { | |
288 | BOOST_CONCEPT_ASSERT((boost_concepts::ForwardTraversal<Iterator>)); // Make sure you passed a ForwardIterator | |
289 | ||
290 | this->assign(first, last); // may throw | |
291 | } | |
292 | ||
293 | //! @brief Constructs a copy of other varray. | |
294 | //! | |
295 | //! @param other The varray which content will be copied to this one. | |
296 | //! | |
297 | //! @par Throws | |
298 | //! If Value's copy constructor throws. | |
299 | //! | |
300 | //! @par Complexity | |
301 | //! Linear O(N). | |
302 | varray(varray const& other) | |
303 | : m_size(other.size()) | |
304 | { | |
305 | namespace sv = varray_detail; | |
306 | sv::uninitialized_copy(other.begin(), other.end(), this->begin()); // may throw | |
307 | } | |
308 | ||
309 | //! @pre <tt>other.size() <= capacity()</tt>. | |
310 | //! | |
311 | //! @brief Constructs a copy of other varray. | |
312 | //! | |
313 | //! @param other The varray which content will be copied to this one. | |
314 | //! | |
315 | //! @par Throws | |
316 | //! If Value's copy constructor throws. | |
317 | //! @internal | |
318 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
319 | //! @endinternal | |
320 | //! | |
321 | //! @par Complexity | |
322 | //! Linear O(N). | |
323 | template <std::size_t C> | |
324 | varray(varray<value_type, C> const& other) | |
325 | : m_size(other.size()) | |
326 | { | |
327 | errh::check_capacity(*this, other.size()); // may throw | |
328 | ||
329 | namespace sv = varray_detail; | |
330 | sv::uninitialized_copy(other.begin(), other.end(), this->begin()); // may throw | |
331 | } | |
332 | ||
333 | //! @brief Copy assigns Values stored in the other varray to this one. | |
334 | //! | |
335 | //! @param other The varray which content will be copied to this one. | |
336 | //! | |
337 | //! @par Throws | |
338 | //! If Value's copy constructor or copy assignment throws. | |
339 | //! | |
340 | //! @par Complexity | |
341 | //! Linear O(N). | |
342 | varray & operator=(BOOST_COPY_ASSIGN_REF(varray) other) | |
343 | { | |
344 | this->assign(other.begin(), other.end()); // may throw | |
345 | ||
346 | return *this; | |
347 | } | |
348 | ||
349 | //! @pre <tt>other.size() <= capacity()</tt> | |
350 | //! | |
351 | //! @brief Copy assigns Values stored in the other varray to this one. | |
352 | //! | |
353 | //! @param other The varray which content will be copied to this one. | |
354 | //! | |
355 | //! @par Throws | |
356 | //! If Value's copy constructor or copy assignment throws. | |
357 | //! @internal | |
358 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
359 | //! @endinternal | |
360 | //! | |
361 | //! @par Complexity | |
362 | //! Linear O(N). | |
363 | template <std::size_t C> | |
364 | varray & operator=(BOOST_COPY_ASSIGN_REF_2_TEMPL_ARGS(varray, value_type, C) other) | |
365 | { | |
366 | this->assign(other.begin(), other.end()); // may throw | |
367 | ||
368 | return *this; | |
369 | } | |
370 | ||
371 | //! @brief Move constructor. Moves Values stored in the other varray to this one. | |
372 | //! | |
373 | //! @param other The varray which content will be moved to this one. | |
374 | //! | |
375 | //! @par Throws | |
376 | //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor throws. | |
377 | //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor throws. | |
378 | //! @internal | |
379 | //! @li It throws only if \c use_memop_in_swap_and_move is \c false_type - default. | |
380 | //! @endinternal | |
381 | //! | |
382 | //! @par Complexity | |
383 | //! Linear O(N). | |
384 | varray(BOOST_RV_REF(varray) other) | |
385 | { | |
386 | typedef typename | |
387 | vt::use_memop_in_swap_and_move use_memop_in_swap_and_move; | |
388 | ||
389 | this->move_ctor_dispatch(other, use_memop_in_swap_and_move()); | |
390 | } | |
391 | ||
392 | //! @pre <tt>other.size() <= capacity()</tt> | |
393 | //! | |
394 | //! @brief Move constructor. Moves Values stored in the other varray to this one. | |
395 | //! | |
396 | //! @param other The varray which content will be moved to this one. | |
397 | //! | |
398 | //! @par Throws | |
399 | //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor throws. | |
400 | //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor throws. | |
401 | //! @internal | |
402 | //! @li It throws only if \c use_memop_in_swap_and_move is false_type - default. | |
403 | //! @endinternal | |
404 | //! @internal | |
405 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
406 | //! @endinternal | |
407 | //! | |
408 | //! @par Complexity | |
409 | //! Linear O(N). | |
410 | template <std::size_t C> | |
411 | varray(BOOST_RV_REF_2_TEMPL_ARGS(varray, value_type, C) other) | |
412 | : m_size(other.m_size) | |
413 | { | |
414 | errh::check_capacity(*this, other.size()); // may throw | |
415 | ||
416 | typedef typename | |
417 | vt::use_memop_in_swap_and_move use_memop_in_swap_and_move; | |
418 | ||
419 | this->move_ctor_dispatch(other, use_memop_in_swap_and_move()); | |
420 | } | |
421 | ||
422 | //! @brief Move assignment. Moves Values stored in the other varray to this one. | |
423 | //! | |
424 | //! @param other The varray which content will be moved to this one. | |
425 | //! | |
426 | //! @par Throws | |
427 | //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor or move assignment throws. | |
428 | //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor or copy assignment throws. | |
429 | //! @internal | |
430 | //! @li It throws only if \c use_memop_in_swap_and_move is \c false_type - default. | |
431 | //! @endinternal | |
432 | //! | |
433 | //! @par Complexity | |
434 | //! Linear O(N). | |
435 | varray & operator=(BOOST_RV_REF(varray) other) | |
436 | { | |
437 | if ( &other == this ) | |
438 | return *this; | |
439 | ||
440 | typedef typename | |
441 | vt::use_memop_in_swap_and_move use_memop_in_swap_and_move; | |
442 | ||
443 | this->move_assign_dispatch(other, use_memop_in_swap_and_move()); | |
444 | ||
445 | return *this; | |
446 | } | |
447 | ||
448 | //! @pre <tt>other.size() <= capacity()</tt> | |
449 | //! | |
450 | //! @brief Move assignment. Moves Values stored in the other varray to this one. | |
451 | //! | |
452 | //! @param other The varray which content will be moved to this one. | |
453 | //! | |
454 | //! @par Throws | |
455 | //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor or move assignment throws. | |
456 | //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor or copy assignment throws. | |
457 | //! @internal | |
458 | //! @li It throws only if \c use_memop_in_swap_and_move is \c false_type - default. | |
459 | //! @endinternal | |
460 | //! @internal | |
461 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
462 | //! @endinternal | |
463 | //! | |
464 | //! @par Complexity | |
465 | //! Linear O(N). | |
466 | template <std::size_t C> | |
467 | varray & operator=(BOOST_RV_REF_2_TEMPL_ARGS(varray, value_type, C) other) | |
468 | { | |
469 | errh::check_capacity(*this, other.size()); // may throw | |
470 | ||
471 | typedef typename | |
472 | vt::use_memop_in_swap_and_move use_memop_in_swap_and_move; | |
473 | ||
474 | this->move_assign_dispatch(other, use_memop_in_swap_and_move()); | |
475 | ||
476 | return *this; | |
477 | } | |
478 | ||
479 | //! @brief Destructor. Destroys Values stored in this container. | |
480 | //! | |
481 | //! @par Throws | |
482 | //! Nothing | |
483 | //! | |
484 | //! @par Complexity | |
485 | //! Linear O(N). | |
486 | ~varray() | |
487 | { | |
488 | namespace sv = varray_detail; | |
489 | sv::destroy(this->begin(), this->end()); | |
490 | } | |
491 | ||
492 | //! @brief Swaps contents of the other varray and this one. | |
493 | //! | |
494 | //! @param other The varray which content will be swapped with this one's content. | |
495 | //! | |
496 | //! @par Throws | |
497 | //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor or move assignment throws, | |
498 | //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor or copy assignment throws, | |
499 | //! @internal | |
500 | //! @li It throws only if \c use_memop_in_swap_and_move and \c use_optimized_swap are \c false_type - default. | |
501 | //! @endinternal | |
502 | //! | |
503 | //! @par Complexity | |
504 | //! Linear O(N). | |
505 | void swap(varray & other) | |
506 | { | |
507 | typedef typename | |
508 | vt::use_optimized_swap use_optimized_swap; | |
509 | ||
510 | this->swap_dispatch(other, use_optimized_swap()); | |
511 | } | |
512 | ||
513 | //! @pre <tt>other.size() <= capacity() && size() <= other.capacity()</tt> | |
514 | //! | |
515 | //! @brief Swaps contents of the other varray and this one. | |
516 | //! | |
517 | //! @param other The varray which content will be swapped with this one's content. | |
518 | //! | |
519 | //! @par Throws | |
520 | //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor or move assignment throws, | |
521 | //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor or copy assignment throws, | |
522 | //! @internal | |
523 | //! @li It throws only if \c use_memop_in_swap_and_move and \c use_optimized_swap are \c false_type - default. | |
524 | //! @endinternal | |
525 | //! @internal | |
526 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
527 | //! @endinternal | |
528 | //! | |
529 | //! @par Complexity | |
530 | //! Linear O(N). | |
531 | template <std::size_t C> | |
532 | void swap(varray<value_type, C> & other) | |
533 | { | |
534 | errh::check_capacity(*this, other.size()); | |
535 | errh::check_capacity(other, this->size()); | |
536 | ||
537 | typedef typename | |
538 | vt::use_optimized_swap use_optimized_swap; | |
539 | ||
540 | this->swap_dispatch(other, use_optimized_swap()); | |
541 | } | |
542 | ||
543 | //! @pre <tt>count <= capacity()</tt> | |
544 | //! | |
545 | //! @brief Inserts or erases elements at the end such that | |
546 | //! the size becomes count. New elements are default constructed. | |
547 | //! | |
548 | //! @param count The number of elements which will be stored in the container. | |
549 | //! | |
550 | //! @par Throws | |
551 | //! If Value's default constructor throws. | |
552 | //! @internal | |
553 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
554 | //! @endinternal | |
555 | //! | |
556 | //! @par Complexity | |
557 | //! Linear O(N). | |
558 | void resize(size_type count) | |
559 | { | |
560 | namespace sv = varray_detail; | |
561 | typedef typename vt::disable_trivial_init dti; | |
562 | ||
563 | if ( count < m_size ) | |
564 | { | |
565 | sv::destroy(this->begin() + count, this->end()); | |
566 | } | |
567 | else | |
568 | { | |
569 | errh::check_capacity(*this, count); // may throw | |
570 | ||
571 | sv::uninitialized_fill(this->end(), this->begin() + count, dti()); // may throw | |
572 | } | |
573 | m_size = count; // update end | |
574 | } | |
575 | ||
576 | //! @pre <tt>count <= capacity()</tt> | |
577 | //! | |
578 | //! @brief Inserts or erases elements at the end such that | |
579 | //! the size becomes count. New elements are copy constructed from value. | |
580 | //! | |
581 | //! @param count The number of elements which will be stored in the container. | |
582 | //! @param value The value used to copy construct the new element. | |
583 | //! | |
584 | //! @par Throws | |
585 | //! If Value's copy constructor throws. | |
586 | //! @internal | |
587 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
588 | //! @endinternal | |
589 | //! | |
590 | //! @par Complexity | |
591 | //! Linear O(N). | |
592 | void resize(size_type count, value_type const& value) | |
593 | { | |
594 | if ( count < m_size ) | |
595 | { | |
596 | namespace sv = varray_detail; | |
597 | sv::destroy(this->begin() + count, this->end()); | |
598 | } | |
599 | else | |
600 | { | |
601 | errh::check_capacity(*this, count); // may throw | |
602 | ||
603 | std::uninitialized_fill(this->end(), this->begin() + count, value); // may throw | |
604 | } | |
605 | m_size = count; // update end | |
606 | } | |
607 | ||
608 | //! @pre <tt>count <= capacity()</tt> | |
609 | //! | |
610 | //! @brief This call has no effect because the Capacity of this container is constant. | |
611 | //! | |
612 | //! @param count The number of elements which the container should be able to contain. | |
613 | //! | |
614 | //! @par Throws | |
615 | //! Nothing. | |
616 | //! @internal | |
617 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
618 | //! @endinternal | |
619 | //! | |
620 | //! @par Complexity | |
621 | //! Linear O(N). | |
622 | void reserve(size_type count) | |
623 | { | |
624 | errh::check_capacity(*this, count); // may throw | |
625 | } | |
626 | ||
627 | //! @pre <tt>size() < capacity()</tt> | |
628 | //! | |
629 | //! @brief Adds a copy of value at the end. | |
630 | //! | |
631 | //! @param value The value used to copy construct the new element. | |
632 | //! | |
633 | //! @par Throws | |
634 | //! If Value's copy constructor throws. | |
635 | //! @internal | |
636 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
637 | //! @endinternal | |
638 | //! | |
639 | //! @par Complexity | |
640 | //! Constant O(1). | |
641 | void push_back(value_type const& value) | |
642 | { | |
643 | typedef typename vt::disable_trivial_init dti; | |
644 | ||
645 | errh::check_capacity(*this, m_size + 1); // may throw | |
646 | ||
647 | namespace sv = varray_detail; | |
648 | sv::construct(dti(), this->end(), value); // may throw | |
649 | ++m_size; // update end | |
650 | } | |
651 | ||
652 | //! @pre <tt>size() < capacity()</tt> | |
653 | //! | |
654 | //! @brief Moves value to the end. | |
655 | //! | |
656 | //! @param value The value to move construct the new element. | |
657 | //! | |
658 | //! @par Throws | |
659 | //! If Value's move constructor throws. | |
660 | //! @internal | |
661 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
662 | //! @endinternal | |
663 | //! | |
664 | //! @par Complexity | |
665 | //! Constant O(1). | |
666 | void push_back(BOOST_RV_REF(value_type) value) | |
667 | { | |
668 | typedef typename vt::disable_trivial_init dti; | |
669 | ||
670 | errh::check_capacity(*this, m_size + 1); // may throw | |
671 | ||
672 | namespace sv = varray_detail; | |
673 | sv::construct(dti(), this->end(), ::boost::move(value)); // may throw | |
674 | ++m_size; // update end | |
675 | } | |
676 | ||
677 | //! @pre <tt>!empty()</tt> | |
678 | //! | |
679 | //! @brief Destroys last value and decreases the size. | |
680 | //! | |
681 | //! @par Throws | |
682 | //! Nothing by default. | |
683 | //! | |
684 | //! @par Complexity | |
685 | //! Constant O(1). | |
686 | void pop_back() | |
687 | { | |
688 | errh::check_not_empty(*this); | |
689 | ||
690 | namespace sv = varray_detail; | |
691 | sv::destroy(this->end() - 1); | |
692 | --m_size; // update end | |
693 | } | |
694 | ||
695 | //! @pre | |
696 | //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>. | |
697 | //! @li <tt>size() < capacity()</tt> | |
698 | //! | |
699 | //! @brief Inserts a copy of element at position. | |
700 | //! | |
701 | //! @param position The position at which the new value will be inserted. | |
702 | //! @param value The value used to copy construct the new element. | |
703 | //! | |
704 | //! @par Throws | |
705 | //! @li If Value's copy constructor or copy assignment throws | |
706 | //! @li If Value's move constructor or move assignment throws. | |
707 | //! @internal | |
708 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
709 | //! @endinternal | |
710 | //! | |
711 | //! @par Complexity | |
712 | //! Constant or linear. | |
713 | iterator insert(iterator position, value_type const& value) | |
714 | { | |
715 | typedef typename vt::disable_trivial_init dti; | |
716 | namespace sv = varray_detail; | |
717 | ||
718 | errh::check_iterator_end_eq(*this, position); | |
719 | errh::check_capacity(*this, m_size + 1); // may throw | |
720 | ||
721 | if ( position == this->end() ) | |
722 | { | |
723 | sv::construct(dti(), position, value); // may throw | |
724 | ++m_size; // update end | |
725 | } | |
726 | else | |
727 | { | |
728 | // TODO - should move be used only if it's nonthrowing? | |
729 | value_type & r = *(this->end() - 1); | |
730 | sv::construct(dti(), this->end(), boost::move(r)); // may throw | |
731 | ++m_size; // update end | |
732 | sv::move_backward(position, this->end() - 2, this->end() - 1); // may throw | |
733 | sv::assign(position, value); // may throw | |
734 | } | |
735 | ||
736 | return position; | |
737 | } | |
738 | ||
739 | //! @pre | |
740 | //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>. | |
741 | //! @li <tt>size() < capacity()</tt> | |
742 | //! | |
743 | //! @brief Inserts a move-constructed element at position. | |
744 | //! | |
745 | //! @param position The position at which the new value will be inserted. | |
746 | //! @param value The value used to move construct the new element. | |
747 | //! | |
748 | //! @par Throws | |
749 | //! If Value's move constructor or move assignment throws. | |
750 | //! @internal | |
751 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
752 | //! @endinternal | |
753 | //! | |
754 | //! @par Complexity | |
755 | //! Constant or linear. | |
756 | iterator insert(iterator position, BOOST_RV_REF(value_type) value) | |
757 | { | |
758 | typedef typename vt::disable_trivial_init dti; | |
759 | namespace sv = varray_detail; | |
760 | ||
761 | errh::check_iterator_end_eq(*this, position); | |
762 | errh::check_capacity(*this, m_size + 1); // may throw | |
763 | ||
764 | if ( position == this->end() ) | |
765 | { | |
766 | sv::construct(dti(), position, boost::move(value)); // may throw | |
767 | ++m_size; // update end | |
768 | } | |
769 | else | |
770 | { | |
771 | // TODO - should move be used only if it's nonthrowing? | |
772 | value_type & r = *(this->end() - 1); | |
773 | sv::construct(dti(), this->end(), boost::move(r)); // may throw | |
774 | ++m_size; // update end | |
775 | sv::move_backward(position, this->end() - 2, this->end() - 1); // may throw | |
776 | sv::assign(position, boost::move(value)); // may throw | |
777 | } | |
778 | ||
779 | return position; | |
780 | } | |
781 | ||
782 | //! @pre | |
783 | //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>. | |
784 | //! @li <tt>size() + count <= capacity()</tt> | |
785 | //! | |
786 | //! @brief Inserts a count copies of value at position. | |
787 | //! | |
788 | //! @param position The position at which new elements will be inserted. | |
789 | //! @param count The number of new elements which will be inserted. | |
790 | //! @param value The value used to copy construct new elements. | |
791 | //! | |
792 | //! @par Throws | |
793 | //! @li If Value's copy constructor or copy assignment throws. | |
794 | //! @li If Value's move constructor or move assignment throws. | |
795 | //! @internal | |
796 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
797 | //! @endinternal | |
798 | //! | |
799 | //! @par Complexity | |
800 | //! Linear O(N). | |
801 | iterator insert(iterator position, size_type count, value_type const& value) | |
802 | { | |
803 | errh::check_iterator_end_eq(*this, position); | |
804 | errh::check_capacity(*this, m_size + count); // may throw | |
805 | ||
806 | if ( position == this->end() ) | |
807 | { | |
808 | std::uninitialized_fill(position, position + count, value); // may throw | |
809 | m_size += count; // update end | |
810 | } | |
811 | else | |
812 | { | |
813 | namespace sv = varray_detail; | |
814 | ||
815 | difference_type to_move = std::distance(position, this->end()); | |
816 | ||
817 | // TODO - should following lines check for exception and revert to the old size? | |
818 | ||
819 | if ( count < static_cast<size_type>(to_move) ) | |
820 | { | |
821 | sv::uninitialized_move(this->end() - count, this->end(), this->end()); // may throw | |
822 | m_size += count; // update end | |
823 | sv::move_backward(position, position + to_move - count, this->end() - count); // may throw | |
824 | std::fill_n(position, count, value); // may throw | |
825 | } | |
826 | else | |
827 | { | |
828 | std::uninitialized_fill(this->end(), position + count, value); // may throw | |
829 | m_size += count - to_move; // update end | |
830 | sv::uninitialized_move(position, position + to_move, position + count); // may throw | |
831 | m_size += to_move; // update end | |
832 | std::fill_n(position, to_move, value); // may throw | |
833 | } | |
834 | } | |
835 | ||
836 | return position; | |
837 | } | |
838 | ||
839 | //! @pre | |
840 | //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>. | |
841 | //! @li <tt>distance(first, last) <= capacity()</tt> | |
842 | //! @li \c Iterator must meet the \c ForwardTraversalIterator concept. | |
843 | //! | |
844 | //! @brief Inserts a copy of a range <tt>[first, last)</tt> at position. | |
845 | //! | |
846 | //! @param position The position at which new elements will be inserted. | |
847 | //! @param first The iterator to the first element of a range used to construct new elements. | |
848 | //! @param last The iterator to the one after the last element of a range used to construct new elements. | |
849 | //! | |
850 | //! @par Throws | |
851 | //! @li If Value's constructor and assignment taking a dereferenced \c Iterator. | |
852 | //! @li If Value's move constructor or move assignment throws. | |
853 | //! @internal | |
854 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
855 | //! @endinternal | |
856 | //! | |
857 | //! @par Complexity | |
858 | //! Linear O(N). | |
859 | template <typename Iterator> | |
860 | iterator insert(iterator position, Iterator first, Iterator last) | |
861 | { | |
862 | BOOST_CONCEPT_ASSERT((boost_concepts::ForwardTraversal<Iterator>)); // Make sure you passed a ForwardIterator | |
863 | ||
864 | typedef typename boost::iterator_traversal<Iterator>::type traversal; | |
865 | this->insert_dispatch(position, first, last, traversal()); | |
866 | ||
867 | return position; | |
868 | } | |
869 | ||
870 | //! @pre \c position must be a valid iterator of \c *this in range <tt>[begin(), end())</tt> | |
871 | //! | |
872 | //! @brief Erases Value from position. | |
873 | //! | |
874 | //! @param position The position of the element which will be erased from the container. | |
875 | //! | |
876 | //! @par Throws | |
877 | //! If Value's move assignment throws. | |
878 | //! | |
879 | //! @par Complexity | |
880 | //! Linear O(N). | |
881 | iterator erase(iterator position) | |
882 | { | |
883 | namespace sv = varray_detail; | |
884 | ||
885 | errh::check_iterator_end_neq(*this, position); | |
886 | ||
887 | //TODO - add empty check? | |
888 | //errh::check_empty(*this); | |
889 | ||
890 | sv::move(position + 1, this->end(), position); // may throw | |
891 | sv::destroy(this->end() - 1); | |
892 | --m_size; | |
893 | ||
894 | return position; | |
895 | } | |
896 | ||
897 | //! @pre | |
898 | //! @li \c first and \c last must define a valid range | |
899 | //! @li iterators must be in range <tt>[begin(), end()]</tt> | |
900 | //! | |
901 | //! @brief Erases Values from a range <tt>[first, last)</tt>. | |
902 | //! | |
903 | //! @param first The position of the first element of a range which will be erased from the container. | |
904 | //! @param last The position of the one after the last element of a range which will be erased from the container. | |
905 | //! | |
906 | //! @par Throws | |
907 | //! If Value's move assignment throws. | |
908 | //! | |
909 | //! @par Complexity | |
910 | //! Linear O(N). | |
911 | iterator erase(iterator first, iterator last) | |
912 | { | |
913 | namespace sv = varray_detail; | |
914 | ||
915 | errh::check_iterator_end_eq(*this, first); | |
916 | errh::check_iterator_end_eq(*this, last); | |
917 | ||
918 | difference_type n = std::distance(first, last); | |
919 | ||
920 | //TODO - add invalid range check? | |
921 | //BOOST_GEOMETRY_INDEX_ASSERT(0 <= n, "invalid range"); | |
922 | //TODO - add this->size() check? | |
923 | //BOOST_GEOMETRY_INDEX_ASSERT(n <= this->size(), "invalid range"); | |
924 | ||
925 | sv::move(last, this->end(), first); // may throw | |
926 | sv::destroy(this->end() - n, this->end()); | |
927 | m_size -= n; | |
928 | ||
929 | return first; | |
930 | } | |
931 | ||
932 | //! @pre <tt>distance(first, last) <= capacity()</tt> | |
933 | //! | |
934 | //! @brief Assigns a range <tt>[first, last)</tt> of Values to this container. | |
935 | //! | |
936 | //! @param first The iterator to the first element of a range used to construct new content of this container. | |
937 | //! @param last The iterator to the one after the last element of a range used to construct new content of this container. | |
938 | //! | |
939 | //! @par Throws | |
940 | //! If Value's copy constructor or copy assignment throws, | |
941 | //! | |
942 | //! @par Complexity | |
943 | //! Linear O(N). | |
944 | template <typename Iterator> | |
945 | void assign(Iterator first, Iterator last) | |
946 | { | |
947 | BOOST_CONCEPT_ASSERT((boost_concepts::ForwardTraversal<Iterator>)); // Make sure you passed a ForwardIterator | |
948 | ||
949 | typedef typename boost::iterator_traversal<Iterator>::type traversal; | |
950 | this->assign_dispatch(first, last, traversal()); // may throw | |
951 | } | |
952 | ||
953 | //! @pre <tt>count <= capacity()</tt> | |
954 | //! | |
955 | //! @brief Assigns a count copies of value to this container. | |
956 | //! | |
957 | //! @param count The new number of elements which will be container in the container. | |
958 | //! @param value The value which will be used to copy construct the new content. | |
959 | //! | |
960 | //! @par Throws | |
961 | //! If Value's copy constructor or copy assignment throws. | |
962 | //! | |
963 | //! @par Complexity | |
964 | //! Linear O(N). | |
965 | void assign(size_type count, value_type const& value) | |
966 | { | |
967 | if ( count < m_size ) | |
968 | { | |
969 | namespace sv = varray_detail; | |
970 | ||
971 | std::fill_n(this->begin(), count, value); // may throw | |
972 | sv::destroy(this->begin() + count, this->end()); | |
973 | } | |
974 | else | |
975 | { | |
976 | errh::check_capacity(*this, count); // may throw | |
977 | ||
978 | std::fill_n(this->begin(), m_size, value); // may throw | |
979 | std::uninitialized_fill(this->end(), this->begin() + count, value); // may throw | |
980 | } | |
981 | m_size = count; // update end | |
982 | } | |
983 | ||
984 | #if !defined(BOOST_CONTAINER_VARRAY_DISABLE_EMPLACE) | |
985 | #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
986 | //! @pre <tt>size() < capacity()</tt> | |
987 | //! | |
988 | //! @brief Inserts a Value constructed with | |
989 | //! \c std::forward<Args>(args)... in the end of the container. | |
990 | //! | |
991 | //! @param args The arguments of the constructor of the new element which will be created at the end of the container. | |
992 | //! | |
993 | //! @par Throws | |
994 | //! If in-place constructor throws or Value's move constructor throws. | |
995 | //! @internal | |
996 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
997 | //! @endinternal | |
998 | //! | |
999 | //! @par Complexity | |
1000 | //! Constant O(1). | |
1001 | template<class ...Args> | |
1002 | void emplace_back(BOOST_FWD_REF(Args) ...args) | |
1003 | { | |
1004 | typedef typename vt::disable_trivial_init dti; | |
1005 | ||
1006 | errh::check_capacity(*this, m_size + 1); // may throw | |
1007 | ||
1008 | namespace sv = varray_detail; | |
1009 | sv::construct(dti(), this->end(), ::boost::forward<Args>(args)...); // may throw | |
1010 | ++m_size; // update end | |
1011 | } | |
1012 | ||
1013 | //! @pre | |
1014 | //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt> | |
1015 | //! @li <tt>size() < capacity()</tt> | |
1016 | //! | |
1017 | //! @brief Inserts a Value constructed with | |
1018 | //! \c std::forward<Args>(args)... before position | |
1019 | //! | |
1020 | //! @param position The position at which new elements will be inserted. | |
1021 | //! @param args The arguments of the constructor of the new element. | |
1022 | //! | |
1023 | //! @par Throws | |
1024 | //! If in-place constructor throws or if Value's move constructor or move assignment throws. | |
1025 | //! @internal | |
1026 | //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default). | |
1027 | //! @endinternal | |
1028 | //! | |
1029 | //! @par Complexity | |
1030 | //! Constant or linear. | |
1031 | template<class ...Args> | |
1032 | iterator emplace(iterator position, BOOST_FWD_REF(Args) ...args) | |
1033 | { | |
1034 | typedef typename vt::disable_trivial_init dti; | |
1035 | ||
1036 | namespace sv = varray_detail; | |
1037 | ||
1038 | errh::check_iterator_end_eq(*this, position); | |
1039 | errh::check_capacity(*this, m_size + 1); // may throw | |
1040 | ||
1041 | if ( position == this->end() ) | |
1042 | { | |
1043 | sv::construct(dti(), position, ::boost::forward<Args>(args)...); // may throw | |
1044 | ++m_size; // update end | |
1045 | } | |
1046 | else | |
1047 | { | |
1048 | // TODO - should following lines check for exception and revert to the old size? | |
1049 | ||
1050 | // TODO - should move be used only if it's nonthrowing? | |
1051 | value_type & r = *(this->end() - 1); | |
1052 | sv::construct(dti(), this->end(), boost::move(r)); // may throw | |
1053 | ++m_size; // update end | |
1054 | sv::move_backward(position, this->end() - 2, this->end() - 1); // may throw | |
1055 | ||
1056 | aligned_storage<sizeof(value_type), alignment_of<value_type>::value> temp_storage; | |
1057 | value_type * val_p = static_cast<value_type *>(temp_storage.address()); | |
1058 | sv::construct(dti(), val_p, ::boost::forward<Args>(args)...); // may throw | |
1059 | sv::scoped_destructor<value_type> d(val_p); | |
1060 | sv::assign(position, ::boost::move(*val_p)); // may throw | |
1061 | } | |
1062 | ||
1063 | return position; | |
1064 | } | |
1065 | ||
1066 | #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1067 | ||
1068 | #define BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_EMPLACE(N) \ | |
1069 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1070 | void emplace_back(BOOST_MOVE_UREF##N) \ | |
1071 | { \ | |
1072 | typedef typename vt::disable_trivial_init dti; \ | |
1073 | \ | |
1074 | errh::check_capacity(*this, m_size + 1); /*may throw*/\ | |
1075 | \ | |
1076 | namespace sv = varray_detail; \ | |
1077 | sv::construct(dti(), this->end() BOOST_MOVE_I##N BOOST_MOVE_FWD##N ); /*may throw*/\ | |
1078 | ++m_size; /*update end*/ \ | |
1079 | } \ | |
1080 | \ | |
1081 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1082 | iterator emplace(iterator position BOOST_MOVE_I##N BOOST_MOVE_UREF##N) \ | |
1083 | { \ | |
1084 | typedef typename vt::disable_trivial_init dti; \ | |
1085 | namespace sv = varray_detail; \ | |
1086 | \ | |
1087 | errh::check_iterator_end_eq(*this, position); \ | |
1088 | errh::check_capacity(*this, m_size + 1); /*may throw*/\ | |
1089 | \ | |
1090 | if ( position == this->end() ) \ | |
1091 | { \ | |
1092 | sv::construct(dti(), position BOOST_MOVE_I##N BOOST_MOVE_FWD##N ); /*may throw*/\ | |
1093 | ++m_size; /*update end*/ \ | |
1094 | } \ | |
1095 | else \ | |
1096 | { \ | |
1097 | /* TODO - should following lines check for exception and revert to the old size? */ \ | |
1098 | /* TODO - should move be used only if it's nonthrowing? */ \ | |
1099 | \ | |
1100 | value_type & r = *(this->end() - 1); \ | |
1101 | sv::construct(dti(), this->end(), boost::move(r)); /*may throw*/\ | |
1102 | ++m_size; /*update end*/ \ | |
1103 | sv::move_backward(position, this->end() - 2, this->end() - 1); /*may throw*/\ | |
1104 | \ | |
1105 | aligned_storage<sizeof(value_type), alignment_of<value_type>::value> temp_storage; \ | |
1106 | value_type * val_p = static_cast<value_type *>(temp_storage.address()); \ | |
1107 | sv::construct(dti(), val_p BOOST_MOVE_I##N BOOST_MOVE_FWD##N ); /*may throw*/\ | |
1108 | sv::scoped_destructor<value_type> d(val_p); \ | |
1109 | sv::assign(position, ::boost::move(*val_p)); /*may throw*/\ | |
1110 | } \ | |
1111 | \ | |
1112 | return position; \ | |
1113 | } \ | |
1114 | ||
1115 | BOOST_MOVE_ITERATE_0TO9(BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_EMPLACE) | |
1116 | #undef BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_EMPLACE | |
1117 | ||
1118 | #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1119 | #endif // !BOOST_CONTAINER_VARRAY_DISABLE_EMPLACE | |
1120 | ||
1121 | //! @brief Removes all elements from the container. | |
1122 | //! | |
1123 | //! @par Throws | |
1124 | //! Nothing. | |
1125 | //! | |
1126 | //! @par Complexity | |
1127 | //! Constant O(1). | |
1128 | void clear() | |
1129 | { | |
1130 | namespace sv = varray_detail; | |
1131 | sv::destroy(this->begin(), this->end()); | |
1132 | m_size = 0; // update end | |
1133 | } | |
1134 | ||
1135 | //! @pre <tt>i < size()</tt> | |
1136 | //! | |
1137 | //! @brief Returns reference to the i-th element. | |
1138 | //! | |
1139 | //! @param i The element's index. | |
1140 | //! | |
1141 | //! @return reference to the i-th element | |
1142 | //! from the beginning of the container. | |
1143 | //! | |
1144 | //! @par Throws | |
1145 | //! \c std::out_of_range exception by default. | |
1146 | //! | |
1147 | //! @par Complexity | |
1148 | //! Constant O(1). | |
1149 | reference at(size_type i) | |
1150 | { | |
1151 | errh::throw_out_of_bounds(*this, i); // may throw | |
1152 | return *(this->begin() + i); | |
1153 | } | |
1154 | ||
1155 | //! @pre <tt>i < size()</tt> | |
1156 | //! | |
1157 | //! @brief Returns const reference to the i-th element. | |
1158 | //! | |
1159 | //! @param i The element's index. | |
1160 | //! | |
1161 | //! @return const reference to the i-th element | |
1162 | //! from the beginning of the container. | |
1163 | //! | |
1164 | //! @par Throws | |
1165 | //! \c std::out_of_range exception by default. | |
1166 | //! | |
1167 | //! @par Complexity | |
1168 | //! Constant O(1). | |
1169 | const_reference at(size_type i) const | |
1170 | { | |
1171 | errh::throw_out_of_bounds(*this, i); // may throw | |
1172 | return *(this->begin() + i); | |
1173 | } | |
1174 | ||
1175 | //! @pre <tt>i < size()</tt> | |
1176 | //! | |
1177 | //! @brief Returns reference to the i-th element. | |
1178 | //! | |
1179 | //! @param i The element's index. | |
1180 | //! | |
1181 | //! @return reference to the i-th element | |
1182 | //! from the beginning of the container. | |
1183 | //! | |
1184 | //! @par Throws | |
1185 | //! Nothing by default. | |
1186 | //! | |
1187 | //! @par Complexity | |
1188 | //! Constant O(1). | |
1189 | reference operator[](size_type i) | |
1190 | { | |
1191 | // TODO: Remove bounds check? std::vector and std::array operator[] don't check. | |
1192 | errh::check_index(*this, i); | |
1193 | return *(this->begin() + i); | |
1194 | } | |
1195 | ||
1196 | //! @pre <tt>i < size()</tt> | |
1197 | //! | |
1198 | //! @brief Returns const reference to the i-th element. | |
1199 | //! | |
1200 | //! @param i The element's index. | |
1201 | //! | |
1202 | //! @return const reference to the i-th element | |
1203 | //! from the beginning of the container. | |
1204 | //! | |
1205 | //! @par Throws | |
1206 | //! Nothing by default. | |
1207 | //! | |
1208 | //! @par Complexity | |
1209 | //! Constant O(1). | |
1210 | const_reference operator[](size_type i) const | |
1211 | { | |
1212 | errh::check_index(*this, i); | |
1213 | return *(this->begin() + i); | |
1214 | } | |
1215 | ||
1216 | //! @pre \c !empty() | |
1217 | //! | |
1218 | //! @brief Returns reference to the first element. | |
1219 | //! | |
1220 | //! @return reference to the first element | |
1221 | //! from the beginning of the container. | |
1222 | //! | |
1223 | //! @par Throws | |
1224 | //! Nothing by default. | |
1225 | //! | |
1226 | //! @par Complexity | |
1227 | //! Constant O(1). | |
1228 | reference front() | |
1229 | { | |
1230 | errh::check_not_empty(*this); | |
1231 | return *(this->begin()); | |
1232 | } | |
1233 | ||
1234 | //! @pre \c !empty() | |
1235 | //! | |
1236 | //! @brief Returns const reference to the first element. | |
1237 | //! | |
1238 | //! @return const reference to the first element | |
1239 | //! from the beginning of the container. | |
1240 | //! | |
1241 | //! @par Throws | |
1242 | //! Nothing by default. | |
1243 | //! | |
1244 | //! @par Complexity | |
1245 | //! Constant O(1). | |
1246 | const_reference front() const | |
1247 | { | |
1248 | errh::check_not_empty(*this); | |
1249 | return *(this->begin()); | |
1250 | } | |
1251 | ||
1252 | //! @pre \c !empty() | |
1253 | //! | |
1254 | //! @brief Returns reference to the last element. | |
1255 | //! | |
1256 | //! @return reference to the last element | |
1257 | //! from the beginning of the container. | |
1258 | //! | |
1259 | //! @par Throws | |
1260 | //! Nothing by default. | |
1261 | //! | |
1262 | //! @par Complexity | |
1263 | //! Constant O(1). | |
1264 | reference back() | |
1265 | { | |
1266 | errh::check_not_empty(*this); | |
1267 | return *(this->end() - 1); | |
1268 | } | |
1269 | ||
1270 | //! @pre \c !empty() | |
1271 | //! | |
1272 | //! @brief Returns const reference to the first element. | |
1273 | //! | |
1274 | //! @return const reference to the last element | |
1275 | //! from the beginning of the container. | |
1276 | //! | |
1277 | //! @par Throws | |
1278 | //! Nothing by default. | |
1279 | //! | |
1280 | //! @par Complexity | |
1281 | //! Constant O(1). | |
1282 | const_reference back() const | |
1283 | { | |
1284 | errh::check_not_empty(*this); | |
1285 | return *(this->end() - 1); | |
1286 | } | |
1287 | ||
1288 | //! @brief Pointer such that <tt>[data(), data() + size())</tt> is a valid range. | |
1289 | //! For a non-empty vector <tt>data() == &front()</tt>. | |
1290 | //! | |
1291 | //! @par Throws | |
1292 | //! Nothing. | |
1293 | //! | |
1294 | //! @par Complexity | |
1295 | //! Constant O(1). | |
1296 | Value * data() | |
1297 | { | |
1298 | return boost::addressof(*(this->ptr())); | |
1299 | } | |
1300 | ||
1301 | //! @brief Const pointer such that <tt>[data(), data() + size())</tt> is a valid range. | |
1302 | //! For a non-empty vector <tt>data() == &front()</tt>. | |
1303 | //! | |
1304 | //! @par Throws | |
1305 | //! Nothing. | |
1306 | //! | |
1307 | //! @par Complexity | |
1308 | //! Constant O(1). | |
1309 | const Value * data() const | |
1310 | { | |
1311 | return boost::addressof(*(this->ptr())); | |
1312 | } | |
1313 | ||
1314 | ||
1315 | //! @brief Returns iterator to the first element. | |
1316 | //! | |
1317 | //! @return iterator to the first element contained in the vector. | |
1318 | //! | |
1319 | //! @par Throws | |
1320 | //! Nothing. | |
1321 | //! | |
1322 | //! @par Complexity | |
1323 | //! Constant O(1). | |
1324 | iterator begin() { return this->ptr(); } | |
1325 | ||
1326 | //! @brief Returns const iterator to the first element. | |
1327 | //! | |
1328 | //! @return const_iterator to the first element contained in the vector. | |
1329 | //! | |
1330 | //! @par Throws | |
1331 | //! Nothing. | |
1332 | //! | |
1333 | //! @par Complexity | |
1334 | //! Constant O(1). | |
1335 | const_iterator begin() const { return this->ptr(); } | |
1336 | ||
1337 | //! @brief Returns const iterator to the first element. | |
1338 | //! | |
1339 | //! @return const_iterator to the first element contained in the vector. | |
1340 | //! | |
1341 | //! @par Throws | |
1342 | //! Nothing. | |
1343 | //! | |
1344 | //! @par Complexity | |
1345 | //! Constant O(1). | |
1346 | const_iterator cbegin() const { return this->ptr(); } | |
1347 | ||
1348 | //! @brief Returns iterator to the one after the last element. | |
1349 | //! | |
1350 | //! @return iterator pointing to the one after the last element contained in the vector. | |
1351 | //! | |
1352 | //! @par Throws | |
1353 | //! Nothing. | |
1354 | //! | |
1355 | //! @par Complexity | |
1356 | //! Constant O(1). | |
1357 | iterator end() { return this->begin() + m_size; } | |
1358 | ||
1359 | //! @brief Returns const iterator to the one after the last element. | |
1360 | //! | |
1361 | //! @return const_iterator pointing to the one after the last element contained in the vector. | |
1362 | //! | |
1363 | //! @par Throws | |
1364 | //! Nothing. | |
1365 | //! | |
1366 | //! @par Complexity | |
1367 | //! Constant O(1). | |
1368 | const_iterator end() const { return this->begin() + m_size; } | |
1369 | ||
1370 | //! @brief Returns const iterator to the one after the last element. | |
1371 | //! | |
1372 | //! @return const_iterator pointing to the one after the last element contained in the vector. | |
1373 | //! | |
1374 | //! @par Throws | |
1375 | //! Nothing. | |
1376 | //! | |
1377 | //! @par Complexity | |
1378 | //! Constant O(1). | |
1379 | const_iterator cend() const { return this->cbegin() + m_size; } | |
1380 | ||
1381 | //! @brief Returns reverse iterator to the first element of the reversed container. | |
1382 | //! | |
1383 | //! @return reverse_iterator pointing to the beginning | |
1384 | //! of the reversed varray. | |
1385 | //! | |
1386 | //! @par Throws | |
1387 | //! Nothing. | |
1388 | //! | |
1389 | //! @par Complexity | |
1390 | //! Constant O(1). | |
1391 | reverse_iterator rbegin() { return reverse_iterator(this->end()); } | |
1392 | ||
1393 | //! @brief Returns const reverse iterator to the first element of the reversed container. | |
1394 | //! | |
1395 | //! @return const_reverse_iterator pointing to the beginning | |
1396 | //! of the reversed varray. | |
1397 | //! | |
1398 | //! @par Throws | |
1399 | //! Nothing. | |
1400 | //! | |
1401 | //! @par Complexity | |
1402 | //! Constant O(1). | |
1403 | const_reverse_iterator rbegin() const { return const_reverse_iterator(this->end()); } | |
1404 | ||
1405 | //! @brief Returns const reverse iterator to the first element of the reversed container. | |
1406 | //! | |
1407 | //! @return const_reverse_iterator pointing to the beginning | |
1408 | //! of the reversed varray. | |
1409 | //! | |
1410 | //! @par Throws | |
1411 | //! Nothing. | |
1412 | //! | |
1413 | //! @par Complexity | |
1414 | //! Constant O(1). | |
1415 | const_reverse_iterator crbegin() const { return const_reverse_iterator(this->end()); } | |
1416 | ||
1417 | //! @brief Returns reverse iterator to the one after the last element of the reversed container. | |
1418 | //! | |
1419 | //! @return reverse_iterator pointing to the one after the last element | |
1420 | //! of the reversed varray. | |
1421 | //! | |
1422 | //! @par Throws | |
1423 | //! Nothing. | |
1424 | //! | |
1425 | //! @par Complexity | |
1426 | //! Constant O(1). | |
1427 | reverse_iterator rend() { return reverse_iterator(this->begin()); } | |
1428 | ||
1429 | //! @brief Returns const reverse iterator to the one after the last element of the reversed container. | |
1430 | //! | |
1431 | //! @return const_reverse_iterator pointing to the one after the last element | |
1432 | //! of the reversed varray. | |
1433 | //! | |
1434 | //! @par Throws | |
1435 | //! Nothing. | |
1436 | //! | |
1437 | //! @par Complexity | |
1438 | //! Constant O(1). | |
1439 | const_reverse_iterator rend() const { return const_reverse_iterator(this->begin()); } | |
1440 | ||
1441 | //! @brief Returns const reverse iterator to the one after the last element of the reversed container. | |
1442 | //! | |
1443 | //! @return const_reverse_iterator pointing to the one after the last element | |
1444 | //! of the reversed varray. | |
1445 | //! | |
1446 | //! @par Throws | |
1447 | //! Nothing. | |
1448 | //! | |
1449 | //! @par Complexity | |
1450 | //! Constant O(1). | |
1451 | const_reverse_iterator crend() const { return const_reverse_iterator(this->begin()); } | |
1452 | ||
1453 | //! @brief Returns container's capacity. | |
1454 | //! | |
1455 | //! @return container's capacity. | |
1456 | //! | |
1457 | //! @par Throws | |
1458 | //! Nothing. | |
1459 | //! | |
1460 | //! @par Complexity | |
1461 | //! Constant O(1). | |
1462 | static size_type capacity() { return Capacity; } | |
1463 | ||
1464 | //! @brief Returns container's capacity. | |
1465 | //! | |
1466 | //! @return container's capacity. | |
1467 | //! | |
1468 | //! @par Throws | |
1469 | //! Nothing. | |
1470 | //! | |
1471 | //! @par Complexity | |
1472 | //! Constant O(1). | |
1473 | static size_type max_size() { return Capacity; } | |
1474 | ||
1475 | //! @brief Returns the number of stored elements. | |
1476 | //! | |
1477 | //! @return Number of elements contained in the container. | |
1478 | //! | |
1479 | //! @par Throws | |
1480 | //! Nothing. | |
1481 | //! | |
1482 | //! @par Complexity | |
1483 | //! Constant O(1). | |
1484 | size_type size() const { return m_size; } | |
1485 | ||
1486 | //! @brief Queries if the container contains elements. | |
1487 | //! | |
1488 | //! @return true if the number of elements contained in the | |
1489 | //! container is equal to 0. | |
1490 | //! | |
1491 | //! @par Throws | |
1492 | //! Nothing. | |
1493 | //! | |
1494 | //! @par Complexity | |
1495 | //! Constant O(1). | |
1496 | bool empty() const { return 0 == m_size; } | |
1497 | ||
1498 | private: | |
1499 | ||
1500 | // @par Throws | |
1501 | // Nothing. | |
1502 | // @par Complexity | |
1503 | // Linear O(N). | |
1504 | template <std::size_t C> | |
1505 | void move_ctor_dispatch(varray<value_type, C> & other, boost::true_type /*use_memop*/) | |
1506 | { | |
1507 | ::memcpy(this->data(), other.data(), sizeof(Value) * other.m_size); | |
1508 | m_size = other.m_size; | |
1509 | } | |
1510 | ||
1511 | // @par Throws | |
1512 | // @li If boost::has_nothrow_move<Value>::value is true and Value's move constructor throws | |
1513 | // @li If boost::has_nothrow_move<Value>::value is false and Value's copy constructor throws. | |
1514 | // @par Complexity | |
1515 | // Linear O(N). | |
1516 | template <std::size_t C> | |
1517 | void move_ctor_dispatch(varray<value_type, C> & other, boost::false_type /*use_memop*/) | |
1518 | { | |
1519 | namespace sv = varray_detail; | |
1520 | sv::uninitialized_move_if_noexcept(other.begin(), other.end(), this->begin()); // may throw | |
1521 | m_size = other.m_size; | |
1522 | } | |
1523 | ||
1524 | // @par Throws | |
1525 | // Nothing. | |
1526 | // @par Complexity | |
1527 | // Linear O(N). | |
1528 | template <std::size_t C> | |
1529 | void move_assign_dispatch(varray<value_type, C> & other, boost::true_type /*use_memop*/) | |
1530 | { | |
1531 | this->clear(); | |
1532 | ||
1533 | ::memcpy(this->data(), other.data(), sizeof(Value) * other.m_size); | |
1534 | std::swap(m_size, other.m_size); | |
1535 | } | |
1536 | ||
1537 | // @par Throws | |
1538 | // @li If boost::has_nothrow_move<Value>::value is true and Value's move constructor or move assignment throws | |
1539 | // @li If boost::has_nothrow_move<Value>::value is false and Value's copy constructor or move assignment throws. | |
1540 | // @par Complexity | |
1541 | // Linear O(N). | |
1542 | template <std::size_t C> | |
1543 | void move_assign_dispatch(varray<value_type, C> & other, boost::false_type /*use_memop*/) | |
1544 | { | |
1545 | namespace sv = varray_detail; | |
1546 | if ( m_size <= static_cast<size_type>(other.size()) ) | |
1547 | { | |
1548 | sv::move_if_noexcept(other.begin(), other.begin() + m_size, this->begin()); // may throw | |
1549 | // TODO - perform uninitialized_copy first? | |
1550 | sv::uninitialized_move_if_noexcept(other.begin() + m_size, other.end(), this->end()); // may throw | |
1551 | } | |
1552 | else | |
1553 | { | |
1554 | sv::move_if_noexcept(other.begin(), other.end(), this->begin()); // may throw | |
1555 | sv::destroy(this->begin() + other.size(), this->end()); | |
1556 | } | |
1557 | m_size = other.size(); // update end | |
1558 | } | |
1559 | ||
1560 | // @par Throws | |
1561 | // Nothing. | |
1562 | // @par Complexity | |
1563 | // Linear O(N). | |
1564 | template <std::size_t C> | |
1565 | void swap_dispatch(varray<value_type, C> & other, boost::true_type const& /*use_optimized_swap*/) | |
1566 | { | |
1567 | typedef typename | |
1568 | boost::mpl::if_c< | |
1569 | Capacity < C, | |
1570 | aligned_storage_type, | |
1571 | typename varray<value_type, C>::aligned_storage_type | |
1572 | >::type | |
1573 | storage_type; | |
1574 | ||
1575 | storage_type temp; | |
1576 | Value * temp_ptr = reinterpret_cast<Value*>(temp.address()); | |
1577 | ||
1578 | ::memcpy(temp_ptr, this->data(), sizeof(Value) * this->size()); | |
1579 | ::memcpy(this->data(), other.data(), sizeof(Value) * other.size()); | |
1580 | ::memcpy(other.data(), temp_ptr, sizeof(Value) * this->size()); | |
1581 | ||
1582 | std::swap(m_size, other.m_size); | |
1583 | } | |
1584 | ||
1585 | // @par Throws | |
1586 | // If Value's move constructor or move assignment throws | |
1587 | // but only if use_memop_in_swap_and_move is false_type - default. | |
1588 | // @par Complexity | |
1589 | // Linear O(N). | |
1590 | template <std::size_t C> | |
1591 | void swap_dispatch(varray<value_type, C> & other, boost::false_type const& /*use_optimized_swap*/) | |
1592 | { | |
1593 | namespace sv = varray_detail; | |
1594 | ||
1595 | typedef typename | |
1596 | vt::use_memop_in_swap_and_move use_memop_in_swap_and_move; | |
1597 | ||
1598 | if ( this->size() < other.size() ) | |
1599 | swap_dispatch_impl(this->begin(), this->end(), other.begin(), other.end(), use_memop_in_swap_and_move()); // may throw | |
1600 | else | |
1601 | swap_dispatch_impl(other.begin(), other.end(), this->begin(), this->end(), use_memop_in_swap_and_move()); // may throw | |
1602 | std::swap(m_size, other.m_size); | |
1603 | } | |
1604 | ||
1605 | // @par Throws | |
1606 | // Nothing. | |
1607 | // @par Complexity | |
1608 | // Linear O(N). | |
1609 | void swap_dispatch_impl(iterator first_sm, iterator last_sm, iterator first_la, iterator last_la, boost::true_type const& /*use_memop*/) | |
1610 | { | |
1611 | //BOOST_GEOMETRY_INDEX_ASSERT(std::distance(first_sm, last_sm) <= std::distance(first_la, last_la), | |
1612 | // "incompatible ranges"); | |
1613 | ||
1614 | namespace sv = varray_detail; | |
1615 | for (; first_sm != last_sm ; ++first_sm, ++first_la) | |
1616 | { | |
1617 | boost::aligned_storage< | |
1618 | sizeof(value_type), | |
1619 | boost::alignment_of<value_type>::value | |
1620 | > temp_storage; | |
1621 | value_type * temp_ptr = reinterpret_cast<value_type*>(temp_storage.address()); | |
1622 | ||
1623 | ::memcpy(temp_ptr, boost::addressof(*first_sm), sizeof(value_type)); | |
1624 | ::memcpy(boost::addressof(*first_sm), boost::addressof(*first_la), sizeof(value_type)); | |
1625 | ::memcpy(boost::addressof(*first_la), temp_ptr, sizeof(value_type)); | |
1626 | } | |
1627 | ||
1628 | ::memcpy(first_sm, first_la, sizeof(value_type) * std::distance(first_la, last_la)); | |
1629 | } | |
1630 | ||
1631 | // @par Throws | |
1632 | // If Value's move constructor or move assignment throws. | |
1633 | // @par Complexity | |
1634 | // Linear O(N). | |
1635 | void swap_dispatch_impl(iterator first_sm, iterator last_sm, iterator first_la, iterator last_la, boost::false_type const& /*use_memop*/) | |
1636 | { | |
1637 | //BOOST_GEOMETRY_INDEX_ASSERT(std::distance(first_sm, last_sm) <= std::distance(first_la, last_la), | |
1638 | // "incompatible ranges"); | |
1639 | ||
1640 | namespace sv = varray_detail; | |
1641 | for (; first_sm != last_sm ; ++first_sm, ++first_la) | |
1642 | { | |
1643 | //boost::swap(*first_sm, *first_la); // may throw | |
1644 | value_type temp(boost::move(*first_sm)); // may throw | |
1645 | *first_sm = boost::move(*first_la); // may throw | |
1646 | *first_la = boost::move(temp); // may throw | |
1647 | } | |
1648 | sv::uninitialized_move(first_la, last_la, first_sm); // may throw | |
1649 | sv::destroy(first_la, last_la); | |
1650 | } | |
1651 | ||
1652 | // insert | |
1653 | ||
1654 | // @par Throws | |
1655 | // If Value's move constructor, move assignment throws | |
1656 | // or if Value's copy constructor or copy assignment throws. | |
1657 | // @par Complexity | |
1658 | // Linear O(N). | |
1659 | template <typename Iterator> | |
1660 | void insert_dispatch(iterator position, Iterator first, Iterator last, boost::random_access_traversal_tag const&) | |
1661 | { | |
1662 | BOOST_CONCEPT_ASSERT((boost_concepts::RandomAccessTraversal<Iterator>)); // Make sure you passed a RandomAccessIterator | |
1663 | ||
1664 | errh::check_iterator_end_eq(*this, position); | |
1665 | ||
1666 | typename boost::iterator_difference<Iterator>::type | |
1667 | count = std::distance(first, last); | |
1668 | ||
1669 | errh::check_capacity(*this, m_size + count); // may throw | |
1670 | ||
1671 | if ( position == this->end() ) | |
1672 | { | |
1673 | namespace sv = varray_detail; | |
1674 | ||
1675 | sv::uninitialized_copy(first, last, position); // may throw | |
1676 | m_size += count; // update end | |
1677 | } | |
1678 | else | |
1679 | { | |
1680 | this->insert_in_the_middle(position, first, last, count); // may throw | |
1681 | } | |
1682 | } | |
1683 | ||
1684 | // @par Throws | |
1685 | // If Value's move constructor, move assignment throws | |
1686 | // or if Value's copy constructor or copy assignment throws. | |
1687 | // @par Complexity | |
1688 | // Linear O(N). | |
1689 | template <typename Iterator, typename Traversal> | |
1690 | void insert_dispatch(iterator position, Iterator first, Iterator last, Traversal const& /*not_random_access*/) | |
1691 | { | |
1692 | errh::check_iterator_end_eq(*this, position); | |
1693 | ||
1694 | if ( position == this->end() ) | |
1695 | { | |
1696 | namespace sv = varray_detail; | |
1697 | ||
1698 | std::ptrdiff_t d = std::distance(position, this->begin() + Capacity); | |
1699 | std::size_t count = sv::uninitialized_copy_s(first, last, position, d); // may throw | |
1700 | ||
1701 | errh::check_capacity(*this, count <= static_cast<std::size_t>(d) ? m_size + count : Capacity + 1); // may throw | |
1702 | ||
1703 | m_size += count; | |
1704 | } | |
1705 | else | |
1706 | { | |
1707 | typename boost::iterator_difference<Iterator>::type | |
1708 | count = std::distance(first, last); | |
1709 | ||
1710 | errh::check_capacity(*this, m_size + count); // may throw | |
1711 | ||
1712 | this->insert_in_the_middle(position, first, last, count); // may throw | |
1713 | } | |
1714 | } | |
1715 | ||
1716 | // @par Throws | |
1717 | // If Value's move constructor, move assignment throws | |
1718 | // or if Value's copy constructor or copy assignment throws. | |
1719 | // @par Complexity | |
1720 | // Linear O(N). | |
1721 | template <typename Iterator> | |
1722 | void insert_in_the_middle(iterator position, Iterator first, Iterator last, difference_type count) | |
1723 | { | |
1724 | namespace sv = varray_detail; | |
1725 | ||
1726 | difference_type to_move = std::distance(position, this->end()); | |
1727 | ||
1728 | // TODO - should following lines check for exception and revert to the old size? | |
1729 | ||
1730 | if ( count < to_move ) | |
1731 | { | |
1732 | sv::uninitialized_move(this->end() - count, this->end(), this->end()); // may throw | |
1733 | m_size += count; // update end | |
1734 | sv::move_backward(position, position + to_move - count, this->end() - count); // may throw | |
1735 | sv::copy(first, last, position); // may throw | |
1736 | } | |
1737 | else | |
1738 | { | |
1739 | Iterator middle_iter = first; | |
1740 | std::advance(middle_iter, to_move); | |
1741 | ||
1742 | sv::uninitialized_copy(middle_iter, last, this->end()); // may throw | |
1743 | m_size += count - to_move; // update end | |
1744 | sv::uninitialized_move(position, position + to_move, position + count); // may throw | |
1745 | m_size += to_move; // update end | |
1746 | sv::copy(first, middle_iter, position); // may throw | |
1747 | } | |
1748 | } | |
1749 | ||
1750 | // assign | |
1751 | ||
1752 | // @par Throws | |
1753 | // If Value's constructor or assignment taking dereferenced Iterator throws. | |
1754 | // @par Complexity | |
1755 | // Linear O(N). | |
1756 | template <typename Iterator> | |
1757 | void assign_dispatch(Iterator first, Iterator last, boost::random_access_traversal_tag const& /*not_random_access*/) | |
1758 | { | |
1759 | namespace sv = varray_detail; | |
1760 | ||
1761 | typename boost::iterator_difference<Iterator>::type | |
1762 | s = std::distance(first, last); | |
1763 | ||
1764 | errh::check_capacity(*this, s); // may throw | |
1765 | ||
1766 | if ( m_size <= static_cast<size_type>(s) ) | |
1767 | { | |
1768 | sv::copy(first, first + m_size, this->begin()); // may throw | |
1769 | // TODO - perform uninitialized_copy first? | |
1770 | sv::uninitialized_copy(first + m_size, last, this->end()); // may throw | |
1771 | } | |
1772 | else | |
1773 | { | |
1774 | sv::copy(first, last, this->begin()); // may throw | |
1775 | sv::destroy(this->begin() + s, this->end()); | |
1776 | } | |
1777 | m_size = s; // update end | |
1778 | } | |
1779 | ||
1780 | // @par Throws | |
1781 | // If Value's constructor or assignment taking dereferenced Iterator throws. | |
1782 | // @par Complexity | |
1783 | // Linear O(N). | |
1784 | template <typename Iterator, typename Traversal> | |
1785 | void assign_dispatch(Iterator first, Iterator last, Traversal const& /*not_random_access*/) | |
1786 | { | |
1787 | namespace sv = varray_detail; | |
1788 | ||
1789 | size_type s = 0; | |
1790 | iterator it = this->begin(); | |
1791 | ||
1792 | for ( ; it != this->end() && first != last ; ++it, ++first, ++s ) | |
1793 | *it = *first; // may throw | |
1794 | ||
1795 | sv::destroy(it, this->end()); | |
1796 | ||
1797 | std::ptrdiff_t d = std::distance(it, this->begin() + Capacity); | |
1798 | std::size_t count = sv::uninitialized_copy_s(first, last, it, d); // may throw | |
1799 | s += count; | |
1800 | ||
1801 | errh::check_capacity(*this, count <= static_cast<std::size_t>(d) ? s : Capacity + 1); // may throw | |
1802 | ||
1803 | m_size = s; // update end | |
1804 | } | |
1805 | ||
1806 | pointer ptr() | |
1807 | { | |
1808 | return pointer(static_cast<Value*>(m_storage.address())); | |
1809 | } | |
1810 | ||
1811 | const_pointer ptr() const | |
1812 | { | |
1813 | return const_pointer(static_cast<const Value*>(m_storage.address())); | |
1814 | } | |
1815 | ||
1816 | size_type m_size; | |
1817 | aligned_storage_type m_storage; | |
1818 | }; | |
1819 | ||
1820 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1821 | ||
1822 | template<typename Value> | |
1823 | class varray<Value, 0> | |
1824 | { | |
1825 | typedef varray_detail::varray_traits<Value, 0> vt; | |
1826 | typedef varray_detail::checker<varray> errh; | |
1827 | ||
1828 | public: | |
1829 | typedef typename vt::value_type value_type; | |
1830 | typedef typename vt::size_type size_type; | |
1831 | typedef typename vt::difference_type difference_type; | |
1832 | typedef typename vt::pointer pointer; | |
1833 | typedef typename vt::const_pointer const_pointer; | |
1834 | typedef typename vt::reference reference; | |
1835 | typedef typename vt::const_reference const_reference; | |
1836 | ||
1837 | typedef pointer iterator; | |
1838 | typedef const_pointer const_iterator; | |
1839 | typedef boost::reverse_iterator<iterator> reverse_iterator; | |
1840 | typedef boost::reverse_iterator<const_iterator> const_reverse_iterator; | |
1841 | ||
1842 | // nothrow | |
1843 | varray() {} | |
1844 | ||
1845 | // strong | |
1846 | explicit varray(size_type count) | |
1847 | { | |
1848 | errh::check_capacity(*this, count); // may throw | |
1849 | } | |
1850 | ||
1851 | // strong | |
1852 | varray(size_type count, value_type const&) | |
1853 | { | |
1854 | errh::check_capacity(*this, count); // may throw | |
1855 | } | |
1856 | ||
1857 | // strong | |
1858 | varray(varray const& /*other*/) | |
1859 | { | |
1860 | //errh::check_capacity(*this, count); | |
1861 | } | |
1862 | ||
1863 | // strong | |
1864 | template <std::size_t C> | |
1865 | varray(varray<value_type, C> const& other) | |
1866 | { | |
1867 | errh::check_capacity(*this, other.size()); // may throw | |
1868 | } | |
1869 | ||
1870 | // strong | |
1871 | template <typename Iterator> | |
1872 | varray(Iterator first, Iterator last) | |
1873 | { | |
1874 | errh::check_capacity(*this, std::distance(first, last)); // may throw | |
1875 | } | |
1876 | ||
1877 | // basic | |
1878 | varray & operator=(varray const& /*other*/) | |
1879 | { | |
1880 | //errh::check_capacity(*this, other.size()); | |
1881 | return *this; | |
1882 | } | |
1883 | ||
1884 | // basic | |
1885 | template <size_t C> | |
1886 | varray & operator=(varray<value_type, C> const& other) | |
1887 | { | |
1888 | errh::check_capacity(*this, other.size()); // may throw | |
1889 | return *this; | |
1890 | } | |
1891 | ||
1892 | // nothrow | |
1893 | ~varray() {} | |
1894 | ||
1895 | // strong | |
1896 | void resize(size_type count) | |
1897 | { | |
1898 | errh::check_capacity(*this, count); // may throw | |
1899 | } | |
1900 | ||
1901 | // strong | |
1902 | void resize(size_type count, value_type const&) | |
1903 | { | |
1904 | errh::check_capacity(*this, count); // may throw | |
1905 | } | |
1906 | ||
1907 | ||
1908 | // nothrow | |
1909 | void reserve(size_type count) | |
1910 | { | |
1911 | errh::check_capacity(*this, count); // may throw | |
1912 | } | |
1913 | ||
1914 | // strong | |
1915 | void push_back(value_type const&) | |
1916 | { | |
1917 | errh::check_capacity(*this, 1); // may throw | |
1918 | } | |
1919 | ||
1920 | // nothrow | |
1921 | void pop_back() | |
1922 | { | |
1923 | errh::check_not_empty(*this); | |
1924 | } | |
1925 | ||
1926 | // basic | |
1927 | void insert(iterator position, value_type const&) | |
1928 | { | |
1929 | errh::check_iterator_end_eq(*this, position); | |
1930 | errh::check_capacity(*this, 1); // may throw | |
1931 | } | |
1932 | ||
1933 | // basic | |
1934 | void insert(iterator position, size_type count, value_type const&) | |
1935 | { | |
1936 | errh::check_iterator_end_eq(*this, position); | |
1937 | errh::check_capacity(*this, count); // may throw | |
1938 | } | |
1939 | ||
1940 | // basic | |
1941 | template <typename Iterator> | |
1942 | void insert(iterator, Iterator first, Iterator last) | |
1943 | { | |
1944 | // TODO - add MPL_ASSERT, check if Iterator is really an iterator | |
1945 | errh::check_capacity(*this, std::distance(first, last)); // may throw | |
1946 | } | |
1947 | ||
1948 | // basic | |
1949 | void erase(iterator position) | |
1950 | { | |
1951 | errh::check_iterator_end_neq(*this, position); | |
1952 | } | |
1953 | ||
1954 | // basic | |
1955 | void erase(iterator first, iterator last) | |
1956 | { | |
1957 | errh::check_iterator_end_eq(*this, first); | |
1958 | errh::check_iterator_end_eq(*this, last); | |
1959 | ||
1960 | //BOOST_GEOMETRY_INDEX_ASSERT(0 <= n, "invalid range"); | |
1961 | } | |
1962 | ||
1963 | // basic | |
1964 | template <typename Iterator> | |
1965 | void assign(Iterator first, Iterator last) | |
1966 | { | |
1967 | // TODO - add MPL_ASSERT, check if Iterator is really an iterator | |
1968 | errh::check_capacity(*this, std::distance(first, last)); // may throw | |
1969 | } | |
1970 | ||
1971 | // basic | |
1972 | void assign(size_type count, value_type const&) | |
1973 | { | |
1974 | errh::check_capacity(*this, count); // may throw | |
1975 | } | |
1976 | ||
1977 | // nothrow | |
1978 | void clear() {} | |
1979 | ||
1980 | // strong | |
1981 | reference at(size_type i) | |
1982 | { | |
1983 | errh::throw_out_of_bounds(*this, i); // may throw | |
1984 | return *(this->begin() + i); | |
1985 | } | |
1986 | ||
1987 | // strong | |
1988 | const_reference at(size_type i) const | |
1989 | { | |
1990 | errh::throw_out_of_bounds(*this, i); // may throw | |
1991 | return *(this->begin() + i); | |
1992 | } | |
1993 | ||
1994 | // nothrow | |
1995 | reference operator[](size_type i) | |
1996 | { | |
1997 | errh::check_index(*this, i); | |
1998 | return *(this->begin() + i); | |
1999 | } | |
2000 | ||
2001 | // nothrow | |
2002 | const_reference operator[](size_type i) const | |
2003 | { | |
2004 | errh::check_index(*this, i); | |
2005 | return *(this->begin() + i); | |
2006 | } | |
2007 | ||
2008 | // nothrow | |
2009 | reference front() | |
2010 | { | |
2011 | errh::check_not_empty(*this); | |
2012 | return *(this->begin()); | |
2013 | } | |
2014 | ||
2015 | // nothrow | |
2016 | const_reference front() const | |
2017 | { | |
2018 | errh::check_not_empty(*this); | |
2019 | return *(this->begin()); | |
2020 | } | |
2021 | ||
2022 | // nothrow | |
2023 | reference back() | |
2024 | { | |
2025 | errh::check_not_empty(*this); | |
2026 | return *(this->end() - 1); | |
2027 | } | |
2028 | ||
2029 | // nothrow | |
2030 | const_reference back() const | |
2031 | { | |
2032 | errh::check_not_empty(*this); | |
2033 | return *(this->end() - 1); | |
2034 | } | |
2035 | ||
2036 | // nothrow | |
2037 | Value * data() { return boost::addressof(*(this->ptr())); } | |
2038 | const Value * data() const { return boost::addressof(*(this->ptr())); } | |
2039 | ||
2040 | // nothrow | |
2041 | iterator begin() { return this->ptr(); } | |
2042 | const_iterator begin() const { return this->ptr(); } | |
2043 | const_iterator cbegin() const { return this->ptr(); } | |
2044 | iterator end() { return this->begin(); } | |
2045 | const_iterator end() const { return this->begin(); } | |
2046 | const_iterator cend() const { return this->cbegin(); } | |
2047 | // nothrow | |
2048 | reverse_iterator rbegin() { return reverse_iterator(this->end()); } | |
2049 | const_reverse_iterator rbegin() const { return reverse_iterator(this->end()); } | |
2050 | const_reverse_iterator crbegin() const { return reverse_iterator(this->end()); } | |
2051 | reverse_iterator rend() { return reverse_iterator(this->begin()); } | |
2052 | const_reverse_iterator rend() const { return reverse_iterator(this->begin()); } | |
2053 | const_reverse_iterator crend() const { return reverse_iterator(this->begin()); } | |
2054 | ||
2055 | // nothrow | |
2056 | size_type capacity() const { return 0; } | |
2057 | size_type max_size() const { return 0; } | |
2058 | size_type size() const { return 0; } | |
2059 | bool empty() const { return true; } | |
2060 | ||
2061 | private: | |
2062 | pointer ptr() | |
2063 | { | |
2064 | return pointer(reinterpret_cast<Value*>(this)); | |
2065 | } | |
2066 | ||
2067 | const_pointer ptr() const | |
2068 | { | |
2069 | return const_pointer(reinterpret_cast<const Value*>(this)); | |
2070 | } | |
2071 | }; | |
2072 | ||
2073 | #endif // !BOOST_CONTAINER_DOXYGEN_INVOKED | |
2074 | ||
2075 | //! @brief Checks if contents of two varrays are equal. | |
2076 | //! | |
2077 | //! @ingroup varray_non_member | |
2078 | //! | |
2079 | //! @param x The first varray. | |
2080 | //! @param y The second varray. | |
2081 | //! | |
2082 | //! @return \c true if containers have the same size and elements in both containers are equal. | |
2083 | //! | |
2084 | //! @par Complexity | |
2085 | //! Linear O(N). | |
2086 | template<typename V, std::size_t C1, std::size_t C2> | |
2087 | bool operator== (varray<V, C1> const& x, varray<V, C2> const& y) | |
2088 | { | |
2089 | return x.size() == y.size() && std::equal(x.begin(), x.end(), y.begin()); | |
2090 | } | |
2091 | ||
2092 | //! @brief Checks if contents of two varrays are not equal. | |
2093 | //! | |
2094 | //! @ingroup varray_non_member | |
2095 | //! | |
2096 | //! @param x The first varray. | |
2097 | //! @param y The second varray. | |
2098 | //! | |
2099 | //! @return \c true if containers have different size or elements in both containers are not equal. | |
2100 | //! | |
2101 | //! @par Complexity | |
2102 | //! Linear O(N). | |
2103 | template<typename V, std::size_t C1, std::size_t C2> | |
2104 | bool operator!= (varray<V, C1> const& x, varray<V, C2> const& y) | |
2105 | { | |
2106 | return !(x==y); | |
2107 | } | |
2108 | ||
2109 | //! @brief Lexicographically compares varrays. | |
2110 | //! | |
2111 | //! @ingroup varray_non_member | |
2112 | //! | |
2113 | //! @param x The first varray. | |
2114 | //! @param y The second varray. | |
2115 | //! | |
2116 | //! @return \c true if x compares lexicographically less than y. | |
2117 | //! | |
2118 | //! @par Complexity | |
2119 | //! Linear O(N). | |
2120 | template<typename V, std::size_t C1, std::size_t C2> | |
2121 | bool operator< (varray<V, C1> const& x, varray<V, C2> const& y) | |
2122 | { | |
2123 | return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); | |
2124 | } | |
2125 | ||
2126 | //! @brief Lexicographically compares varrays. | |
2127 | //! | |
2128 | //! @ingroup varray_non_member | |
2129 | //! | |
2130 | //! @param x The first varray. | |
2131 | //! @param y The second varray. | |
2132 | //! | |
2133 | //! @return \c true if y compares lexicographically less than x. | |
2134 | //! | |
2135 | //! @par Complexity | |
2136 | //! Linear O(N). | |
2137 | template<typename V, std::size_t C1, std::size_t C2> | |
2138 | bool operator> (varray<V, C1> const& x, varray<V, C2> const& y) | |
2139 | { | |
2140 | return y<x; | |
2141 | } | |
2142 | ||
2143 | //! @brief Lexicographically compares varrays. | |
2144 | //! | |
2145 | //! @ingroup varray_non_member | |
2146 | //! | |
2147 | //! @param x The first varray. | |
2148 | //! @param y The second varray. | |
2149 | //! | |
2150 | //! @return \c true if y don't compare lexicographically less than x. | |
2151 | //! | |
2152 | //! @par Complexity | |
2153 | //! Linear O(N). | |
2154 | template<typename V, std::size_t C1, std::size_t C2> | |
2155 | bool operator<= (varray<V, C1> const& x, varray<V, C2> const& y) | |
2156 | { | |
2157 | return !(y<x); | |
2158 | } | |
2159 | ||
2160 | //! @brief Lexicographically compares varrays. | |
2161 | //! | |
2162 | //! @ingroup varray_non_member | |
2163 | //! | |
2164 | //! @param x The first varray. | |
2165 | //! @param y The second varray. | |
2166 | //! | |
2167 | //! @return \c true if x don't compare lexicographically less than y. | |
2168 | //! | |
2169 | //! @par Complexity | |
2170 | //! Linear O(N). | |
2171 | template<typename V, std::size_t C1, std::size_t C2> | |
2172 | bool operator>= (varray<V, C1> const& x, varray<V, C2> const& y) | |
2173 | { | |
2174 | return !(x<y); | |
2175 | } | |
2176 | ||
2177 | //! @brief Swaps contents of two varrays. | |
2178 | //! | |
2179 | //! This function calls varray::swap(). | |
2180 | //! | |
2181 | //! @ingroup varray_non_member | |
2182 | //! | |
2183 | //! @param x The first varray. | |
2184 | //! @param y The second varray. | |
2185 | //! | |
2186 | //! @par Complexity | |
2187 | //! Linear O(N). | |
2188 | template<typename V, std::size_t C1, std::size_t C2> | |
2189 | inline void swap(varray<V, C1> & x, varray<V, C2> & y) | |
2190 | { | |
2191 | x.swap(y); | |
2192 | } | |
2193 | ||
2194 | }}}} // namespace boost::geometry::index::detail | |
2195 | ||
2196 | // TODO - REMOVE/CHANGE | |
2197 | #include <boost/container/detail/config_end.hpp> | |
2198 | ||
2199 | #endif // BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_HPP |