1 // Boost.Container varray
3 // Copyright (c) 2012-2013 Adam Wulkiewicz, Lodz, Poland.
4 // Copyright (c) 2011-2013 Andrew Hundt.
5 // Copyright (c) 2014-2014 Ion Gaztanaga
7 // Use, modification and distribution is subject to the Boost Software License,
8 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
11 #ifndef BOOST_CONTAINER_DETAIL_VARRAY_HPP
12 #define BOOST_CONTAINER_DETAIL_VARRAY_HPP
14 #ifndef BOOST_CONFIG_HPP
15 # include <boost/config.hpp>
18 #if defined(BOOST_HAS_PRAGMA_ONCE)
22 #include <boost/container/detail/config_begin.hpp>
23 #include <boost/container/detail/workaround.hpp>
25 #include <boost/container/detail/addressof.hpp>
26 #include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare
27 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
28 #include <boost/move/detail/fwd_macros.hpp>
30 #include <boost/container/detail/iterator.hpp>
31 #include <boost/container/detail/iterators.hpp>
32 #include <boost/container/detail/mpl.hpp>
33 #include <boost/container/detail/type_traits.hpp>
34 #include <boost/move/adl_move_swap.hpp> //adl_move_swap
37 #include "varray_util.hpp"
39 #include <boost/assert.hpp>
40 #include <boost/config.hpp>
42 #include <boost/static_assert.hpp>
44 #ifndef BOOST_NO_EXCEPTIONS
46 #endif // BOOST_NO_EXCEPTIONS
50 * @defgroup varray_non_member varray non-member functions
53 namespace boost { namespace container { namespace dtl {
55 // Forward declaration
56 template <typename Value, std::size_t Capacity, typename Strategy>
61 // TODO: Improve error messages
62 // possibly include N in the strategy, and provide size as an optoinal allocate_failed parameter?
63 // Example of current error with reserve(4) when capacity is 3:
64 // "boost/container/varray.hpp(66): size can't exceed the capacity"
66 // "cannot reserve(4) due to fixed capacity of 3 elements"
68 //! @brief The default strategy.
70 //! @tparam Value Type of element stored in the container.
71 template <typename Value>
74 typedef Value value_type;
75 typedef std::size_t size_type;
76 typedef std::ptrdiff_t difference_type;
77 typedef Value* pointer;
78 typedef const Value* const_pointer;
79 typedef Value& reference;
80 typedef const Value& const_reference;
82 static void allocate_failed()
84 BOOST_ASSERT_MSG(false, "size can't exceed the capacity");
88 //! @brief The strategy adapting info from passed Allocator.
90 //! This strategy defines the same types that are defined in the Allocator.
92 //! @tparam Allocator The Allocator which will be adapted.
93 template <typename Allocator>
94 struct allocator_adaptor
96 typedef typename Allocator::value_type value_type;
97 typedef typename Allocator::size_type size_type;
98 typedef typename Allocator::difference_type difference_type;
99 typedef typename Allocator::pointer pointer;
100 typedef typename Allocator::const_pointer const_pointer;
101 typedef typename Allocator::reference reference;
102 typedef typename Allocator::const_reference const_reference;
104 static void allocate_failed()
106 BOOST_ASSERT_MSG(false, "size can't exceed the capacity");
110 } // namespace strategy
112 struct varray_error_handler
114 template <typename V, std::size_t Capacity, typename S>
115 static void check_capacity(varray<V, Capacity, S> const&, std::size_t s)
118 S::allocate_failed();
121 template <typename V, std::size_t C, typename S>
122 static void check_at(varray<V, C, S> const& v,
123 typename varray<V, C, S>::size_type i)
127 // TODO - use BOOST_THROW_EXCEPTION here?
128 #ifndef BOOST_NO_EXCEPTIONS
130 throw std::out_of_range("index out of bounds");
131 #else // BOOST_NO_EXCEPTIONS
132 BOOST_ASSERT_MSG(i < v.size(), "index out of bounds");
133 #endif // BOOST_NO_EXCEPTIONS
136 template <typename V, std::size_t C, typename S>
137 static void check_operator_brackets(varray<V, C, S> const& v,
138 typename varray<V, C, S>::size_type i)
142 BOOST_ASSERT_MSG(i < v.size(), "index out of bounds");
145 template <typename V, std::size_t C, typename S>
146 static void check_empty(varray<V, C, S> const& v)
149 BOOST_ASSERT_MSG(0 < v.size(), "the container is empty");
152 template <typename V, std::size_t C, typename S>
153 static void check_iterator_end_neq(varray<V, C, S> const& v,
154 typename varray<V, C, S>::const_iterator position)
158 BOOST_ASSERT_MSG(v.begin() <= position && position < v.end(), "iterator out of bounds");
161 template <typename V, std::size_t C, typename S>
162 static void check_iterator_end_eq(varray<V, C, S> const& v,
163 typename varray<V, C, S>::const_iterator position)
167 BOOST_ASSERT_MSG(v.begin() <= position && position <= v.end(), "iterator out of bounds");
171 template <typename Value, std::size_t Capacity, typename Strategy>
174 typedef typename Strategy::value_type value_type;
175 typedef typename Strategy::size_type size_type;
176 typedef typename Strategy::difference_type difference_type;
177 typedef typename Strategy::pointer pointer;
178 typedef typename Strategy::const_pointer const_pointer;
179 typedef typename Strategy::reference reference;
180 typedef typename Strategy::const_reference const_reference;
182 typedef varray_error_handler error_handler;
184 typedef false_type use_memop_in_swap_and_move;
185 typedef false_type use_optimized_swap;
186 typedef false_type disable_trivial_init;
190 * @brief A variable-size array container with fixed capacity.
192 * varray is a sequence container like boost::container::vector with contiguous storage that can
193 * change in size, along with the static allocation, low overhead, and fixed capacity of boost::array.
195 * A varray is a sequence that supports random access to elements, constant time insertion and
196 * removal of elements at the end, and linear time insertion and removal of elements at the beginning or
197 * in the middle. The number of elements in a varray may vary dynamically up to a fixed capacity
198 * because elements are stored within the object itself similarly to an array. However, objects are
199 * initialized as they are inserted into varray unlike C arrays or std::array which must construct
200 * all elements on instantiation. The behavior of varray enables the use of statically allocated
201 * elements in cases with complex object lifetime requirements that would otherwise not be trivially
204 * @par Error Handling
205 * Insertion beyond the capacity and out of bounds errors result in undefined behavior unless
206 * otherwise specified. In this respect if size() == capacity(), then varray::push_back()
207 * behaves like std::vector pop_front() if size() == empty(). The reason for this difference
208 * is because unlike vectors, varray does not perform allocation.
210 * @par Advanced Usage
211 * Error handling behavior can be modified to more closely match std::vector exception behavior
212 * when exceeding bounds by providing an alternate Strategy and varray_traits instantiation.
214 * @tparam Value The type of element that will be stored.
215 * @tparam Capacity The maximum number of elements varray can store, fixed at compile time.
216 * @tparam Strategy Defines the public typedefs and error handlers,
217 * implements StaticVectorStrategy and has some similarities
220 template <typename Value, std::size_t Capacity, typename Strategy = strategy::def<Value> >
223 typedef dtl::varray_traits<
224 Value, Capacity, Strategy
227 typedef typename vt::error_handler errh;
228 typedef typename aligned_storage<
229 sizeof(Value[Capacity]),
230 boost::container::dtl::alignment_of<Value[Capacity]>::value
231 >::type aligned_storage_type;
233 template <typename V, std::size_t C, typename S>
236 BOOST_COPYABLE_AND_MOVABLE(varray)
238 #ifdef BOOST_NO_CXX11_RVALUE_REFERENCES
240 template <std::size_t C, typename S>
241 varray & operator=(varray<Value, C, S> & sv)
243 typedef varray<Value, C, S> other;
244 this->operator=(static_cast<const ::boost::rv<other> &>(const_cast<const other &>(sv)));
250 //! @brief The type of elements stored in the container.
251 typedef typename vt::value_type value_type;
252 //! @brief The unsigned integral type used by the container.
253 typedef typename vt::size_type size_type;
254 //! @brief The pointers difference type.
255 typedef typename vt::difference_type difference_type;
256 //! @brief The pointer type.
257 typedef typename vt::pointer pointer;
258 //! @brief The const pointer type.
259 typedef typename vt::const_pointer const_pointer;
260 //! @brief The value reference type.
261 typedef typename vt::reference reference;
262 //! @brief The value const reference type.
263 typedef typename vt::const_reference const_reference;
265 //! @brief The iterator type.
266 typedef pointer iterator;
267 //! @brief The const iterator type.
268 typedef const_pointer const_iterator;
269 //! @brief The reverse iterator type.
270 typedef boost::container::reverse_iterator<iterator> reverse_iterator;
271 //! @brief The const reverse iterator.
272 typedef boost::container::reverse_iterator<const_iterator> const_reverse_iterator;
274 //! @brief The type of a strategy used by the varray.
275 typedef Strategy strategy_type;
277 //! @brief Constructs an empty varray.
288 //! @pre <tt>count <= capacity()</tt>
290 //! @brief Constructs a varray containing count value initialized Values.
292 //! @param count The number of values which will be contained in the container.
295 //! If Value's value initialization throws.
297 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
302 explicit varray(size_type count)
305 this->resize(count); // may throw
308 //! @pre <tt>count <= capacity()</tt>
310 //! @brief Constructs a varray containing count copies of value.
312 //! @param count The number of copies of a values that will be contained in the container.
313 //! @param value The value which will be used to copy construct values.
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 varray(size_type count, value_type const& value)
326 this->resize(count, value); // may throw
330 //! @li <tt>distance(first, last) <= capacity()</tt>
331 //! @li Iterator must meet the \c ForwardIterator.
333 //! @brief Constructs a varray containing copy of a range <tt>[first, last)</tt>.
335 //! @param first The iterator to the first element in range.
336 //! @param last The iterator to the one after the last element in range.
339 //! If Value's constructor taking a dereferenced Iterator throws.
341 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
346 template <typename Iterator>
347 varray(Iterator first, Iterator last)
350 this->assign(first, last); // may throw
353 //! @brief Constructs a copy of other varray.
355 //! @param other The varray which content will be copied to this one.
358 //! If Value's copy constructor throws.
362 varray(varray const& other)
363 : m_size(other.size())
365 namespace sv = varray_detail;
366 sv::uninitialized_copy(other.begin(), other.end(), this->begin()); // may throw
369 //! @pre <tt>other.size() <= capacity()</tt>.
371 //! @brief Constructs a copy of other varray.
373 //! @param other The varray which content will be copied to this one.
376 //! If Value's copy constructor throws.
378 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
383 template <std::size_t C, typename S>
384 varray(varray<value_type, C, S> const& other)
385 : m_size(other.size())
387 errh::check_capacity(*this, other.size()); // may throw
389 namespace sv = varray_detail;
390 sv::uninitialized_copy(other.begin(), other.end(), this->begin()); // may throw
393 //! @brief Copy assigns Values stored in the other varray to this one.
395 //! @param other The varray which content will be copied to this one.
398 //! If Value's copy constructor or copy assignment throws.
402 varray & operator=(BOOST_COPY_ASSIGN_REF(varray) other)
404 this->assign(other.begin(), other.end()); // may throw
409 //! @pre <tt>other.size() <= capacity()</tt>
411 //! @brief Copy assigns Values stored in the other varray to this one.
413 //! @param other The varray which content will be copied to this one.
416 //! If Value's copy constructor or copy assignment throws.
418 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
423 template <std::size_t C, typename S>
424 // TEMPORARY WORKAROUND
425 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
426 varray & operator=(::boost::rv< varray<value_type, C, S> > const& other)
428 varray & operator=(varray<value_type, C, S> const& other)
431 this->assign(other.begin(), other.end()); // may throw
436 //! @brief Move constructor. Moves Values stored in the other varray to this one.
438 //! @param other The varray which content will be moved to this one.
441 //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor throws.
442 //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor throws.
444 //! @li It throws only if \c use_memop_in_swap_and_move is \c false_type - default.
449 varray(BOOST_RV_REF(varray) other)
452 vt::use_memop_in_swap_and_move use_memop_in_swap_and_move;
454 this->move_ctor_dispatch(other, use_memop_in_swap_and_move());
457 //! @pre <tt>other.size() <= capacity()</tt>
459 //! @brief Move constructor. Moves Values stored in the other varray to this one.
461 //! @param other The varray which content will be moved to this one.
464 //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor throws.
465 //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor throws.
467 //! @li It throws only if \c use_memop_in_swap_and_move is false_type - default.
470 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
475 template <std::size_t C, typename S>
476 varray(BOOST_RV_REF_3_TEMPL_ARGS(varray, value_type, C, S) other)
477 : m_size(other.m_size)
479 errh::check_capacity(*this, other.size()); // may throw
482 vt::use_memop_in_swap_and_move use_memop_in_swap_and_move;
484 this->move_ctor_dispatch(other, use_memop_in_swap_and_move());
487 //! @brief Move assignment. Moves Values stored in the other varray to this one.
489 //! @param other The varray which content will be moved to this one.
492 //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor or move assignment throws.
493 //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor or copy assignment throws.
495 //! @li It throws only if \c use_memop_in_swap_and_move is \c false_type - default.
500 varray & operator=(BOOST_RV_REF(varray) other)
502 if ( &other == this )
506 vt::use_memop_in_swap_and_move use_memop_in_swap_and_move;
508 this->move_assign_dispatch(other, use_memop_in_swap_and_move());
513 //! @pre <tt>other.size() <= capacity()</tt>
515 //! @brief Move assignment. Moves Values stored in the other varray to this one.
517 //! @param other The varray which content will be moved to this one.
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 is \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, typename S>
532 varray & operator=(BOOST_RV_REF_3_TEMPL_ARGS(varray, value_type, C, S) other)
534 errh::check_capacity(*this, other.size()); // may throw
537 vt::use_memop_in_swap_and_move use_memop_in_swap_and_move;
539 this->move_assign_dispatch(other, use_memop_in_swap_and_move());
544 //! @brief Destructor. Destroys Values stored in this container.
553 namespace sv = varray_detail;
554 sv::destroy(this->begin(), this->end());
557 //! @brief Swaps contents of the other varray and this one.
559 //! @param other The varray which content will be swapped with this one's content.
562 //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor or move assignment throws,
563 //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor or copy assignment throws,
565 //! @li It throws only if \c use_memop_in_swap_and_move and \c use_optimized_swap are \c false_type - default.
570 void swap(varray & other)
573 vt::use_optimized_swap use_optimized_swap;
575 this->swap_dispatch(other, use_optimized_swap());
578 //! @pre <tt>other.size() <= capacity() && size() <= other.capacity()</tt>
580 //! @brief Swaps contents of the other varray and this one.
582 //! @param other The varray which content will be swapped with this one's content.
585 //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor or move assignment throws,
586 //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor or copy assignment throws,
588 //! @li It throws only if \c use_memop_in_swap_and_move and \c use_optimized_swap are \c false_type - default.
591 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
596 template <std::size_t C, typename S>
597 void swap(varray<value_type, C, S> & other)
599 errh::check_capacity(*this, other.size());
600 errh::check_capacity(other, this->size());
603 vt::use_optimized_swap use_optimized_swap;
605 this->swap_dispatch(other, use_optimized_swap());
608 //! @pre <tt>count <= capacity()</tt>
610 //! @brief Inserts or erases elements at the end such that
611 //! the size becomes count. New elements are value initialized.
613 //! @param count The number of elements which will be stored in the container.
616 //! If Value's value initialization throws.
618 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
623 void resize(size_type count)
625 namespace sv = varray_detail;
626 typedef typename vt::disable_trivial_init dti;
628 if ( count < m_size )
630 sv::destroy(this->begin() + count, this->end());
634 errh::check_capacity(*this, count); // may throw
636 sv::uninitialized_fill(this->end(), this->begin() + count, dti()); // may throw
638 m_size = count; // update end
641 //! @pre <tt>count <= capacity()</tt>
643 //! @brief Inserts or erases elements at the end such that
644 //! the size becomes count. New elements are copy constructed from value.
646 //! @param count The number of elements which will be stored in the container.
647 //! @param value The value used to copy construct the new element.
650 //! If Value's copy constructor throws.
652 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
657 void resize(size_type count, value_type const& value)
659 if ( count < m_size )
661 namespace sv = varray_detail;
662 sv::destroy(this->begin() + count, this->end());
666 errh::check_capacity(*this, count); // may throw
668 std::uninitialized_fill(this->end(), this->begin() + count, value); // may throw
670 m_size = count; // update end
673 //! @pre <tt>count <= capacity()</tt>
675 //! @brief This call has no effect because the Capacity of this container is constant.
677 //! @param count The number of elements which the container should be able to contain.
682 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
687 void reserve(size_type count)
689 errh::check_capacity(*this, count); // may throw
692 //! @pre <tt>size() < capacity()</tt>
694 //! @brief Adds a copy of value at the end.
696 //! @param value The value used to copy construct the new element.
699 //! If Value's copy constructor throws.
701 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
706 void push_back(value_type const& value)
708 typedef typename vt::disable_trivial_init dti;
710 errh::check_capacity(*this, m_size + 1); // may throw
712 namespace sv = varray_detail;
713 sv::construct(dti(), this->end(), value); // may throw
714 ++m_size; // update end
717 //! @pre <tt>size() < capacity()</tt>
719 //! @brief Moves value to the end.
721 //! @param value The value to move construct the new element.
724 //! If Value's move constructor throws.
726 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
731 void push_back(BOOST_RV_REF(value_type) value)
733 typedef typename vt::disable_trivial_init dti;
735 errh::check_capacity(*this, m_size + 1); // may throw
737 namespace sv = varray_detail;
738 sv::construct(dti(), this->end(), ::boost::move(value)); // may throw
739 ++m_size; // update end
742 //! @pre <tt>!empty()</tt>
744 //! @brief Destroys last value and decreases the size.
747 //! Nothing by default.
753 errh::check_empty(*this);
755 namespace sv = varray_detail;
756 sv::destroy(this->end() - 1);
757 --m_size; // update end
761 //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>.
762 //! @li <tt>size() < capacity()</tt>
764 //! @brief Inserts a copy of element at position.
766 //! @param position The position at which the new value will be inserted.
767 //! @param value The value used to copy construct the new element.
770 //! @li If Value's copy constructor or copy assignment throws
771 //! @li If Value's move constructor or move assignment throws.
773 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
777 //! Constant or linear.
778 iterator insert(iterator position, value_type const& value)
780 return this->priv_insert(position, value);
784 //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>.
785 //! @li <tt>size() < capacity()</tt>
787 //! @brief Inserts a move-constructed element at position.
789 //! @param position The position at which the new value will be inserted.
790 //! @param value The value used to move construct the new element.
793 //! If Value's move constructor or move assignment throws.
795 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
799 //! Constant or linear.
800 iterator insert(iterator position, BOOST_RV_REF(value_type) value)
802 return this->priv_insert(position, boost::move(value));
806 //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>.
807 //! @li <tt>size() + count <= capacity()</tt>
809 //! @brief Inserts a count copies of value at position.
811 //! @param position The position at which new elements will be inserted.
812 //! @param count The number of new elements which will be inserted.
813 //! @param value The value used to copy construct new elements.
816 //! @li If Value's copy constructor or copy assignment throws.
817 //! @li If Value's move constructor or move assignment throws.
819 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
824 iterator insert(iterator position, size_type count, value_type const& value)
826 errh::check_iterator_end_eq(*this, position);
827 errh::check_capacity(*this, m_size + count); // may throw
829 if ( position == this->end() )
831 std::uninitialized_fill(position, position + count, value); // may throw
832 m_size += count; // update end
836 namespace sv = varray_detail;
838 difference_type to_move = boost::container::iterator_distance(position, this->end());
840 // TODO - should following lines check for exception and revert to the old size?
842 if ( count < static_cast<size_type>(to_move) )
844 sv::uninitialized_move(this->end() - count, this->end(), this->end()); // may throw
845 m_size += count; // update end
846 sv::move_backward(position, position + to_move - count, this->end() - count); // may throw
847 std::fill_n(position, count, value); // may throw
851 std::uninitialized_fill(this->end(), position + count, value); // may throw
852 m_size += count - to_move; // update end
853 sv::uninitialized_move(position, position + to_move, position + count); // may throw
854 m_size += to_move; // update end
855 std::fill_n(position, to_move, value); // may throw
863 //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>.
864 //! @li <tt>distance(first, last) <= capacity()</tt>
865 //! @li \c Iterator must meet the \c ForwardIterator.
867 //! @brief Inserts a copy of a range <tt>[first, last)</tt> at position.
869 //! @param position The position at which new elements will be inserted.
870 //! @param first The iterator to the first element of a range used to construct new elements.
871 //! @param last The iterator to the one after the last element of a range used to construct new elements.
874 //! @li If Value's constructor and assignment taking a dereferenced \c Iterator.
875 //! @li If Value's move constructor or move assignment throws.
877 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
882 template <typename Iterator>
883 iterator insert(iterator position, Iterator first, Iterator last)
885 this->insert_dispatch(position, first, last);
889 //! @pre \c position must be a valid iterator of \c *this in range <tt>[begin(), end())</tt>
891 //! @brief Erases Value from position.
893 //! @param position The position of the element which will be erased from the container.
896 //! If Value's move assignment throws.
900 iterator erase(iterator position)
902 namespace sv = varray_detail;
904 errh::check_iterator_end_neq(*this, position);
906 //TODO - add empty check?
907 //errh::check_empty(*this);
909 sv::move(position + 1, this->end(), position); // may throw
910 sv::destroy(this->end() - 1);
917 //! @li \c first and \c last must define a valid range
918 //! @li iterators must be in range <tt>[begin(), end()]</tt>
920 //! @brief Erases Values from a range <tt>[first, last)</tt>.
922 //! @param first The position of the first element of a range which will be erased from the container.
923 //! @param last The position of the one after the last element of a range which will be erased from the container.
926 //! If Value's move assignment throws.
930 iterator erase(iterator first, iterator last)
932 namespace sv = varray_detail;
934 errh::check_iterator_end_eq(*this, first);
935 errh::check_iterator_end_eq(*this, last);
937 difference_type n = boost::container::iterator_distance(first, last);
939 //TODO - add invalid range check?
940 //BOOST_ASSERT_MSG(0 <= n, "invalid range");
941 //TODO - add this->size() check?
942 //BOOST_ASSERT_MSG(n <= this->size(), "invalid range");
944 sv::move(last, this->end(), first); // may throw
945 sv::destroy(this->end() - n, this->end());
951 //! @pre <tt>distance(first, last) <= capacity()</tt>
953 //! @brief Assigns a range <tt>[first, last)</tt> of Values to this container.
955 //! @param first The iterator to the first element of a range used to construct new content of this container.
956 //! @param last The iterator to the one after the last element of a range used to construct new content of this container.
959 //! If Value's copy constructor or copy assignment throws,
963 template <typename Iterator>
964 void assign(Iterator first, Iterator last)
966 this->assign_dispatch(first, last); // may throw
969 //! @pre <tt>count <= capacity()</tt>
971 //! @brief Assigns a count copies of value to this container.
973 //! @param count The new number of elements which will be container in the container.
974 //! @param value The value which will be used to copy construct the new content.
977 //! If Value's copy constructor or copy assignment throws.
981 void assign(size_type count, value_type const& value)
983 if ( count < m_size )
985 namespace sv = varray_detail;
987 std::fill_n(this->begin(), count, value); // may throw
988 sv::destroy(this->begin() + count, this->end());
992 errh::check_capacity(*this, count); // may throw
994 std::fill_n(this->begin(), m_size, value); // may throw
995 std::uninitialized_fill(this->end(), this->begin() + count, value); // may throw
997 m_size = count; // update end
1000 #if !defined(BOOST_CONTAINER_VARRAY_DISABLE_EMPLACE)
1001 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1002 //! @pre <tt>size() < capacity()</tt>
1004 //! @brief Inserts a Value constructed with
1005 //! \c std::forward<Args>(args)... in the end of the container.
1007 //! @param args The arguments of the constructor of the new element which will be created at the end of the container.
1010 //! If in-place constructor throws or Value's move constructor throws.
1012 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
1017 template<class ...Args>
1018 void emplace_back(BOOST_FWD_REF(Args) ...args)
1020 typedef typename vt::disable_trivial_init dti;
1022 errh::check_capacity(*this, m_size + 1); // may throw
1024 namespace sv = varray_detail;
1025 sv::construct(dti(), this->end(), ::boost::forward<Args>(args)...); // may throw
1026 ++m_size; // update end
1030 //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>
1031 //! @li <tt>size() < capacity()</tt>
1033 //! @brief Inserts a Value constructed with
1034 //! \c std::forward<Args>(args)... before position
1036 //! @param position The position at which new elements will be inserted.
1037 //! @param args The arguments of the constructor of the new element.
1040 //! If in-place constructor throws or if Value's move constructor or move assignment throws.
1042 //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
1046 //! Constant or linear.
1047 template<class ...Args>
1048 iterator emplace(iterator position, BOOST_FWD_REF(Args) ...args)
1050 typedef typename vt::disable_trivial_init dti;
1052 namespace sv = varray_detail;
1054 errh::check_iterator_end_eq(*this, position);
1055 errh::check_capacity(*this, m_size + 1); // may throw
1057 if ( position == this->end() )
1059 sv::construct(dti(), position, ::boost::forward<Args>(args)...); // may throw
1060 ++m_size; // update end
1064 // TODO - should following lines check for exception and revert to the old size?
1066 // TODO - should move be used only if it's nonthrowing?
1067 value_type & r = *(this->end() - 1);
1068 sv::construct(dti(), this->end(), boost::move(r)); // may throw
1069 ++m_size; // update end
1070 sv::move_backward(position, this->end() - 2, this->end() - 1); // may throw
1072 typename aligned_storage
1073 <sizeof(value_type), alignment_of<value_type>::value>::type temp_storage;
1074 value_type * val_p = static_cast<value_type*>(static_cast<void*>(&temp_storage));
1075 sv::construct(dti(), val_p, ::boost::forward<Args>(args)...); // may throw
1076 sv::scoped_destructor<value_type> d(val_p);
1077 sv::assign(position, ::boost::move(*val_p)); // may throw
1083 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || BOOST_CONTAINER_DOXYGEN_INVOKED
1085 #define BOOST_CONTAINER_VARRAY_EMPLACE_CODE(N) \
1086 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1087 void emplace_back(BOOST_MOVE_UREF##N)\
1089 typedef typename vt::disable_trivial_init dti;\
1090 errh::check_capacity(*this, m_size + 1);/*may throw*/\
1092 namespace sv = varray_detail;\
1093 sv::construct(dti(), this->end() BOOST_MOVE_I##N BOOST_MOVE_FWD##N ); /*may throw*/\
1094 ++m_size; /*update end*/\
1097 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1098 iterator emplace(iterator position BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1100 typedef typename vt::disable_trivial_init dti;\
1101 namespace sv = varray_detail;\
1102 errh::check_iterator_end_eq(*this, position);\
1103 errh::check_capacity(*this, m_size + 1); /*may throw*/\
1104 if ( position == this->end() ){\
1105 sv::construct(dti(), position BOOST_MOVE_I##N BOOST_MOVE_FWD##N ); /*may throw*/\
1106 ++m_size; /*update end*/\
1109 /* TODO - should following lines check for exception and revert to the old size? */\
1110 /* TODO - should move be used only if it's nonthrowing? */\
1111 value_type & r = *(this->end() - 1);\
1112 sv::construct(dti(), this->end(), boost::move(r));/*may throw*/\
1113 ++m_size; /*update end*/\
1114 sv::move_backward(position, this->end() - 2, this->end() - 1);/*may throw*/\
1115 typename aligned_storage\
1116 <sizeof(value_type), alignment_of<value_type>::value>::type temp_storage;\
1117 value_type * val_p = static_cast<value_type*>(static_cast<void*>(&temp_storage));\
1118 sv::construct(dti(), val_p BOOST_MOVE_I##N BOOST_MOVE_FWD##N ); /*may throw*/\
1119 sv::scoped_destructor<value_type> d(val_p);\
1120 sv::assign(position, ::boost::move(*val_p));/*may throw*/\
1124 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_VARRAY_EMPLACE_CODE)
1125 #undef BOOST_CONTAINER_VARRAY_EMPLACE_CODE
1127 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || BOOST_CONTAINER_DOXYGEN_INVOKED
1128 #endif // !BOOST_CONTAINER_VARRAY_DISABLE_EMPLACE
1130 //! @brief Removes all elements from the container.
1139 namespace sv = varray_detail;
1140 sv::destroy(this->begin(), this->end());
1141 m_size = 0; // update end
1144 //! @pre <tt>i < size()</tt>
1146 //! @brief Returns reference to the i-th element.
1148 //! @param i The element's index.
1150 //! @return reference to the i-th element
1151 //! from the beginning of the container.
1154 //! \c std::out_of_range exception by default.
1158 reference at(size_type i)
1160 errh::check_at(*this, i); // may throw
1161 return *(this->begin() + i);
1164 //! @pre <tt>i < size()</tt>
1166 //! @brief Returns const reference to the i-th element.
1168 //! @param i The element's index.
1170 //! @return const reference to the i-th element
1171 //! from the beginning of the container.
1174 //! \c std::out_of_range exception by default.
1178 const_reference at(size_type i) const
1180 errh::check_at(*this, i); // may throw
1181 return *(this->begin() + i);
1184 //! @pre <tt>i < size()</tt>
1186 //! @brief Returns reference to the i-th element.
1188 //! @param i The element's index.
1190 //! @return reference to the i-th element
1191 //! from the beginning of the container.
1194 //! Nothing by default.
1198 reference operator[](size_type i)
1200 // TODO: Remove bounds check? std::vector and std::array operator[] don't check.
1201 errh::check_operator_brackets(*this, i);
1202 return *(this->begin() + i);
1205 //! @pre <tt>i < size()</tt>
1207 //! @brief Returns const reference to the i-th element.
1209 //! @param i The element's index.
1211 //! @return const reference to the i-th element
1212 //! from the beginning of the container.
1215 //! Nothing by default.
1219 const_reference operator[](size_type i) const
1221 errh::check_operator_brackets(*this, i);
1222 return *(this->begin() + i);
1225 //! @pre \c !empty()
1227 //! @brief Returns reference to the first element.
1229 //! @return reference to the first element
1230 //! from the beginning of the container.
1233 //! Nothing by default.
1239 errh::check_empty(*this);
1240 return *(this->begin());
1243 //! @pre \c !empty()
1245 //! @brief Returns const reference to the first element.
1247 //! @return const reference to the first element
1248 //! from the beginning of the container.
1251 //! Nothing by default.
1255 const_reference front() const
1257 errh::check_empty(*this);
1258 return *(this->begin());
1261 //! @pre \c !empty()
1263 //! @brief Returns reference to the last element.
1265 //! @return reference to the last element
1266 //! from the beginning of the container.
1269 //! Nothing by default.
1275 errh::check_empty(*this);
1276 return *(this->end() - 1);
1279 //! @pre \c !empty()
1281 //! @brief Returns const reference to the first element.
1283 //! @return const reference to the last element
1284 //! from the beginning of the container.
1287 //! Nothing by default.
1291 const_reference back() const
1293 errh::check_empty(*this);
1294 return *(this->end() - 1);
1297 //! @brief Pointer such that <tt>[data(), data() + size())</tt> is a valid range.
1298 //! For a non-empty vector <tt>data() == &front()</tt>.
1307 return (addressof)(*(this->ptr()));
1310 //! @brief Const pointer such that <tt>[data(), data() + size())</tt> is a valid range.
1311 //! For a non-empty vector <tt>data() == &front()</tt>.
1318 const Value * data() const
1320 return (addressof)(*(this->ptr()));
1324 //! @brief Returns iterator to the first element.
1326 //! @return iterator to the first element contained in the vector.
1333 iterator begin() { return this->ptr(); }
1335 //! @brief Returns const iterator to the first element.
1337 //! @return const_iterator to the first element contained in the vector.
1344 const_iterator begin() const { return this->ptr(); }
1346 //! @brief Returns const iterator to the first element.
1348 //! @return const_iterator to the first element contained in the vector.
1355 const_iterator cbegin() const { return this->ptr(); }
1357 //! @brief Returns iterator to the one after the last element.
1359 //! @return iterator pointing to the one after the last element contained in the vector.
1366 iterator end() { return this->begin() + m_size; }
1368 //! @brief Returns const iterator to the one after the last element.
1370 //! @return const_iterator pointing to the one after the last element contained in the vector.
1377 const_iterator end() const { return this->begin() + m_size; }
1379 //! @brief Returns const iterator to the one after the last element.
1381 //! @return const_iterator pointing to the one after the last element contained in the vector.
1388 const_iterator cend() const { return this->cbegin() + m_size; }
1390 //! @brief Returns reverse iterator to the first element of the reversed container.
1392 //! @return reverse_iterator pointing to the beginning
1393 //! of the reversed varray.
1400 reverse_iterator rbegin() { return reverse_iterator(this->end()); }
1402 //! @brief Returns const reverse iterator to the first element of the reversed container.
1404 //! @return const_reverse_iterator pointing to the beginning
1405 //! of the reversed varray.
1412 const_reverse_iterator rbegin() const { return reverse_iterator(this->end()); }
1414 //! @brief Returns const reverse iterator to the first element of the reversed container.
1416 //! @return const_reverse_iterator pointing to the beginning
1417 //! of the reversed varray.
1424 const_reverse_iterator crbegin() const { return reverse_iterator(this->end()); }
1426 //! @brief Returns reverse iterator to the one after the last element of the reversed container.
1428 //! @return reverse_iterator pointing to the one after the last element
1429 //! of the reversed varray.
1436 reverse_iterator rend() { return reverse_iterator(this->begin()); }
1438 //! @brief Returns const reverse iterator to the one after the last element of the reversed container.
1440 //! @return const_reverse_iterator pointing to the one after the last element
1441 //! of the reversed varray.
1448 const_reverse_iterator rend() const { return reverse_iterator(this->begin()); }
1450 //! @brief Returns const reverse iterator to the one after the last element of the reversed container.
1452 //! @return const_reverse_iterator pointing to the one after the last element
1453 //! of the reversed varray.
1460 const_reverse_iterator crend() const { return reverse_iterator(this->begin()); }
1462 //! @brief Returns container's capacity.
1464 //! @return container's capacity.
1471 static size_type capacity() { return Capacity; }
1473 //! @brief Returns container's capacity.
1475 //! @return container's capacity.
1482 static size_type max_size() { return Capacity; }
1484 //! @brief Returns the number of stored elements.
1486 //! @return Number of elements contained in the container.
1493 size_type size() const { return m_size; }
1495 //! @brief Queries if the container contains elements.
1497 //! @return true if the number of elements contained in the
1498 //! container is equal to 0.
1505 bool empty() const { return 0 == m_size; }
1513 template <std::size_t C, typename S>
1514 void move_ctor_dispatch(varray<value_type, C, S> & other, true_type /*use_memop*/)
1516 ::memcpy(this->data(), other.data(), sizeof(Value) * other.m_size);
1517 m_size = other.m_size;
1521 // @li If boost::has_nothrow_move<Value>::value is true and Value's move constructor throws
1522 // @li If boost::has_nothrow_move<Value>::value is false and Value's copy constructor throws.
1525 template <std::size_t C, typename S>
1526 void move_ctor_dispatch(varray<value_type, C, S> & other, false_type /*use_memop*/)
1528 namespace sv = varray_detail;
1529 sv::uninitialized_move_if_noexcept(other.begin(), other.end(), this->begin()); // may throw
1530 m_size = other.m_size;
1537 template <std::size_t C, typename S>
1538 void move_assign_dispatch(varray<value_type, C, S> & other, true_type /*use_memop*/)
1542 ::memcpy(this->data(), other.data(), sizeof(Value) * other.m_size);
1543 boost::adl_move_swap(m_size, other.m_size);
1547 // @li If boost::has_nothrow_move<Value>::value is true and Value's move constructor or move assignment throws
1548 // @li If boost::has_nothrow_move<Value>::value is false and Value's copy constructor or move assignment throws.
1551 template <std::size_t C, typename S>
1552 void move_assign_dispatch(varray<value_type, C, S> & other, false_type /*use_memop*/)
1554 namespace sv = varray_detail;
1555 if ( m_size <= static_cast<size_type>(other.size()) )
1557 sv::move_if_noexcept(other.begin(), other.begin() + m_size, this->begin()); // may throw
1558 // TODO - perform uninitialized_copy first?
1559 sv::uninitialized_move_if_noexcept(other.begin() + m_size, other.end(), this->end()); // may throw
1563 sv::move_if_noexcept(other.begin(), other.end(), this->begin()); // may throw
1564 sv::destroy(this->begin() + other.size(), this->end());
1566 m_size = other.size(); // update end
1573 template <std::size_t C, typename S>
1574 void swap_dispatch(varray<value_type, C, S> & other, true_type const& /*use_optimized_swap*/)
1579 aligned_storage_type,
1580 typename varray<value_type, C, S>::aligned_storage_type
1584 storage_type temp_storage;
1585 value_type * temp_ptr = static_cast<value_type*>(static_cast<void*>(&temp_storage));
1587 ::memcpy(temp_ptr, this->data(), sizeof(Value) * this->size());
1588 ::memcpy(this->data(), other.data(), sizeof(Value) * other.size());
1589 ::memcpy(other.data(), temp_ptr, sizeof(Value) * this->size());
1591 boost::adl_move_swap(m_size, other.m_size);
1595 // If Value's move constructor or move assignment throws
1596 // but only if use_memop_in_swap_and_move is false_type - default.
1599 template <std::size_t C, typename S>
1600 void swap_dispatch(varray<value_type, C, S> & other, false_type const& /*use_optimized_swap*/)
1602 namespace sv = varray_detail;
1605 vt::use_memop_in_swap_and_move use_memop_in_swap_and_move;
1607 if ( this->size() < other.size() )
1608 swap_dispatch_impl(this->begin(), this->end(), other.begin(), other.end(), use_memop_in_swap_and_move()); // may throw
1610 swap_dispatch_impl(other.begin(), other.end(), this->begin(), this->end(), use_memop_in_swap_and_move()); // may throw
1611 boost::adl_move_swap(m_size, other.m_size);
1618 void swap_dispatch_impl(iterator first_sm, iterator last_sm, iterator first_la, iterator last_la, true_type const& /*use_memop*/)
1620 //BOOST_ASSERT_MSG(boost::container::iterator_distance(first_sm, last_sm) <= boost::container::iterator_distance(first_la, last_la));
1622 namespace sv = varray_detail;
1623 for (; first_sm != last_sm ; ++first_sm, ++first_la)
1625 typename aligned_storage<
1627 alignment_of<value_type>::value
1628 >::type temp_storage;
1629 value_type * temp_ptr = static_cast<value_type*>(static_cast<void*>(&temp_storage));
1630 ::memcpy(temp_ptr, (addressof)(*first_sm), sizeof(value_type));
1631 ::memcpy((addressof)(*first_sm), (addressof)(*first_la), sizeof(value_type));
1632 ::memcpy((addressof)(*first_la), temp_ptr, sizeof(value_type));
1635 ::memcpy(first_sm, first_la, sizeof(value_type) * boost::container::iterator_distance(first_la, last_la));
1639 // If Value's move constructor or move assignment throws.
1642 void swap_dispatch_impl(iterator first_sm, iterator last_sm, iterator first_la, iterator last_la, false_type const& /*use_memop*/)
1644 //BOOST_ASSERT_MSG(boost::container::iterator_distance(first_sm, last_sm) <= boost::container::iterator_distance(first_la, last_la));
1646 namespace sv = varray_detail;
1647 for (; first_sm != last_sm ; ++first_sm, ++first_la)
1649 //boost::adl_move_swap(*first_sm, *first_la); // may throw
1650 value_type temp(boost::move(*first_sm)); // may throw
1651 *first_sm = boost::move(*first_la); // may throw
1652 *first_la = boost::move(temp); // may throw
1654 sv::uninitialized_move(first_la, last_la, first_sm); // may throw
1655 sv::destroy(first_la, last_la);
1661 // If Value's move constructor or move assignment throws
1662 // or if Value's copy assignment throws.
1665 template <typename V>
1666 iterator priv_insert(iterator position, V & value)
1668 typedef typename vt::disable_trivial_init dti;
1669 namespace sv = varray_detail;
1671 errh::check_iterator_end_eq(*this, position);
1672 errh::check_capacity(*this, m_size + 1); // may throw
1674 if ( position == this->end() )
1676 sv::construct(dti(), position, value); // may throw
1677 ++m_size; // update end
1681 // TODO - should following lines check for exception and revert to the old size?
1683 // TODO - should move be used only if it's nonthrowing?
1684 value_type & r = *(this->end() - 1);
1685 sv::construct(dti(), this->end(), boost::move(r)); // may throw
1686 ++m_size; // update end
1687 sv::move_backward(position, this->end() - 2, this->end() - 1); // may throw
1688 sv::assign(position, value); // may throw
1697 // If Value's move constructor, move assignment throws
1698 // or if Value's copy constructor or copy assignment throws.
1701 template <typename Iterator>
1702 typename iterator_enable_if_tag<Iterator, std::random_access_iterator_tag>::type
1703 insert_dispatch(iterator position, Iterator first, Iterator last)
1705 errh::check_iterator_end_eq(*this, position);
1707 size_type count = boost::container::iterator_distance(first, last);
1709 errh::check_capacity(*this, m_size + count); // may throw
1711 if ( position == this->end() )
1713 namespace sv = varray_detail;
1715 sv::uninitialized_copy(first, last, position); // may throw
1716 m_size += count; // update end
1720 this->insert_in_the_middle(position, first, last, count); // may throw
1725 // If Value's move constructor, move assignment throws
1726 // or if Value's copy constructor or copy assignment throws.
1729 template <typename Iterator, typename Category>
1730 typename iterator_disable_if_tag<Iterator, std::random_access_iterator_tag>::type
1731 insert_dispatch(iterator position, Iterator first, Iterator last)
1733 errh::check_iterator_end_eq(*this, position);
1735 if ( position == this->end() )
1737 namespace sv = varray_detail;
1739 std::ptrdiff_t d = boost::container::iterator_distance(position, this->begin() + Capacity);
1740 std::size_t count = sv::uninitialized_copy_s(first, last, position, d); // may throw
1742 errh::check_capacity(*this, count <= static_cast<std::size_t>(d) ? m_size + count : Capacity + 1); // may throw
1748 size_type count = boost::container::iterator_distance(first, last);
1750 errh::check_capacity(*this, m_size + count); // may throw
1752 this->insert_in_the_middle(position, first, last, count); // may throw
1757 // If Value's move constructor, move assignment throws
1758 // or if Value's copy constructor or copy assignment throws.
1761 template <typename Iterator>
1762 void insert_in_the_middle(iterator position, Iterator first, Iterator last, difference_type count)
1764 namespace sv = varray_detail;
1766 difference_type to_move = boost::container::iterator_distance(position, this->end());
1768 // TODO - should following lines check for exception and revert to the old size?
1770 if ( count < to_move )
1772 sv::uninitialized_move(this->end() - count, this->end(), this->end()); // may throw
1773 m_size += count; // update end
1774 sv::move_backward(position, position + to_move - count, this->end() - count); // may throw
1775 sv::copy(first, last, position); // may throw
1779 Iterator middle_iter = first;
1780 boost::container::iterator_advance(middle_iter, to_move);
1782 sv::uninitialized_copy(middle_iter, last, this->end()); // may throw
1783 m_size += count - to_move; // update end
1784 sv::uninitialized_move(position, position + to_move, position + count); // may throw
1785 m_size += to_move; // update end
1786 sv::copy(first, middle_iter, position); // may throw
1793 // If Value's constructor or assignment taking dereferenced Iterator throws.
1796 template <typename Iterator>
1797 typename iterator_enable_if_tag<Iterator, std::random_access_iterator_tag>::type
1798 assign_dispatch(Iterator first, Iterator last)
1800 namespace sv = varray_detail;
1802 size_type s = boost::container::iterator_distance(first, last);
1804 errh::check_capacity(*this, s); // may throw
1806 if ( m_size <= static_cast<size_type>(s) )
1808 sv::copy(first, first + m_size, this->begin()); // may throw
1809 // TODO - perform uninitialized_copy first?
1810 sv::uninitialized_copy(first + m_size, last, this->end()); // may throw
1814 sv::copy(first, last, this->begin()); // may throw
1815 sv::destroy(this->begin() + s, this->end());
1817 m_size = s; // update end
1821 // If Value's constructor or assignment taking dereferenced Iterator throws.
1824 template <typename Iterator, typename Category>
1825 typename iterator_disable_if_tag<Iterator, std::random_access_iterator_tag>::type
1826 assign_dispatch(Iterator first, Iterator last)
1828 namespace sv = varray_detail;
1831 iterator it = this->begin();
1833 for ( ; it != this->end() && first != last ; ++it, ++first, ++s )
1834 *it = *first; // may throw
1836 sv::destroy(it, this->end());
1838 std::ptrdiff_t d = boost::container::iterator_distance(it, this->begin() + Capacity);
1839 std::size_t count = sv::uninitialized_copy_s(first, last, it, d); // may throw
1842 errh::check_capacity(*this, count <= static_cast<std::size_t>(d) ? s : Capacity + 1); // may throw
1844 m_size = s; // update end
1849 return pointer(static_cast<Value*>(static_cast<void*>(&m_storage)));
1852 const_pointer ptr() const
1854 return pointer(static_cast<const Value*>(static_cast<const void*>(&m_storage)));
1858 aligned_storage_type m_storage;
1861 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1863 template<typename Value, typename Strategy>
1864 class varray<Value, 0, Strategy>
1866 typedef varray_traits<
1870 typedef typename vt::size_type stored_size_type;
1871 typedef typename vt::error_handler errh;
1874 typedef typename vt::value_type value_type;
1875 typedef stored_size_type size_type;
1876 typedef typename vt::difference_type difference_type;
1877 typedef typename vt::pointer pointer;
1878 typedef typename vt::const_pointer const_pointer;
1879 typedef typename vt::reference reference;
1880 typedef typename vt::const_reference const_reference;
1882 typedef pointer iterator;
1883 typedef const_pointer const_iterator;
1884 typedef boost::container::reverse_iterator<iterator> reverse_iterator;
1885 typedef boost::container::reverse_iterator<const_iterator> const_reverse_iterator;
1891 explicit varray(size_type count)
1893 errh::check_capacity(*this, count); // may throw
1897 varray(size_type count, value_type const&)
1899 errh::check_capacity(*this, count); // may throw
1903 varray(varray const& other)
1905 errh::check_capacity(*this, other.size());
1909 template <size_t C, typename S>
1910 varray(varray<value_type, C, S> const& other)
1912 errh::check_capacity(*this, other.size()); // may throw
1916 template <typename Iterator>
1917 varray(Iterator first, Iterator last)
1919 errh::check_capacity(*this, boost::container::iterator_distance(first, last)); // may throw
1923 varray & operator=(varray const& other)
1925 errh::check_capacity(*this, other.size());
1930 template <size_t C, typename S>
1931 varray & operator=(varray<value_type, C, S> const& other)
1933 errh::check_capacity(*this, other.size()); // may throw
1941 void resize(size_type count)
1943 errh::check_capacity(*this, count); // may throw
1947 void resize(size_type count, value_type const&)
1949 errh::check_capacity(*this, count); // may throw
1954 void reserve(size_type count)
1956 errh::check_capacity(*this, count); // may throw
1960 void push_back(value_type const&)
1962 errh::check_capacity(*this, 1); // may throw
1968 errh::check_empty(*this);
1972 void insert(iterator position, value_type const&)
1974 errh::check_iterator_end_eq(*this, position);
1975 errh::check_capacity(*this, 1); // may throw
1979 void insert(iterator position, size_type count, value_type const&)
1981 errh::check_iterator_end_eq(*this, position);
1982 errh::check_capacity(*this, count); // may throw
1986 template <typename Iterator>
1987 void insert(iterator, Iterator first, Iterator last)
1989 errh::check_capacity(*this, boost::container::iterator_distance(first, last)); // may throw
1993 void erase(iterator position)
1995 errh::check_iterator_end_neq(*this, position);
1999 void erase(iterator first, iterator last)
2001 errh::check_iterator_end_eq(*this, first);
2002 errh::check_iterator_end_eq(*this, last);
2004 //BOOST_ASSERT_MSG(0 <= n, "invalid range");
2008 template <typename Iterator>
2009 void assign(Iterator first, Iterator last)
2011 errh::check_capacity(*this, boost::container::iterator_distance(first, last)); // may throw
2015 void assign(size_type count, value_type const&)
2017 errh::check_capacity(*this, count); // may throw
2024 reference at(size_type i)
2026 errh::check_at(*this, i); // may throw
2027 return *(this->begin() + i);
2031 const_reference at(size_type i) const
2033 errh::check_at(*this, i); // may throw
2034 return *(this->begin() + i);
2038 reference operator[](size_type i)
2040 errh::check_operator_brackets(*this, i);
2041 return *(this->begin() + i);
2045 const_reference operator[](size_type i) const
2047 errh::check_operator_brackets(*this, i);
2048 return *(this->begin() + i);
2054 errh::check_empty(*this);
2055 return *(this->begin());
2059 const_reference front() const
2061 errh::check_empty(*this);
2062 return *(this->begin());
2068 errh::check_empty(*this);
2069 return *(this->end() - 1);
2073 const_reference back() const
2075 errh::check_empty(*this);
2076 return *(this->end() - 1);
2080 Value * data() { return (addressof)(*(this->ptr())); }
2081 const Value * data() const { return (addressof)(*(this->ptr())); }
2084 iterator begin() { return this->ptr(); }
2085 const_iterator begin() const { return this->ptr(); }
2086 const_iterator cbegin() const { return this->ptr(); }
2087 iterator end() { return this->begin(); }
2088 const_iterator end() const { return this->begin(); }
2089 const_iterator cend() const { return this->cbegin(); }
2091 reverse_iterator rbegin() { return reverse_iterator(this->end()); }
2092 const_reverse_iterator rbegin() const { return reverse_iterator(this->end()); }
2093 const_reverse_iterator crbegin() const { return reverse_iterator(this->end()); }
2094 reverse_iterator rend() { return reverse_iterator(this->begin()); }
2095 const_reverse_iterator rend() const { return reverse_iterator(this->begin()); }
2096 const_reverse_iterator crend() const { return reverse_iterator(this->begin()); }
2099 size_type capacity() const { return 0; }
2100 size_type max_size() const { return 0; }
2101 size_type size() const { return 0; }
2102 bool empty() const { return true; }
2108 return pointer(reinterpret_cast<Value*>(this));
2111 const_pointer ptr() const
2113 return const_pointer(reinterpret_cast<const Value*>(this));
2117 #endif // !BOOST_CONTAINER_DOXYGEN_INVOKED
2119 //! @brief Checks if contents of two varrays are equal.
2121 //! @ingroup varray_non_member
2123 //! @param x The first varray.
2124 //! @param y The second varray.
2126 //! @return \c true if containers have the same size and elements in both containers are equal.
2130 template<typename V, std::size_t C1, typename S1, std::size_t C2, typename S2>
2131 bool operator== (varray<V, C1, S1> const& x, varray<V, C2, S2> const& y)
2133 return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin());
2136 //! @brief Checks if contents of two varrays are not equal.
2138 //! @ingroup varray_non_member
2140 //! @param x The first varray.
2141 //! @param y The second varray.
2143 //! @return \c true if containers have different size or elements in both containers are not equal.
2147 template<typename V, std::size_t C1, typename S1, std::size_t C2, typename S2>
2148 bool operator!= (varray<V, C1, S1> const& x, varray<V, C2, S2> const& y)
2153 //! @brief Lexicographically compares varrays.
2155 //! @ingroup varray_non_member
2157 //! @param x The first varray.
2158 //! @param y The second varray.
2160 //! @return \c true if x compares lexicographically less than y.
2164 template<typename V, std::size_t C1, typename S1, std::size_t C2, typename S2>
2165 bool operator< (varray<V, C1, S1> const& x, varray<V, C2, S2> const& y)
2167 return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
2170 //! @brief Lexicographically compares varrays.
2172 //! @ingroup varray_non_member
2174 //! @param x The first varray.
2175 //! @param y The second varray.
2177 //! @return \c true if y compares lexicographically less than x.
2181 template<typename V, std::size_t C1, typename S1, std::size_t C2, typename S2>
2182 bool operator> (varray<V, C1, S1> const& x, varray<V, C2, S2> const& y)
2187 //! @brief Lexicographically compares varrays.
2189 //! @ingroup varray_non_member
2191 //! @param x The first varray.
2192 //! @param y The second varray.
2194 //! @return \c true if y don't compare lexicographically less than x.
2198 template<typename V, std::size_t C1, typename S1, std::size_t C2, typename S2>
2199 bool operator<= (varray<V, C1, S1> const& x, varray<V, C2, S2> const& y)
2204 //! @brief Lexicographically compares varrays.
2206 //! @ingroup varray_non_member
2208 //! @param x The first varray.
2209 //! @param y The second varray.
2211 //! @return \c true if x don't compare lexicographically less than y.
2215 template<typename V, std::size_t C1, typename S1, std::size_t C2, typename S2>
2216 bool operator>= (varray<V, C1, S1> const& x, varray<V, C2, S2> const& y)
2221 //! @brief Swaps contents of two varrays.
2223 //! This function calls varray::swap().
2225 //! @ingroup varray_non_member
2227 //! @param x The first varray.
2228 //! @param y The second varray.
2232 template<typename V, std::size_t C1, typename S1, std::size_t C2, typename S2>
2233 inline void swap(varray<V, C1, S1> & x, varray<V, C2, S2> & y)
2238 }}} // namespace boost::container::dtl
2240 #include <boost/container/detail/config_end.hpp>
2242 #endif // BOOST_CONTAINER_DETAIL_VARRAY_HPP