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_VARRAY_HPP
12 #define BOOST_CONTAINER_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>
24 #include "detail/varray.hpp"
25 #include <boost/move/utility_core.hpp>
27 namespace boost { namespace container {
30 * @defgroup varray_non_member varray non-member functions
34 * @brief A variable-size array container with fixed capacity.
36 * varray is a sequence container like boost::container::vector with contiguous storage that can
37 * change in size, along with the static allocation, low overhead, and fixed capacity of boost::array.
39 * A varray is a sequence that supports random access to elements, constant time insertion and
40 * removal of elements at the end, and linear time insertion and removal of elements at the beginning or
41 * in the middle. The number of elements in a varray may vary dynamically up to a fixed capacity
42 * because elements are stored within the object itself similarly to an array. However, objects are
43 * initialized as they are inserted into varray unlike C arrays or std::array which must construct
44 * all elements on instantiation. The behavior of varray enables the use of statically allocated
45 * elements in cases with complex object lifetime requirements that would otherwise not be trivially
49 * Insertion beyond the capacity and out of bounds errors result in undefined behavior.
50 * The reason for this is because unlike vectors, varray does not perform allocation.
52 * @tparam Value The type of element that will be stored.
53 * @tparam Capacity The maximum number of elements varray can store, fixed at compile time.
55 template <typename Value, std::size_t Capacity>
57 : public dtl::varray<Value, Capacity>
59 typedef dtl::varray<Value, Capacity> base_t;
61 BOOST_COPYABLE_AND_MOVABLE(varray)
64 //! @brief The type of elements stored in the container.
65 typedef typename base_t::value_type value_type;
66 //! @brief The unsigned integral type used by the container.
67 typedef typename base_t::size_type size_type;
68 //! @brief The pointers difference type.
69 typedef typename base_t::difference_type difference_type;
70 //! @brief The pointer type.
71 typedef typename base_t::pointer pointer;
72 //! @brief The const pointer type.
73 typedef typename base_t::const_pointer const_pointer;
74 //! @brief The value reference type.
75 typedef typename base_t::reference reference;
76 //! @brief The value const reference type.
77 typedef typename base_t::const_reference const_reference;
78 //! @brief The iterator type.
79 typedef typename base_t::iterator iterator;
80 //! @brief The const iterator type.
81 typedef typename base_t::const_iterator const_iterator;
82 //! @brief The reverse iterator type.
83 typedef typename base_t::reverse_iterator reverse_iterator;
84 //! @brief The const reverse iterator.
85 typedef typename base_t::const_reverse_iterator const_reverse_iterator;
87 //! @brief Constructs an empty varray.
98 //! @pre <tt>count <= capacity()</tt>
100 //! @brief Constructs a varray containing count value initialized Values.
102 //! @param count The number of values which will be contained in the container.
105 //! If Value's value initialization throws.
109 explicit varray(size_type count)
113 //! @pre <tt>count <= capacity()</tt>
115 //! @brief Constructs a varray containing count copies of value.
117 //! @param count The number of copies of a values that will be contained in the container.
118 //! @param value The value which will be used to copy construct values.
121 //! If Value's copy constructor throws.
125 varray(size_type count, value_type const& value)
126 : base_t(count, value)
130 //! @li <tt>distance(first, last) <= capacity()</tt>
131 //! @li Iterator must meet the \c ForwardTraversalIterator concept.
133 //! @brief Constructs a varray containing copy of a range <tt>[first, last)</tt>.
135 //! @param first The iterator to the first element in range.
136 //! @param last The iterator to the one after the last element in range.
139 //! If Value's constructor taking a dereferenced Iterator throws.
143 template <typename Iterator>
144 varray(Iterator first, Iterator last)
145 : base_t(first, last)
148 //! @brief Constructs a copy of other varray.
150 //! @param other The varray which content will be copied to this one.
153 //! If Value's copy constructor throws.
157 varray(varray const& other)
161 //! @pre <tt>other.size() <= capacity()</tt>.
163 //! @brief Constructs a copy of other varray.
165 //! @param other The varray which content will be copied to this one.
168 //! If Value's copy constructor throws.
172 template <std::size_t C>
173 varray(varray<value_type, C> const& other) : base_t(other) {}
175 //! @brief Copy assigns Values stored in the other varray to this one.
177 //! @param other The varray which content will be copied to this one.
180 //! If Value's copy constructor or copy assignment throws.
184 varray & operator=(BOOST_COPY_ASSIGN_REF(varray) other)
186 base_t::operator=(static_cast<base_t const&>(other));
190 //! @pre <tt>other.size() <= capacity()</tt>
192 //! @brief Copy assigns Values stored in the other varray to this one.
194 //! @param other The varray which content will be copied to this one.
197 //! If Value's copy constructor or copy assignment throws.
201 template <std::size_t C>
202 // TEMPORARY WORKAROUND
203 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
204 varray & operator=(::boost::rv< varray<value_type, C> > const& other)
206 varray & operator=(varray<value_type, C> const& other)
209 base_t::operator=(static_cast<varray<value_type, C> const&>(other));
213 //! @brief Move constructor. Moves Values stored in the other varray to this one.
215 //! @param other The varray which content will be moved to this one.
218 //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor throws.
219 //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor throws.
223 varray(BOOST_RV_REF(varray) other)
224 : base_t(boost::move(static_cast<base_t&>(other)))
227 //! @pre <tt>other.size() <= capacity()</tt>
229 //! @brief Move constructor. Moves Values stored in the other varray to this one.
231 //! @param other The varray which content will be moved to this one.
234 //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor throws.
235 //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor throws.
239 template <std::size_t C>
240 varray(BOOST_RV_REF_2_TEMPL_ARGS(varray, value_type, C) other)
241 : base_t(boost::move(static_cast<dtl::varray<value_type, C>&>(other)))
244 //! @brief Move assignment. Moves Values stored in the other varray to this one.
246 //! @param other The varray which content will be moved to this one.
249 //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor or move assignment throws.
250 //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor or copy assignment throws.
254 varray & operator=(BOOST_RV_REF(varray) other)
256 base_t::operator=(boost::move(static_cast<base_t&>(other)));
260 //! @pre <tt>other.size() <= capacity()</tt>
262 //! @brief Move assignment. Moves Values stored in the other varray to this one.
264 //! @param other The varray which content will be moved to this one.
267 //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor or move assignment throws.
268 //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor or copy assignment throws.
272 template <std::size_t C>
273 varray & operator=(BOOST_RV_REF_2_TEMPL_ARGS(varray, value_type, C) other)
275 base_t::operator=(boost::move(static_cast<dtl::varray<value_type, C>&>(other)));
279 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
281 //! @brief Destructor. Destroys Values stored in this container.
290 //! @brief Swaps contents of the other varray and this one.
292 //! @param other The varray which content will be swapped with this one's content.
295 //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor or move assignment throws,
296 //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor or copy assignment throws,
300 void swap(varray & other);
302 //! @pre <tt>other.size() <= capacity() && size() <= other.capacity()</tt>
304 //! @brief Swaps contents of the other varray and this one.
306 //! @param other The varray which content will be swapped with this one's content.
309 //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor or move assignment throws,
310 //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor or copy assignment throws,
314 template <std::size_t C>
315 void swap(varray<value_type, C> & other);
317 //! @pre <tt>count <= capacity()</tt>
319 //! @brief Inserts or erases elements at the end such that
320 //! the size becomes count. New elements are value initialized.
322 //! @param count The number of elements which will be stored in the container.
325 //! If Value's value initialization throws.
329 void resize(size_type count);
331 //! @pre <tt>count <= capacity()</tt>
333 //! @brief Inserts or erases elements at the end such that
334 //! the size becomes count. New elements are copy constructed from value.
336 //! @param count The number of elements which will be stored in the container.
337 //! @param value The value used to copy construct the new element.
340 //! If Value's copy constructor throws.
344 void resize(size_type count, value_type const& value);
346 //! @pre <tt>count <= capacity()</tt>
348 //! @brief This call has no effect because the Capacity of this container is constant.
350 //! @param count The number of elements which the container should be able to contain.
357 void reserve(size_type count);
359 //! @pre <tt>size() < capacity()</tt>
361 //! @brief Adds a copy of value at the end.
363 //! @param value The value used to copy construct the new element.
366 //! If Value's copy constructor throws.
370 void push_back(value_type const& value);
372 //! @pre <tt>size() < capacity()</tt>
374 //! @brief Moves value to the end.
376 //! @param value The value to move construct the new element.
379 //! If Value's move constructor throws.
383 void push_back(BOOST_RV_REF(value_type) value);
385 //! @pre <tt>!empty()</tt>
387 //! @brief Destroys last value and decreases the size.
390 //! Nothing by default.
397 //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>.
398 //! @li <tt>size() < capacity()</tt>
400 //! @brief Inserts a copy of element at position.
402 //! @param position The position at which the new value will be inserted.
403 //! @param value The value used to copy construct the new element.
406 //! @li If Value's copy constructor or copy assignment throws
407 //! @li If Value's move constructor or move assignment throws.
410 //! Constant or linear.
411 iterator insert(iterator position, value_type const& value);
414 //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>.
415 //! @li <tt>size() < capacity()</tt>
417 //! @brief Inserts a move-constructed element at position.
419 //! @param position The position at which the new value will be inserted.
420 //! @param value The value used to move construct the new element.
423 //! If Value's move constructor or move assignment throws.
426 //! Constant or linear.
427 iterator insert(iterator position, BOOST_RV_REF(value_type) value);
430 //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>.
431 //! @li <tt>size() + count <= capacity()</tt>
433 //! @brief Inserts a count copies of value at position.
435 //! @param position The position at which new elements will be inserted.
436 //! @param count The number of new elements which will be inserted.
437 //! @param value The value used to copy construct new elements.
440 //! @li If Value's copy constructor or copy assignment throws.
441 //! @li If Value's move constructor or move assignment throws.
445 iterator insert(iterator position, size_type count, value_type const& value);
448 //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>.
449 //! @li <tt>distance(first, last) <= capacity()</tt>
450 //! @li \c Iterator must meet the \c ForwardTraversalIterator concept.
452 //! @brief Inserts a copy of a range <tt>[first, last)</tt> at position.
454 //! @param position The position at which new elements will be inserted.
455 //! @param first The iterator to the first element of a range used to construct new elements.
456 //! @param last The iterator to the one after the last element of a range used to construct new elements.
459 //! @li If Value's constructor and assignment taking a dereferenced \c Iterator.
460 //! @li If Value's move constructor or move assignment throws.
464 template <typename Iterator>
465 iterator insert(iterator position, Iterator first, Iterator last);
467 //! @pre \c position must be a valid iterator of \c *this in range <tt>[begin(), end())</tt>
469 //! @brief Erases Value from position.
471 //! @param position The position of the element which will be erased from the container.
474 //! If Value's move assignment throws.
478 iterator erase(iterator position);
481 //! @li \c first and \c last must define a valid range
482 //! @li iterators must be in range <tt>[begin(), end()]</tt>
484 //! @brief Erases Values from a range <tt>[first, last)</tt>.
486 //! @param first The position of the first element of a range which will be erased from the container.
487 //! @param last The position of the one after the last element of a range which will be erased from the container.
490 //! If Value's move assignment throws.
494 iterator erase(iterator first, iterator last);
496 //! @pre <tt>distance(first, last) <= capacity()</tt>
498 //! @brief Assigns a range <tt>[first, last)</tt> of Values to this container.
500 //! @param first The iterator to the first element of a range used to construct new content of this container.
501 //! @param last The iterator to the one after the last element of a range used to construct new content of this container.
504 //! If Value's copy constructor or copy assignment throws,
508 template <typename Iterator>
509 void assign(Iterator first, Iterator last);
511 //! @pre <tt>count <= capacity()</tt>
513 //! @brief Assigns a count copies of value to this container.
515 //! @param count The new number of elements which will be container in the container.
516 //! @param value The value which will be used to copy construct the new content.
519 //! If Value's copy constructor or copy assignment throws.
523 void assign(size_type count, value_type const& value);
525 //! @pre <tt>size() < capacity()</tt>
527 //! @brief Inserts a Value constructed with
528 //! \c std::forward<Args>(args)... in the end of the container.
530 //! @param args The arguments of the constructor of the new element which will be created at the end of the container.
533 //! If in-place constructor throws or Value's move constructor throws.
537 template<class ...Args>
538 void emplace_back(Args &&...args);
541 //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>
542 //! @li <tt>size() < capacity()</tt>
544 //! @brief Inserts a Value constructed with
545 //! \c std::forward<Args>(args)... before position
547 //! @param position The position at which new elements will be inserted.
548 //! @param args The arguments of the constructor of the new element.
551 //! If in-place constructor throws or if Value's move constructor or move assignment throws.
554 //! Constant or linear.
555 template<class ...Args>
556 iterator emplace(iterator position, Args &&...args);
558 //! @brief Removes all elements from the container.
567 //! @pre <tt>i < size()</tt>
569 //! @brief Returns reference to the i-th element.
571 //! @param i The element's index.
573 //! @return reference to the i-th element
574 //! from the beginning of the container.
577 //! \c std::out_of_range exception by default.
581 reference at(size_type i);
583 //! @pre <tt>i < size()</tt>
585 //! @brief Returns const reference to the i-th element.
587 //! @param i The element's index.
589 //! @return const reference to the i-th element
590 //! from the beginning of the container.
593 //! \c std::out_of_range exception by default.
597 const_reference at(size_type i) const;
599 //! @pre <tt>i < size()</tt>
601 //! @brief Returns reference to the i-th element.
603 //! @param i The element's index.
605 //! @return reference to the i-th element
606 //! from the beginning of the container.
609 //! Nothing by default.
613 reference operator[](size_type i);
615 //! @pre <tt>i < size()</tt>
617 //! @brief Returns const reference to the i-th element.
619 //! @param i The element's index.
621 //! @return const reference to the i-th element
622 //! from the beginning of the container.
625 //! Nothing by default.
629 const_reference operator[](size_type i) const;
633 //! @brief Returns reference to the first element.
635 //! @return reference to the first element
636 //! from the beginning of the container.
639 //! Nothing by default.
647 //! @brief Returns const reference to the first element.
649 //! @return const reference to the first element
650 //! from the beginning of the container.
653 //! Nothing by default.
657 const_reference front() const;
661 //! @brief Returns reference to the last element.
663 //! @return reference to the last element
664 //! from the beginning of the container.
667 //! Nothing by default.
675 //! @brief Returns const reference to the first element.
677 //! @return const reference to the last element
678 //! from the beginning of the container.
681 //! Nothing by default.
685 const_reference back() const;
687 //! @brief Pointer such that <tt>[data(), data() + size())</tt> is a valid range.
688 //! For a non-empty vector <tt>data() == &front()</tt>.
697 //! @brief Const pointer such that <tt>[data(), data() + size())</tt> is a valid range.
698 //! For a non-empty vector <tt>data() == &front()</tt>.
705 const Value * data() const;
707 //! @brief Returns iterator to the first element.
709 //! @return iterator to the first element contained in the vector.
718 //! @brief Returns const iterator to the first element.
720 //! @return const_iterator to the first element contained in the vector.
727 const_iterator begin() const;
729 //! @brief Returns const iterator to the first element.
731 //! @return const_iterator to the first element contained in the vector.
738 const_iterator cbegin() const;
740 //! @brief Returns iterator to the one after the last element.
742 //! @return iterator pointing to the one after the last element contained in the vector.
751 //! @brief Returns const iterator to the one after the last element.
753 //! @return const_iterator pointing to the one after the last element contained in the vector.
760 const_iterator end() const;
762 //! @brief Returns const iterator to the one after the last element.
764 //! @return const_iterator pointing to the one after the last element contained in the vector.
771 const_iterator cend() const;
773 //! @brief Returns reverse iterator to the first element of the reversed container.
775 //! @return reverse_iterator pointing to the beginning
776 //! of the reversed varray.
783 reverse_iterator rbegin();
785 //! @brief Returns const reverse iterator to the first element of the reversed container.
787 //! @return const_reverse_iterator pointing to the beginning
788 //! of the reversed varray.
795 const_reverse_iterator rbegin() const;
797 //! @brief Returns const reverse iterator to the first element of the reversed container.
799 //! @return const_reverse_iterator pointing to the beginning
800 //! of the reversed varray.
807 const_reverse_iterator crbegin() const;
809 //! @brief Returns reverse iterator to the one after the last element of the reversed container.
811 //! @return reverse_iterator pointing to the one after the last element
812 //! of the reversed varray.
819 reverse_iterator rend();
821 //! @brief Returns const reverse iterator to the one after the last element of the reversed container.
823 //! @return const_reverse_iterator pointing to the one after the last element
824 //! of the reversed varray.
831 const_reverse_iterator rend() const;
833 //! @brief Returns const reverse iterator to the one after the last element of the reversed container.
835 //! @return const_reverse_iterator pointing to the one after the last element
836 //! of the reversed varray.
843 const_reverse_iterator crend() const;
845 //! @brief Returns container's capacity.
847 //! @return container's capacity.
854 static size_type capacity();
856 //! @brief Returns container's capacity.
858 //! @return container's capacity.
865 static size_type max_size();
867 //! @brief Returns the number of stored elements.
869 //! @return Number of elements contained in the container.
876 size_type size() const;
878 //! @brief Queries if the container contains elements.
880 //! @return true if the number of elements contained in the
881 //! container is equal to 0.
890 #endif // BOOST_CONTAINER_DOXYGEN_INVOKED
894 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
896 //! @brief Checks if contents of two varrays are equal.
898 //! @ingroup varray_non_member
900 //! @param x The first varray.
901 //! @param y The second varray.
903 //! @return \c true if containers have the same size and elements in both containers are equal.
907 template<typename V, std::size_t C1, std::size_t C2>
908 bool operator== (varray<V, C1> const& x, varray<V, C2> const& y);
910 //! @brief Checks if contents of two varrays are not equal.
912 //! @ingroup varray_non_member
914 //! @param x The first varray.
915 //! @param y The second varray.
917 //! @return \c true if containers have different size or elements in both containers are not equal.
921 template<typename V, std::size_t C1, std::size_t C2>
922 bool operator!= (varray<V, C1> const& x, varray<V, C2> const& y);
924 //! @brief Lexicographically compares varrays.
926 //! @ingroup varray_non_member
928 //! @param x The first varray.
929 //! @param y The second varray.
931 //! @return \c true if x compares lexicographically less than y.
935 template<typename V, std::size_t C1, std::size_t C2>
936 bool operator< (varray<V, C1> const& x, varray<V, C2> const& y);
938 //! @brief Lexicographically compares varrays.
940 //! @ingroup varray_non_member
942 //! @param x The first varray.
943 //! @param y The second varray.
945 //! @return \c true if y compares lexicographically less than x.
949 template<typename V, std::size_t C1, std::size_t C2>
950 bool operator> (varray<V, C1> const& x, varray<V, C2> const& y);
952 //! @brief Lexicographically compares varrays.
954 //! @ingroup varray_non_member
956 //! @param x The first varray.
957 //! @param y The second varray.
959 //! @return \c true if y don't compare lexicographically less than x.
963 template<typename V, std::size_t C1, std::size_t C2>
964 bool operator<= (varray<V, C1> const& x, varray<V, C2> const& y);
966 //! @brief Lexicographically compares varrays.
968 //! @ingroup varray_non_member
970 //! @param x The first varray.
971 //! @param y The second varray.
973 //! @return \c true if x don't compare lexicographically less than y.
977 template<typename V, std::size_t C1, std::size_t C2>
978 bool operator>= (varray<V, C1> const& x, varray<V, C2> const& y);
980 //! @brief Swaps contents of two varrays.
982 //! This function calls varray::swap().
984 //! @ingroup varray_non_member
986 //! @param x The first varray.
987 //! @param y The second varray.
991 template<typename V, std::size_t C1, std::size_t C2>
992 inline void swap(varray<V, C1> & x, varray<V, C2> & y);
994 #endif // BOOST_CONTAINER_DOXYGEN_INVOKED
996 }} // namespace boost::container
998 #include <boost/container/detail/config_end.hpp>
1000 #endif // BOOST_CONTAINER_VARRAY_HPP