Subject: [Boost-commit] svn:boost r77911 - in trunk/boost/container: . detail
From: igaztanaga_at_[hidden]
Date: 2012-04-11 02:26:23
Author: igaztanaga
Date: 2012-04-11 02:26:20 EDT (Wed, 11 Apr 2012)
New Revision: 77911
URL: http://svn.boost.org/trac/boost/changeset/77911
Log:
Updated scoped allocator support
Text files modified:
trunk/boost/container/detail/tree.hpp | 52 ++-----------------
trunk/boost/container/flat_map.hpp | 26 ++++++---
trunk/boost/container/list.hpp | 6 --
trunk/boost/container/scoped_allocator.hpp | 105 +++++++++++++++++++++------------------
trunk/boost/container/slist.hpp | 6 --
trunk/boost/container/stable_vector.hpp | 6 --
trunk/boost/container/vector.hpp | 89 ++++++++++++++++++++++++++++-----
7 files changed, 154 insertions(+), 136 deletions(-)
Modified: trunk/boost/container/detail/tree.hpp
==============================================================================
--- trunk/boost/container/detail/tree.hpp (original)
+++ trunk/boost/container/detail/tree.hpp 2012-04-11 02:26:20 EDT (Wed, 11 Apr 2012)
@@ -110,8 +110,9 @@
struct rbtree_node
: public rbtree_hook<VoidPointer>::type
{
- //private:
+ private:
//BOOST_COPYABLE_AND_MOVABLE(rbtree_node)
+ rbtree_node();
public:
typedef typename rbtree_hook<VoidPointer>::type hook_type;
@@ -121,46 +122,6 @@
typedef rbtree_node<T, VoidPointer> node_type;
- private:
- rbtree_node();
- rbtree_node (const rbtree_node &);
- rbtree_node & operator=(const rbtree_node &);
-
-/*
- rbtree_node(const rbtree_node &other)
- : m_data(other.m_data)
- {}
-
- rbtree_node(BOOST_RV_REF(rbtree_node) other)
- : m_data(::boost::move(other.m_data))
- {}
-
- #ifndef BOOST_CONTAINER_PERFECT_FORWARDING
-
- #define BOOST_PP_LOCAL_MACRO(n) \
- template<BOOST_PP_ENUM_PARAMS(n, class P)> \
- rbtree_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
- : m_data(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)) \
- {} \
- //!
- #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
- #include BOOST_PP_LOCAL_ITERATE()
-
- #else //#ifndef BOOST_CONTAINER_PERFECT_FORWARDING
-
- template<class ...Args>
- rbtree_node(Args &&...args)
- : m_data(boost::forward<Args>(args)...)
- {}
- #endif//#ifndef BOOST_CONTAINER_PERFECT_FORWARDING
-
- rbtree_node &operator=(const rbtree_node &other)
- { do_assign(other.m_data); return *this; }
-
- rbtree_node &operator=(BOOST_RV_REF(rbtree_node) other)
- { do_move_assign(other.m_data); return *this; }
-*/
- public:
T &get_data()
{
T* ptr = reinterpret_cast<T*>(&this->m_data);
@@ -173,7 +134,6 @@
return *ptr;
}
-// private:
internal_type m_data;
template<class A, class B>
@@ -900,9 +860,9 @@
if(this->empty()){
//Insert with end hint, to achieve linear
//complexity if [first, last) is ordered
- const_iterator end(this->end());
+ const_iterator hint(this->cend());
for( ; first != last; ++first)
- this->insert_unique(end, *first);
+ hint = this->insert_unique(hint, *first);
}
else{
for( ; first != last; ++first)
@@ -941,9 +901,9 @@
{
//Insert with end hint, to achieve linear
//complexity if [first, last) is ordered
- const_iterator end(this->cend());
+ const_iterator hint(this->cend());
for( ; first != last; ++first)
- this->insert_equal(end, *first);
+ hint = this->insert_equal(hint, *first);
}
iterator erase(const_iterator position)
Modified: trunk/boost/container/flat_map.hpp
==============================================================================
--- trunk/boost/container/flat_map.hpp (original)
+++ trunk/boost/container/flat_map.hpp 2012-04-11 02:26:20 EDT (Wed, 11 Apr 2012)
@@ -165,8 +165,13 @@
get_flat_tree_iterators
<pointer>::const_reverse_iterator const_reverse_iterator;
typedef A allocator_type;
+
+ //!Standard extension
typedef A stored_allocator_type;
+ //!Standard extension for C++03 compilers with non-movable std::pair
+ typedef impl_value_type movable_value_type;
+
public:
//! <b>Effects</b>: Default constructs an empty flat_map.
//!
@@ -499,7 +504,7 @@
//! to the elements with bigger keys than x.
//!
//! <b>Note</b>: If an element is inserted it might invalidate elements.
- std::pair<iterator,bool> insert(BOOST_RV_REF(impl_value_type) x)
+ std::pair<iterator,bool> insert(BOOST_RV_REF(movable_value_type) x)
{
return container_detail::force<std::pair<iterator,bool> >
(m_flat_tree.insert_unique(boost::move(x)));
@@ -530,8 +535,11 @@
//!
//! <b>Note</b>: If an element is inserted it might invalidate elements.
iterator insert(const_iterator position, BOOST_RV_REF(value_type) x)
- { return container_detail::force_copy<iterator>
- (m_flat_tree.insert_unique(container_detail::force<impl_const_iterator>(position), boost::move(container_detail::force<impl_value_type>(x)))); }
+ {
+ return container_detail::force_copy<iterator>
+ (m_flat_tree.insert_unique( container_detail::force<impl_const_iterator>(position)
+ , boost::move(container_detail::force<impl_value_type>(x))));
+ }
//! <b>Effects</b>: Inserts an element move constructed from x in the container.
//! p is a hint pointing to where the insert should start to search.
@@ -542,7 +550,7 @@
//! right before p) plus insertion linear to the elements with bigger keys than x.
//!
//! <b>Note</b>: If an element is inserted it might invalidate elements.
- iterator insert(const_iterator position, BOOST_RV_REF(impl_value_type) x)
+ iterator insert(const_iterator position, BOOST_RV_REF(movable_value_type) x)
{
return container_detail::force_copy<iterator>(
m_flat_tree.insert_unique(container_detail::force<impl_const_iterator>(position), boost::move(x)));
@@ -719,13 +727,13 @@
//!
//! <b>Complexity</b>: Logarithmic
std::pair<iterator,iterator> equal_range(const key_type& x)
- { return container_detail::force<std::pair<iterator,iterator> >(m_flat_tree.equal_range(x)); }
+ { return container_detail::force_copy<std::pair<iterator,iterator> >(m_flat_tree.equal_range(x)); }
//! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
//!
//! <b>Complexity</b>: Logarithmic
std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const
- { return container_detail::force<std::pair<const_iterator,const_iterator> >(m_flat_tree.equal_range(x)); }
+ { return container_detail::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.equal_range(x)); }
//! <b>Effects</b>: Number of elements for which memory has been allocated.
//! capacity() is always greater than or equal to size().
@@ -931,6 +939,8 @@
typedef A allocator_type;
//Non-standard extension
typedef A stored_allocator_type;
+ //!Standard extension for C++03 compilers with non-movable std::pair
+ typedef impl_value_type movable_value_type;
//! <b>Effects</b>: Default constructs an empty flat_map.
//!
@@ -1389,14 +1399,14 @@
//!
//! <b>Complexity</b>: Logarithmic
std::pair<iterator,iterator> equal_range(const key_type& x)
- { return container_detail::force_copy<std::pair<iterator,iterator> >(m_flat_tree.equal_range(x)); }
+ { return container_detail::force<std::pair<iterator,iterator> >(m_flat_tree.equal_range(x)); }
//! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
//!
//! <b>Complexity</b>: Logarithmic
std::pair<const_iterator,const_iterator>
equal_range(const key_type& x) const
- { return container_detail::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.equal_range(x)); }
+ { return container_detail::force<std::pair<const_iterator,const_iterator> >(m_flat_tree.equal_range(x)); }
//! <b>Effects</b>: Number of elements for which memory has been allocated.
//! capacity() is always greater than or equal to size().
Modified: trunk/boost/container/list.hpp
==============================================================================
--- trunk/boost/container/list.hpp (original)
+++ trunk/boost/container/list.hpp 2012-04-11 02:26:20 EDT (Wed, 11 Apr 2012)
@@ -65,12 +65,6 @@
struct list_node
: public list_hook<VoidPointer>::type
{
- private:
- list_node();
- list_node(const list_node &);
- list_node & operator=(const list_node &);
-
- public:
typedef typename list_hook<VoidPointer>::type hook_type;
T m_data;
};
Modified: trunk/boost/container/scoped_allocator.hpp
==============================================================================
--- trunk/boost/container/scoped_allocator.hpp (original)
+++ trunk/boost/container/scoped_allocator.hpp 2012-04-11 02:26:20 EDT (Wed, 11 Apr 2012)
@@ -294,8 +294,6 @@
// Check if we can detect is_convertible using advanced SFINAE expressions
#if !defined(BOOST_NO_SFINAE_EXPR)
- #define BOOST_CONTAINER_IS_CONSTRUCTIBLE_AVAILABLE
-
//! Code inspired by Mathias Gaunard's is_convertible.cpp found in the Boost mailing list
//! http://boost.2283326.n4.nabble.com/type-traits-is-constructible-when-decltype-is-supported-td3575452.html
//! Thanks Mathias!
@@ -973,14 +971,18 @@
//! and, if the elements themselves are containers, the third allocator is passed to
//! the elements' elements, and so on. If containers are nested to a depth greater
//! than the number of allocators, the last allocator is used repeatedly, as in the
- //! single-allocator case, for any remaining recursions. [Note: The
+ //! single-allocator case, for any remaining recursions.
+ //!
+ //! [<b>Note</b>: The
//! scoped_allocator_adaptor is derived from the outer allocator type so it can be
//! substituted for the outer allocator type in most expressions. -end note]
//!
//! In the construct member functions, `OUTERMOST(x)` is x if x does not have
//! an `outer_allocator()` member function and
//! `OUTERMOST(x.outer_allocator())` otherwise; `OUTERMOST_ALLOC_TRAITS(x)` is
- //! `allocator_traits<decltype(OUTERMOST(x))>`. [Note: `OUTERMOST(x)` and
+ //! `allocator_traits<decltype(OUTERMOST(x))>`.
+ //!
+ //! [<b>Note</b>: `OUTERMOST(x)` and
//! `OUTERMOST_ALLOC_TRAITS(x)` are recursive operations. It is incumbent upon
//! the definition of `outer_allocator()` to ensure that the recursion terminates.
//! It will terminate for all instantiations of scoped_allocator_adaptor. -end note]
@@ -1067,7 +1069,7 @@
> other;
};
- //! Effects: value-initializes the OuterAlloc base class
+ //! <b>Effects</b>: value-initializes the OuterAlloc base class
//! and the inner allocator object.
scoped_allocator_adaptor()
{}
@@ -1075,13 +1077,13 @@
~scoped_allocator_adaptor()
{}
- //! Effects: initializes each allocator within the adaptor with
+ //! <b>Effects</b>: initializes each allocator within the adaptor with
//! the corresponding allocator from other.
scoped_allocator_adaptor(const scoped_allocator_adaptor& other)
: base_type(other.base())
{}
- //! Effects: move constructs each allocator within the adaptor with
+ //! <b>Effects</b>: move constructs each allocator within the adaptor with
//! the corresponding allocator from other.
scoped_allocator_adaptor(BOOST_RV_REF(scoped_allocator_adaptor) other)
: base_type(::boost::move(other.base()))
@@ -1089,8 +1091,9 @@
#if !defined(BOOST_NO_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- //! Requires: OuterAlloc shall be constructible from OuterA2.
- //! Effects: initializes the OuterAlloc base class with boost::forward<OuterA2>(outerAlloc) and inner
+ //! <b>Requires</b>: OuterAlloc shall be constructible from OuterA2.
+ //!
+ //! <b>Effects</b>: initializes the OuterAlloc base class with boost::forward<OuterA2>(outerAlloc) and inner
//! with innerAllocs...(hence recursively initializing each allocator within the adaptor with the
//! corresponding allocator from the argument list).
template <class OuterA2>
@@ -1113,8 +1116,9 @@
#endif // #if !defined(BOOST_NO_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- //! Requires: OuterAlloc shall be constructible from OuterA2.
- //! Effects: initializes each allocator within the adaptor with the corresponding allocator from other.
+ //! <b>Requires</b>: OuterAlloc shall be constructible from OuterA2.
+ //!
+ //! <b>Effects</b>: initializes each allocator within the adaptor with the corresponding allocator from other.
template <class OuterA2>
scoped_allocator_adaptor(const scoped_allocator_adaptor<OuterA2
#if !defined(BOOST_NO_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
@@ -1126,8 +1130,9 @@
: base_type(other.base())
{}
- //! Requires: OuterAlloc shall be constructible from OuterA2.
- //! Effects: initializes each allocator within the adaptor with the corresponding allocator
+ //! <b>Requires</b>: OuterAlloc shall be constructible from OuterA2.
+ //!
+ //! <b>Effects</b>: initializes each allocator within the adaptor with the corresponding allocator
//! rvalue from other.
template <class OuterA2>
scoped_allocator_adaptor(BOOST_RV_REF_BEG scoped_allocator_adaptor<OuterA2
@@ -1152,35 +1157,35 @@
return *this;
}
- //! Returns:
- //! static_cast<OuterAlloc&>(*this).
+ //! <b>Returns</b>:
+ //! `static_cast<OuterAlloc&>(*this)`.
outer_allocator_type & outer_allocator()
{ return *this; }
- //! Returns:
- //! static_cast<const OuterAlloc&>(*this).
+ //! <b>Returns</b>:
+ //! `static_cast<const OuterAlloc&>(*this)`.
const outer_allocator_type &outer_allocator() const
{ return *this; }
- //! Returns:
- //! *this if sizeof...(InnerAllocs) is zero; otherwise, inner.
+ //! <b>Returns</b>:
+ //! *this if `sizeof...(InnerAllocs)` is zero; otherwise, inner.
inner_allocator_type& inner_allocator()
{ return base_type::inner_allocator(); }
- //! Returns:
- //! *this if sizeof...(InnerAllocs) is zero; otherwise, inner.
+ //! <b>Returns</b>:
+ //! *this if `sizeof...(InnerAllocs)` is zero; otherwise, inner.
inner_allocator_type const& inner_allocator() const
{ return base_type::inner_allocator(); }
- //! Returns:
- //! allocator_traits<OuterAlloc>::max_size(outer_allocator()).
+ //! <b>Returns</b>:
+ //! `allocator_traits<OuterAlloc>::max_size(outer_allocator())`.
size_type max_size() const
{
return outer_traits_type::max_size(this->outer_allocator());
}
- //! Effects:
- //! calls OUTERMOST_ALLOC_TRAITS(*this)::destroy(OUTERMOST(*this), p).
+ //! <b>Effects</b>:
+ //! calls `OUTERMOST_ALLOC_TRAITS(*this)::destroy(OUTERMOST(*this), p)`.
template <class T>
void destroy(T* p)
{
@@ -1188,30 +1193,30 @@
::destroy(get_outermost_allocator(this->outer_allocator()), p);
}
- //! Returns:
- //! allocator_traits<OuterAlloc>::allocate(outer_allocator(), n).
+ //! <b>Returns</b>:
+ //! `allocator_traits<OuterAlloc>::allocate(outer_allocator(), n)`.
pointer allocate(size_type n)
{
return outer_traits_type::allocate(this->outer_allocator(), n);
}
- //! Returns:
- //! allocator_traits<OuterAlloc>::allocate(outer_allocator(), n, hint).
+ //! <b>Returns</b>:
+ //! `allocator_traits<OuterAlloc>::allocate(outer_allocator(), n, hint)`.
pointer allocate(size_type n, const_void_pointer hint)
{
return outer_traits_type::allocate(this->outer_allocator(), n, hint);
}
- //! Effects:
- //! allocator_traits<OuterAlloc>::deallocate(outer_allocator(), p, n);
+ //! <b>Effects</b>:
+ //! `allocator_traits<OuterAlloc>::deallocate(outer_allocator(), p, n)`.
void deallocate(pointer p, size_type n)
{
outer_traits_type::deallocate(this->outer_allocator(), p, n);
}
- //! Returns: A new scoped_allocator_adaptor object where each allocator
+ //! <b>Returns</b>: A new scoped_allocator_adaptor object where each allocator
//! A in the adaptor is initialized from the result of calling
- //! allocator_traits<A>::select_on_container_copy_construction() on
+ //! `allocator_traits<A>::select_on_container_copy_construction()` on
//! the corresponding allocator in *this.
scoped_allocator_adaptor select_on_container_copy_construction() const
{
@@ -1228,30 +1233,32 @@
#if !defined(BOOST_NO_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
- //! Effects:
- //! 1) If uses_allocator<T, inner_allocator_type>::value is false calls
- //! OUTERMOST_ALLOC_TRAITS(*this)::construct
- //! (OUTERMOST(*this), p, std::forward<Args>(args)...).
+ //! <b>Effects</b>:
+ //! 1) If `uses_allocator<T, inner_allocator_type>::value` is false calls
+ //! `OUTERMOST_ALLOC_TRAITS(*this)::construct
+ //! (OUTERMOST(*this), p, std::forward<Args>(args)...)`.
//!
- //! 2) Otherwise, if uses_allocator<T, inner_allocator_type>::value is true and
- //! is_constructible<T, allocator_arg_t, inner_allocator_type, Args...>::value is true, calls
- //! OUTERMOST_ALLOC_TRAITS(*this)::construct(OUTERMOST(*this), p, allocator_arg,
- //! inner_allocator(), std::forward<Args>(args)...).
+ //! 2) Otherwise, if `uses_allocator<T, inner_allocator_type>::value` is true and
+ //! `is_constructible<T, allocator_arg_t, inner_allocator_type, Args...>::value` is true, calls
+ //! `OUTERMOST_ALLOC_TRAITS(*this)::construct(OUTERMOST(*this), p, allocator_arg,
+ //! inner_allocator(), std::forward<Args>(args)...)`.
//!
- //! [Note: In compilers without advanced decltype SFINAE support, is_constructible can't be,
- //! implemented so that condition will be replaced by
+ //! [<b>Note</b>: In compilers without advanced decltype SFINAE support, `is_constructible` can't
+ //! be implemented so that condition will be replaced by
//! constructible_with_allocator_prefix<T>::value. -end note]
//!
//! 3) Otherwise, if uses_allocator<T, inner_allocator_type>::value is true and
- //! is_constructible<T, Args..., inner_allocator_type>::value is true, calls
- //! OUTERMOST_ALLOC_TRAITS(*this)::construct(OUTERMOST(*this), p,
- //! std::forward<Args>(args)..., inner_allocator()).
+ //! `is_constructible<T, Args..., inner_allocator_type>::value` is true, calls
+ //! `OUTERMOST_ALLOC_TRAITS(*this)::construct(OUTERMOST(*this), p,
+ //! std::forward<Args>(args)..., inner_allocator())`.
//!
- //! [Note: In compilers without advanced decltype SFINAE support, is_constructible can't be,
+ //! [<b>Note</b>: In compilers without advanced decltype SFINAE support, `is_constructible` can't be
//! implemented so that condition will be replaced by
- //! constructible_with_allocator_suffix<T>::value. -end note]
+ //! `constructible_with_allocator_suffix<T>::value`. -end note]
+ //!
+ //! 4) Otherwise, the program is ill-formed.
//!
- //! 4) Otherwise, the program is ill-formed. [Note: An error will result if uses_allocator evaluates
+ //! [<b>Note</b>: An error will result if `uses_allocator` evaluates
//! to true but the specific constructor does not take an allocator. This definition prevents a silent
//! failure to pass an inner allocator to a contained element. -end note]
template < typename T, class ...Args>
Modified: trunk/boost/container/slist.hpp
==============================================================================
--- trunk/boost/container/slist.hpp (original)
+++ trunk/boost/container/slist.hpp 2012-04-11 02:26:20 EDT (Wed, 11 Apr 2012)
@@ -65,12 +65,6 @@
struct slist_node
: public slist_hook<VoidPointer>::type
{
- private:
- slist_node();
- slist_node(const slist_node &);
- slist_node & operator=(const slist_node &);
-
- public:
typedef typename slist_hook<VoidPointer>::type hook_type;
T m_data;
};
Modified: trunk/boost/container/stable_vector.hpp
==============================================================================
--- trunk/boost/container/stable_vector.hpp (original)
+++ trunk/boost/container/stable_vector.hpp 2012-04-11 02:26:20 EDT (Wed, 11 Apr 2012)
@@ -119,12 +119,6 @@
struct node_type
: public node_type_base<VoidPointer>
{
- private:
- node_type();
- node_type(const node_type &);
- node_type & operator=(const node_type &);
-
- public:
T value;
};
Modified: trunk/boost/container/vector.hpp
==============================================================================
--- trunk/boost/container/vector.hpp (original)
+++ trunk/boost/container/vector.hpp 2012-04-11 02:26:20 EDT (Wed, 11 Apr 2012)
@@ -1463,9 +1463,10 @@
}
}
- private:
- template<class BiDirIt>
- void insert_at_ordered_positions(const size_type *positions, size_type element_count, BiDirIt end)
+ public:
+ //Absolutely experimental. This function might change, disappear or simply crash!
+ template<class BiDirPosIt, class BiDirValueIt>
+ void insert_ordered_at(size_type element_count, BiDirPosIt last_position_it, BiDirValueIt last_value_it)
{
const size_type old_size_pos = this->size();
this->reserve(old_size_pos + element_count);
@@ -1481,16 +1482,16 @@
//Loop for each insertion backwards, first moving the elements after the insertion point,
//then inserting the element.
while(insertions_left){
- const size_type pos = positions[insertions_left - 1];
+ const size_type pos = static_cast<size_type>(*(--last_position_it));
BOOST_ASSERT(pos <= old_size_pos);
//Shift the range after the insertion point, function will take care if the shift
//crosses the size() boundary, using copy/move or uninitialized copy/move if necessary.
- size_type new_hole_size = shift_range(pos, next_pos, this->size(), insertions_left);
+ size_type new_hole_size = insert_ordered_at_shift_range(pos, next_pos, this->size(), insertions_left);
if(new_hole_size > 0){
- //The hole was reduced by shift_range so expand exception rollback range backwards
+ //The hole was reduced by insert_ordered_at_shift_range so expand exception rollback range backwards
past_hole_values_destroyer.increment_size_backwards(next_pos - pos);
//Insert the new value in the hole
- allocator_traits_type::construct(this->alloc(), begin_ptr + pos + insertions_left - 1, *(--end));
+ allocator_traits_type::construct(this->alloc(), begin_ptr + pos + insertions_left - 1, *(--last_value_it));
--new_hole_size;
if(new_hole_size == 0){
//Hole was just filled, disable exception rollback and change vector size
@@ -1504,12 +1505,12 @@
}
else{
if(hole_size){
- //Hole was just filled by shift_range, disable exception rollback and change vector size
+ //Hole was just filled by insert_ordered_at_shift_range, disable exception rollback and change vector size
past_hole_values_destroyer.release();
this->members_.m_size += element_count;
}
//Insert the new value in the already constructed range
- begin_ptr[pos + insertions_left - 1] = *(--end);
+ begin_ptr[pos + insertions_left - 1] = *(--last_value_it);
}
--insertions_left;
hole_size = new_hole_size;
@@ -1517,7 +1518,58 @@
}
}
- size_type shift_range(size_type first_pos, size_type last_pos, size_type limit_pos, size_type shift_count)
+ //Takes the range pointed by [first_pos, last_pos) and shifts it to the right
+ //by 'shift_count'. 'limit_pos' marks the end of constructed elements.
+ //
+ //Precondition: first_pos <= last_pos <= limit_pos
+ //
+ //The shift operation might cross limit_pos so elements to moved beyond limit_pos
+ //are uninitialized_moved with an allocator. Other elements are moved.
+ //
+ //The shift operation might left uninitialized elements after limit_pos
+ //and the number of uninitialized elements is returned by the function.
+ //
+ //Old situation:
+ // first_pos last_pos old_limit
+ // | | |
+ // ____________V_______V__________________V_____________
+ //| prefix | range | suffix |raw_mem ~
+ //|____________|_______|__________________|_____________~
+ //
+ //New situation in Case A (hole_size == 0):
+ // range is moved through move assignments
+ //
+ // first_pos last_pos old_limit
+ // | | |
+ // ____________V_______V__________________V_____________
+ //| prefix' | | | range |suffix'|raw_mem ~
+ //|________________+______|___^___|_______|_____________~
+ // | |
+ // |_>_>_>_>_>^
+ //
+ //
+ //New situation in Case B (hole_size >= 0):
+ // range is moved through uninitialized moves
+ //
+ // first_pos last_pos old_limit
+ // | | |
+ // ____________V_______V__________________V________________
+ //| prefix' | | | [hole] | range |
+ //|_______________________________________|________|___^___|
+ // | |
+ // |_>_>_>_>_>_>_>_>_>_>_>_>_>_>_>_>_>_^
+ //
+ //New situation in Case C (hole_size == 0):
+ // range is moved through move assignments and uninitialized moves
+ //
+ // first_pos last_pos old_limit
+ // | | |
+ // ____________V_______V__________________V___
+ //| prefix' | | | range |
+ //|___________________________________|___^___|
+ // | |
+ // |_>_>_>_>_>_>_>_>_>_>_>^
+ size_type insert_ordered_at_shift_range(size_type first_pos, size_type last_pos, size_type limit_pos, size_type shift_count)
{
BOOST_ASSERT(first_pos <= last_pos);
BOOST_ASSERT(last_pos <= limit_pos);
@@ -1525,20 +1577,27 @@
T* const begin_ptr = container_detail::to_raw_pointer(this->members_.m_start);
size_type hole_size = 0;
- if((last_pos + shift_count) < limit_pos){
- //All inside
+ //Case A:
+ if((last_pos + shift_count) <= limit_pos){
+ //All move assigned
boost::move_backward(begin_ptr + first_pos, begin_ptr + last_pos, begin_ptr + last_pos + shift_count);
}
+ //Case B:
else if((first_pos + shift_count) >= limit_pos){
- //All outside
+ //All uninitialized_moved
::boost::container::uninitialized_move_alloc
(this->alloc(), begin_ptr + first_pos, begin_ptr + last_pos, begin_ptr + first_pos + shift_count);
hole_size = last_pos + shift_count - limit_pos;
}
+ //Case C:
else{
+ //Some uninitialized_moved
+ T* const limit_ptr = begin_ptr + limit_pos;
+ T* const boundary_ptr = limit_ptr - shift_count;
::boost::container::uninitialized_move_alloc
- (this->alloc(), begin_ptr + limit_pos - shift_count, begin_ptr + last_pos, begin_ptr + limit_pos);
- boost::move_backward(begin_ptr + first_pos, begin_ptr + limit_pos - shift_count, begin_ptr + limit_pos + shift_count);
+ (this->alloc(), boundary_ptr, begin_ptr + last_pos, limit_ptr);
+ //The rest is move assigned
+ boost::move_backward(begin_ptr + first_pos, boundary_ptr, limit_ptr + shift_count);
}
return hole_size;
}