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(str: "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(dest: this->data(), src: other.data(), n: 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(dest: this->data(), src: other.data(), n: 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(dest: temp_ptr, src: this->data(), n: sizeof(Value) * this->size()); |
1579 | ::memcpy(dest: this->data(), src: other.data(), n: sizeof(Value) * other.size()); |
1580 | ::memcpy(dest: other.data(), src: temp_ptr, n: 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(dest: temp_ptr, src: boost::addressof(*first_sm), n: sizeof(value_type)); |
1624 | ::memcpy(dest: boost::addressof(*first_sm), src: boost::addressof(*first_la), n: sizeof(value_type)); |
1625 | ::memcpy(dest: boost::addressof(*first_la), src: temp_ptr, n: sizeof(value_type)); |
1626 | } |
1627 | |
1628 | ::memcpy(dest: first_sm, src: first_la, n: 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 |
2200 | |