Subject: [Boost-commit] svn:boost r84675 - in trunk/boost/geometry/index/detail: . rtree/node
From: adam.wulkiewicz_at_[hidden]
Date: 2013-06-07 13:34:58
Author: awulkiew
Date: 2013-06-07 13:34:58 EDT (Fri, 07 Jun 2013)
New Revision: 84675
URL: http://svn.boost.org/trac/boost/changeset/84675
Log:
geometry.index: varray replaced by optimized, advanced varray with move semantics and emplace support, developed by: Andrew Hundt and Adam Wulkiewicz.
Added:
trunk/boost/geometry/index/detail/varray_detail.hpp (contents, props changed)
Text files modified:
trunk/boost/geometry/index/detail/assert.hpp | 3
trunk/boost/geometry/index/detail/rtree/node/node_d_mem_static.hpp | 10
trunk/boost/geometry/index/detail/rtree/node/node_s_mem_static.hpp | 6
trunk/boost/geometry/index/detail/varray.hpp | 2194 +++++++++++++++++++++++++++++++--------
trunk/boost/geometry/index/detail/varray_detail.hpp | 714 +++++++++++++
5 files changed, 2470 insertions(+), 457 deletions(-)
Modified: trunk/boost/geometry/index/detail/assert.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/assert.hpp Fri Jun 7 13:33:25 2013 (r84674)
+++ trunk/boost/geometry/index/detail/assert.hpp 2013-06-07 13:34:58 EDT (Fri, 07 Jun 2013) (r84675)
@@ -14,6 +14,9 @@
#define BOOST_GEOMETRY_INDEX_ASSERT(CONDITION, TEXT_MSG) \
BOOST_ASSERT_MSG(CONDITION, TEXT_MSG)
+// TODO - change it to something like:
+// BOOST_ASSERT((CONDITION) && (TEXT_MSG))
+
#if defined(BOOST_DISABLE_ASSERTS) || defined(NDEBUG)
#define BOOST_GEOMETRY_INDEX_ASSERT_UNUSED_PARAM(PARAM)
Modified: trunk/boost/geometry/index/detail/rtree/node/node_d_mem_static.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/node/node_d_mem_static.hpp Fri Jun 7 13:33:25 2013 (r84674)
+++ trunk/boost/geometry/index/detail/rtree/node/node_d_mem_static.hpp 2013-06-07 13:34:58 EDT (Fri, 07 Jun 2013) (r84675)
@@ -25,8 +25,7 @@
typedef detail::varray<
rtree::ptr_pair<Box, typename Allocators::node_pointer>,
- Parameters::max_elements + 1,
- elements_allocator_type
+ Parameters::max_elements + 1
> elements_type;
template <typename Alloc>
@@ -48,8 +47,7 @@
typedef detail::varray<
Value,
- Parameters::max_elements + 1,
- elements_allocator_type
+ Parameters::max_elements + 1
> elements_type;
template <typename Alloc>
@@ -88,8 +86,8 @@
};
// elements derived type
-template <typename OldValue, size_t N, typename A, typename NewValue>
-struct container_from_elements_type<detail::varray<OldValue, N, A>, NewValue>
+template <typename OldValue, size_t N, typename NewValue>
+struct container_from_elements_type<detail::varray<OldValue, N>, NewValue>
{
typedef detail::varray<NewValue, N> type;
};
Modified: trunk/boost/geometry/index/detail/rtree/node/node_s_mem_static.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/node/node_s_mem_static.hpp Fri Jun 7 13:33:25 2013 (r84674)
+++ trunk/boost/geometry/index/detail/rtree/node/node_s_mem_static.hpp 2013-06-07 13:34:58 EDT (Fri, 07 Jun 2013) (r84675)
@@ -26,8 +26,7 @@
typedef detail::varray<
rtree::ptr_pair<Box, typename Allocators::node_pointer>,
- Parameters::max_elements + 1,
- elements_allocator_type
+ Parameters::max_elements + 1
> elements_type;
template <typename Alloc>
@@ -45,8 +44,7 @@
typedef detail::varray<
Value,
- Parameters::max_elements + 1,
- elements_allocator_type
+ Parameters::max_elements + 1
> elements_type;
template <typename Alloc>
Modified: trunk/boost/geometry/index/detail/varray.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/varray.hpp Fri Jun 7 13:33:25 2013 (r84674)
+++ trunk/boost/geometry/index/detail/varray.hpp 2013-06-07 13:34:58 EDT (Fri, 07 Jun 2013) (r84675)
@@ -1,6 +1,7 @@
-// Boost.Geometry Index
+// Boost.Container varray
//
-// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
+// Copyright (c) 2012-2013 Adam Wulkiewicz, Lodz, Poland.
+// Copyright (c) 2011-2013 Andrew Hundt.
//
// Use, modification and distribution is subject to the Boost Software License,
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
@@ -9,224 +10,787 @@
#ifndef BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_HPP
#define BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_HPP
-#include <cstddef>
-
-#include <boost/move/move.hpp>
-#include <boost/aligned_storage.hpp>
-#include <boost/iterator/reverse_iterator.hpp>
+// TODO - REMOVE/CHANGE
+#include <boost/container/detail/config_begin.hpp>
+#include <boost/container/detail/workaround.hpp>
+#include <boost/container/detail/preprocessor.hpp>
+
+#include <boost/config.hpp>
+#include <boost/swap.hpp>
+#include <boost/integer.hpp>
#include <boost/mpl/assert.hpp>
-#include <boost/mpl/if.hpp>
-#include <boost/mpl/and.hpp>
-#include <boost/mpl/or.hpp>
-#include <boost/type_traits/is_same.hpp>
+#include <boost/type_traits/is_unsigned.hpp>
#include <boost/type_traits/alignment_of.hpp>
#include <boost/type_traits/aligned_storage.hpp>
-#include <boost/type_traits/has_trivial_assign.hpp>
-#include <boost/type_traits/has_trivial_copy.hpp>
-#include <boost/type_traits/has_trivial_constructor.hpp>
-#include <boost/type_traits/has_trivial_destructor.hpp>
+
+// TODO - use std::reverse_iterator and std::iterator_traits
+// instead Boost.Iterator to remove dependency?
+// or boost/detail/iterator.hpp ?
+#include <boost/iterator/reverse_iterator.hpp>
+#include <boost/iterator/iterator_concepts.hpp>
#include <boost/geometry/index/detail/assert.hpp>
-#ifdef BOOST_MSVC
-#pragma warning (push)
-#pragma warning (disable : 4996) // deprecated functions
-#endif
+#include <boost/geometry/index/detail/assert.hpp>
+#include <boost/geometry/index/detail/varray_detail.hpp>
+
+/*!
+\defgroup varray_non_member varray non-member functions
+*/
namespace boost { namespace geometry { namespace index { namespace detail {
+
+namespace varray_detail {
-template <typename V>
-struct varray_default_alloc
+template <typename Value, std::size_t Capacity>
+struct varray_traits
{
+ typedef Value value_type;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
- typedef V * pointer;
- typedef const V * const_pointer;
+ typedef Value * pointer;
+ typedef const Value * const_pointer;
+ typedef Value & reference;
+ typedef const Value & const_reference;
+
+ typedef boost::false_type use_memop_in_swap_and_move;
+ typedef boost::false_type use_optimized_swap;
+ typedef boost::false_type disable_trivial_init;
+};
+
+template <typename Varray>
+struct checker
+{
+ typedef typename Varray::size_type size_type;
+ typedef typename Varray::const_iterator const_iterator;
+
+ static inline void check_capacity(Varray const& v, size_type s)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(s <= v.capacity(), "size too big");
+ // unused params
+ (void)v;
+ }
+
+ static inline void throw_out_of_bounds(Varray const& v, size_type i)
+ {
+//#ifndef BOOST_NO_EXCEPTIONS
+ if ( v.size() <= i )
+ BOOST_THROW_EXCEPTION(std::out_of_range("index out of bounds"));
+//#else // BOOST_NO_EXCEPTIONS
+// BOOST_GEOMETRY_INDEX_ASSERT(i < v.size(), "index out of bounds");
+//#endif // BOOST_NO_EXCEPTIONS
+ }
+
+ static inline void check_index(Varray const& v, size_type i)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(i < v.size(), "index out of bounds");
+ }
+
+ static inline void check_not_empty(Varray const& v)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(!v.empty(), "the container is empty");
+ }
+
+ static inline void check_iterator_end_neq(Varray const& v, const_iterator position)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(v.begin() <= position && position < v.end(), "iterator out of bounds");
+ }
+
+ static inline void check_iterator_end_eq(Varray const& v, const_iterator position)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(v.begin() <= position && position <= v.end(), "iterator out of bounds");
+ }
};
-template <typename Value, size_t Capacity, typename Al = varray_default_alloc<Value> >
+} // namespace varray_detail
+
+/*!
+\brief A variable-size array container with fixed capacity.
+
+varray is a sequence container like boost::container::vector with contiguous storage that can
+change in size, along with the static allocation, low overhead, and fixed capacity of boost::array.
+
+A varray is a sequence that supports random access to elements, constant time insertion and
+removal of elements at the end, and linear time insertion and removal of elements at the beginning or
+in the middle. The number of elements in a varray may vary dynamically up to a fixed capacity
+because elements are stored within the object itself similarly to an array. However, objects are
+initialized as they are inserted into varray unlike C arrays or std::array which must construct
+all elements on instantiation. The behavior of varray enables the use of statically allocated
+elements in cases with complex object lifetime requirements that would otherwise not be trivially
+possible.
+
+\par Error Handling
+ Insertion beyond the capacity and out of bounds errors result in undefined behavior unless
+ otherwise specified. In this respect if size() == capacity(), then varray::push_back()
+ behaves like std::vector pop_front() if size() == empty(). The reason for this difference
+ is because unlike vectors, varray does not perform allocation.
+
+\par Advanced Usage
+ Error handling behavior can be modified to more closely match std::vector exception behavior
+ when exceeding bounds by providing an alternate Strategy and varray_traits instantiation.
+
+\tparam Value The type of element that will be stored.
+\tparam Capacity The maximum number of elements varray can store, fixed at compile time.
+\tparam Strategy Defines the public typedefs and error handlers,
+ implements StaticVectorStrategy and has some similarities
+ to an Allocator.
+*/
+template <typename Value, std::size_t Capacity>
class varray
{
+ typedef varray_detail::varray_traits<Value, Capacity> vt;
+ typedef varray_detail::checker<varray> errh;
+
BOOST_MPL_ASSERT_MSG(
- (0 < Capacity),
- INVALID_CAPACITY,
- (varray));
+ ( boost::is_unsigned<typename vt::size_type>::value &&
+ sizeof(typename boost::uint_value_t<Capacity>::least) <= sizeof(typename vt::size_type) ),
+ SIZE_TYPE_IS_TOO_SMALL_FOR_SPECIFIED_CAPACITY,
+ (varray)
+ );
+
+ typedef boost::aligned_storage<
+ sizeof(Value[Capacity]),
+ boost::alignment_of<Value[Capacity]>::value
+ > aligned_storage_type;
+
+ template <typename V, std::size_t C>
+ friend class varray;
BOOST_COPYABLE_AND_MOVABLE(varray)
+#ifdef BOOST_NO_RVALUE_REFERENCES
public:
- typedef Value value_type;
- typedef Value& reference;
- typedef Value const& const_reference;
- typedef typename Al::size_type size_type;
- typedef typename Al::difference_type difference_type;
- typedef typename Al::pointer pointer;
- typedef typename Al::const_pointer const_pointer;
+ template <std::size_t C>
+ varray & operator=(varray<Value, C> & sv)
+ {
+ typedef varray<Value, C> other;
+ this->operator=(static_cast<const ::boost::rv<other> &>(const_cast<const other &>(sv)));
+ return *this;
+ }
+#endif
+
+public:
+ //! @brief The type of elements stored in the container.
+ typedef typename vt::value_type value_type;
+ //! @brief The unsigned integral type used by the container.
+ typedef typename vt::size_type size_type;
+ //! @brief The pointers difference type.
+ typedef typename vt::difference_type difference_type;
+ //! @brief The pointer type.
+ typedef typename vt::pointer pointer;
+ //! @brief The const pointer type.
+ typedef typename vt::const_pointer const_pointer;
+ //! @brief The value reference type.
+ typedef typename vt::reference reference;
+ //! @brief The value const reference type.
+ typedef typename vt::const_reference const_reference;
+
+ //! @brief The iterator type.
typedef pointer iterator;
+ //! @brief The const iterator type.
typedef const_pointer const_iterator;
+ //! @brief The reverse iterator type.
typedef boost::reverse_iterator<iterator> reverse_iterator;
+ //! @brief The const reverse iterator.
typedef boost::reverse_iterator<const_iterator> const_reverse_iterator;
- // nothrow
+ //! @brief Constructs an empty varray.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
varray()
: m_size(0)
{}
- // strong
+ //! @pre <tt>count <= capacity()</tt>
+ //!
+ //! @brief Constructs a varray containing count default constructed Values.
+ //!
+ //! @param count The number of values which will be contained in the container.
+ //!
+ //! @par Throws
+ //! If Value's default constructor throws.
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Linear O(N).
explicit varray(size_type count)
: m_size(0)
{
- resize(count); // may throw
+ this->resize(count); // may throw
}
- // strong
+ //! @pre <tt>count <= capacity()</tt>
+ //!
+ //! @brief Constructs a varray containing count copies of value.
+ //!
+ //! @param count The number of copies of a values that will be contained in the container.
+ //! @param value The value which will be used to copy construct values.
+ //!
+ //! @par Throws
+ //! If Value's copy constructor throws.
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Linear O(N).
varray(size_type count, value_type const& value)
: m_size(0)
{
- resize(count, value); // may throw
+ this->resize(count, value); // may throw
}
- // strong
- varray(varray const& other)
- : m_size(other.m_size)
+ //! @pre
+ //! @li <tt>distance(first, last) <= capacity()</tt>
+ //! @li Iterator must meet the \c ForwardTraversalIterator concept.
+ //!
+ //! @brief Constructs a varray containing copy of a range <tt>[first, last)</tt>.
+ //!
+ //! @param first The iterator to the first element in range.
+ //! @param last The iterator to the one after the last element in range.
+ //!
+ //! @par Throws
+ //! If Value's constructor taking a dereferenced Iterator throws.
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Linear O(N).
+ template <typename Iterator>
+ varray(Iterator first, Iterator last)
+ : m_size(0)
{
- this->uninitialized_copy(other.begin(), other.end(), this->begin()); // may throw
+ BOOST_CONCEPT_ASSERT((boost_concepts::ForwardTraversal<Iterator>)); // Make sure you passed a ForwardIterator
+
+ this->assign(first, last); // may throw
}
- // strong
- varray(BOOST_RV_REF(varray) other)
- : m_size(other.m_size)
+ //! @brief Constructs a copy of other varray.
+ //!
+ //! @param other The varray which content will be copied to this one.
+ //!
+ //! @par Throws
+ //! If Value's copy constructor throws.
+ //!
+ //! @par Complexity
+ //! Linear O(N).
+ varray(varray const& other)
+ : m_size(other.size())
{
- this->uninitialized_move(other.begin(), other.end(), this->begin()); // may throw
+ namespace sv = varray_detail;
+ sv::uninitialized_copy(other.begin(), other.end(), this->begin()); // may throw
}
- // strong
- template <typename Iterator>
- varray(Iterator first, Iterator last)
- : m_size(0)
+ //! @pre <tt>other.size() <= capacity()</tt>.
+ //!
+ //! @brief Constructs a copy of other varray.
+ //!
+ //! @param other The varray which content will be copied to this one.
+ //!
+ //! @par Throws
+ //! If Value's copy constructor throws.
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Linear O(N).
+ template <std::size_t C>
+ varray(varray<value_type, C> const& other)
+ : m_size(other.size())
{
- assign(first, last); // may throw
+ errh::check_capacity(*this, other.size()); // may throw
+
+ namespace sv = varray_detail;
+ sv::uninitialized_copy(other.begin(), other.end(), this->begin()); // may throw
}
- // basic
+ //! @brief Copy assigns Values stored in the other varray to this one.
+ //!
+ //! @param other The varray which content will be copied to this one.
+ //!
+ //! @par Throws
+ //! If Value's copy constructor or copy assignment throws.
+ //!
+ //! @par Complexity
+ //! Linear O(N).
varray & operator=(BOOST_COPY_ASSIGN_REF(varray) other)
{
- assign(other.begin(), other.end()); // may throw
+ this->assign(other.begin(), other.end()); // may throw
return *this;
}
- // basic
+ //! @pre <tt>other.size() <= capacity()</tt>
+ //!
+ //! @brief Copy assigns Values stored in the other varray to this one.
+ //!
+ //! @param other The varray which content will be copied to this one.
+ //!
+ //! @par Throws
+ //! If Value's copy constructor or copy assignment throws.
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Linear O(N).
+ template <std::size_t C>
+// TEMPORARY WORKAROUND
+#if defined(BOOST_NO_RVALUE_REFERENCES)
+ varray & operator=(::boost::rv< varray<value_type, C> > const& other)
+#else
+ varray & operator=(varray<value_type, C> const& other)
+#endif
+ {
+ this->assign(other.begin(), other.end()); // may throw
+
+ return *this;
+ }
+
+ //! @brief Move constructor. Moves Values stored in the other varray to this one.
+ //!
+ //! @param other The varray which content will be moved to this one.
+ //!
+ //! @par Throws
+ //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor throws.
+ //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor throws.
+ //! @internal
+ //! @li It throws only if \c use_memop_in_swap_and_move is \c false_type - default.
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Linear O(N).
+ varray(BOOST_RV_REF(varray) other)
+ {
+ typedef typename
+ vt::use_memop_in_swap_and_move use_memop_in_swap_and_move;
+
+ this->move_ctor_dispatch(other, use_memop_in_swap_and_move());
+ }
+
+ //! @pre <tt>other.size() <= capacity()</tt>
+ //!
+ //! @brief Move constructor. Moves Values stored in the other varray to this one.
+ //!
+ //! @param other The varray which content will be moved to this one.
+ //!
+ //! @par Throws
+ //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor throws.
+ //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor throws.
+ //! @internal
+ //! @li It throws only if \c use_memop_in_swap_and_move is false_type - default.
+ //! @endinternal
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Linear O(N).
+ template <std::size_t C>
+ varray(BOOST_RV_REF_2_TEMPL_ARGS(varray, value_type, C) other)
+ : m_size(other.m_size)
+ {
+ errh::check_capacity(*this, other.size()); // may throw
+
+ typedef typename
+ vt::use_memop_in_swap_and_move use_memop_in_swap_and_move;
+
+ this->move_ctor_dispatch(other, use_memop_in_swap_and_move());
+ }
+
+ //! @brief Move assignment. Moves Values stored in the other varray to this one.
+ //!
+ //! @param other The varray which content will be moved to this one.
+ //!
+ //! @par Throws
+ //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor or move assignment throws.
+ //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor or copy assignment throws.
+ //! @internal
+ //! @li It throws only if \c use_memop_in_swap_and_move is \c false_type - default.
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Linear O(N).
varray & operator=(BOOST_RV_REF(varray) other)
{
- assign(other.begin(), other.end()); // may throw
+ if ( &other == this )
+ return *this;
+
+ typedef typename
+ vt::use_memop_in_swap_and_move use_memop_in_swap_and_move;
+
+ this->move_assign_dispatch(other, use_memop_in_swap_and_move());
return *this;
}
- // nothrow
+ //! @pre <tt>other.size() <= capacity()</tt>
+ //!
+ //! @brief Move assignment. Moves Values stored in the other varray to this one.
+ //!
+ //! @param other The varray which content will be moved to this one.
+ //!
+ //! @par Throws
+ //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor or move assignment throws.
+ //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor or copy assignment throws.
+ //! @internal
+ //! @li It throws only if \c use_memop_in_swap_and_move is \c false_type - default.
+ //! @endinternal
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Linear O(N).
+ template <std::size_t C>
+ varray & operator=(BOOST_RV_REF_2_TEMPL_ARGS(varray, value_type, C) other)
+ {
+ errh::check_capacity(*this, other.size()); // may throw
+
+ typedef typename
+ vt::use_memop_in_swap_and_move use_memop_in_swap_and_move;
+
+ this->move_assign_dispatch(other, use_memop_in_swap_and_move());
+
+ return *this;
+ }
+
+ //! @brief Destructor. Destroys Values stored in this container.
+ //!
+ //! @par Throws
+ //! Nothing
+ //!
+ //! @par Complexity
+ //! Linear O(N).
~varray()
{
- this->destroy(this->begin(), this->end());
+ namespace sv = varray_detail;
+ sv::destroy(this->begin(), this->end());
}
- // strong
+ //! @brief Swaps contents of the other varray and this one.
+ //!
+ //! @param other The varray which content will be swapped with this one's content.
+ //!
+ //! @par Throws
+ //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor or move assignment throws,
+ //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor or copy assignment throws,
+ //! @internal
+ //! @li It throws only if \c use_memop_in_swap_and_move and \c use_optimized_swap are \c false_type - default.
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Linear O(N).
+ void swap(varray & other)
+ {
+ typedef typename
+ vt::use_optimized_swap use_optimized_swap;
+
+ this->swap_dispatch(other, use_optimized_swap());
+ }
+
+ //! @pre <tt>other.size() <= capacity() && size() <= other.capacity()</tt>
+ //!
+ //! @brief Swaps contents of the other varray and this one.
+ //!
+ //! @param other The varray which content will be swapped with this one's content.
+ //!
+ //! @par Throws
+ //! @li If \c boost::has_nothrow_move<Value>::value is \c true and Value's move constructor or move assignment throws,
+ //! @li If \c boost::has_nothrow_move<Value>::value is \c false and Value's copy constructor or copy assignment throws,
+ //! @internal
+ //! @li It throws only if \c use_memop_in_swap_and_move and \c use_optimized_swap are \c false_type - default.
+ //! @endinternal
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Linear O(N).
+ template <std::size_t C>
+ void swap(varray<value_type, C> & other)
+ {
+ errh::check_capacity(*this, other.size());
+ errh::check_capacity(other, this->size());
+
+ typedef typename
+ vt::use_optimized_swap use_optimized_swap;
+
+ this->swap_dispatch(other, use_optimized_swap());
+ }
+
+ //! @pre <tt>count <= capacity()</tt>
+ //!
+ //! @brief Inserts or erases elements at the end such that
+ //! the size becomes count. New elements are default constructed.
+ //!
+ //! @param count The number of elements which will be stored in the container.
+ //!
+ //! @par Throws
+ //! If Value's default constructor throws.
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Linear O(N).
void resize(size_type count)
{
+ namespace sv = varray_detail;
+ typedef typename vt::disable_trivial_init dti;
+
if ( count < m_size )
{
- this->destroy(this->begin() + count, this->end());
+ sv::destroy(this->begin() + count, this->end());
}
else
{
- check_capacity(count);
+ errh::check_capacity(*this, count); // may throw
- this->construct(this->end(), this->begin() + count); // may throw
+ sv::uninitialized_fill(this->end(), this->begin() + count, dti()); // may throw
}
m_size = count; // update end
}
- // strong
+ //! @pre <tt>count <= capacity()</tt>
+ //!
+ //! @brief Inserts or erases elements at the end such that
+ //! the size becomes count. New elements are copy constructed from value.
+ //!
+ //! @param count The number of elements which will be stored in the container.
+ //! @param value The value used to copy construct the new element.
+ //!
+ //! @par Throws
+ //! If Value's copy constructor throws.
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Linear O(N).
void resize(size_type count, value_type const& value)
{
if ( count < m_size )
{
- this->destroy(this->begin() + count, this->end());
+ namespace sv = varray_detail;
+ sv::destroy(this->begin() + count, this->end());
}
else
{
- check_capacity(count);
+ errh::check_capacity(*this, count); // may throw
std::uninitialized_fill(this->end(), this->begin() + count, value); // may throw
}
m_size = count; // update end
}
- // nothrow
+ //! @pre <tt>count <= capacity()</tt>
+ //!
+ //! @brief This call has no effect because the Capacity of this container is constant.
+ //!
+ //! @param count The number of elements which the container should be able to contain.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Linear O(N).
void reserve(size_type count)
{
- check_capacity(count);
+ errh::check_capacity(*this, count); // may throw
}
- // strong
+ //! @pre <tt>size() < capacity()</tt>
+ //!
+ //! @brief Adds a copy of value at the end.
+ //!
+ //! @param value The value used to copy construct the new element.
+ //!
+ //! @par Throws
+ //! If Value's copy constructor throws.
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Constant O(1).
void push_back(value_type const& value)
{
- check_capacity(m_size + 1);
+ typedef typename vt::disable_trivial_init dti;
+
+ errh::check_capacity(*this, m_size + 1); // may throw
- this->uninitialized_fill(this->end(), value); // may throw
+ namespace sv = varray_detail;
+ sv::construct(dti(), this->end(), value); // may throw
++m_size; // update end
}
+ //! @pre <tt>size() < capacity()</tt>
+ //!
+ //! @brief Moves value to the end.
+ //!
+ //! @param value The value to move construct the new element.
+ //!
+ //! @par Throws
+ //! If Value's move constructor throws.
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Constant O(1).
void push_back(BOOST_RV_REF(value_type) value)
{
- check_capacity(m_size + 1);
+ typedef typename vt::disable_trivial_init dti;
+
+ errh::check_capacity(*this, m_size + 1); // may throw
- this->uninitialized_fill(this->end(), value); // may throw
+ namespace sv = varray_detail;
+ sv::construct(dti(), this->end(), ::boost::move(value)); // may throw
++m_size; // update end
}
- // nothrow
+ //! @pre <tt>!empty()</tt>
+ //!
+ //! @brief Destroys last value and decreases the size.
+ //!
+ //! @par Throws
+ //! Nothing by default.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
void pop_back()
{
- check_empty();
+ errh::check_not_empty(*this);
- //--m_size; // update end
- //this->destroy(this->end());
-
- // safer and more intuitive version
- this->destroy(this->end() - 1);
+ namespace sv = varray_detail;
+ sv::destroy(this->end() - 1);
--m_size; // update end
}
- // basic
- void insert(iterator position, value_type const& value)
+ //! @pre
+ //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>.
+ //! @li <tt>size() < capacity()</tt>
+ //!
+ //! @brief Inserts a copy of element at position.
+ //!
+ //! @param position The position at which the new value will be inserted.
+ //! @param value The value used to copy construct the new element.
+ //!
+ //! @par Throws
+ //! @li If Value's copy constructor or copy assignment throws
+ //! @li If Value's move constructor or move assignment throws.
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Constant or linear.
+ iterator insert(iterator position, value_type const& value)
{
- check_iterator_end_eq(position);
- check_capacity(m_size + 1);
+ typedef typename vt::disable_trivial_init dti;
+ namespace sv = varray_detail;
+
+ errh::check_iterator_end_eq(*this, position);
+ errh::check_capacity(*this, m_size + 1); // may throw
if ( position == this->end() )
{
- this->uninitialized_fill(position, value); // may throw
+ sv::construct(dti(), position, value); // may throw
++m_size; // update end
}
else
{
- // TODO - should following lines check for exception and revert to the old size?
+ // TODO - should move be used only if it's nonthrowing?
+ value_type & r = *(this->end() - 1);
+ sv::construct(dti(), this->end(), boost::move(r)); // may throw
+ ++m_size; // update end
+ sv::move_backward(position, this->end() - 2, this->end() - 1); // may throw
+ sv::assign(position, value); // may throw
+ }
- this->uninitialized_fill(this->end(), *(this->end() - 1)); // may throw
+ return position;
+ }
+
+ //! @pre
+ //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>.
+ //! @li <tt>size() < capacity()</tt>
+ //!
+ //! @brief Inserts a move-constructed element at position.
+ //!
+ //! @param position The position at which the new value will be inserted.
+ //! @param value The value used to move construct the new element.
+ //!
+ //! @par Throws
+ //! If Value's move constructor or move assignment throws.
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Constant or linear.
+ iterator insert(iterator position, BOOST_RV_REF(value_type) value)
+ {
+ typedef typename vt::disable_trivial_init dti;
+ namespace sv = varray_detail;
+
+ errh::check_iterator_end_eq(*this, position);
+ errh::check_capacity(*this, m_size + 1); // may throw
+
+ if ( position == this->end() )
+ {
+ sv::construct(dti(), position, boost::move(value)); // may throw
++m_size; // update end
- this->move_backward(position, this->end() - 2, this->end() - 1); // may throw
- this->fill(position, value); // may throw
}
+ else
+ {
+ // TODO - should move be used only if it's nonthrowing?
+ value_type & r = *(this->end() - 1);
+ sv::construct(dti(), this->end(), boost::move(r)); // may throw
+ ++m_size; // update end
+ sv::move_backward(position, this->end() - 2, this->end() - 1); // may throw
+ sv::assign(position, boost::move(value)); // may throw
+ }
+
+ return position;
}
- // basic
- void insert(iterator position, size_type count, value_type const& value)
+ //! @pre
+ //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>.
+ //! @li <tt>size() + count <= capacity()</tt>
+ //!
+ //! @brief Inserts a count copies of value at position.
+ //!
+ //! @param position The position at which new elements will be inserted.
+ //! @param count The number of new elements which will be inserted.
+ //! @param value The value used to copy construct new elements.
+ //!
+ //! @par Throws
+ //! @li If Value's copy constructor or copy assignment throws.
+ //! @li If Value's move constructor or move assignment throws.
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Linear O(N).
+ iterator insert(iterator position, size_type count, value_type const& value)
{
- check_iterator_end_eq(position);
- check_capacity(m_size + count);
+ errh::check_iterator_end_eq(*this, position);
+ errh::check_capacity(*this, m_size + count); // may throw
if ( position == this->end() )
{
@@ -235,658 +799,1394 @@
}
else
{
+ namespace sv = varray_detail;
+
difference_type to_move = std::distance(position, this->end());
// TODO - should following lines check for exception and revert to the old size?
if ( count < static_cast<size_type>(to_move) )
{
- this->uninitialized_copy(this->end() - count, this->end(), this->end()); // may throw
+ sv::uninitialized_move(this->end() - count, this->end(), this->end()); // may throw
m_size += count; // update end
- this->move_backward(position, position + to_move - count, this->end() - count); // may throw
- std::fill_n(position, count, value); // may throw
+ sv::move_backward(position, position + to_move - count, this->end() - count); // may throw
+ std::fill_n(position, count, value); // may throw
}
else
{
- std::uninitialized_fill(this->end(), position + count, value); // may throw
+ std::uninitialized_fill(this->end(), position + count, value); // may throw
m_size += count - to_move; // update end
- this->uninitialized_copy(position, position + to_move, position + count); // may throw
+ sv::uninitialized_move(position, position + to_move, position + count); // may throw
m_size += to_move; // update end
- std::fill_n(position, to_move, value); // may throw
+ std::fill_n(position, to_move, value); // may throw
}
}
+
+ return position;
}
- // basic
+ //! @pre
+ //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>.
+ //! @li <tt>distance(first, last) <= capacity()</tt>
+ //! @li \c Iterator must meet the \c ForwardTraversalIterator concept.
+ //!
+ //! @brief Inserts a copy of a range <tt>[first, last)</tt> at position.
+ //!
+ //! @param position The position at which new elements will be inserted.
+ //! @param first The iterator to the first element of a range used to construct new elements.
+ //! @param last The iterator to the one after the last element of a range used to construct new elements.
+ //!
+ //! @par Throws
+ //! @li If Value's constructor and assignment taking a dereferenced \c Iterator.
+ //! @li If Value's move constructor or move assignment throws.
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Linear O(N).
template <typename Iterator>
- void insert(iterator position, Iterator first, Iterator last)
+ iterator insert(iterator position, Iterator first, Iterator last)
{
+ BOOST_CONCEPT_ASSERT((boost_concepts::ForwardTraversal<Iterator>)); // Make sure you passed a ForwardIterator
+
typedef typename boost::iterator_traversal<Iterator>::type traversal;
this->insert_dispatch(position, first, last, traversal());
+
+ return position;
}
- // basic
- void erase(iterator position)
- {
- check_iterator_end_neq(position);
+ //! @pre \c position must be a valid iterator of \c *this in range <tt>[begin(), end())</tt>
+ //!
+ //! @brief Erases Value from position.
+ //!
+ //! @param position The position of the element which will be erased from the container.
+ //!
+ //! @par Throws
+ //! If Value's move assignment throws.
+ //!
+ //! @par Complexity
+ //! Linear O(N).
+ iterator erase(iterator position)
+ {
+ namespace sv = varray_detail;
+
+ errh::check_iterator_end_neq(*this, position);
- this->move(position + 1, this->end(), position); // may throw
- this->destroy(this->end() - 1);
+ //TODO - add empty check?
+ //errh::check_empty(*this);
+
+ sv::move(position + 1, this->end(), position); // may throw
+ sv::destroy(this->end() - 1);
--m_size;
+
+ return position;
}
- // basic
- void erase(iterator first, iterator last)
+ //! @pre
+ //! @li \c first and \c last must define a valid range
+ //! @li iterators must be in range <tt>[begin(), end()]</tt>
+ //!
+ //! @brief Erases Values from a range <tt>[first, last)</tt>.
+ //!
+ //! @param first The position of the first element of a range which will be erased from the container.
+ //! @param last The position of the one after the last element of a range which will be erased from the container.
+ //!
+ //! @par Throws
+ //! If Value's move assignment throws.
+ //!
+ //! @par Complexity
+ //! Linear O(N).
+ iterator erase(iterator first, iterator last)
{
- check_iterator_end_eq(first);
- check_iterator_end_eq(last);
+ namespace sv = varray_detail;
+
+ errh::check_iterator_end_eq(*this, first);
+ errh::check_iterator_end_eq(*this, last);
difference_type n = std::distance(first, last);
- BOOST_ASSERT_MSG(0 <= n, "invalid range");
+
+ //TODO - add invalid range check?
+ //BOOST_ASSERT_MSG(0 <= n, "invalid range");
+ //TODO - add this->size() check?
+ //BOOST_ASSERT_MSG(n <= this->size(), "invalid range");
- this->move(last, this->end(), first); // may throw
- this->destroy(this->end() - n, this->end());
+ sv::move(last, this->end(), first); // may throw
+ sv::destroy(this->end() - n, this->end());
m_size -= n;
+
+ return first;
}
- // basic
+ //! @pre <tt>distance(first, last) <= capacity()</tt>
+ //!
+ //! @brief Assigns a range <tt>[first, last)</tt> of Values to this container.
+ //!
+ //! @param first The iterator to the first element of a range used to construct new content of this container.
+ //! @param last The iterator to the one after the last element of a range used to construct new content of this container.
+ //!
+ //! @par Throws
+ //! If Value's copy constructor or copy assignment throws,
+ //!
+ //! @par Complexity
+ //! Linear O(N).
template <typename Iterator>
void assign(Iterator first, Iterator last)
{
+ BOOST_CONCEPT_ASSERT((boost_concepts::ForwardTraversal<Iterator>)); // Make sure you passed a ForwardIterator
+
typedef typename boost::iterator_traversal<Iterator>::type traversal;
this->assign_dispatch(first, last, traversal()); // may throw
}
- // basic
+ //! @pre <tt>count <= capacity()</tt>
+ //!
+ //! @brief Assigns a count copies of value to this container.
+ //!
+ //! @param count The new number of elements which will be container in the container.
+ //! @param value The value which will be used to copy construct the new content.
+ //!
+ //! @par Throws
+ //! If Value's copy constructor or copy assignment throws.
+ //!
+ //! @par Complexity
+ //! Linear O(N).
void assign(size_type count, value_type const& value)
{
if ( count < m_size )
{
- std::fill_n(this->begin(), count, value);
- this->destroy(this->begin() + count, this->end());
+ namespace sv = varray_detail;
+
+ std::fill_n(this->begin(), count, value); // may throw
+ sv::destroy(this->begin() + count, this->end());
}
else
{
- check_capacity(count);
+ errh::check_capacity(*this, count); // may throw
- std::fill_n(this->begin(), m_size, value);
+ std::fill_n(this->begin(), m_size, value); // may throw
std::uninitialized_fill(this->end(), this->begin() + count, value); // may throw
}
m_size = count; // update end
}
- // nothrow
+#if !defined(BOOST_CONTAINER_VARRAY_DISABLE_EMPLACE)
+#if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+ //! @pre <tt>size() < capacity()</tt>
+ //!
+ //! @brief Inserts a Value constructed with
+ //! \c std::forward<Args>(args)... in the end of the container.
+ //!
+ //! @param args The arguments of the constructor of the new element which will be created at the end of the container.
+ //!
+ //! @par Throws
+ //! If in-place constructor throws or Value's move constructor throws.
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Constant O(1).
+ template<class ...Args>
+ void emplace_back(BOOST_FWD_REF(Args) ...args)
+ {
+ typedef typename vt::disable_trivial_init dti;
+
+ errh::check_capacity(*this, m_size + 1); // may throw
+
+ namespace sv = varray_detail;
+ sv::construct(dti(), this->end(), ::boost::forward<Args>(args)...); // may throw
+ ++m_size; // update end
+ }
+
+ //! @pre
+ //! @li \c position must be a valid iterator of \c *this in range <tt>[begin(), end()]</tt>
+ //! @li <tt>size() < capacity()</tt>
+ //!
+ //! @brief Inserts a Value constructed with
+ //! \c std::forward<Args>(args)... before position
+ //!
+ //! @param position The position at which new elements will be inserted.
+ //! @param args The arguments of the constructor of the new element.
+ //!
+ //! @par Throws
+ //! If in-place constructor throws or if Value's move constructor or move assignment throws.
+ //! @internal
+ //! @li If a throwing error handler is specified, throws when the capacity is exceeded. (not by default).
+ //! @endinternal
+ //!
+ //! @par Complexity
+ //! Constant or linear.
+ template<class ...Args>
+ iterator emplace(iterator position, BOOST_FWD_REF(Args) ...args)
+ {
+ typedef typename vt::disable_trivial_init dti;
+
+ namespace sv = varray_detail;
+
+ errh::check_iterator_end_eq(*this, position);
+ errh::check_capacity(*this, m_size + 1); // may throw
+
+ if ( position == this->end() )
+ {
+ sv::construct(dti(), position, ::boost::forward<Args>(args)...); // may throw
+ ++m_size; // update end
+ }
+ else
+ {
+ // TODO - should following lines check for exception and revert to the old size?
+
+ // TODO - should move be used only if it's nonthrowing?
+ value_type & r = *(this->end() - 1);
+ sv::construct(dti(), this->end(), boost::move(r)); // may throw
+ ++m_size; // update end
+ sv::move_backward(position, this->end() - 2, this->end() - 1); // may throw
+
+ aligned_storage<sizeof(value_type), alignment_of<value_type>::value> temp_storage;
+ value_type * val_p = static_cast<value_type *>(temp_storage.address());
+ sv::construct(dti(), val_p, ::boost::forward<Args>(args)...); // may throw
+ sv::scoped_destructor<value_type> d(val_p);
+ sv::assign(position, ::boost::move(*val_p)); // may throw
+ }
+
+ return position;
+ }
+
+#else // BOOST_CONTAINER_PERFECT_FORWARDING || BOOST_CONTAINER_DOXYGEN_INVOKED
+
+ #define BOOST_PP_LOCAL_MACRO(n) \
+ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
+ void emplace_back(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { \
+ typedef typename vt::disable_trivial_init dti; \
+ \
+ errh::check_capacity(*this, m_size + 1); /*may throw*/\
+ \
+ namespace sv = varray_detail; \
+ sv::construct(dti(), this->end() BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) ); /*may throw*/\
+ ++m_size; /*update end*/ \
+ } \
+ //
+ #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
+ #include BOOST_PP_LOCAL_ITERATE()
+
+ #define BOOST_PP_LOCAL_MACRO(n) \
+ BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
+ iterator emplace(iterator position BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+ { \
+ typedef typename vt::disable_trivial_init dti; \
+ namespace sv = varray_detail; \
+ \
+ errh::check_iterator_end_eq(*this, position); \
+ errh::check_capacity(*this, m_size + 1); /*may throw*/\
+ \
+ if ( position == this->end() ) \
+ { \
+ sv::construct(dti(), position BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) ); /*may throw*/\
+ ++m_size; /*update end*/ \
+ } \
+ else \
+ { \
+ /* TODO - should following lines check for exception and revert to the old size? */ \
+ /* TODO - should move be used only if it's nonthrowing? */ \
+ \
+ value_type & r = *(this->end() - 1); \
+ sv::construct(dti(), this->end(), boost::move(r)); /*may throw*/\
+ ++m_size; /*update end*/ \
+ sv::move_backward(position, this->end() - 2, this->end() - 1); /*may throw*/\
+ \
+ aligned_storage<sizeof(value_type), alignment_of<value_type>::value> temp_storage; \
+ value_type * val_p = static_cast<value_type *>(temp_storage.address()); \
+ sv::construct(dti(), val_p BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) ); /*may throw*/\
+ sv::scoped_destructor<value_type> d(val_p); \
+ sv::assign(position, ::boost::move(*val_p)); /*may throw*/\
+ } \
+ \
+ return position; \
+ } \
+ //
+ #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
+ #include BOOST_PP_LOCAL_ITERATE()
+
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING || BOOST_CONTAINER_DOXYGEN_INVOKED
+#endif // !BOOST_CONTAINER_VARRAY_DISABLE_EMPLACE
+
+ //! @brief Removes all elements from the container.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
void clear()
{
- this->destroy(this->begin(), this->end());
+ namespace sv = varray_detail;
+ sv::destroy(this->begin(), this->end());
m_size = 0; // update end
}
- // strong
- Value & at(size_type i)
+ //! @pre <tt>i < size()</tt>
+ //!
+ //! @brief Returns reference to the i-th element.
+ //!
+ //! @param i The element's index.
+ //!
+ //! @return reference to the i-th element
+ //! from the beginning of the container.
+ //!
+ //! @par Throws
+ //! \c std::out_of_range exception by default.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
+ reference at(size_type i)
{
- if ( m_size <= i )
- throw std::out_of_range("index out of bounds");
+ errh::throw_out_of_bounds(*this, i); // may throw
return *(this->begin() + i);
}
- // strong
- Value const& at(size_type i) const
+ //! @pre <tt>i < size()</tt>
+ //!
+ //! @brief Returns const reference to the i-th element.
+ //!
+ //! @param i The element's index.
+ //!
+ //! @return const reference to the i-th element
+ //! from the beginning of the container.
+ //!
+ //! @par Throws
+ //! \c std::out_of_range exception by default.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
+ const_reference at(size_type i) const
{
- if ( m_size <= i )
- throw std::out_of_range("index out of bounds");
+ errh::throw_out_of_bounds(*this, i); // may throw
return *(this->begin() + i);
}
- // nothrow
- Value & operator[](size_type i)
+ //! @pre <tt>i < size()</tt>
+ //!
+ //! @brief Returns reference to the i-th element.
+ //!
+ //! @param i The element's index.
+ //!
+ //! @return reference to the i-th element
+ //! from the beginning of the container.
+ //!
+ //! @par Throws
+ //! Nothing by default.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
+ reference operator[](size_type i)
{
- BOOST_ASSERT_MSG(i < m_size, "index out of bounds");
+ // TODO: Remove bounds check? std::vector and std::array operator[] don't check.
+ errh::check_index(*this, i);
return *(this->begin() + i);
}
- // nothrow
- Value const& operator[](size_type i) const
+ //! @pre <tt>i < size()</tt>
+ //!
+ //! @brief Returns const reference to the i-th element.
+ //!
+ //! @param i The element's index.
+ //!
+ //! @return const reference to the i-th element
+ //! from the beginning of the container.
+ //!
+ //! @par Throws
+ //! Nothing by default.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
+ const_reference operator[](size_type i) const
{
- BOOST_ASSERT_MSG(i < m_size, "index out of bounds");
+ errh::check_index(*this, i);
return *(this->begin() + i);
}
- // nothrow
- Value & front()
+ //! @pre \c !empty()
+ //!
+ //! @brief Returns reference to the first element.
+ //!
+ //! @return reference to the first element
+ //! from the beginning of the container.
+ //!
+ //! @par Throws
+ //! Nothing by default.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
+ reference front()
{
- check_empty();
+ errh::check_not_empty(*this);
return *(this->begin());
}
- // nothrow
- Value const& front() const
+ //! @pre \c !empty()
+ //!
+ //! @brief Returns const reference to the first element.
+ //!
+ //! @return const reference to the first element
+ //! from the beginning of the container.
+ //!
+ //! @par Throws
+ //! Nothing by default.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
+ const_reference front() const
{
- check_empty();
+ errh::check_not_empty(*this);
return *(this->begin());
}
- // nothrow
- Value & back()
+ //! @pre \c !empty()
+ //!
+ //! @brief Returns reference to the last element.
+ //!
+ //! @return reference to the last element
+ //! from the beginning of the container.
+ //!
+ //! @par Throws
+ //! Nothing by default.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
+ reference back()
{
- check_empty();
+ errh::check_not_empty(*this);
return *(this->end() - 1);
}
- // nothrow
- Value const& back() const
+ //! @pre \c !empty()
+ //!
+ //! @brief Returns const reference to the first element.
+ //!
+ //! @return const reference to the last element
+ //! from the beginning of the container.
+ //!
+ //! @par Throws
+ //! Nothing by default.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
+ const_reference back() const
{
- check_empty();
+ errh::check_not_empty(*this);
return *(this->end() - 1);
}
- // nothrow
- Value * data() { return this->ptr(); }
- const Value * data() const { return this->ptr(); }
-
- // nothrow
+ //! @brief Pointer such that <tt>[data(), data() + size())</tt> is a valid range.
+ //! For a non-empty vector <tt>data() == &front()</tt>.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
+ Value * data()
+ {
+ return boost::addressof(*(this->ptr()));
+ }
+
+ //! @brief Const pointer such that <tt>[data(), data() + size())</tt> is a valid range.
+ //! For a non-empty vector <tt>data() == &front()</tt>.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
+ const Value * data() const
+ {
+ return boost::addressof(*(this->ptr()));
+ }
+
+
+ //! @brief Returns iterator to the first element.
+ //!
+ //! @return iterator to the first element contained in the vector.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
iterator begin() { return this->ptr(); }
+
+ //! @brief Returns const iterator to the first element.
+ //!
+ //! @return const_iterator to the first element contained in the vector.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
const_iterator begin() const { return this->ptr(); }
+
+ //! @brief Returns const iterator to the first element.
+ //!
+ //! @return const_iterator to the first element contained in the vector.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
const_iterator cbegin() const { return this->ptr(); }
+
+ //! @brief Returns iterator to the one after the last element.
+ //!
+ //! @return iterator pointing to the one after the last element contained in the vector.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
iterator end() { return this->begin() + m_size; }
+
+ //! @brief Returns const iterator to the one after the last element.
+ //!
+ //! @return const_iterator pointing to the one after the last element contained in the vector.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
const_iterator end() const { return this->begin() + m_size; }
+
+ //! @brief Returns const iterator to the one after the last element.
+ //!
+ //! @return const_iterator pointing to the one after the last element contained in the vector.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
const_iterator cend() const { return this->cbegin() + m_size; }
- // nothrow
+
+ //! @brief Returns reverse iterator to the first element of the reversed container.
+ //!
+ //! @return reverse_iterator pointing to the beginning
+ //! of the reversed varray.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
reverse_iterator rbegin() { return reverse_iterator(this->end()); }
+
+ //! @brief Returns const reverse iterator to the first element of the reversed container.
+ //!
+ //! @return const_reverse_iterator pointing to the beginning
+ //! of the reversed varray.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
const_reverse_iterator rbegin() const { return reverse_iterator(this->end()); }
+
+ //! @brief Returns const reverse iterator to the first element of the reversed container.
+ //!
+ //! @return const_reverse_iterator pointing to the beginning
+ //! of the reversed varray.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
const_reverse_iterator crbegin() const { return reverse_iterator(this->end()); }
+
+ //! @brief Returns reverse iterator to the one after the last element of the reversed container.
+ //!
+ //! @return reverse_iterator pointing to the one after the last element
+ //! of the reversed varray.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
reverse_iterator rend() { return reverse_iterator(this->begin()); }
+
+ //! @brief Returns const reverse iterator to the one after the last element of the reversed container.
+ //!
+ //! @return const_reverse_iterator pointing to the one after the last element
+ //! of the reversed varray.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
const_reverse_iterator rend() const { return reverse_iterator(this->begin()); }
+
+ //! @brief Returns const reverse iterator to the one after the last element of the reversed container.
+ //!
+ //! @return const_reverse_iterator pointing to the one after the last element
+ //! of the reversed varray.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
const_reverse_iterator crend() const { return reverse_iterator(this->begin()); }
- // nothrow
+ //! @brief Returns container's capacity.
+ //!
+ //! @return container's capacity.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
static size_type capacity() { return Capacity; }
+
+ //! @brief Returns container's capacity.
+ //!
+ //! @return container's capacity.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
static size_type max_size() { return Capacity; }
+
+ //! @brief Returns the number of stored elements.
+ //!
+ //! @return Number of elements contained in the container.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
size_type size() const { return m_size; }
+
+ //! @brief Queries if the container contains elements.
+ //!
+ //! @return true if the number of elements contained in the
+ //! container is equal to 0.
+ //!
+ //! @par Throws
+ //! Nothing.
+ //!
+ //! @par Complexity
+ //! Constant O(1).
bool empty() const { return 0 == m_size; }
private:
+ // @par Throws
+ // Nothing.
+ // @par Complexity
+ // Linear O(N).
+ template <std::size_t C>
+ void move_ctor_dispatch(varray<value_type, C> & other, boost::true_type /*use_memop*/)
+ {
+ ::memcpy(this->data(), other.data(), sizeof(Value) * other.m_size);
+ m_size = other.m_size;
+ }
+
+ // @par Throws
+ // @li If boost::has_nothrow_move<Value>::value is true and Value's move constructor throws
+ // @li If boost::has_nothrow_move<Value>::value is false and Value's copy constructor throws.
+ // @par Complexity
+ // Linear O(N).
+ template <std::size_t C>
+ void move_ctor_dispatch(varray<value_type, C> & other, boost::false_type /*use_memop*/)
+ {
+ namespace sv = varray_detail;
+ sv::uninitialized_move_if_noexcept(other.begin(), other.end(), this->begin()); // may throw
+ m_size = other.m_size;
+ }
+
+ // @par Throws
+ // Nothing.
+ // @par Complexity
+ // Linear O(N).
+ template <std::size_t C>
+ void move_assign_dispatch(varray<value_type, C> & other, boost::true_type /*use_memop*/)
+ {
+ this->clear();
+
+ ::memcpy(this->data(), other.data(), sizeof(Value) * other.m_size);
+ boost::swap(m_size, other.m_size);
+ }
+
+ // @par Throws
+ // @li If boost::has_nothrow_move<Value>::value is true and Value's move constructor or move assignment throws
+ // @li If boost::has_nothrow_move<Value>::value is false and Value's copy constructor or move assignment throws.
+ // @par Complexity
+ // Linear O(N).
+ template <std::size_t C>
+ void move_assign_dispatch(varray<value_type, C> & other, boost::false_type /*use_memop*/)
+ {
+ namespace sv = varray_detail;
+ if ( m_size <= static_cast<size_type>(other.size()) )
+ {
+ sv::move_if_noexcept(other.begin(), other.begin() + m_size, this->begin()); // may throw
+ // TODO - perform uninitialized_copy first?
+ sv::uninitialized_move_if_noexcept(other.begin() + m_size, other.end(), this->end()); // may throw
+ }
+ else
+ {
+ sv::move_if_noexcept(other.begin(), other.end(), this->begin()); // may throw
+ sv::destroy(this->begin() + other.size(), this->end());
+ }
+ m_size = other.size(); // update end
+ }
+
+ // @par Throws
+ // Nothing.
+ // @par Complexity
+ // Linear O(N).
+ template <std::size_t C>
+ void swap_dispatch(varray<value_type, C> & other, boost::true_type const& /*use_optimized_swap*/)
+ {
+ typedef typename
+ boost::mpl::if_c<
+ Capacity < C,
+ aligned_storage_type,
+ typename varray<value_type, C>::aligned_storage_type
+ >::type
+ storage_type;
+
+ storage_type temp;
+ Value * temp_ptr = reinterpret_cast<Value*>(temp.address());
+
+ ::memcpy(temp_ptr, this->data(), sizeof(Value) * this->size());
+ ::memcpy(this->data(), other.data(), sizeof(Value) * other.size());
+ ::memcpy(other.data(), temp_ptr, sizeof(Value) * this->size());
+
+ boost::swap(m_size, other.m_size);
+ }
+
+ // @par Throws
+ // If Value's move constructor or move assignment throws
+ // but only if use_memop_in_swap_and_move is false_type - default.
+ // @par Complexity
+ // Linear O(N).
+ template <std::size_t C>
+ void swap_dispatch(varray<value_type, C> & other, boost::false_type const& /*use_optimized_swap*/)
+ {
+ namespace sv = varray_detail;
+
+ typedef typename
+ vt::use_memop_in_swap_and_move use_memop_in_swap_and_move;
+
+ if ( this->size() < other.size() )
+ swap_dispatch_impl(this->begin(), this->end(), other.begin(), other.end(), use_memop_in_swap_and_move()); // may throw
+ else
+ swap_dispatch_impl(other.begin(), other.end(), this->begin(), this->end(), use_memop_in_swap_and_move()); // may throw
+ boost::swap(m_size, other.m_size);
+ }
+
+ // @par Throws
+ // Nothing.
+ // @par Complexity
+ // Linear O(N).
+ void swap_dispatch_impl(iterator first_sm, iterator last_sm, iterator first_la, iterator last_la, boost::true_type const& /*use_memop*/)
+ {
+ //BOOST_ASSERT_MSG(std::distance(first_sm, last_sm) <= std::distance(first_la, last_la));
+
+ namespace sv = varray_detail;
+ for (; first_sm != last_sm ; ++first_sm, ++first_la)
+ {
+ boost::aligned_storage<
+ sizeof(value_type),
+ boost::alignment_of<value_type>::value
+ > temp_storage;
+ value_type * temp_ptr = reinterpret_cast<value_type*>(temp_storage.address());
+
+ ::memcpy(temp_ptr, boost::addressof(*first_sm), sizeof(value_type));
+ ::memcpy(boost::addressof(*first_sm), boost::addressof(*first_la), sizeof(value_type));
+ ::memcpy(boost::addressof(*first_la), temp_ptr, sizeof(value_type));
+ }
+
+ ::memcpy(first_sm, first_la, sizeof(value_type) * std::distance(first_la, last_la));
+ }
+
+ // @par Throws
+ // If Value's move constructor or move assignment throws.
+ // @par Complexity
+ // Linear O(N).
+ void swap_dispatch_impl(iterator first_sm, iterator last_sm, iterator first_la, iterator last_la, boost::false_type const& /*use_memop*/)
+ {
+ //BOOST_ASSERT_MSG(std::distance(first_sm, last_sm) <= std::distance(first_la, last_la));
+
+ namespace sv = varray_detail;
+ for (; first_sm != last_sm ; ++first_sm, ++first_la)
+ {
+ //boost::swap(*first_sm, *first_la); // may throw
+ value_type temp(boost::move(*first_sm)); // may throw
+ *first_sm = boost::move(*first_la); // may throw
+ *first_la = boost::move(temp); // may throw
+ }
+ sv::uninitialized_move(first_la, last_la, first_sm); // may throw
+ sv::destroy(first_la, last_la);
+ }
+
// insert
+ // @par Throws
+ // If Value's move constructor, move assignment throws
+ // or if Value's copy constructor or copy assignment throws.
+ // @par Complexity
+ // Linear O(N).
template <typename Iterator>
void insert_dispatch(iterator position, Iterator first, Iterator last, boost::random_access_traversal_tag const&)
{
- check_iterator_end_eq(position);
+ BOOST_CONCEPT_ASSERT((boost_concepts::RandomAccessTraversal<Iterator>)); // Make sure you passed a RandomAccessIterator
- difference_type count = std::distance(first, last);
+ errh::check_iterator_end_eq(*this, position);
+
+ typename boost::iterator_difference<Iterator>::type
+ count = std::distance(first, last);
- check_capacity(m_size + count);
+ errh::check_capacity(*this, m_size + count); // may throw
if ( position == this->end() )
{
- this->uninitialized_copy(first, last, position); // may throw
+ namespace sv = varray_detail;
+
+ sv::uninitialized_copy(first, last, position); // may throw
m_size += count; // update end
}
else
{
- this->insert_in_the_middle(position, first, last, count); // may throw
+ this->insert_in_the_middle(position, first, last, count); // may throw
}
}
+ // @par Throws
+ // If Value's move constructor, move assignment throws
+ // or if Value's copy constructor or copy assignment throws.
+ // @par Complexity
+ // Linear O(N).
template <typename Iterator, typename Traversal>
void insert_dispatch(iterator position, Iterator first, Iterator last, Traversal const& /*not_random_access*/)
{
- check_iterator_end_eq(position);
+ errh::check_iterator_end_eq(*this, position);
if ( position == this->end() )
{
- std::pair<bool, size_type> copy_data =
- this->uninitialized_copy_checked(first, last, position, std::distance(position, this->begin() + Capacity)); // may throw
+ namespace sv = varray_detail;
+
+ std::ptrdiff_t d = std::distance(position, this->begin() + Capacity);
+ std::size_t count = sv::uninitialized_copy_s(first, last, position, d); // may throw
- check_capacity(copy_data.first ? m_size + copy_data.second : Capacity + 1);
+ errh::check_capacity(*this, count <= static_cast<std::size_t>(d) ? m_size + count : Capacity + 1); // may throw
- m_size += copy_data.second;
+ m_size += count;
}
else
{
- difference_type count = std::distance(first, last);
+ typename boost::iterator_difference<Iterator>::type
+ count = std::distance(first, last);
- check_capacity(m_size + count);
+ errh::check_capacity(*this, m_size + count); // may throw
- this->insert_in_the_middle(position, first, last, count); // may throw
+ this->insert_in_the_middle(position, first, last, count); // may throw
}
}
+ // @par Throws
+ // If Value's move constructor, move assignment throws
+ // or if Value's copy constructor or copy assignment throws.
+ // @par Complexity
+ // Linear O(N).
template <typename Iterator>
void insert_in_the_middle(iterator position, Iterator first, Iterator last, difference_type count)
{
+ namespace sv = varray_detail;
+
difference_type to_move = std::distance(position, this->end());
// TODO - should following lines check for exception and revert to the old size?
if ( count < to_move )
{
- this->uninitialized_copy(this->end() - count, this->end(), this->end()); // may throw
+ sv::uninitialized_move(this->end() - count, this->end(), this->end()); // may throw
m_size += count; // update end
- this->move_backward(position, position + to_move - count, this->end() - count); // may throw
- this->copy(first, last, position); // may throw
+ sv::move_backward(position, position + to_move - count, this->end() - count); // may throw
+ sv::copy(first, last, position); // may throw
}
else
{
Iterator middle_iter = first;
std::advance(middle_iter, to_move);
- this->uninitialized_copy(middle_iter, last, this->end()); // may throw
+ sv::uninitialized_copy(middle_iter, last, this->end()); // may throw
m_size += count - to_move; // update end
- this->uninitialized_copy(position, position + to_move, position + count); // may throw
+ sv::uninitialized_move(position, position + to_move, position + count); // may throw
m_size += to_move; // update end
- this->copy(first, middle_iter, position) ; // may throw
+ sv::copy(first, middle_iter, position); // may throw
}
}
// assign
+ // @par Throws
+ // If Value's constructor or assignment taking dereferenced Iterator throws.
+ // @par Complexity
+ // Linear O(N).
template <typename Iterator>
void assign_dispatch(Iterator first, Iterator last, boost::random_access_traversal_tag const& /*not_random_access*/)
{
- size_type s = std::distance(first, last);
+ namespace sv = varray_detail;
+
+ typename boost::iterator_difference<Iterator>::type
+ s = std::distance(first, last);
- check_capacity(s);
+ errh::check_capacity(*this, s); // may throw
- if ( m_size <= s )
+ if ( m_size <= static_cast<size_type>(s) )
{
- this->copy(first, first + m_size, this->begin()); // may throw
+ sv::copy(first, first + m_size, this->begin()); // may throw
// TODO - perform uninitialized_copy first?
- this->uninitialized_copy(first + m_size, last, this->end()); // may throw
+ sv::uninitialized_copy(first + m_size, last, this->end()); // may throw
}
else
{
- this->copy(first, last, this->begin()); // may throw
- this->destroy(this->begin() + s, this->end());
+ sv::copy(first, last, this->begin()); // may throw
+ sv::destroy(this->begin() + s, this->end());
}
m_size = s; // update end
}
+ // @par Throws
+ // If Value's constructor or assignment taking dereferenced Iterator throws.
+ // @par Complexity
+ // Linear O(N).
template <typename Iterator, typename Traversal>
void assign_dispatch(Iterator first, Iterator last, Traversal const& /*not_random_access*/)
{
+ namespace sv = varray_detail;
+
size_type s = 0;
iterator it = this->begin();
for ( ; it != this->end() && first != last ; ++it, ++first, ++s )
- *it = *first; // may throw
+ *it = *first; // may throw
- this->destroy(it, this->end());
+ sv::destroy(it, this->end());
- std::pair<bool, size_type> copy_data =
- this->uninitialized_copy_checked(first, last, it, std::distance(it, this->begin() + Capacity)); // may throw
- s += copy_data.second;
+ std::ptrdiff_t d = std::distance(it, this->begin() + Capacity);
+ std::size_t count = sv::uninitialized_copy_s(first, last, it, d); // may throw
+ s += count;
- check_capacity(copy_data.first ? s : Capacity + 1);
+ errh::check_capacity(*this, count <= static_cast<std::size_t>(d) ? s : Capacity + 1); // may throw
m_size = s; // update end
}
- // uninitialized_copy_checked
-
- template <typename Iterator>
- std::pair<bool, size_type> uninitialized_copy_checked(Iterator first, Iterator last, iterator dest, size_type max_count)
+ pointer ptr()
{
- size_type count = 0;
- iterator it = dest;
- BOOST_TRY
- {
- for ( ; first != last ; ++it, ++first, ++count )
- {
- if ( max_count <= count )
- return std::make_pair(false, count);
+ return pointer(static_cast<Value*>(m_storage.address()));
+ }
- this->uninitialized_fill(it, *first); // may throw
- }
- }
- BOOST_CATCH(...)
- {
- this->destroy(dest, it);
- BOOST_RETHROW
- }
- BOOST_CATCH_END
- return std::make_pair(true, count);
+ const_pointer ptr() const
+ {
+ return const_pointer(static_cast<const Value*>(m_storage.address()));
}
- // copy
+ size_type m_size;
+ aligned_storage_type m_storage;
+};
- template <typename Iterator>
- void copy(Iterator first, Iterator last, iterator dst)
+#if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+
+template<typename Value>
+class varray<Value, 0>
+{
+ typedef varray_detail::varray_traits<Value, 0> vt;
+ typedef varray_detail::checker<varray> errh;
+
+public:
+ typedef typename vt::value_type value_type;
+ typedef typename vt::size_type size_type;
+ typedef typename vt::difference_type difference_type;
+ typedef typename vt::pointer pointer;
+ typedef typename vt::const_pointer const_pointer;
+ typedef typename vt::reference reference;
+ typedef typename vt::const_reference const_reference;
+
+ typedef pointer iterator;
+ typedef const_pointer const_iterator;
+ typedef boost::reverse_iterator<iterator> reverse_iterator;
+ typedef boost::reverse_iterator<const_iterator> const_reverse_iterator;
+
+ // nothrow
+ varray() {}
+
+ // strong
+ explicit varray(size_type count)
{
- typedef typename
- mpl::and_<
- has_trivial_assign<value_type>,
- mpl::or_<
- is_same<Iterator, value_type *>,
- is_same<Iterator, const value_type *>
- >,
- mpl::or_<
- is_same<iterator, value_type *>,
- is_same<iterator, const value_type *>
- >
- >::type
- use_memcpy;
-
- this->copy_dispatch(first, last, dst, use_memcpy()); // may throw
+ errh::check_capacity(*this, count); // may throw
}
- void copy_dispatch(const value_type * first, const value_type * last, value_type * dst,
- boost::mpl::bool_<true> const& /*use_memcpy*/)
+ // strong
+ varray(size_type count, value_type const&)
{
- ::memmove(dst, first, sizeof(value_type) * std::distance(first, last));
+ errh::check_capacity(*this, count); // may throw
}
- template <typename Iterator>
- void copy_dispatch(Iterator first, Iterator last, iterator dst,
- boost::mpl::bool_<false> const& /*use_memcpy*/)
+ // strong
+ varray(varray const& other)
{
- std::copy(first, last, dst); // may throw
+ //errh::check_capacity(*this, count);
}
- // uninitialized_copy
+ // strong
+ template <std::size_t C>
+ varray(varray<value_type, C> const& other)
+ {
+ errh::check_capacity(*this, other.size()); // may throw
+ }
+ // strong
template <typename Iterator>
- void uninitialized_copy(Iterator first, Iterator last, iterator dst)
+ varray(Iterator first, Iterator last)
{
- typedef typename
- mpl::and_<
- has_trivial_copy<value_type>,
- mpl::or_<
- is_same<Iterator, value_type *>,
- is_same<Iterator, const value_type *>
- >,
- mpl::or_<
- is_same<iterator, value_type *>,
- is_same<iterator, const value_type *>
- >
- >::type
- use_memcpy;
-
- this->uninitialized_copy_dispatch(first, last, dst, use_memcpy()); // may throw
+ errh::check_capacity(*this, std::distance(first, last)); // may throw
}
- void uninitialized_copy_dispatch(const value_type * first, const value_type * last, value_type * dst,
- boost::mpl::bool_<true> const& /*use_memcpy*/)
+ // basic
+ varray & operator=(varray const& other)
{
- ::memcpy(dst, first, sizeof(value_type) * std::distance(first, last));
+ //errh::check_capacity(*this, other.size());
+ return *this;
}
- template <typename Iterator>
- void uninitialized_copy_dispatch(Iterator first, Iterator last, iterator dst,
- boost::mpl::bool_<false> const& /*use_memcpy*/)
+ // basic
+ template <size_t C>
+ varray & operator=(varray<value_type, C> const& other)
{
- std::uninitialized_copy(first, last, dst); // may throw
+ errh::check_capacity(*this, other.size()); // may throw
+ return *this;
}
- // uninitialized_fill
+ // nothrow
+ ~varray() {}
- template <typename V>
- void uninitialized_fill(iterator dst, V const& v)
+ // strong
+ void resize(size_type count)
{
- typedef typename
- mpl::and_<
- has_trivial_copy<value_type>,
- is_same<V, value_type>
- >::type
- use_memcpy;
-
- uninitialized_fill_dispatch(dst, v, use_memcpy()); // may throw
+ errh::check_capacity(*this, count); // may throw
}
- void uninitialized_fill_dispatch(iterator dst, value_type const& v,
- boost::mpl::bool_<true> const& /*use_memcpy*/)
+ // strong
+ void resize(size_type count, value_type const&)
{
- // TODO - check if value_type has operator& defined and call this version only if it hasn't
- const value_type * vptr = &v;
- ::memcpy(&(*dst), vptr, sizeof(value_type));
+ errh::check_capacity(*this, count); // may throw
}
- template <typename V>
- void uninitialized_fill_dispatch(iterator dst, V const& v,
- boost::mpl::bool_<false> const& /*use_memcpy*/)
+
+ // nothrow
+ void reserve(size_type count)
{
- new (&(*dst)) value_type(v); // may throw
+ errh::check_capacity(*this, count); // may throw
}
- template <typename V>
- void uninitialized_fill(iterator dst, BOOST_RV_REF(V) v)
+ // strong
+ void push_back(value_type const&)
{
- // TODO optimized version if has_trivial_move
- new (&(*dst)) value_type(v); // may throw
+ errh::check_capacity(*this, 1); // may throw
}
- // move
-
- template <typename Iterator>
- void move(Iterator first, Iterator last, iterator dst)
+ // nothrow
+ void pop_back()
{
- typedef typename
- mpl::and_<
- has_trivial_assign<value_type>,
- mpl::or_<
- is_same<Iterator, value_type *>,
- is_same<Iterator, const value_type *>
- >,
- mpl::or_<
- is_same<iterator, value_type *>,
- is_same<iterator, const value_type *>
- >
- >::type
- use_memcpy;
+ errh::check_not_empty(*this);
+ }
- this->move_dispatch(first, last, dst, use_memcpy()); // may throw
+ // basic
+ void insert(iterator position, value_type const&)
+ {
+ errh::check_iterator_end_eq(*this, position);
+ errh::check_capacity(*this, 1); // may throw
}
- void move_dispatch(const value_type * first, const value_type * last, value_type * dst,
- boost::mpl::bool_<true> const& /*use_mem*/)
+ // basic
+ void insert(iterator position, size_type count, value_type const&)
{
- ::memmove(dst, first, sizeof(value_type) * std::distance(first, last));
+ errh::check_iterator_end_eq(*this, position);
+ errh::check_capacity(*this, count); // may throw
}
+ // basic
template <typename Iterator>
- void move_dispatch(Iterator first, Iterator last, iterator dst,
- boost::mpl::bool_<false> const& /*use_mem*/)
+ void insert(iterator, Iterator first, Iterator last)
{
- std::copy(first, last, dst); // may throw
+ // TODO - add MPL_ASSERT, check if Iterator is really an iterator
+ typedef typename boost::iterator_traversal<Iterator>::type traversal;
+ errh::check_capacity(*this, std::distance(first, last)); // may throw
}
- // move_backward
+ // basic
+ void erase(iterator position)
+ {
+ errh::check_iterator_end_neq(*this, position);
+ }
- void move_backward(iterator first, iterator last, iterator dst)
+ // basic
+ void erase(iterator first, iterator last)
{
- typedef typename
- mpl::and_<
- has_trivial_assign<value_type>,
- mpl::or_<
- is_same<iterator, value_type *>,
- is_same<iterator, const value_type *>
- >
- >::type
- use_memcpy;
+ errh::check_iterator_end_eq(*this, first);
+ errh::check_iterator_end_eq(*this, last);
- this->move_backward_dispatch(first, last, dst, use_memcpy()); // may throw
+ //BOOST_ASSERT_MSG(0 <= n, "invalid range");
}
- void move_backward_dispatch(value_type * first, value_type * last, value_type * dst,
- boost::mpl::bool_<true> const& /*has_trivial_assign*/)
+ // basic
+ template <typename Iterator>
+ void assign(Iterator first, Iterator last)
{
- difference_type n = std::distance(first, last);
- ::memmove(dst - n, first, sizeof(value_type) * n);
+ // TODO - add MPL_ASSERT, check if Iterator is really an iterator
+ typedef typename boost::iterator_traversal<Iterator>::type traversal;
+ errh::check_capacity(*this, std::distance(first, last)); // may throw
}
- void move_backward_dispatch(iterator first, iterator last, iterator dst,
- boost::mpl::bool_<false> const& /*has_trivial_assign*/)
+ // basic
+ void assign(size_type count, value_type const&)
{
- std::copy_backward(first, last, dst); // may throw
+ errh::check_capacity(*this, count); // may throw
}
- // uninitialized_fill
+ // nothrow
+ void clear() {}
- template <typename V>
- void fill(iterator dst, V const& v)
+ // strong
+ reference at(size_type i)
{
- fill_dispatch(dst, v, has_trivial_assign<value_type>()); // may throw
+ errh::throw_out_of_bounds(*this, i); // may throw
+ return *(this->begin() + i);
}
- void fill_dispatch(iterator ptr, value_type const& v,
- boost::true_type const& /*has_trivial_assign*/)
+ // strong
+ const_reference at(size_type i) const
{
- // TODO - check if value_type has operator& defined and call this version only if it hasn't
- const value_type * vptr = &v;
- ::memcpy(&(*ptr), vptr, sizeof(value_type));
+ errh::throw_out_of_bounds(*this, i); // may throw
+ return *(this->begin() + i);
}
- template <typename V>
- void fill_dispatch(iterator ptr, V const& v,
- boost::false_type const& /*has_trivial_assign*/)
+ // nothrow
+ reference operator[](size_type i)
{
- *ptr = v; // may throw
+ errh::check_index(*this, i);
+ return *(this->begin() + i);
}
- // destroy
-
- void destroy(iterator first, iterator last)
+ // nothrow
+ const_reference operator[](size_type i) const
{
- this->destroy_dispatch(first, last, has_trivial_destructor<value_type>());
+ errh::check_index(*this, i);
+ return *(this->begin() + i);
}
- void destroy_dispatch(iterator /*first*/, iterator /*last*/,
- boost::true_type const& /*has_trivial_destructor*/)
- {}
-
- void destroy_dispatch(iterator first, iterator last,
- boost::false_type const& /*has_trivial_destructor*/)
+ // nothrow
+ reference front()
{
- for ( ; first != last ; ++first )
- first->~value_type();
+ errh::check_not_empty(*this);
+ return *(this->begin());
}
- // destroy
-
- void destroy(iterator it)
+ // nothrow
+ const_reference front() const
{
- this->destroy_dispatch(it, has_trivial_destructor<value_type>());
+ errh::check_not_empty(*this);
+ return *(this->begin());
}
- void destroy_dispatch(iterator /*ptr*/,
- boost::true_type const& /*has_trivial_destructor*/)
- {}
-
- void destroy_dispatch(iterator ptr,
- boost::false_type const& /*has_trivial_destructor*/)
+ // nothrow
+ reference back()
{
- ptr->~value_type();
+ errh::check_not_empty(*this);
+ return *(this->end() - 1);
}
- // uninitialized_move
-
- template <typename Iterator>
- void uninitialized_move(Iterator first, Iterator last, iterator dst)
+ // nothrow
+ const_reference back() const
{
- iterator o = dst;
- BOOST_TRY
- {
- for (; first != last; ++first, ++o )
- new (boost::addressof(*o)) value_type(boost::move(*first));
- }
- BOOST_CATCH(...)
- {
- destroy(dst, o);
- BOOST_RETHROW
- }
- BOOST_CATCH_END
+ errh::check_not_empty(*this);
+ return *(this->end() - 1);
}
- // construct
+ // nothrow
+ Value * data() { return boost::addressof(*(this->ptr())); }
+ const Value * data() const { return boost::addressof(*(this->ptr())); }
- void construct(iterator first, iterator last)
- {
- this->construct_dispatch(first, last, has_trivial_constructor<value_type>()); // may throw
- }
+ // nothrow
+ iterator begin() { return this->ptr(); }
+ const_iterator begin() const { return this->ptr(); }
+ const_iterator cbegin() const { return this->ptr(); }
+ iterator end() { return this->begin(); }
+ const_iterator end() const { return this->begin(); }
+ const_iterator cend() const { return this->cbegin(); }
+ // nothrow
+ reverse_iterator rbegin() { return reverse_iterator(this->end()); }
+ const_reverse_iterator rbegin() const { return reverse_iterator(this->end()); }
+ const_reverse_iterator crbegin() const { return reverse_iterator(this->end()); }
+ reverse_iterator rend() { return reverse_iterator(this->begin()); }
+ const_reverse_iterator rend() const { return reverse_iterator(this->begin()); }
+ const_reverse_iterator crend() const { return reverse_iterator(this->begin()); }
- void construct_dispatch(iterator /*first*/, iterator /*last*/,
- boost::true_type const& /*has_trivial_constructor*/)
- {}
+ // nothrow
+ size_type capacity() const { return 0; }
+ size_type max_size() const { return 0; }
+ size_type size() const { return 0; }
+ bool empty() const { return true; }
- void construct_dispatch(iterator first, iterator last,
- boost::false_type const& /*has_trivial_constructor*/)
+private:
+ pointer ptr()
{
- iterator it = first;
- BOOST_TRY
- {
- for ( ; it != last ; ++it )
- new (&(*it)) value_type(); // may throw
- }
- BOOST_CATCH(...)
- {
- this->destroy(first, it);
- BOOST_RETHROW
- }
- BOOST_CATCH_END
+ return pointer(reinterpret_cast<Value*>(this));
}
- void check_capacity(size_type BOOST_GEOMETRY_INDEX_ASSERT_UNUSED_PARAM(s)) const
+ const_pointer ptr() const
{
- BOOST_ASSERT_MSG(s <= Capacity, "size can't exceed the capacity");
- //if ( Capacity < s ) throw std::bad_alloc();
+ return const_pointer(reinterpret_cast<const Value*>(this));
}
+};
- void check_empty() const
- {
- BOOST_ASSERT_MSG(0 < m_size, "the container is empty");
- }
+#endif // !BOOST_CONTAINER_DOXYGEN_INVOKED
- void check_iterator_end_neq(const_iterator position) const
- {
- BOOST_ASSERT_MSG(this->begin() <= position && position < this->end(), "iterator out of bounds");
+//! @brief Checks if contents of two varrays are equal.
+//!
+//! @ingroup varray_non_member
+//!
+//! @param x The first varray.
+//! @param y The second varray.
+//!
+//! @return \c true if containers have the same size and elements in both containers are equal.
+//!
+//! @par Complexity
+//! Linear O(N).
+template<typename V, std::size_t C1, std::size_t C2>
+bool operator== (varray<V, C1> const& x, varray<V, C2> const& y)
+{
+ return x.size() == y.size() && std::equal(x.begin(), x.end(), y.begin());
+}
- /*BOOST_GEOMETRY_INDEX_ASSERT_UNUSED_PARAM(
- difference_type dist = std::distance(this->begin(), position);
- )
- BOOST_ASSERT_MSG(
- 0 <= dist &&
- ( sizeof(dist) <= sizeof(m_size) ?
- (static_cast<size_type>(dist) < m_size) :
- ( dist < static_cast<difference_type>(m_size))
- ), "invalid iterator"
- );*/
- }
+//! @brief Checks if contents of two varrays are not equal.
+//!
+//! @ingroup varray_non_member
+//!
+//! @param x The first varray.
+//! @param y The second varray.
+//!
+//! @return \c true if containers have different size or elements in both containers are not equal.
+//!
+//! @par Complexity
+//! Linear O(N).
+template<typename V, std::size_t C1, std::size_t C2>
+bool operator!= (varray<V, C1> const& x, varray<V, C2> const& y)
+{
+ return !(x==y);
+}
- void check_iterator_end_eq(const_iterator position) const
- {
- BOOST_ASSERT_MSG(this->begin() <= position && position <= this->end(), "iterator out of bounds");
+//! @brief Lexicographically compares varrays.
+//!
+//! @ingroup varray_non_member
+//!
+//! @param x The first varray.
+//! @param y The second varray.
+//!
+//! @return \c true if x compares lexicographically less than y.
+//!
+//! @par Complexity
+//! Linear O(N).
+template<typename V, std::size_t C1, std::size_t C2>
+bool operator< (varray<V, C1> const& x, varray<V, C2> const& y)
+{
+ return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
+}
- /*BOOST_GEOMETRY_INDEX_ASSERT_UNUSED_PARAM(
- difference_type dist = std::distance(this->begin(), position);
- )
- BOOST_ASSERT_MSG(
- 0 <= dist &&
- ( sizeof(dist) <= sizeof(m_size) ?
- (static_cast<size_type>(dist) <= m_size) :
- ( dist <= static_cast<difference_type>(m_size))
- ), "invalid iterator"
- );*/
- }
+//! @brief Lexicographically compares varrays.
+//!
+//! @ingroup varray_non_member
+//!
+//! @param x The first varray.
+//! @param y The second varray.
+//!
+//! @return \c true if y compares lexicographically less than x.
+//!
+//! @par Complexity
+//! Linear O(N).
+template<typename V, std::size_t C1, std::size_t C2>
+bool operator> (varray<V, C1> const& x, varray<V, C2> const& y)
+{
+ return y<x;
+}
- pointer ptr()
- {
- return pointer(static_cast<value_type *>(m_storage.address()));
- }
+//! @brief Lexicographically compares varrays.
+//!
+//! @ingroup varray_non_member
+//!
+//! @param x The first varray.
+//! @param y The second varray.
+//!
+//! @return \c true if y don't compare lexicographically less than x.
+//!
+//! @par Complexity
+//! Linear O(N).
+template<typename V, std::size_t C1, std::size_t C2>
+bool operator<= (varray<V, C1> const& x, varray<V, C2> const& y)
+{
+ return !(y<x);
+}
- const_pointer ptr() const
- {
- return const_pointer(static_cast<const value_type *>(m_storage.address()));
- }
+//! @brief Lexicographically compares varrays.
+//!
+//! @ingroup varray_non_member
+//!
+//! @param x The first varray.
+//! @param y The second varray.
+//!
+//! @return \c true if x don't compare lexicographically less than y.
+//!
+//! @par Complexity
+//! Linear O(N).
+template<typename V, std::size_t C1, std::size_t C2>
+bool operator>= (varray<V, C1> const& x, varray<V, C2> const& y)
+{
+ return !(x<y);
+}
- boost::aligned_storage<sizeof(Value[Capacity]), boost::alignment_of<Value[Capacity]>::value> m_storage;
- size_type m_size;
-};
+//! @brief Swaps contents of two varrays.
+//!
+//! This function calls varray::swap().
+//!
+//! @ingroup varray_non_member
+//!
+//! @param x The first varray.
+//! @param y The second varray.
+//!
+//! @par Complexity
+//! Linear O(N).
+template<typename V, std::size_t C1, std::size_t C2>
+inline void swap(varray<V, C1> & x, varray<V, C2> & y)
+{
+ x.swap(y);
+}
}}}} // namespace boost::geometry::index::detail
-#ifdef BOOST_MSVC
-#pragma warning (pop)
-#endif
+// TODO - REMOVE/CHANGE
+#include <boost/container/detail/config_end.hpp>
#endif // BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_HPP
Added: trunk/boost/geometry/index/detail/varray_detail.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/geometry/index/detail/varray_detail.hpp 2013-06-07 13:34:58 EDT (Fri, 07 Jun 2013) (r84675)
@@ -0,0 +1,714 @@
+// Boost.Geometry
+//
+// varray details
+//
+// Copyright (c) 2012-2013 Adam Wulkiewicz, Lodz, Poland.
+// Copyright (c) 2011-2013 Andrew Hundt.
+//
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_DETAIL_HPP
+#define BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_DETAIL_HPP
+
+#include <cstddef>
+#include <cstring>
+#include <memory>
+#include <limits>
+
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/and.hpp>
+#include <boost/mpl/or.hpp>
+#include <boost/mpl/int.hpp>
+
+#include <boost/type_traits/is_same.hpp>
+#include <boost/type_traits/remove_const.hpp>
+#include <boost/type_traits/remove_reference.hpp>
+#include <boost/type_traits/has_trivial_assign.hpp>
+#include <boost/type_traits/has_trivial_copy.hpp>
+#include <boost/type_traits/has_trivial_constructor.hpp>
+#include <boost/type_traits/has_trivial_destructor.hpp>
+//#include <boost/type_traits/has_nothrow_constructor.hpp>
+//#include <boost/type_traits/has_nothrow_copy.hpp>
+//#include <boost/type_traits/has_nothrow_assign.hpp>
+//#include <boost/type_traits/has_nothrow_destructor.hpp>
+
+#include <boost/detail/no_exceptions_support.hpp>
+#include <boost/config.hpp>
+#include <boost/move/move.hpp>
+#include <boost/utility/addressof.hpp>
+#include <boost/iterator/iterator_traits.hpp>
+
+// TODO - move vectors iterators optimization to the other, optional file instead of checking defines?
+
+#if defined(BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_ENABLE_VECTOR_OPTIMIZATION) && !defined(BOOST_NO_EXCEPTIONS)
+#include <vector>
+#include <boost/container/vector.hpp>
+#endif // BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_ENABLE_VECTOR_OPTIMIZATION && !BOOST_NO_EXCEPTIONS
+
+namespace boost { namespace geometry { namespace index { namespace detail { namespace varray_detail {
+
+template <typename I>
+struct are_elements_contiguous : boost::is_pointer<I>
+{};
+
+// EXPERIMENTAL - not finished
+// Conditional setup - mark vector iterators defined in known implementations
+// as iterators pointing to contiguous ranges
+
+#if defined(BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_ENABLE_VECTOR_OPTIMIZATION) && !defined(BOOST_NO_EXCEPTIONS)
+
+template <typename Pointer>
+struct are_elements_contiguous<
+ boost::container::container_detail::vector_const_iterator<Pointer>
+> : boost::true_type
+{};
+
+template <typename Pointer>
+struct are_elements_contiguous<
+ boost::container::container_detail::vector_iterator<Pointer>
+> : boost::true_type
+{};
+
+#if defined(BOOST_DINKUMWARE_STDLIB)
+
+template <typename T>
+struct are_elements_contiguous<
+ std::_Vector_const_iterator<T>
+> : boost::true_type
+{};
+
+template <typename T>
+struct are_elements_contiguous<
+ std::_Vector_iterator<T>
+> : boost::true_type
+{};
+
+#elif defined(BOOST_GNU_STDLIB)
+
+template <typename P, typename T, typename A>
+struct are_elements_contiguous<
+ __gnu_cxx::__normal_iterator<P, std::vector<T, A> >
+> : boost::true_type
+{};
+
+#elif defined(_LIBCPP_VERSION)
+
+// TODO - test it first
+//template <typename P>
+//struct are_elements_contiguous<
+// __wrap_iter<P>
+//> : boost::true_type
+//{};
+
+#else // OTHER_STDLIB
+
+// TODO - add other iterators implementations
+
+#endif // STDLIB
+
+#endif // BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_ENABLE_VECTOR_OPTIMIZATION && !BOOST_NO_EXCEPTIONS
+
+// True if iterator values are the same and both iterators points to the ranges of contiguous elements
+
+template <typename I, typename O>
+struct are_corresponding :
+ ::boost::mpl::and_<
+ ::boost::is_same<
+ ::boost::remove_const<
+ typename ::boost::iterator_value<I>::type
+ >,
+ ::boost::remove_const<
+ typename ::boost::iterator_value<O>::type
+ >
+ >,
+ are_elements_contiguous<I>,
+ are_elements_contiguous<O>
+ >
+{};
+
+template <typename I, typename V>
+struct is_corresponding_value :
+ ::boost::is_same<
+ ::boost::remove_const<
+ typename ::boost::iterator_value<I>::type
+ >,
+ ::boost::remove_const<V>
+ >
+{};
+
+// destroy(I, I)
+
+template <typename I>
+void destroy_dispatch(I /*first*/, I /*last*/,
+ boost::true_type const& /*has_trivial_destructor*/)
+{}
+
+template <typename I>
+void destroy_dispatch(I first, I last,
+ boost::false_type const& /*has_trivial_destructor*/)
+{
+ typedef typename boost::iterator_value<I>::type value_type;
+ for ( ; first != last ; ++first )
+ first->~value_type();
+}
+
+template <typename I>
+void destroy(I first, I last)
+{
+ typedef typename boost::iterator_value<I>::type value_type;
+ destroy_dispatch(first, last, has_trivial_destructor<value_type>());
+}
+
+// destroy(I)
+
+template <typename I>
+void destroy_dispatch(I /*pos*/,
+ boost::true_type const& /*has_trivial_destructor*/)
+{}
+
+template <typename I>
+void destroy_dispatch(I pos,
+ boost::false_type const& /*has_trivial_destructor*/)
+{
+ typedef typename boost::iterator_value<I>::type value_type;
+ pos->~value_type();
+}
+
+template <typename I>
+void destroy(I pos)
+{
+ typedef typename boost::iterator_value<I>::type value_type;
+ destroy_dispatch(pos, has_trivial_destructor<value_type>());
+}
+
+// copy(I, I, O)
+
+template <typename I, typename O>
+inline O copy_dispatch(I first, I last, O dst,
+ boost::mpl::bool_<true> const& /*use_memmove*/)
+{
+ typedef typename boost::iterator_value<I>::type value_type;
+ typename boost::iterator_difference<I>::type d = std::distance(first, last);
+
+ ::memmove(boost::addressof(*dst), boost::addressof(*first), sizeof(value_type) * d);
+ return dst + d;
+}
+
+template <typename I, typename O>
+inline O copy_dispatch(I first, I last, O dst,
+ boost::mpl::bool_<false> const& /*use_memmove*/)
+{
+ return std::copy(first, last, dst); // may throw
+}
+
+template <typename I, typename O>
+inline O copy(I first, I last, O dst)
+{
+ typedef typename
+ ::boost::mpl::and_<
+ are_corresponding<I, O>,
+ ::boost::has_trivial_assign<
+ typename ::boost::iterator_value<O>::type
+ >
+ >::type
+ use_memmove;
+
+ return copy_dispatch(first, last, dst, use_memmove()); // may throw
+}
+
+// uninitialized_copy(I, I, O)
+
+template <typename I, typename O>
+inline
+O uninitialized_copy_dispatch(I first, I last, O dst,
+ boost::mpl::bool_<true> const& /*use_memcpy*/)
+{
+ typedef typename boost::iterator_value<I>::type value_type;
+ typename boost::iterator_difference<I>::type d = std::distance(first, last);
+
+ ::memcpy(boost::addressof(*dst), boost::addressof(*first), sizeof(value_type) * d);
+ return dst + d;
+}
+
+template <typename I, typename F>
+inline
+F uninitialized_copy_dispatch(I first, I last, F dst,
+ boost::mpl::bool_<false> const& /*use_memcpy*/)
+{
+ return std::uninitialized_copy(first, last, dst); // may throw
+}
+
+template <typename I, typename F>
+inline
+F uninitialized_copy(I first, I last, F dst)
+{
+ typedef typename
+ ::boost::mpl::and_<
+ are_corresponding<I, F>,
+ ::boost::has_trivial_copy<
+ typename ::boost::iterator_value<F>::type
+ >
+ >::type
+ use_memcpy;
+
+ return uninitialized_copy_dispatch(first, last, dst, use_memcpy()); // may throw
+}
+
+// uninitialized_move(I, I, O)
+
+template <typename I, typename O>
+inline
+O uninitialized_move_dispatch(I first, I last, O dst,
+ boost::mpl::bool_<true> const& /*use_memcpy*/)
+{
+ typedef typename boost::iterator_value<I>::type value_type;
+ typename boost::iterator_difference<I>::type d = std::distance(first, last);
+
+ ::memcpy(boost::addressof(*dst), boost::addressof(*first), sizeof(value_type) * d);
+ return dst + d;
+}
+
+template <typename I, typename O>
+inline
+O uninitialized_move_dispatch(I first, I last, O dst,
+ boost::mpl::bool_<false> const& /*use_memcpy*/)
+{
+ //return boost::uninitialized_move(first, last, dst); // may throw
+
+ O o = dst;
+
+ BOOST_TRY
+ {
+ typedef typename std::iterator_traits<O>::value_type value_type;
+ for (; first != last; ++first, ++o )
+ new (boost::addressof(*o)) value_type(boost::move(*first));
+ }
+ BOOST_CATCH(...)
+ {
+ destroy(dst, o);
+ BOOST_RETHROW;
+ }
+ BOOST_CATCH_END
+
+ return dst;
+}
+
+template <typename I, typename O>
+inline
+O uninitialized_move(I first, I last, O dst)
+{
+ typedef typename
+ ::boost::mpl::and_<
+ are_corresponding<I, O>,
+ ::boost::has_trivial_copy<
+ typename ::boost::iterator_value<O>::type
+ >
+ >::type
+ use_memcpy;
+
+ return uninitialized_move_dispatch(first, last, dst, use_memcpy()); // may throw
+}
+
+// TODO - move uses memmove - implement 2nd version using memcpy?
+
+// move(I, I, O)
+
+template <typename I, typename O>
+inline
+O move_dispatch(I first, I last, O dst,
+ boost::mpl::bool_<true> const& /*use_memmove*/)
+{
+ typedef typename boost::iterator_value<I>::type value_type;
+ typename boost::iterator_difference<I>::type d = std::distance(first, last);
+
+ ::memmove(boost::addressof(*dst), boost::addressof(*first), sizeof(value_type) * d);
+ return dst + d;
+}
+
+template <typename I, typename O>
+inline
+O move_dispatch(I first, I last, O dst,
+ boost::mpl::bool_<false> const& /*use_memmove*/)
+{
+ return boost::move(first, last, dst); // may throw
+}
+
+template <typename I, typename O>
+inline
+O move(I first, I last, O dst)
+{
+ typedef typename
+ ::boost::mpl::and_<
+ are_corresponding<I, O>,
+ ::boost::has_trivial_assign<
+ typename ::boost::iterator_value<O>::type
+ >
+ >::type
+ use_memmove;
+
+ return move_dispatch(first, last, dst, use_memmove()); // may throw
+}
+
+// move_backward(BDI, BDI, BDO)
+
+template <typename BDI, typename BDO>
+inline
+BDO move_backward_dispatch(BDI first, BDI last, BDO dst,
+ boost::mpl::bool_<true> const& /*use_memmove*/)
+{
+ typedef typename boost::iterator_value<BDI>::type value_type;
+ typename boost::iterator_difference<BDI>::type d = std::distance(first, last);
+
+ BDO foo(dst - d);
+ ::memmove(boost::addressof(*foo), boost::addressof(*first), sizeof(value_type) * d);
+ return foo;
+}
+
+template <typename BDI, typename BDO>
+inline
+BDO move_backward_dispatch(BDI first, BDI last, BDO dst,
+ boost::mpl::bool_<false> const& /*use_memmove*/)
+{
+ return boost::move_backward(first, last, dst); // may throw
+}
+
+template <typename BDI, typename BDO>
+inline
+BDO move_backward(BDI first, BDI last, BDO dst)
+{
+ typedef typename
+ ::boost::mpl::and_<
+ are_corresponding<BDI, BDO>,
+ ::boost::has_trivial_assign<
+ typename ::boost::iterator_value<BDO>::type
+ >
+ >::type
+ use_memmove;
+
+ return move_backward_dispatch(first, last, dst, use_memmove()); // may throw
+}
+
+template <typename T>
+struct has_nothrow_move : public
+ ::boost::mpl::or_<
+ boost::mpl::bool_<
+ ::boost::has_nothrow_move<
+ typename ::boost::remove_const<T>::type
+ >::value
+ >,
+ boost::mpl::bool_<
+ ::boost::has_nothrow_move<T>::value
+ >
+ >
+{};
+
+// uninitialized_move_if_noexcept(I, I, O)
+
+template <typename I, typename O>
+inline
+O uninitialized_move_if_noexcept_dispatch(I first, I last, O dst, boost::mpl::bool_<true> const& /*use_move*/)
+{ return uninitialized_move(first, last, dst); }
+
+template <typename I, typename O>
+inline
+O uninitialized_move_if_noexcept_dispatch(I first, I last, O dst, boost::mpl::bool_<false> const& /*use_move*/)
+{ return uninitialized_copy(first, last, dst); }
+
+template <typename I, typename O>
+inline
+O uninitialized_move_if_noexcept(I first, I last, O dst)
+{
+ typedef typename has_nothrow_move<
+ typename ::boost::iterator_value<O>::type
+ >::type use_move;
+
+ return uninitialized_move_if_noexcept_dispatch(first, last, dst, use_move()); // may throw
+}
+
+// move_if_noexcept(I, I, O)
+
+template <typename I, typename O>
+inline
+O move_if_noexcept_dispatch(I first, I last, O dst, boost::mpl::bool_<true> const& /*use_move*/)
+{ return move(first, last, dst); }
+
+template <typename I, typename O>
+inline
+O move_if_noexcept_dispatch(I first, I last, O dst, boost::mpl::bool_<false> const& /*use_move*/)
+{ return copy(first, last, dst); }
+
+template <typename I, typename O>
+inline
+O move_if_noexcept(I first, I last, O dst)
+{
+ typedef typename has_nothrow_move<
+ typename ::boost::iterator_value<O>::type
+ >::type use_move;
+
+ return move_if_noexcept_dispatch(first, last, dst, use_move()); // may throw
+}
+
+// uninitialized_fill(I, I)
+
+template <typename I>
+inline
+void uninitialized_fill_dispatch(I first, I last,
+ boost::true_type const& /*has_trivial_constructor*/,
+ boost::true_type const& /*disable_trivial_init*/)
+{}
+
+template <typename I>
+inline
+void uninitialized_fill_dispatch(I first, I last,
+ boost::true_type const& /*has_trivial_constructor*/,
+ boost::false_type const& /*disable_trivial_init*/)
+{
+ typedef typename boost::iterator_value<I>::type value_type;
+ for ( ; first != last ; ++first )
+ new (boost::addressof(*first)) value_type();
+}
+
+template <typename I, typename DisableTrivialInit>
+inline
+void uninitialized_fill_dispatch(I first, I last,
+ boost::false_type const& /*has_trivial_constructor*/,
+ DisableTrivialInit const& /*not_used*/)
+{
+ typedef typename boost::iterator_value<I>::type value_type;
+ I it = first;
+
+ BOOST_TRY
+ {
+ for ( ; it != last ; ++it )
+ new (boost::addressof(*it)) value_type(); // may throw
+ }
+ BOOST_CATCH(...)
+ {
+ destroy(first, it);
+ BOOST_RETHROW;
+ }
+ BOOST_CATCH_END
+}
+
+template <typename I, typename DisableTrivialInit>
+inline
+void uninitialized_fill(I first, I last, DisableTrivialInit const& disable_trivial_init)
+{
+ typedef typename boost::iterator_value<I>::type value_type;
+ uninitialized_fill_dispatch(first, last, boost::has_trivial_constructor<value_type>(), disable_trivial_init); // may throw
+}
+
+// construct(I)
+
+template <typename I>
+inline
+void construct_dispatch(boost::mpl::bool_<true> const& /*dont_init*/, I pos)
+{}
+
+template <typename I>
+inline
+void construct_dispatch(boost::mpl::bool_<false> const& /*dont_init*/, I pos)
+{
+ typedef typename ::boost::iterator_value<I>::type value_type;
+ new (static_cast<void*>(::boost::addressof(*pos))) value_type(); // may throw
+}
+
+template <typename DisableTrivialInit, typename I>
+inline
+void construct(DisableTrivialInit const&, I pos)
+{
+ typedef typename ::boost::iterator_value<I>::type value_type;
+ typedef typename ::boost::mpl::and_<
+ boost::has_trivial_constructor<value_type>,
+ DisableTrivialInit
+ >::type dont_init;
+
+ construct_dispatch(dont_init(), pos); // may throw
+}
+
+// construct(I, V)
+
+template <typename I, typename V>
+inline
+void construct_dispatch(I pos, V const& v,
+ boost::mpl::bool_<true> const& /*use_memcpy*/)
+{
+ ::memcpy(boost::addressof(*pos), boost::addressof(v), sizeof(V));
+}
+
+template <typename I, typename P>
+inline
+void construct_dispatch(I pos, P const& p,
+ boost::mpl::bool_<false> const& /*use_memcpy*/)
+{
+ typedef typename boost::iterator_value<I>::type V;
+ new (static_cast<void*>(boost::addressof(*pos))) V(p); // may throw
+}
+
+template <typename DisableTrivialInit, typename I, typename P>
+inline
+void construct(DisableTrivialInit const&,
+ I pos, P const& p)
+{
+ typedef typename
+ ::boost::mpl::and_<
+ is_corresponding_value<I, P>,
+ ::boost::has_trivial_copy<P>
+ >::type
+ use_memcpy;
+
+ construct_dispatch(pos, p, use_memcpy()); // may throw
+}
+
+// Needed by push_back(V &&)
+
+template <typename DisableTrivialInit, typename I, typename P>
+inline
+void construct(DisableTrivialInit const&, I pos, BOOST_RV_REF(P) p)
+{
+ typedef typename
+ ::boost::mpl::and_<
+ is_corresponding_value<I, P>,
+ ::boost::has_trivial_copy<P>
+ >::type
+ use_memcpy;
+
+ typedef typename boost::iterator_value<I>::type V;
+ new (static_cast<void*>(boost::addressof(*pos))) V(::boost::move(p)); // may throw
+}
+
+// Needed by emplace_back() and emplace()
+
+#if !defined(BOOST_CONTAINER_VARRAY_DISABLE_EMPLACE)
+#if !defined(BOOST_NO_VARIADIC_TEMPLATES)
+
+template <typename DisableTrivialInit, typename I, class ...Args>
+inline
+void construct(DisableTrivialInit const&,
+ I pos,
+ BOOST_FWD_REF(Args) ...args)
+{
+ typedef typename boost::iterator_value<I>::type V;
+ new (static_cast<void*>(boost::addressof(*pos))) V(::boost::forward<Args>(args)...); // may throw
+}
+
+#else // !BOOST_NO_VARIADIC_TEMPLATES
+
+// BOOST_NO_RVALUE_REFERENCES -> P0 const& p0
+// !BOOST_NO_RVALUE_REFERENCES -> P0 && p0
+// which means that version with one parameter may take V const& v
+
+#define BOOST_PP_LOCAL_MACRO(n) \
+template <typename DisableTrivialInit, typename I, typename P BOOST_PP_ENUM_TRAILING_PARAMS(n, typename P) > \
+inline \
+void construct(DisableTrivialInit const&, \
+ I pos, \
+ BOOST_CONTAINER_PP_PARAM(P, p) \
+ BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
+{ \
+ typedef typename boost::iterator_value<I>::type V; \
+ new \
+ (static_cast<void*>(boost::addressof(*pos))) \
+ V(p, BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); /*may throw*/ \
+} \
+//
+#define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
+#include BOOST_PP_LOCAL_ITERATE()
+
+#endif // !BOOST_NO_VARIADIC_TEMPLATES
+#endif // !BOOST_CONTAINER_VARRAY_DISABLE_EMPLACE
+
+// assign(I, V)
+
+template <typename I, typename V>
+inline
+void assign_dispatch(I pos, V const& v,
+ boost::mpl::bool_<true> const& /*use_memcpy*/)
+{
+ ::memcpy(boost::addressof(*pos), boost::addressof(v), sizeof(V));
+}
+
+template <typename I, typename V>
+inline
+void assign_dispatch(I pos, V const& v,
+ boost::mpl::bool_<false> const& /*use_memcpy*/)
+{
+ *pos = v; // may throw
+}
+
+template <typename I, typename V>
+inline
+void assign(I pos, V const& v)
+{
+ typedef typename
+ ::boost::mpl::and_<
+ is_corresponding_value<I, V>,
+ ::boost::has_trivial_assign<V>
+ >::type
+ use_memcpy;
+
+ assign_dispatch(pos, v, use_memcpy()); // may throw
+}
+
+template <typename I, typename V>
+inline
+void assign(I pos, BOOST_RV_REF(V) v)
+{
+ *pos = boost::move(v); // may throw
+}
+
+
+// uninitialized_copy_s
+
+template <typename I, typename F>
+inline std::size_t uninitialized_copy_s(I first, I last, F dest, std::size_t max_count)
+{
+ std::size_t count = 0;
+ F it = dest;
+
+ BOOST_TRY
+ {
+ for ( ; first != last ; ++it, ++first, ++count )
+ {
+ if ( max_count <= count )
+ return (std::numeric_limits<std::size_t>::max)();
+
+ // dummy 0 as DisableTrivialInit
+ construct(0, it, *first); // may throw
+ }
+ }
+ BOOST_CATCH(...)
+ {
+ destroy(dest, it);
+ BOOST_RETHROW;
+ }
+ BOOST_CATCH_END
+
+ return count;
+}
+
+// scoped_destructor
+
+template<class T>
+class scoped_destructor
+{
+public:
+ scoped_destructor(T * ptr) : m_ptr(ptr) {}
+
+ ~scoped_destructor()
+ {
+ if(m_ptr)
+ destroy(m_ptr);
+ }
+
+ void release() { m_ptr = 0; }
+
+private:
+ T * m_ptr;
+};
+
+}}}}} // namespace boost::geometry::index::detail::varray_detail
+
+#endif // BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_DETAIL_HPP