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
48namespace boost { namespace geometry { namespace index { namespace detail {
49
50namespace varray_detail {
51
52template <typename Value, std::size_t Capacity>
53struct 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
68template <typename Varray>
69struct 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
128varray is a sequence container like boost::container::vector with contiguous storage that can
129change in size, along with the static allocation, low overhead, and fixed capacity of boost::array.
130
131A varray is a sequence that supports random access to elements, constant time insertion and
132removal of elements at the end, and linear time insertion and removal of elements at the beginning or
133in the middle. The number of elements in a varray may vary dynamically up to a fixed capacity
134because elements are stored within the object itself similarly to an array. However, objects are
135initialized as they are inserted into varray unlike C arrays or std::array which must construct
136all elements on instantiation. The behavior of varray enables the use of statically allocated
137elements in cases with complex object lifetime requirements that would otherwise not be trivially
138possible.
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*/
156template <typename Value, std::size_t Capacity>
157class 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
180public:
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
190public:
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
1498private:
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
1822template<typename Value>
1823class varray<Value, 0>
1824{
1825 typedef varray_detail::varray_traits<Value, 0> vt;
1826 typedef varray_detail::checker<varray> errh;
1827
1828public:
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
2061private:
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).
2086template<typename V, std::size_t C1, std::size_t C2>
2087bool 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).
2103template<typename V, std::size_t C1, std::size_t C2>
2104bool 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).
2120template<typename V, std::size_t C1, std::size_t C2>
2121bool 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).
2137template<typename V, std::size_t C1, std::size_t C2>
2138bool 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).
2154template<typename V, std::size_t C1, std::size_t C2>
2155bool 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).
2171template<typename V, std::size_t C1, std::size_t C2>
2172bool 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).
2188template<typename V, std::size_t C1, std::size_t C2>
2189inline 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

source code of boost/boost/geometry/index/detail/varray.hpp