1 // Boost.Container varray
3 // Copyright (c) 2012-2015 Adam Wulkiewicz, Lodz, Poland.
4 // Copyright (c) 2011-2013 Andrew Hundt.
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)
10 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_HPP
11 #define BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_HPP
13 // TODO - REMOVE/CHANGE
14 #include <boost/container/detail/config_begin.hpp>
15 #include <boost/container/detail/workaround.hpp>
17 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
18 #include <boost/move/detail/fwd_macros.hpp>
21 #include <boost/config.hpp>
22 #include <boost/swap.hpp>
23 #include <boost/integer.hpp>
25 #include <boost/mpl/assert.hpp>
27 #include <boost/type_traits/is_unsigned.hpp>
28 #include <boost/type_traits/alignment_of.hpp>
29 #include <boost/type_traits/aligned_storage.hpp>
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>
37 #include <boost/geometry/index/detail/assert.hpp>
38 #include <boost/geometry/index/detail/exception.hpp>
40 #include <boost/geometry/index/detail/varray_detail.hpp>
42 #include <boost/concept_check.hpp>
45 \defgroup varray_non_member varray non-member functions
48 namespace boost { namespace geometry { namespace index { namespace detail {
50 namespace varray_detail {
52 template <typename Value, std::size_t Capacity>
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;
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;
68 template <typename Varray>
71 typedef typename Varray::size_type size_type;
72 typedef typename Varray::const_iterator const_iterator;
74 static inline void check_capacity(Varray const& v, size_type s)
76 BOOST_GEOMETRY_INDEX_ASSERT(s <= v.capacity(), "size too big");
78 ::boost::ignore_unused_variable_warning(v);
79 ::boost::ignore_unused_variable_warning(s);
82 static inline void throw_out_of_bounds(Varray const& v, size_type i)
85 throw_out_of_range("index out of bounds");
87 ::boost::ignore_unused_variable_warning(v);
88 ::boost::ignore_unused_variable_warning(i);
91 static inline void check_index(Varray const& v, size_type i)
93 BOOST_GEOMETRY_INDEX_ASSERT(i < v.size(), "index out of bounds");
95 ::boost::ignore_unused_variable_warning(v);
96 ::boost::ignore_unused_variable_warning(i);
99 static inline void check_not_empty(Varray const& v)
101 BOOST_GEOMETRY_INDEX_ASSERT(!v.empty(), "the container is empty");
103 ::boost::ignore_unused_variable_warning(v);
106 static inline void check_iterator_end_neq(Varray const& v, const_iterator position)
108 BOOST_GEOMETRY_INDEX_ASSERT(v.begin() <= position && position < v.end(), "iterator out of bounds");
110 ::boost::ignore_unused_variable_warning(v);
111 ::boost::ignore_unused_variable_warning(position);
114 static inline void check_iterator_end_eq(Varray const& v, const_iterator position)
116 BOOST_GEOMETRY_INDEX_ASSERT(v.begin() <= position && position <= v.end(), "iterator out of bounds");
118 ::boost::ignore_unused_variable_warning(v);
119 ::boost::ignore_unused_variable_warning(position);
123 } // namespace varray_detail
126 \brief A variable-size array container with fixed capacity.
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.
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
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.
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.
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
156 template <typename Value, std::size_t Capacity>
159 typedef varray_detail::varray_traits<Value, Capacity> vt;
160 typedef varray_detail::checker<varray> errh;
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,
169 typedef boost::aligned_storage<
170 sizeof(Value[Capacity]),
171 boost::alignment_of<Value[Capacity]>::value
172 > aligned_storage_type;
174 template <typename V, std::size_t C>
177 BOOST_COPYABLE_AND_MOVABLE(varray)
179 #ifdef BOOST_NO_CXX11_RVALUE_REFERENCES
181 template <std::size_t C>
182 varray & operator=(varray<Value, C> & sv)
184 typedef varray<Value, C> other;
185 this->operator=(static_cast<const ::boost::rv<other> &>(const_cast<const other &>(sv)));
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;
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;
215 //! @brief Constructs an empty varray.
226 //! @pre <tt>count <= capacity()</tt>
228 //! @brief Constructs a varray containing count default constructed Values.
230 //! @param count The number of values which will be contained in the container.
233 //! If Value's default constructor throws.
235 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
240 explicit varray(size_type count)
243 this->resize(count); // may throw
246 //! @pre <tt>count <= capacity()</tt>
248 //! @brief Constructs a varray containing count copies of value.
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.
254 //! If Value's copy constructor throws.
256 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
261 varray(size_type count, value_type const& value)
264 this->resize(count, value); // may throw
268 //! @li <tt>distance(first, last) <= capacity()</tt>
269 //! @li Iterator must meet the \c ForwardTraversalIterator concept.
271 //! @brief Constructs a varray containing copy of a range <tt>[first, last)</tt>.
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.
277 //! If Value's constructor taking a dereferenced Iterator throws.
279 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
284 template <typename Iterator>
285 varray(Iterator first, Iterator last)
288 BOOST_CONCEPT_ASSERT((boost_concepts::ForwardTraversal<Iterator>)); // Make sure you passed a ForwardIterator
290 this->assign(first, last); // may throw
293 //! @brief Constructs a copy of other varray.
295 //! @param other The varray which content will be copied to this one.
298 //! If Value's copy constructor throws.
302 varray(varray const& other)
303 : m_size(other.size())
305 namespace sv = varray_detail;
306 sv::uninitialized_copy(other.begin(), other.end(), this->begin()); // may throw
309 //! @pre <tt>other.size() <= capacity()</tt>.
311 //! @brief Constructs a copy of other varray.
313 //! @param other The varray which content will be copied to this one.
316 //! If Value's copy constructor throws.
318 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
323 template <std::size_t C>
324 varray(varray<value_type, C> const& other)
325 : m_size(other.size())
327 errh::check_capacity(*this, other.size()); // may throw
329 namespace sv = varray_detail;
330 sv::uninitialized_copy(other.begin(), other.end(), this->begin()); // may throw
333 //! @brief Copy assigns Values stored in the other varray to this one.
335 //! @param other The varray which content will be copied to this one.
338 //! If Value's copy constructor or copy assignment throws.
342 varray & operator=(BOOST_COPY_ASSIGN_REF(varray) other)
344 this->assign(other.begin(), other.end()); // may throw
349 //! @pre <tt>other.size() <= capacity()</tt>
351 //! @brief Copy assigns Values stored in the other varray to this one.
353 //! @param other The varray which content will be copied to this one.
356 //! If Value's copy constructor or copy assignment throws.
358 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
363 template <std::size_t C>
364 varray & operator=(BOOST_COPY_ASSIGN_REF_2_TEMPL_ARGS(varray, value_type, C) other)
366 this->assign(other.begin(), other.end()); // may throw
371 //! @brief Move constructor. Moves Values stored in the other varray to this one.
373 //! @param other The varray which content will be moved to this one.
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.
379 //! @li It throws only if \c use_memop_in_swap_and_move is \c false_type - default.
384 varray(BOOST_RV_REF(varray) other)
387 vt::use_memop_in_swap_and_move use_memop_in_swap_and_move;
389 this->move_ctor_dispatch(other, use_memop_in_swap_and_move());
392 //! @pre <tt>other.size() <= capacity()</tt>
394 //! @brief Move constructor. Moves Values stored in the other varray to this one.
396 //! @param other The varray which content will be moved to this one.
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.
402 //! @li It throws only if \c use_memop_in_swap_and_move is false_type - default.
405 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
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)
414 errh::check_capacity(*this, other.size()); // may throw
417 vt::use_memop_in_swap_and_move use_memop_in_swap_and_move;
419 this->move_ctor_dispatch(other, use_memop_in_swap_and_move());
422 //! @brief Move assignment. Moves Values stored in the other varray to this one.
424 //! @param other The varray which content will be moved to this one.
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.
430 //! @li It throws only if \c use_memop_in_swap_and_move is \c false_type - default.
435 varray & operator=(BOOST_RV_REF(varray) other)
437 if ( &other == this )
441 vt::use_memop_in_swap_and_move use_memop_in_swap_and_move;
443 this->move_assign_dispatch(other, use_memop_in_swap_and_move());
448 //! @pre <tt>other.size() <= capacity()</tt>
450 //! @brief Move assignment. Moves Values stored in the other varray to this one.
452 //! @param other The varray which content will be moved to this one.
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.
458 //! @li It throws only if \c use_memop_in_swap_and_move is \c false_type - default.
461 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
466 template <std::size_t C>
467 varray & operator=(BOOST_RV_REF_2_TEMPL_ARGS(varray, value_type, C) other)
469 errh::check_capacity(*this, other.size()); // may throw
472 vt::use_memop_in_swap_and_move use_memop_in_swap_and_move;
474 this->move_assign_dispatch(other, use_memop_in_swap_and_move());
479 //! @brief Destructor. Destroys Values stored in this container.
488 namespace sv = varray_detail;
489 sv::destroy(this->begin(), this->end());
492 //! @brief Swaps contents of the other varray and this one.
494 //! @param other The varray which content will be swapped with this one's content.
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,
500 //! @li It throws only if \c use_memop_in_swap_and_move and \c use_optimized_swap are \c false_type - default.
505 void swap(varray & other)
508 vt::use_optimized_swap use_optimized_swap;
510 this->swap_dispatch(other, use_optimized_swap());
513 //! @pre <tt>other.size() <= capacity() && size() <= other.capacity()</tt>
515 //! @brief Swaps contents of the other varray and this one.
517 //! @param other The varray which content will be swapped with this one's content.
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,
523 //! @li It throws only if \c use_memop_in_swap_and_move and \c use_optimized_swap are \c false_type - default.
526 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
531 template <std::size_t C>
532 void swap(varray<value_type, C> & other)
534 errh::check_capacity(*this, other.size());
535 errh::check_capacity(other, this->size());
538 vt::use_optimized_swap use_optimized_swap;
540 this->swap_dispatch(other, use_optimized_swap());
543 //! @pre <tt>count <= capacity()</tt>
545 //! @brief Inserts or erases elements at the end such that
546 //! the size becomes count. New elements are default constructed.
548 //! @param count The number of elements which will be stored in the container.
551 //! If Value's default constructor throws.
553 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
558 void resize(size_type count)
560 namespace sv = varray_detail;
561 typedef typename vt::disable_trivial_init dti;
563 if ( count < m_size )
565 sv::destroy(this->begin() + count, this->end());
569 errh::check_capacity(*this, count); // may throw
571 sv::uninitialized_fill(this->end(), this->begin() + count, dti()); // may throw
573 m_size = count; // update end
576 //! @pre <tt>count <= capacity()</tt>
578 //! @brief Inserts or erases elements at the end such that
579 //! the size becomes count. New elements are copy constructed from value.
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.
585 //! If Value's copy constructor throws.
587 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
592 void resize(size_type count, value_type const& value)
594 if ( count < m_size )
596 namespace sv = varray_detail;
597 sv::destroy(this->begin() + count, this->end());
601 errh::check_capacity(*this, count); // may throw
603 std::uninitialized_fill(this->end(), this->begin() + count, value); // may throw
605 m_size = count; // update end
608 //! @pre <tt>count <= capacity()</tt>
610 //! @brief This call has no effect because the Capacity of this container is constant.
612 //! @param count The number of elements which the container should be able to contain.
617 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
622 void reserve(size_type count)
624 errh::check_capacity(*this, count); // may throw
627 //! @pre <tt>size() < capacity()</tt>
629 //! @brief Adds a copy of value at the end.
631 //! @param value The value used to copy construct the new element.
634 //! If Value's copy constructor throws.
636 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
641 void push_back(value_type const& value)
643 typedef typename vt::disable_trivial_init dti;
645 errh::check_capacity(*this, m_size + 1); // may throw
647 namespace sv = varray_detail;
648 sv::construct(dti(), this->end(), value); // may throw
649 ++m_size; // update end
652 //! @pre <tt>size() < capacity()</tt>
654 //! @brief Moves value to the end.
656 //! @param value The value to move construct the new element.
659 //! If Value's move constructor throws.
661 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
666 void push_back(BOOST_RV_REF(value_type) value)
668 typedef typename vt::disable_trivial_init dti;
670 errh::check_capacity(*this, m_size + 1); // may throw
672 namespace sv = varray_detail;
673 sv::construct(dti(), this->end(), ::boost::move(value)); // may throw
674 ++m_size; // update end
677 //! @pre <tt>!empty()</tt>
679 //! @brief Destroys last value and decreases the size.
682 //! Nothing by default.
688 errh::check_not_empty(*this);
690 namespace sv = varray_detail;
691 sv::destroy(this->end() - 1);
692 --m_size; // update end
696 //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>.
697 //! @li <tt>size() < capacity()</tt>
699 //! @brief Inserts a copy of element at position.
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.
705 //! @li If Value's copy constructor or copy assignment throws
706 //! @li If Value's move constructor or move assignment throws.
708 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
712 //! Constant or linear.
713 iterator insert(iterator position, value_type const& value)
715 typedef typename vt::disable_trivial_init dti;
716 namespace sv = varray_detail;
718 errh::check_iterator_end_eq(*this, position);
719 errh::check_capacity(*this, m_size + 1); // may throw
721 if ( position == this->end() )
723 sv::construct(dti(), position, value); // may throw
724 ++m_size; // update end
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
740 //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>.
741 //! @li <tt>size() < capacity()</tt>
743 //! @brief Inserts a move-constructed element at position.
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.
749 //! If Value's move constructor or move assignment throws.
751 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
755 //! Constant or linear.
756 iterator insert(iterator position, BOOST_RV_REF(value_type) value)
758 typedef typename vt::disable_trivial_init dti;
759 namespace sv = varray_detail;
761 errh::check_iterator_end_eq(*this, position);
762 errh::check_capacity(*this, m_size + 1); // may throw
764 if ( position == this->end() )
766 sv::construct(dti(), position, boost::move(value)); // may throw
767 ++m_size; // update end
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
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>
786 //! @brief Inserts a count copies of value at position.
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.
793 //! @li If Value's copy constructor or copy assignment throws.
794 //! @li If Value's move constructor or move assignment throws.
796 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
801 iterator insert(iterator position, size_type count, value_type const& value)
803 errh::check_iterator_end_eq(*this, position);
804 errh::check_capacity(*this, m_size + count); // may throw
806 if ( position == this->end() )
808 std::uninitialized_fill(position, position + count, value); // may throw
809 m_size += count; // update end
813 namespace sv = varray_detail;
815 difference_type to_move = std::distance(position, this->end());
817 // TODO - should following lines check for exception and revert to the old size?
819 if ( count < static_cast<size_type>(to_move) )
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
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
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.
844 //! @brief Inserts a copy of a range <tt>[first, last)</tt> at position.
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.
851 //! @li If Value's constructor and assignment taking a dereferenced \c Iterator.
852 //! @li If Value's move constructor or move assignment throws.
854 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
859 template <typename Iterator>
860 iterator insert(iterator position, Iterator first, Iterator last)
862 BOOST_CONCEPT_ASSERT((boost_concepts::ForwardTraversal<Iterator>)); // Make sure you passed a ForwardIterator
864 typedef typename boost::iterator_traversal<Iterator>::type traversal;
865 this->insert_dispatch(position, first, last, traversal());
870 //! @pre \c position must be a valid iterator of \c *this in range <tt>[begin(), end())</tt>
872 //! @brief Erases Value from position.
874 //! @param position The position of the element which will be erased from the container.
877 //! If Value's move assignment throws.
881 iterator erase(iterator position)
883 namespace sv = varray_detail;
885 errh::check_iterator_end_neq(*this, position);
887 //TODO - add empty check?
888 //errh::check_empty(*this);
890 sv::move(position + 1, this->end(), position); // may throw
891 sv::destroy(this->end() - 1);
898 //! @li \c first and \c last must define a valid range
899 //! @li iterators must be in range <tt>[begin(), end()]</tt>
901 //! @brief Erases Values from a range <tt>[first, last)</tt>.
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.
907 //! If Value's move assignment throws.
911 iterator erase(iterator first, iterator last)
913 namespace sv = varray_detail;
915 errh::check_iterator_end_eq(*this, first);
916 errh::check_iterator_end_eq(*this, last);
918 difference_type n = std::distance(first, last);
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");
925 sv::move(last, this->end(), first); // may throw
926 sv::destroy(this->end() - n, this->end());
932 //! @pre <tt>distance(first, last) <= capacity()</tt>
934 //! @brief Assigns a range <tt>[first, last)</tt> of Values to this container.
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.
940 //! If Value's copy constructor or copy assignment throws,
944 template <typename Iterator>
945 void assign(Iterator first, Iterator last)
947 BOOST_CONCEPT_ASSERT((boost_concepts::ForwardTraversal<Iterator>)); // Make sure you passed a ForwardIterator
949 typedef typename boost::iterator_traversal<Iterator>::type traversal;
950 this->assign_dispatch(first, last, traversal()); // may throw
953 //! @pre <tt>count <= capacity()</tt>
955 //! @brief Assigns a count copies of value to this container.
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.
961 //! If Value's copy constructor or copy assignment throws.
965 void assign(size_type count, value_type const& value)
967 if ( count < m_size )
969 namespace sv = varray_detail;
971 std::fill_n(this->begin(), count, value); // may throw
972 sv::destroy(this->begin() + count, this->end());
976 errh::check_capacity(*this, count); // may throw
978 std::fill_n(this->begin(), m_size, value); // may throw
979 std::uninitialized_fill(this->end(), this->begin() + count, value); // may throw
981 m_size = count; // update end
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>
988 //! @brief Inserts a Value constructed with
989 //! \c std::forward<Args>(args)... in the end of the container.
991 //! @param args The arguments of the constructor of the new element which will be created at the end of the container.
994 //! If in-place constructor throws or Value's move constructor throws.
996 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
1001 template<class ...Args>
1002 void emplace_back(BOOST_FWD_REF(Args) ...args)
1004 typedef typename vt::disable_trivial_init dti;
1006 errh::check_capacity(*this, m_size + 1); // may throw
1008 namespace sv = varray_detail;
1009 sv::construct(dti(), this->end(), ::boost::forward<Args>(args)...); // may throw
1010 ++m_size; // update end
1014 //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>
1015 //! @li <tt>size() < capacity()</tt>
1017 //! @brief Inserts a Value constructed with
1018 //! \c std::forward<Args>(args)... before position
1020 //! @param position The position at which new elements will be inserted.
1021 //! @param args The arguments of the constructor of the new element.
1024 //! If in-place constructor throws or if Value's move constructor or move assignment throws.
1026 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
1030 //! Constant or linear.
1031 template<class ...Args>
1032 iterator emplace(iterator position, BOOST_FWD_REF(Args) ...args)
1034 typedef typename vt::disable_trivial_init dti;
1036 namespace sv = varray_detail;
1038 errh::check_iterator_end_eq(*this, position);
1039 errh::check_capacity(*this, m_size + 1); // may throw
1041 if ( position == this->end() )
1043 sv::construct(dti(), position, ::boost::forward<Args>(args)...); // may throw
1044 ++m_size; // update end
1048 // TODO - should following lines check for exception and revert to the old size?
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
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
1066 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
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) \
1072 typedef typename vt::disable_trivial_init dti; \
1074 errh::check_capacity(*this, m_size + 1); /*may throw*/\
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*/ \
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) \
1084 typedef typename vt::disable_trivial_init dti; \
1085 namespace sv = varray_detail; \
1087 errh::check_iterator_end_eq(*this, position); \
1088 errh::check_capacity(*this, m_size + 1); /*may throw*/\
1090 if ( position == this->end() ) \
1092 sv::construct(dti(), position BOOST_MOVE_I##N BOOST_MOVE_FWD##N ); /*may throw*/\
1093 ++m_size; /*update end*/ \
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? */ \
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*/\
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*/\
1115 BOOST_MOVE_ITERATE_0TO9(BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_EMPLACE)
1116 #undef BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_EMPLACE
1118 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1119 #endif // !BOOST_CONTAINER_VARRAY_DISABLE_EMPLACE
1121 //! @brief Removes all elements from the container.
1130 namespace sv = varray_detail;
1131 sv::destroy(this->begin(), this->end());
1132 m_size = 0; // update end
1135 //! @pre <tt>i < size()</tt>
1137 //! @brief Returns reference to the i-th element.
1139 //! @param i The element's index.
1141 //! @return reference to the i-th element
1142 //! from the beginning of the container.
1145 //! \c std::out_of_range exception by default.
1149 reference at(size_type i)
1151 errh::throw_out_of_bounds(*this, i); // may throw
1152 return *(this->begin() + i);
1155 //! @pre <tt>i < size()</tt>
1157 //! @brief Returns const reference to the i-th element.
1159 //! @param i The element's index.
1161 //! @return const reference to the i-th element
1162 //! from the beginning of the container.
1165 //! \c std::out_of_range exception by default.
1169 const_reference at(size_type i) const
1171 errh::throw_out_of_bounds(*this, i); // may throw
1172 return *(this->begin() + i);
1175 //! @pre <tt>i < size()</tt>
1177 //! @brief Returns reference to the i-th element.
1179 //! @param i The element's index.
1181 //! @return reference to the i-th element
1182 //! from the beginning of the container.
1185 //! Nothing by default.
1189 reference operator[](size_type i)
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);
1196 //! @pre <tt>i < size()</tt>
1198 //! @brief Returns const reference to the i-th element.
1200 //! @param i The element's index.
1202 //! @return const reference to the i-th element
1203 //! from the beginning of the container.
1206 //! Nothing by default.
1210 const_reference operator[](size_type i) const
1212 errh::check_index(*this, i);
1213 return *(this->begin() + i);
1216 //! @pre \c !empty()
1218 //! @brief Returns reference to the first element.
1220 //! @return reference to the first element
1221 //! from the beginning of the container.
1224 //! Nothing by default.
1230 errh::check_not_empty(*this);
1231 return *(this->begin());
1234 //! @pre \c !empty()
1236 //! @brief Returns const reference to the first element.
1238 //! @return const reference to the first element
1239 //! from the beginning of the container.
1242 //! Nothing by default.
1246 const_reference front() const
1248 errh::check_not_empty(*this);
1249 return *(this->begin());
1252 //! @pre \c !empty()
1254 //! @brief Returns reference to the last element.
1256 //! @return reference to the last element
1257 //! from the beginning of the container.
1260 //! Nothing by default.
1266 errh::check_not_empty(*this);
1267 return *(this->end() - 1);
1270 //! @pre \c !empty()
1272 //! @brief Returns const reference to the first element.
1274 //! @return const reference to the last element
1275 //! from the beginning of the container.
1278 //! Nothing by default.
1282 const_reference back() const
1284 errh::check_not_empty(*this);
1285 return *(this->end() - 1);
1288 //! @brief Pointer such that <tt>[data(), data() + size())</tt> is a valid range.
1289 //! For a non-empty vector <tt>data() == &front()</tt>.
1298 return boost::addressof(*(this->ptr()));
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>.
1309 const Value * data() const
1311 return boost::addressof(*(this->ptr()));
1315 //! @brief Returns iterator to the first element.
1317 //! @return iterator to the first element contained in the vector.
1324 iterator begin() { return this->ptr(); }
1326 //! @brief Returns const iterator to the first element.
1328 //! @return const_iterator to the first element contained in the vector.
1335 const_iterator begin() const { return this->ptr(); }
1337 //! @brief Returns const iterator to the first element.
1339 //! @return const_iterator to the first element contained in the vector.
1346 const_iterator cbegin() const { return this->ptr(); }
1348 //! @brief Returns iterator to the one after the last element.
1350 //! @return iterator pointing to the one after the last element contained in the vector.
1357 iterator end() { return this->begin() + m_size; }
1359 //! @brief Returns const iterator to the one after the last element.
1361 //! @return const_iterator pointing to the one after the last element contained in the vector.
1368 const_iterator end() const { return this->begin() + m_size; }
1370 //! @brief Returns const iterator to the one after the last element.
1372 //! @return const_iterator pointing to the one after the last element contained in the vector.
1379 const_iterator cend() const { return this->cbegin() + m_size; }
1381 //! @brief Returns reverse iterator to the first element of the reversed container.
1383 //! @return reverse_iterator pointing to the beginning
1384 //! of the reversed varray.
1391 reverse_iterator rbegin() { return reverse_iterator(this->end()); }
1393 //! @brief Returns const reverse iterator to the first element of the reversed container.
1395 //! @return const_reverse_iterator pointing to the beginning
1396 //! of the reversed varray.
1403 const_reverse_iterator rbegin() const { return const_reverse_iterator(this->end()); }
1405 //! @brief Returns const reverse iterator to the first element of the reversed container.
1407 //! @return const_reverse_iterator pointing to the beginning
1408 //! of the reversed varray.
1415 const_reverse_iterator crbegin() const { return const_reverse_iterator(this->end()); }
1417 //! @brief Returns reverse iterator to the one after the last element of the reversed container.
1419 //! @return reverse_iterator pointing to the one after the last element
1420 //! of the reversed varray.
1427 reverse_iterator rend() { return reverse_iterator(this->begin()); }
1429 //! @brief Returns const reverse iterator to the one after the last element of the reversed container.
1431 //! @return const_reverse_iterator pointing to the one after the last element
1432 //! of the reversed varray.
1439 const_reverse_iterator rend() const { return const_reverse_iterator(this->begin()); }
1441 //! @brief Returns const reverse iterator to the one after the last element of the reversed container.
1443 //! @return const_reverse_iterator pointing to the one after the last element
1444 //! of the reversed varray.
1451 const_reverse_iterator crend() const { return const_reverse_iterator(this->begin()); }
1453 //! @brief Returns container's capacity.
1455 //! @return container's capacity.
1462 static size_type capacity() { return Capacity; }
1464 //! @brief Returns container's capacity.
1466 //! @return container's capacity.
1473 static size_type max_size() { return Capacity; }
1475 //! @brief Returns the number of stored elements.
1477 //! @return Number of elements contained in the container.
1484 size_type size() const { return m_size; }
1486 //! @brief Queries if the container contains elements.
1488 //! @return true if the number of elements contained in the
1489 //! container is equal to 0.
1496 bool empty() const { return 0 == m_size; }
1504 template <std::size_t C>
1505 void move_ctor_dispatch(varray<value_type, C> & other, boost::true_type /*use_memop*/)
1507 ::memcpy(this->data(), other.data(), sizeof(Value) * other.m_size);
1508 m_size = other.m_size;
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.
1516 template <std::size_t C>
1517 void move_ctor_dispatch(varray<value_type, C> & other, boost::false_type /*use_memop*/)
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;
1528 template <std::size_t C>
1529 void move_assign_dispatch(varray<value_type, C> & other, boost::true_type /*use_memop*/)
1533 ::memcpy(this->data(), other.data(), sizeof(Value) * other.m_size);
1534 std::swap(m_size, other.m_size);
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.
1542 template <std::size_t C>
1543 void move_assign_dispatch(varray<value_type, C> & other, boost::false_type /*use_memop*/)
1545 namespace sv = varray_detail;
1546 if ( m_size <= static_cast<size_type>(other.size()) )
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
1554 sv::move_if_noexcept(other.begin(), other.end(), this->begin()); // may throw
1555 sv::destroy(this->begin() + other.size(), this->end());
1557 m_size = other.size(); // update end
1564 template <std::size_t C>
1565 void swap_dispatch(varray<value_type, C> & other, boost::true_type const& /*use_optimized_swap*/)
1570 aligned_storage_type,
1571 typename varray<value_type, C>::aligned_storage_type
1576 Value * temp_ptr = reinterpret_cast<Value*>(temp.address());
1578 ::memcpy(temp_ptr, this->data(), sizeof(Value) * this->size());
1579 ::memcpy(this->data(), other.data(), sizeof(Value) * other.size());
1580 ::memcpy(other.data(), temp_ptr, sizeof(Value) * this->size());
1582 std::swap(m_size, other.m_size);
1586 // If Value's move constructor or move assignment throws
1587 // but only if use_memop_in_swap_and_move is false_type - default.
1590 template <std::size_t C>
1591 void swap_dispatch(varray<value_type, C> & other, boost::false_type const& /*use_optimized_swap*/)
1593 namespace sv = varray_detail;
1596 vt::use_memop_in_swap_and_move use_memop_in_swap_and_move;
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
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);
1609 void swap_dispatch_impl(iterator first_sm, iterator last_sm, iterator first_la, iterator last_la, boost::true_type const& /*use_memop*/)
1611 //BOOST_GEOMETRY_INDEX_ASSERT(std::distance(first_sm, last_sm) <= std::distance(first_la, last_la),
1612 // "incompatible ranges");
1614 namespace sv = varray_detail;
1615 for (; first_sm != last_sm ; ++first_sm, ++first_la)
1617 boost::aligned_storage<
1619 boost::alignment_of<value_type>::value
1621 value_type * temp_ptr = reinterpret_cast<value_type*>(temp_storage.address());
1623 ::memcpy(temp_ptr, boost::addressof(*first_sm), sizeof(value_type));
1624 ::memcpy(boost::addressof(*first_sm), boost::addressof(*first_la), sizeof(value_type));
1625 ::memcpy(boost::addressof(*first_la), temp_ptr, sizeof(value_type));
1628 ::memcpy(first_sm, first_la, sizeof(value_type) * std::distance(first_la, last_la));
1632 // If Value's move constructor or move assignment throws.
1635 void swap_dispatch_impl(iterator first_sm, iterator last_sm, iterator first_la, iterator last_la, boost::false_type const& /*use_memop*/)
1637 //BOOST_GEOMETRY_INDEX_ASSERT(std::distance(first_sm, last_sm) <= std::distance(first_la, last_la),
1638 // "incompatible ranges");
1640 namespace sv = varray_detail;
1641 for (; first_sm != last_sm ; ++first_sm, ++first_la)
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
1648 sv::uninitialized_move(first_la, last_la, first_sm); // may throw
1649 sv::destroy(first_la, last_la);
1655 // If Value's move constructor, move assignment throws
1656 // or if Value's copy constructor or copy assignment throws.
1659 template <typename Iterator>
1660 void insert_dispatch(iterator position, Iterator first, Iterator last, boost::random_access_traversal_tag const&)
1662 BOOST_CONCEPT_ASSERT((boost_concepts::RandomAccessTraversal<Iterator>)); // Make sure you passed a RandomAccessIterator
1664 errh::check_iterator_end_eq(*this, position);
1666 typename boost::iterator_difference<Iterator>::type
1667 count = std::distance(first, last);
1669 errh::check_capacity(*this, m_size + count); // may throw
1671 if ( position == this->end() )
1673 namespace sv = varray_detail;
1675 sv::uninitialized_copy(first, last, position); // may throw
1676 m_size += count; // update end
1680 this->insert_in_the_middle(position, first, last, count); // may throw
1685 // If Value's move constructor, move assignment throws
1686 // or if Value's copy constructor or copy assignment throws.
1689 template <typename Iterator, typename Traversal>
1690 void insert_dispatch(iterator position, Iterator first, Iterator last, Traversal const& /*not_random_access*/)
1692 errh::check_iterator_end_eq(*this, position);
1694 if ( position == this->end() )
1696 namespace sv = varray_detail;
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
1701 errh::check_capacity(*this, count <= static_cast<std::size_t>(d) ? m_size + count : Capacity + 1); // may throw
1707 typename boost::iterator_difference<Iterator>::type
1708 count = std::distance(first, last);
1710 errh::check_capacity(*this, m_size + count); // may throw
1712 this->insert_in_the_middle(position, first, last, count); // may throw
1717 // If Value's move constructor, move assignment throws
1718 // or if Value's copy constructor or copy assignment throws.
1721 template <typename Iterator>
1722 void insert_in_the_middle(iterator position, Iterator first, Iterator last, difference_type count)
1724 namespace sv = varray_detail;
1726 difference_type to_move = std::distance(position, this->end());
1728 // TODO - should following lines check for exception and revert to the old size?
1730 if ( count < to_move )
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
1739 Iterator middle_iter = first;
1740 std::advance(middle_iter, to_move);
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
1753 // If Value's constructor or assignment taking dereferenced Iterator throws.
1756 template <typename Iterator>
1757 void assign_dispatch(Iterator first, Iterator last, boost::random_access_traversal_tag const& /*not_random_access*/)
1759 namespace sv = varray_detail;
1761 typename boost::iterator_difference<Iterator>::type
1762 s = std::distance(first, last);
1764 errh::check_capacity(*this, s); // may throw
1766 if ( m_size <= static_cast<size_type>(s) )
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
1774 sv::copy(first, last, this->begin()); // may throw
1775 sv::destroy(this->begin() + s, this->end());
1777 m_size = s; // update end
1781 // If Value's constructor or assignment taking dereferenced Iterator throws.
1784 template <typename Iterator, typename Traversal>
1785 void assign_dispatch(Iterator first, Iterator last, Traversal const& /*not_random_access*/)
1787 namespace sv = varray_detail;
1790 iterator it = this->begin();
1792 for ( ; it != this->end() && first != last ; ++it, ++first, ++s )
1793 *it = *first; // may throw
1795 sv::destroy(it, this->end());
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
1801 errh::check_capacity(*this, count <= static_cast<std::size_t>(d) ? s : Capacity + 1); // may throw
1803 m_size = s; // update end
1808 return pointer(static_cast<Value*>(m_storage.address()));
1811 const_pointer ptr() const
1813 return const_pointer(static_cast<const Value*>(m_storage.address()));
1817 aligned_storage_type m_storage;
1820 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1822 template<typename Value>
1823 class varray<Value, 0>
1825 typedef varray_detail::varray_traits<Value, 0> vt;
1826 typedef varray_detail::checker<varray> errh;
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;
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;
1846 explicit varray(size_type count)
1848 errh::check_capacity(*this, count); // may throw
1852 varray(size_type count, value_type const&)
1854 errh::check_capacity(*this, count); // may throw
1858 varray(varray const& /*other*/)
1860 //errh::check_capacity(*this, count);
1864 template <std::size_t C>
1865 varray(varray<value_type, C> const& other)
1867 errh::check_capacity(*this, other.size()); // may throw
1871 template <typename Iterator>
1872 varray(Iterator first, Iterator last)
1874 errh::check_capacity(*this, std::distance(first, last)); // may throw
1878 varray & operator=(varray const& /*other*/)
1880 //errh::check_capacity(*this, other.size());
1886 varray & operator=(varray<value_type, C> const& other)
1888 errh::check_capacity(*this, other.size()); // may throw
1896 void resize(size_type count)
1898 errh::check_capacity(*this, count); // may throw
1902 void resize(size_type count, value_type const&)
1904 errh::check_capacity(*this, count); // may throw
1909 void reserve(size_type count)
1911 errh::check_capacity(*this, count); // may throw
1915 void push_back(value_type const&)
1917 errh::check_capacity(*this, 1); // may throw
1923 errh::check_not_empty(*this);
1927 void insert(iterator position, value_type const&)
1929 errh::check_iterator_end_eq(*this, position);
1930 errh::check_capacity(*this, 1); // may throw
1934 void insert(iterator position, size_type count, value_type const&)
1936 errh::check_iterator_end_eq(*this, position);
1937 errh::check_capacity(*this, count); // may throw
1941 template <typename Iterator>
1942 void insert(iterator, Iterator first, Iterator last)
1944 // TODO - add MPL_ASSERT, check if Iterator is really an iterator
1945 errh::check_capacity(*this, std::distance(first, last)); // may throw
1949 void erase(iterator position)
1951 errh::check_iterator_end_neq(*this, position);
1955 void erase(iterator first, iterator last)
1957 errh::check_iterator_end_eq(*this, first);
1958 errh::check_iterator_end_eq(*this, last);
1960 //BOOST_GEOMETRY_INDEX_ASSERT(0 <= n, "invalid range");
1964 template <typename Iterator>
1965 void assign(Iterator first, Iterator last)
1967 // TODO - add MPL_ASSERT, check if Iterator is really an iterator
1968 errh::check_capacity(*this, std::distance(first, last)); // may throw
1972 void assign(size_type count, value_type const&)
1974 errh::check_capacity(*this, count); // may throw
1981 reference at(size_type i)
1983 errh::throw_out_of_bounds(*this, i); // may throw
1984 return *(this->begin() + i);
1988 const_reference at(size_type i) const
1990 errh::throw_out_of_bounds(*this, i); // may throw
1991 return *(this->begin() + i);
1995 reference operator[](size_type i)
1997 errh::check_index(*this, i);
1998 return *(this->begin() + i);
2002 const_reference operator[](size_type i) const
2004 errh::check_index(*this, i);
2005 return *(this->begin() + i);
2011 errh::check_not_empty(*this);
2012 return *(this->begin());
2016 const_reference front() const
2018 errh::check_not_empty(*this);
2019 return *(this->begin());
2025 errh::check_not_empty(*this);
2026 return *(this->end() - 1);
2030 const_reference back() const
2032 errh::check_not_empty(*this);
2033 return *(this->end() - 1);
2037 Value * data() { return boost::addressof(*(this->ptr())); }
2038 const Value * data() const { return boost::addressof(*(this->ptr())); }
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(); }
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()); }
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; }
2064 return pointer(reinterpret_cast<Value*>(this));
2067 const_pointer ptr() const
2069 return const_pointer(reinterpret_cast<const Value*>(this));
2073 #endif // !BOOST_CONTAINER_DOXYGEN_INVOKED
2075 //! @brief Checks if contents of two varrays are equal.
2077 //! @ingroup varray_non_member
2079 //! @param x The first varray.
2080 //! @param y The second varray.
2082 //! @return \c true if containers have the same size and elements in both containers are equal.
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)
2089 return x.size() == y.size() && std::equal(x.begin(), x.end(), y.begin());
2092 //! @brief Checks if contents of two varrays are not equal.
2094 //! @ingroup varray_non_member
2096 //! @param x The first varray.
2097 //! @param y The second varray.
2099 //! @return \c true if containers have different size or elements in both containers are not equal.
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)
2109 //! @brief Lexicographically compares varrays.
2111 //! @ingroup varray_non_member
2113 //! @param x The first varray.
2114 //! @param y The second varray.
2116 //! @return \c true if x compares lexicographically less than y.
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)
2123 return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
2126 //! @brief Lexicographically compares varrays.
2128 //! @ingroup varray_non_member
2130 //! @param x The first varray.
2131 //! @param y The second varray.
2133 //! @return \c true if y compares lexicographically less than x.
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)
2143 //! @brief Lexicographically compares varrays.
2145 //! @ingroup varray_non_member
2147 //! @param x The first varray.
2148 //! @param y The second varray.
2150 //! @return \c true if y don't compare lexicographically less than x.
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)
2160 //! @brief Lexicographically compares varrays.
2162 //! @ingroup varray_non_member
2164 //! @param x The first varray.
2165 //! @param y The second varray.
2167 //! @return \c true if x don't compare lexicographically less than y.
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)
2177 //! @brief Swaps contents of two varrays.
2179 //! This function calls varray::swap().
2181 //! @ingroup varray_non_member
2183 //! @param x The first varray.
2184 //! @param y The second varray.
2188 template<typename V, std::size_t C1, std::size_t C2>
2189 inline void swap(varray<V, C1> & x, varray<V, C2> & y)
2194 }}}} // namespace boost::geometry::index::detail
2196 // TODO - REMOVE/CHANGE
2197 #include <boost/container/detail/config_end.hpp>
2199 #endif // BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_HPP