summaryrefslogtreecommitdiff
path: root/boost/move
diff options
context:
space:
mode:
Diffstat (limited to 'boost/move')
-rw-r--r--boost/move/algo/adaptive_sort.hpp15
-rw-r--r--boost/move/algo/detail/adaptive_sort_merge.hpp95
-rw-r--r--boost/move/algo/detail/basic_op.hpp20
-rw-r--r--boost/move/algo/detail/insertion_sort.hpp19
-rw-r--r--boost/move/algo/detail/merge.hpp80
-rw-r--r--boost/move/algo/detail/merge_sort.hpp12
-rw-r--r--boost/move/algo/move.hpp3
-rw-r--r--boost/move/algo/predicate.hpp86
-rw-r--r--boost/move/algo/unique.hpp55
-rw-r--r--boost/move/detail/destruct_n.hpp7
-rw-r--r--boost/move/detail/fwd_macros.hpp25
-rw-r--r--boost/move/detail/iterator_to_raw_pointer.hpp59
-rw-r--r--boost/move/detail/pointer_element.hpp168
-rw-r--r--boost/move/detail/to_raw_pointer.hpp45
-rw-r--r--boost/move/detail/unique_ptr_meta_utils.hpp2
15 files changed, 544 insertions, 147 deletions
diff --git a/boost/move/algo/adaptive_sort.hpp b/boost/move/algo/adaptive_sort.hpp
index 6b5586e587..c96ab2d78b 100644
--- a/boost/move/algo/adaptive_sort.hpp
+++ b/boost/move/algo/adaptive_sort.hpp
@@ -43,18 +43,25 @@ namespace movelib {
//! ceil(sqrt(std::distance(first, last)))*2.
//!
//! <b>Caution</b>: Experimental implementation, not production-ready.
-template<class RandIt, class Compare>
+template<class RandIt, class RandRawIt, class Compare>
void adaptive_sort( RandIt first, RandIt last, Compare comp
- , typename iterator_traits<RandIt>::value_type* uninitialized = 0
- , std::size_t uninitialized_len = 0)
+ , RandRawIt uninitialized
+ , std::size_t uninitialized_len)
{
typedef typename iterator_traits<RandIt>::size_type size_type;
typedef typename iterator_traits<RandIt>::value_type value_type;
- ::boost::movelib::detail_adaptive::adaptive_xbuf<value_type> xbuf(uninitialized, uninitialized_len);
+ ::boost::movelib::detail_adaptive::adaptive_xbuf<value_type, RandRawIt> xbuf(uninitialized, uninitialized_len);
::boost::movelib::detail_adaptive::adaptive_sort_impl(first, size_type(last - first), comp, xbuf);
}
+template<class RandIt, class Compare>
+void adaptive_sort( RandIt first, RandIt last, Compare comp)
+{
+ typedef typename iterator_traits<RandIt>::value_type value_type;
+ adaptive_sort(first, last, comp, (value_type*)0, 0u);
+}
+
} //namespace movelib {
} //namespace boost {
diff --git a/boost/move/algo/detail/adaptive_sort_merge.hpp b/boost/move/algo/detail/adaptive_sort_merge.hpp
index 63b3f45979..60b5e7b06c 100644
--- a/boost/move/algo/detail/adaptive_sort_merge.hpp
+++ b/boost/move/algo/detail/adaptive_sort_merge.hpp
@@ -154,20 +154,20 @@ typename iterator_traits<ForwardIt>::size_type
return count;
}
-template<class T>
+template<class T, class RandRawIt = T*>
class adaptive_xbuf
{
adaptive_xbuf(const adaptive_xbuf &);
adaptive_xbuf & operator=(const adaptive_xbuf &);
public:
- typedef T* iterator;
+ typedef RandRawIt iterator;
adaptive_xbuf()
- : m_ptr(0), m_size(0), m_capacity(0)
+ : m_ptr(), m_size(0), m_capacity(0)
{}
- adaptive_xbuf(T *raw_memory, std::size_t capacity)
+ adaptive_xbuf(RandRawIt raw_memory, std::size_t capacity)
: m_ptr(raw_memory), m_size(0), m_capacity(capacity)
{}
@@ -183,7 +183,7 @@ class adaptive_xbuf
m_size = n;
}
else{
- T *result = boost::move(first, first+m_size, m_ptr);
+ RandRawIt result = boost::move(first, first+m_size, m_ptr);
boost::uninitialized_move(first+m_size, first+n, result);
m_size = n;
}
@@ -201,8 +201,8 @@ class adaptive_xbuf
iterator add(RandIt it)
{
BOOST_ASSERT(m_size < m_capacity);
- T * p_ret = m_ptr + m_size;
- ::new(p_ret) T(::boost::move(*it));
+ RandRawIt p_ret = m_ptr + m_size;
+ ::new(&*p_ret) T(::boost::move(*it));
++m_size;
return p_ret;
}
@@ -249,14 +249,26 @@ class adaptive_xbuf
}
}
+ private:
+ template<class RIt>
+ static bool is_raw_ptr(RIt)
+ {
+ return false;
+ }
+
+ static bool is_raw_ptr(T*)
+ {
+ return true;
+ }
+
+ public:
template<class U>
bool supports_aligned_trailing(std::size_t size, std::size_t trail_count) const
{
- if(this->data()){
- uintptr_t u_addr_sz = uintptr_t(this->data()+size);
- uintptr_t u_addr_cp = uintptr_t(this->data()+this->capacity());
+ if(this->is_raw_ptr(this->data()) && m_capacity){
+ uintptr_t u_addr_sz = uintptr_t(&*(this->data()+size));
+ uintptr_t u_addr_cp = uintptr_t(&*(this->data()+this->capacity()));
u_addr_sz = ((u_addr_sz + sizeof(U)-1)/sizeof(U))*sizeof(U);
-
return (u_addr_cp >= u_addr_sz) && ((u_addr_cp - u_addr_sz)/sizeof(U) >= trail_count);
}
return false;
@@ -271,7 +283,7 @@ class adaptive_xbuf
template<class U>
U *aligned_trailing(std::size_t pos) const
{
- uintptr_t u_addr = uintptr_t(this->data()+pos);
+ uintptr_t u_addr = uintptr_t(&*(this->data()+pos));
u_addr = ((u_addr + sizeof(U)-1)/sizeof(U))*sizeof(U);
return (U*)u_addr;
}
@@ -302,7 +314,7 @@ class adaptive_xbuf
}
private:
- T *m_ptr;
+ RandRawIt m_ptr;
std::size_t m_size;
std::size_t m_capacity;
};
@@ -458,7 +470,7 @@ RandIt partial_merge_bufferless_impl
if(first1 != last1 && comp(*last1, last1[-1])){
do{
RandIt const old_last1 = last1;
- last1 = lower_bound(last1, last2, *first1, comp);
+ last1 = boost::movelib::lower_bound(last1, last2, *first1, comp);
first1 = rotate_gcd(first1, old_last1, last1);//old_last1 == last1 supported
if(last1 == last2){
return first1;
@@ -604,13 +616,13 @@ void op_buffered_merge
size_type const len1 = size_type(middle-first);
size_type const len2 = size_type(last-middle);
if(len1 <= len2){
- first = upper_bound(first, middle, *middle, comp);
+ first = boost::movelib::upper_bound(first, middle, *middle, comp);
xbuf.move_assign(first, size_type(middle-first));
op_merge_with_right_placed
(xbuf.data(), xbuf.end(), first, middle, last, comp, op);
}
else{
- last = lower_bound(middle, last, middle[-1], comp);
+ last = boost::movelib::lower_bound(middle, last, middle[-1], comp);
xbuf.move_assign(middle, size_type(last-middle));
op_merge_with_left_placed
(first, middle, last, xbuf.data(), xbuf.end(), comp, op);
@@ -618,11 +630,11 @@ void op_buffered_merge
}
}
-template<class RandIt, class Compare>
+template<class RandIt, class Compare, class XBuf>
void buffered_merge
( RandIt first, RandIt const middle, RandIt last
, Compare comp
- , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> &xbuf)
+ , XBuf &xbuf)
{
op_buffered_merge(first, middle, last, comp, move_op(), xbuf);
}
@@ -633,15 +645,14 @@ void buffered_merge
// in the begining of the range, and ordered according to comp
//
// Returns the number of collected keys
-template<class RandIt, class Compare>
+template<class RandIt, class Compare, class XBuf>
typename iterator_traits<RandIt>::size_type
collect_unique
( RandIt const first, RandIt const last
, typename iterator_traits<RandIt>::size_type const max_collected, Compare comp
- , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf)
+ , XBuf & xbuf)
{
typedef typename iterator_traits<RandIt>::size_type size_type;
- typedef typename iterator_traits<RandIt>::value_type value_type;
size_type h = 0;
if(max_collected){
++h; // first key is always here
@@ -650,9 +661,9 @@ typename iterator_traits<RandIt>::size_type
RandIt search_end = u;
if(xbuf.capacity() >= max_collected){
- value_type *const ph0 = xbuf.add(first);
+ typename XBuf::iterator const ph0 = xbuf.add(first);
while(u != last && h < max_collected){
- value_type * const r = lower_bound(ph0, xbuf.end(), *u, comp);
+ typename XBuf::iterator const r = boost::movelib::lower_bound(ph0, xbuf.end(), *u, comp);
//If key not found add it to [h, h+h0)
if(r == xbuf.end() || comp(*u, *r) ){
RandIt const new_h0 = boost::move(search_end, u, h0);
@@ -669,7 +680,7 @@ typename iterator_traits<RandIt>::size_type
}
else{
while(u != last && h < max_collected){
- RandIt const r = lower_bound(h0, search_end, *u, comp);
+ RandIt const r = boost::movelib::lower_bound(h0, search_end, *u, comp);
//If key not found add it to [h, h+h0)
if(r == search_end || comp(*u, *r) ){
RandIt const new_h0 = rotate_gcd(h0, search_end, u);
@@ -1666,14 +1677,14 @@ void op_merge_right_step_once
//
// As a last step, if auxiliary memory is available in-place merge is performed.
// until all is merged or auxiliary memory is not large enough.
-template<class RandIt, class Compare>
+template<class RandIt, class Compare, class XBuf>
typename iterator_traits<RandIt>::size_type
adaptive_sort_build_blocks
( RandIt const first
, typename iterator_traits<RandIt>::size_type const len
, typename iterator_traits<RandIt>::size_type const l_base
, typename iterator_traits<RandIt>::size_type const l_build_buf
- , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf
+ , XBuf & xbuf
, Compare comp)
{
typedef typename iterator_traits<RandIt>::size_type size_type;
@@ -1820,7 +1831,7 @@ void adaptive_sort_combine_blocks
//Returns true if buffer is placed in
//[buffer+len-l_intbuf, buffer+len). Otherwise, buffer is
//[buffer,buffer+l_intbuf)
-template<class RandIt, class Compare>
+template<class RandIt, class Compare, class XBuf>
bool adaptive_sort_combine_all_blocks
( RandIt keys
, typename iterator_traits<RandIt>::size_type &n_keys
@@ -1828,7 +1839,7 @@ bool adaptive_sort_combine_all_blocks
, typename iterator_traits<RandIt>::size_type const l_buf_plus_data
, typename iterator_traits<RandIt>::size_type l_merged
, typename iterator_traits<RandIt>::size_type &l_intbuf
- , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf
+ , XBuf & xbuf
, Compare comp)
{
typedef typename iterator_traits<RandIt>::size_type size_type;
@@ -1916,11 +1927,11 @@ bool adaptive_sort_combine_all_blocks
return buffer_right;
}
-template<class RandIt, class Compare>
+template<class RandIt, class Compare, class XBuf>
void stable_merge
( RandIt first, RandIt const middle, RandIt last
, Compare comp
- , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> &xbuf)
+ , XBuf &xbuf)
{
BOOST_ASSERT(xbuf.empty());
typedef typename iterator_traits<RandIt>::size_type size_type;
@@ -1937,13 +1948,13 @@ void stable_merge
}
-template<class RandIt, class Compare>
+template<class RandIt, class Compare, class XBuf>
void adaptive_sort_final_merge( bool buffer_right
, RandIt const first
, typename iterator_traits<RandIt>::size_type const l_intbuf
, typename iterator_traits<RandIt>::size_type const n_keys
, typename iterator_traits<RandIt>::size_type const len
- , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf
+ , XBuf & xbuf
, Compare comp)
{
//BOOST_ASSERT(n_keys || xbuf.size() == l_intbuf);
@@ -1973,11 +1984,11 @@ void adaptive_sort_final_merge( bool buffer_right
BOOST_MOVE_ADAPTIVE_SORT_PRINT(" After final_merge : ", len);
}
-template<class RandIt, class Compare, class Unsigned, class T>
+template<class RandIt, class Compare, class Unsigned, class XBuf>
bool adaptive_sort_build_params
(RandIt first, Unsigned const len, Compare comp
, Unsigned &n_keys, Unsigned &l_intbuf, Unsigned &l_base, Unsigned &l_build_buf
- , adaptive_xbuf<T> & xbuf
+ , XBuf & xbuf
)
{
typedef Unsigned size_type;
@@ -2064,7 +2075,7 @@ bool adaptive_sort_build_params
return true;
}
-template<class RandIt, class Compare>
+template<class RandIt, class Compare, class XBuf>
inline void adaptive_merge_combine_blocks( RandIt first
, typename iterator_traits<RandIt>::size_type len1
, typename iterator_traits<RandIt>::size_type len2
@@ -2074,7 +2085,7 @@ inline void adaptive_merge_combine_blocks( RandIt first
, bool use_internal_buf
, bool xbuf_used
, Compare comp
- , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf
+ , XBuf & xbuf
)
{
typedef typename iterator_traits<RandIt>::size_type size_type;
@@ -2135,7 +2146,7 @@ inline void adaptive_merge_combine_blocks( RandIt first
}
}
-template<class RandIt, class Compare>
+template<class RandIt, class Compare, class XBuf>
inline void adaptive_merge_final_merge( RandIt first
, typename iterator_traits<RandIt>::size_type len1
, typename iterator_traits<RandIt>::size_type len2
@@ -2145,7 +2156,7 @@ inline void adaptive_merge_final_merge( RandIt first
, bool use_internal_buf
, bool xbuf_used
, Compare comp
- , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf
+ , XBuf & xbuf
)
{
typedef typename iterator_traits<RandIt>::size_type size_type;
@@ -2270,12 +2281,12 @@ inline SizeType adaptive_merge_n_keys_intbuf(SizeType &rl_block, SizeType len1,
//
// * If auxiliary memory is available, the "build_blocks" will be extended to build bigger blocks
// using classic merge.
-template<class RandIt, class Compare>
+template<class RandIt, class Compare, class XBuf>
void adaptive_sort_impl
( RandIt first
, typename iterator_traits<RandIt>::size_type const len
, Compare comp
- , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf
+ , XBuf & xbuf
)
{
typedef typename iterator_traits<RandIt>::size_type size_type;
@@ -2368,13 +2379,13 @@ void adaptive_sort_impl
// * If auxiliary memory is more than csqrtlen+n_keys*sizeof(std::size_t),
// then no csqrtlen need to be extracted and "combine_blocks" will use integral
// keys to combine blocks.
-template<class RandIt, class Compare>
+template<class RandIt, class Compare, class XBuf>
void adaptive_merge_impl
( RandIt first
, typename iterator_traits<RandIt>::size_type const len1
, typename iterator_traits<RandIt>::size_type const len2
, Compare comp
- , adaptive_xbuf<typename iterator_traits<RandIt>::value_type> & xbuf
+ , XBuf & xbuf
)
{
typedef typename iterator_traits<RandIt>::size_type size_type;
diff --git a/boost/move/algo/detail/basic_op.hpp b/boost/move/algo/detail/basic_op.hpp
index a9369e07ba..ea5faf0e53 100644
--- a/boost/move/algo/detail/basic_op.hpp
+++ b/boost/move/algo/detail/basic_op.hpp
@@ -35,19 +35,19 @@ struct four_way_t{};
struct move_op
{
template <class SourceIt, class DestinationIt>
- void operator()(SourceIt source, DestinationIt dest)
+ BOOST_MOVE_FORCEINLINE void operator()(SourceIt source, DestinationIt dest)
{ *dest = ::boost::move(*source); }
template <class SourceIt, class DestinationIt>
- DestinationIt operator()(forward_t, SourceIt first, SourceIt last, DestinationIt dest_begin)
+ BOOST_MOVE_FORCEINLINE DestinationIt operator()(forward_t, SourceIt first, SourceIt last, DestinationIt dest_begin)
{ return ::boost::move(first, last, dest_begin); }
template <class SourceIt, class DestinationIt>
- DestinationIt operator()(backward_t, SourceIt first, SourceIt last, DestinationIt dest_last)
+ BOOST_MOVE_FORCEINLINE DestinationIt operator()(backward_t, SourceIt first, SourceIt last, DestinationIt dest_last)
{ return ::boost::move_backward(first, last, dest_last); }
template <class SourceIt, class DestinationIt1, class DestinationIt2>
- void operator()(three_way_t, SourceIt srcit, DestinationIt1 dest1it, DestinationIt2 dest2it)
+ BOOST_MOVE_FORCEINLINE void operator()(three_way_t, SourceIt srcit, DestinationIt1 dest1it, DestinationIt2 dest2it)
{
*dest2it = boost::move(*dest1it);
*dest1it = boost::move(*srcit);
@@ -64,7 +64,7 @@ struct move_op
}
template <class SourceIt, class DestinationIt1, class DestinationIt2, class DestinationIt3>
- void operator()(four_way_t, SourceIt srcit, DestinationIt1 dest1it, DestinationIt2 dest2it, DestinationIt3 dest3it)
+ BOOST_MOVE_FORCEINLINE void operator()(four_way_t, SourceIt srcit, DestinationIt1 dest1it, DestinationIt2 dest2it, DestinationIt3 dest3it)
{
*dest3it = boost::move(*dest2it);
*dest2it = boost::move(*dest1it);
@@ -75,19 +75,19 @@ struct move_op
struct swap_op
{
template <class SourceIt, class DestinationIt>
- void operator()(SourceIt source, DestinationIt dest)
+ BOOST_MOVE_FORCEINLINE void operator()(SourceIt source, DestinationIt dest)
{ boost::adl_move_swap(*dest, *source); }
template <class SourceIt, class DestinationIt>
- DestinationIt operator()(forward_t, SourceIt first, SourceIt last, DestinationIt dest_begin)
+ BOOST_MOVE_FORCEINLINE DestinationIt operator()(forward_t, SourceIt first, SourceIt last, DestinationIt dest_begin)
{ return boost::adl_move_swap_ranges(first, last, dest_begin); }
template <class SourceIt, class DestinationIt>
- DestinationIt operator()(backward_t, SourceIt first, SourceIt last, DestinationIt dest_begin)
+ BOOST_MOVE_FORCEINLINE DestinationIt operator()(backward_t, SourceIt first, SourceIt last, DestinationIt dest_begin)
{ return boost::adl_move_swap_ranges_backward(first, last, dest_begin); }
template <class SourceIt, class DestinationIt1, class DestinationIt2>
- void operator()(three_way_t, SourceIt srcit, DestinationIt1 dest1it, DestinationIt2 dest2it)
+ BOOST_MOVE_FORCEINLINE void operator()(three_way_t, SourceIt srcit, DestinationIt1 dest1it, DestinationIt2 dest2it)
{
typename ::boost::movelib::iterator_traits<SourceIt>::value_type tmp(boost::move(*dest2it));
*dest2it = boost::move(*dest1it);
@@ -105,7 +105,7 @@ struct swap_op
}
template <class SourceIt, class DestinationIt1, class DestinationIt2, class DestinationIt3>
- void operator()(four_way_t, SourceIt srcit, DestinationIt1 dest1it, DestinationIt2 dest2it, DestinationIt3 dest3it)
+ BOOST_MOVE_FORCEINLINE void operator()(four_way_t, SourceIt srcit, DestinationIt1 dest1it, DestinationIt2 dest2it, DestinationIt3 dest3it)
{
typename ::boost::movelib::iterator_traits<SourceIt>::value_type tmp(boost::move(*dest3it));
*dest3it = boost::move(*dest2it);
diff --git a/boost/move/algo/detail/insertion_sort.hpp b/boost/move/algo/detail/insertion_sort.hpp
index 15df35d9d6..3328f75748 100644
--- a/boost/move/algo/detail/insertion_sort.hpp
+++ b/boost/move/algo/detail/insertion_sort.hpp
@@ -31,6 +31,7 @@
#include <boost/move/detail/destruct_n.hpp>
#include <boost/move/algo/detail/basic_op.hpp>
#include <boost/move/detail/placement_new.hpp>
+#include <boost/move/detail/iterator_to_raw_pointer.hpp>
namespace boost { namespace movelib{
@@ -91,30 +92,30 @@ void insertion_sort(BirdirectionalIterator first, BirdirectionalIterator last, C
}
}
-template <class Compare, class BirdirectionalIterator>
+template <class Compare, class BirdirectionalIterator, class BirdirectionalRawIterator>
void insertion_sort_uninitialized_copy
(BirdirectionalIterator first1, BirdirectionalIterator const last1
- , typename iterator_traits<BirdirectionalIterator>::value_type* const first2
+ , BirdirectionalRawIterator const first2
, Compare comp)
{
typedef typename iterator_traits<BirdirectionalIterator>::value_type value_type;
if (first1 != last1){
- value_type* last2 = first2;
- ::new(last2, boost_move_new_t()) value_type(move(*first1));
- destruct_n<value_type> d(first2);
+ BirdirectionalRawIterator last2 = first2;
+ ::new((iterator_to_raw_pointer)(last2), boost_move_new_t()) value_type(move(*first1));
+ destruct_n<value_type, BirdirectionalRawIterator> d(first2);
d.incr();
for (++last2; ++first1 != last1; ++last2){
- value_type* j2 = last2;
- value_type* k2 = j2;
+ BirdirectionalRawIterator j2 = last2;
+ BirdirectionalRawIterator k2 = j2;
if (comp(*first1, *--k2)){
- ::new(j2, boost_move_new_t()) value_type(move(*k2));
+ ::new((iterator_to_raw_pointer)(j2), boost_move_new_t()) value_type(move(*k2));
d.incr();
for (--j2; k2 != first2 && comp(*first1, *--k2); --j2)
*j2 = move(*k2);
*j2 = move(*first1);
}
else{
- ::new(j2, boost_move_new_t()) value_type(move(*first1));
+ ::new((iterator_to_raw_pointer)(j2), boost_move_new_t()) value_type(move(*first1));
d.incr();
}
}
diff --git a/boost/move/algo/detail/merge.hpp b/boost/move/algo/detail/merge.hpp
index 988ffd35be..621dfa28af 100644
--- a/boost/move/algo/detail/merge.hpp
+++ b/boost/move/algo/detail/merge.hpp
@@ -16,6 +16,8 @@
#include <boost/move/algo/detail/basic_op.hpp>
#include <boost/move/detail/iterator_traits.hpp>
#include <boost/move/detail/destruct_n.hpp>
+#include <boost/move/algo/predicate.hpp>
+#include <boost/move/detail/iterator_to_raw_pointer.hpp>
#include <boost/assert.hpp>
namespace boost {
@@ -181,9 +183,6 @@ void op_merge_left( RandIt buf_first
//and all elements from the second half are less)
op(forward_t(), first1, last1, buf_first);
}
- else{
- buf_first = buf_first;
- }
}
// [buf_first, first1) -> buffer
@@ -312,13 +311,13 @@ void merge_bufferless_ONlogN_recursive
if (len1 > len2) {
len11 = len1 / 2;
first_cut += len11;
- second_cut = lower_bound(middle, last, *first_cut, comp);
+ second_cut = boost::movelib::lower_bound(middle, last, *first_cut, comp);
len22 = size_type(second_cut - middle);
}
else {
len22 = len2 / 2;
second_cut += len22;
- first_cut = upper_bound(first, middle, *second_cut, comp);
+ first_cut = boost::movelib::upper_bound(first, middle, *second_cut, comp);
len11 = size_type(first_cut - first);
}
BidirIt new_middle = rotate_gcd(first_cut, middle, second_cut);
@@ -359,7 +358,7 @@ void merge_bufferless_ON2(RandIt first, RandIt middle, RandIt last, Compare comp
if((middle - first) < (last - middle)){
while(first != middle){
RandIt const old_last1 = middle;
- middle = lower_bound(middle, last, *first, comp);
+ middle = boost::movelib::lower_bound(middle, last, *first, comp);
first = rotate_gcd(first, old_last1, middle);
if(middle == last){
break;
@@ -371,7 +370,7 @@ void merge_bufferless_ON2(RandIt first, RandIt middle, RandIt last, Compare comp
}
else{
while(middle != last){
- RandIt p = upper_bound(first, middle, last[-1], comp);
+ RandIt p = boost::movelib::upper_bound(first, middle, last[-1], comp);
last = rotate_gcd(p, middle, last);
middle = p;
if(middle == first){
@@ -396,65 +395,6 @@ void merge_bufferless(RandIt first, RandIt middle, RandIt last, Compare comp)
#endif //BOOST_ADAPTIVE_MERGE_NLOGN_MERGE
}
-template<class Comp>
-struct antistable
-{
- explicit antistable(Comp &comp)
- : m_comp(comp)
- {}
-
- template<class U, class V>
- bool operator()(const U &u, const V & v)
- { return !m_comp(v, u); }
-
- private:
- antistable & operator=(const antistable &);
- Comp &m_comp;
-};
-
-template <class Comp>
-class negate
-{
- public:
- negate()
- {}
-
- explicit negate(Comp comp)
- : m_comp(comp)
- {}
-
- template <class T1, class T2>
- bool operator()(const T1& l, const T2& r)
- {
- return !m_comp(l, r);
- }
-
- private:
- Comp m_comp;
-};
-
-
-template <class Comp>
-class inverse
-{
- public:
- inverse()
- {}
-
- explicit inverse(Comp comp)
- : m_comp(comp)
- {}
-
- template <class T1, class T2>
- bool operator()(const T1& l, const T2& r)
- {
- return m_comp(r, l);
- }
-
- private:
- Comp m_comp;
-};
-
// [r_first, r_last) are already in the right part of the destination range.
template <class Compare, class InputIterator, class InputOutIterator, class Op>
void op_merge_with_right_placed
@@ -557,12 +497,12 @@ void uninitialized_merge_with_right_placed
typedef typename iterator_traits<InputOutIterator>::value_type value_type;
InputOutIterator const original_r_first = r_first;
- destruct_n<value_type> d(&*dest_first);
+ destruct_n<value_type, InputOutIterator> d(dest_first);
while ( first != last && dest_first != original_r_first ) {
if (r_first == r_last) {
for(; dest_first != original_r_first; ++dest_first, ++first){
- ::new(&*dest_first) value_type(::boost::move(*first));
+ ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*first));
d.incr();
}
d.release();
@@ -572,12 +512,12 @@ void uninitialized_merge_with_right_placed
return;
}
else if (comp(*r_first, *first)) {
- ::new(&*dest_first) value_type(::boost::move(*r_first));
+ ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*r_first));
d.incr();
++r_first;
}
else {
- ::new(&*dest_first) value_type(::boost::move(*first));
+ ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*first));
d.incr();
++first;
}
diff --git a/boost/move/algo/detail/merge_sort.hpp b/boost/move/algo/detail/merge_sort.hpp
index 892639b05f..62d185acb6 100644
--- a/boost/move/algo/detail/merge_sort.hpp
+++ b/boost/move/algo/detail/merge_sort.hpp
@@ -79,9 +79,9 @@ void merge_sort_copy( RandIt first, RandIt last
}
}
-template<class RandIt, class Compare>
+template<class RandIt, class RandItRaw, class Compare>
void merge_sort_uninitialized_copy( RandIt first, RandIt last
- , typename iterator_traits<RandIt>::value_type* uninitialized
+ , RandItRaw uninitialized
, Compare comp)
{
typedef typename iterator_traits<RandIt>::size_type size_type;
@@ -94,7 +94,7 @@ void merge_sort_uninitialized_copy( RandIt first, RandIt last
else{
size_type const half = count/2;
merge_sort_uninitialized_copy(first + half, last, uninitialized + half, comp);
- destruct_n<value_type> d(uninitialized+half);
+ destruct_n<value_type, RandItRaw> d(uninitialized+half);
d.incr(count-half);
merge_sort_copy(first, first + half, first + half, comp);
uninitialized_merge_with_right_placed
@@ -105,9 +105,9 @@ void merge_sort_uninitialized_copy( RandIt first, RandIt last
}
}
-template<class RandIt, class Compare>
+template<class RandIt, class RandItRaw, class Compare>
void merge_sort( RandIt first, RandIt last, Compare comp
- , typename iterator_traits<RandIt>::value_type* uninitialized)
+ , RandItRaw uninitialized)
{
typedef typename iterator_traits<RandIt>::size_type size_type;
typedef typename iterator_traits<RandIt>::value_type value_type;
@@ -123,7 +123,7 @@ void merge_sort( RandIt first, RandIt last, Compare comp
RandIt const rest_it = first + rest;
merge_sort_uninitialized_copy(half_it, last, uninitialized, comp);
- destruct_n<value_type> d(uninitialized);
+ destruct_n<value_type, RandItRaw> d(uninitialized);
d.incr(rest);
merge_sort_copy(first, half_it, rest_it, comp);
merge_with_right_placed
diff --git a/boost/move/algo/move.hpp b/boost/move/algo/move.hpp
index d35f04a399..2390877a43 100644
--- a/boost/move/algo/move.hpp
+++ b/boost/move/algo/move.hpp
@@ -26,6 +26,7 @@
#include <boost/move/utility_core.hpp>
#include <boost/move/detail/iterator_traits.hpp>
+#include <boost/move/detail/iterator_to_raw_pointer.hpp>
#include <boost/detail/no_exceptions_support.hpp>
namespace boost {
@@ -126,7 +127,7 @@ F uninitialized_move(I f, I l, F r
}
BOOST_CATCH(...){
for (; back != r; ++back){
- back->~input_value_type();
+ boost::movelib::iterator_to_raw_pointer(back)->~input_value_type();
}
BOOST_RETHROW;
}
diff --git a/boost/move/algo/predicate.hpp b/boost/move/algo/predicate.hpp
new file mode 100644
index 0000000000..0287d66318
--- /dev/null
+++ b/boost/move/algo/predicate.hpp
@@ -0,0 +1,86 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2015-2016.
+// Distributed under 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)
+//
+// See http://www.boost.org/libs/move for documentation.
+//
+//////////////////////////////////////////////////////////////////////////////
+#ifndef BOOST_MOVE_ALGO_PREDICATE_HPP
+#define BOOST_MOVE_ALGO_PREDICATE_HPP
+
+#include <boost/move/algo/move.hpp>
+#include <boost/move/adl_move_swap.hpp>
+#include <boost/move/algo/detail/basic_op.hpp>
+#include <boost/move/detail/iterator_traits.hpp>
+#include <boost/move/detail/destruct_n.hpp>
+#include <boost/assert.hpp>
+
+namespace boost {
+namespace movelib {
+
+template<class Comp>
+struct antistable
+{
+ explicit antistable(Comp &comp)
+ : m_comp(comp)
+ {}
+
+ template<class U, class V>
+ bool operator()(const U &u, const V & v)
+ { return !m_comp(v, u); }
+
+ private:
+ antistable & operator=(const antistable &);
+ Comp &m_comp;
+};
+
+template <class Comp>
+class negate
+{
+ public:
+ negate()
+ {}
+
+ explicit negate(Comp comp)
+ : m_comp(comp)
+ {}
+
+ template <class T1, class T2>
+ bool operator()(const T1& l, const T2& r)
+ {
+ return !m_comp(l, r);
+ }
+
+ private:
+ Comp m_comp;
+};
+
+
+template <class Comp>
+class inverse
+{
+ public:
+ inverse()
+ {}
+
+ explicit inverse(Comp comp)
+ : m_comp(comp)
+ {}
+
+ template <class T1, class T2>
+ bool operator()(const T1& l, const T2& r)
+ {
+ return m_comp(r, l);
+ }
+
+ private:
+ Comp m_comp;
+};
+
+} //namespace movelib {
+} //namespace boost {
+
+#endif //#define BOOST_MOVE_ALGO_PREDICATE_HPP
diff --git a/boost/move/algo/unique.hpp b/boost/move/algo/unique.hpp
new file mode 100644
index 0000000000..8022a654e2
--- /dev/null
+++ b/boost/move/algo/unique.hpp
@@ -0,0 +1,55 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2017-2017.
+// Distributed under 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)
+//
+// See http://www.boost.org/libs/move for documentation.
+//
+//////////////////////////////////////////////////////////////////////////////
+
+#ifndef BOOST_MOVE_ALGO_UNIQUE_HPP
+#define BOOST_MOVE_ALGO_UNIQUE_HPP
+
+#include <boost/move/detail/config_begin.hpp>
+#include <boost/move/utility_core.hpp>
+
+namespace boost {
+namespace movelib {
+
+//! <b>Requires</b>: The comparison function shall be an equivalence relation. The type of *first shall satisfy
+//! the MoveAssignable requirements
+//!
+//! <b>Effects</b>: For a nonempty range, eliminates all but the first element from every consecutive group
+//! of equivalent elements referred to by the iterator i in the range [first + 1, last) for which the
+//! following conditions hold: pred(*(i - 1), *i) != false.
+//!
+//! <b>Returns</b>: The end of the resulting range.
+//!
+//! <b>Complexity</b>: For nonempty ranges, exactly (last - first) - 1 applications of the corresponding predicate.
+template<class ForwardIterator, class BinaryPredicate>
+ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred)
+{
+ if (first != last) {
+ ForwardIterator next(first);
+ ++next;
+ for (; next != last; ++next, ++first) {
+ if (pred(*first, *next)) { //Find first equal element
+ while (++next != last)
+ if (!pred(*first, *next))
+ *++first = ::boost::move(*next);
+ break;
+ }
+ }
+ ++first;
+ }
+ return first;
+}
+
+} //namespace movelib {
+} //namespace boost {
+
+#include <boost/move/detail/config_end.hpp>
+
+#endif //#define BOOST_MOVE_ALGO_UNIQUE_HPP
diff --git a/boost/move/detail/destruct_n.hpp b/boost/move/detail/destruct_n.hpp
index 06f1f589ed..9f60fc2773 100644
--- a/boost/move/detail/destruct_n.hpp
+++ b/boost/move/detail/destruct_n.hpp
@@ -27,11 +27,11 @@
namespace boost {
namespace movelib{
-template<class T>
+template<class T, class RandItUninit>
class destruct_n
{
public:
- explicit destruct_n(T *raw)
+ explicit destruct_n(RandItUninit raw)
: m_ptr(raw), m_size()
{}
@@ -48,7 +48,6 @@ class destruct_n
void release()
{
m_size = 0u;
- m_ptr = 0;
}
~destruct_n()
@@ -58,7 +57,7 @@ class destruct_n
}
}
private:
- T *m_ptr;
+ RandItUninit m_ptr;
std::size_t m_size;
};
diff --git a/boost/move/detail/fwd_macros.hpp b/boost/move/detail/fwd_macros.hpp
index 7132436783..a5df5f1be7 100644
--- a/boost/move/detail/fwd_macros.hpp
+++ b/boost/move/detail/fwd_macros.hpp
@@ -458,6 +458,31 @@ namespace move_detail {
#define BOOST_MOVE_CLASSDFLTQ8 BOOST_MOVE_CLASSDFLTQ7, class Q7 = void
#define BOOST_MOVE_CLASSDFLTQ9 BOOST_MOVE_CLASSDFLTQ8, class Q8 = void
+//BOOST_MOVE_LAST_TARGN
+#define BOOST_MOVE_LAST_TARG0 void
+#define BOOST_MOVE_LAST_TARG1 P0
+#define BOOST_MOVE_LAST_TARG2 P1
+#define BOOST_MOVE_LAST_TARG3 P2
+#define BOOST_MOVE_LAST_TARG4 P3
+#define BOOST_MOVE_LAST_TARG5 P4
+#define BOOST_MOVE_LAST_TARG6 P5
+#define BOOST_MOVE_LAST_TARG7 P6
+#define BOOST_MOVE_LAST_TARG8 P7
+#define BOOST_MOVE_LAST_TARG9 P8
+
+//BOOST_MOVE_LAST_TARGQN
+#define BOOST_MOVE_LAST_TARGQ0 void
+#define BOOST_MOVE_LAST_TARGQ1 Q0
+#define BOOST_MOVE_LAST_TARGQ2 Q1
+#define BOOST_MOVE_LAST_TARGQ3 Q2
+#define BOOST_MOVE_LAST_TARGQ4 Q3
+#define BOOST_MOVE_LAST_TARGQ5 Q4
+#define BOOST_MOVE_LAST_TARGQ6 Q5
+#define BOOST_MOVE_LAST_TARGQ7 Q6
+#define BOOST_MOVE_LAST_TARGQ8 Q7
+#define BOOST_MOVE_LAST_TARGQ9 Q8
+
+
//BOOST_MOVE_TARGN
#define BOOST_MOVE_TARG0
#define BOOST_MOVE_TARG1 P0
diff --git a/boost/move/detail/iterator_to_raw_pointer.hpp b/boost/move/detail/iterator_to_raw_pointer.hpp
new file mode 100644
index 0000000000..97ee3a6595
--- /dev/null
+++ b/boost/move/detail/iterator_to_raw_pointer.hpp
@@ -0,0 +1,59 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2014-2015. Distributed under 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)
+//
+// See http://www.boost.org/libs/container for documentation.
+//
+//////////////////////////////////////////////////////////////////////////////
+#ifndef BOOST_MOVE_DETAIL_ITERATOR_TO_RAW_POINTER_HPP
+#define BOOST_MOVE_DETAIL_ITERATOR_TO_RAW_POINTER_HPP
+
+#ifndef BOOST_CONFIG_HPP
+# include <boost/config.hpp>
+#endif
+
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+# pragma once
+#endif
+
+#include <boost/move/detail/iterator_traits.hpp>
+#include <boost/move/detail/to_raw_pointer.hpp>
+#include <boost/move/detail/pointer_element.hpp>
+
+namespace boost {
+namespace movelib {
+namespace detail {
+
+template <class T>
+inline T* iterator_to_pointer(T* i)
+{ return i; }
+
+template <class Iterator>
+inline typename boost::movelib::iterator_traits<Iterator>::pointer
+ iterator_to_pointer(const Iterator &i)
+{ return i.operator->(); }
+
+template <class Iterator>
+struct iterator_to_element_ptr
+{
+ typedef typename boost::movelib::iterator_traits<Iterator>::pointer pointer;
+ typedef typename boost::movelib::pointer_element<pointer>::type element_type;
+ typedef element_type* type;
+};
+
+} //namespace detail {
+
+template <class Iterator>
+inline typename boost::movelib::detail::iterator_to_element_ptr<Iterator>::type
+ iterator_to_raw_pointer(const Iterator &i)
+{
+ return ::boost::movelib::to_raw_pointer
+ ( ::boost::movelib::detail::iterator_to_pointer(i) );
+}
+
+} //namespace movelib {
+} //namespace boost {
+
+#endif //#ifndef BOOST_MOVE_DETAIL_ITERATOR_TO_RAW_POINTER_HPP
diff --git a/boost/move/detail/pointer_element.hpp b/boost/move/detail/pointer_element.hpp
new file mode 100644
index 0000000000..ecdd6080ce
--- /dev/null
+++ b/boost/move/detail/pointer_element.hpp
@@ -0,0 +1,168 @@
+//////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2014-2017. Distributed under 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)
+//
+// See http://www.boost.org/libs/move for documentation.
+//
+//////////////////////////////////////////////////////////////////////////////
+
+#ifndef BOOST_MOVE_DETAIL_POINTER_ELEMENT_HPP
+#define BOOST_MOVE_DETAIL_POINTER_ELEMENT_HPP
+
+#ifndef BOOST_CONFIG_HPP
+# include <boost/config.hpp>
+#endif
+
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+# pragma once
+#endif
+
+#ifndef BOOST_MOVE_DETAIL_WORKAROUND_HPP
+#include <boost/move/detail/workaround.hpp>
+#endif //BOOST_MOVE_DETAIL_WORKAROUND_HPP
+
+namespace boost {
+namespace movelib {
+namespace detail{
+
+//////////////////////
+//struct first_param
+//////////////////////
+
+template <typename T> struct first_param
+{ typedef void type; };
+
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+ template <template <typename, typename...> class TemplateClass, typename T, typename... Args>
+ struct first_param< TemplateClass<T, Args...> >
+ {
+ typedef T type;
+ };
+
+#else //C++03 compilers
+
+ template < template //0arg
+ <class
+ > class TemplateClass, class T
+ >
+ struct first_param
+ < TemplateClass<T> >
+ { typedef T type; };
+
+ template < template //1arg
+ <class,class
+ > class TemplateClass, class T
+ , class P0>
+ struct first_param
+ < TemplateClass<T, P0> >
+ { typedef T type; };
+
+ template < template //2arg
+ <class,class,class
+ > class TemplateClass, class T
+ , class P0, class P1>
+ struct first_param
+ < TemplateClass<T, P0, P1> >
+ { typedef T type; };
+
+ template < template //3arg
+ <class,class,class,class
+ > class TemplateClass, class T
+ , class P0, class P1, class P2>
+ struct first_param
+ < TemplateClass<T, P0, P1, P2> >
+ { typedef T type; };
+
+ template < template //4arg
+ <class,class,class,class,class
+ > class TemplateClass, class T
+ , class P0, class P1, class P2, class P3>
+ struct first_param
+ < TemplateClass<T, P0, P1, P2, P3> >
+ { typedef T type; };
+
+ template < template //5arg
+ <class,class,class,class,class,class
+ > class TemplateClass, class T
+ , class P0, class P1, class P2, class P3, class P4>
+ struct first_param
+ < TemplateClass<T, P0, P1, P2, P3, P4> >
+ { typedef T type; };
+
+ template < template //6arg
+ <class,class,class,class,class,class,class
+ > class TemplateClass, class T
+ , class P0, class P1, class P2, class P3, class P4, class P5>
+ struct first_param
+ < TemplateClass<T, P0, P1, P2, P3, P4, P5> >
+ { typedef T type; };
+
+ template < template //7arg
+ <class,class,class,class,class,class,class,class
+ > class TemplateClass, class T
+ , class P0, class P1, class P2, class P3, class P4, class P5, class P6>
+ struct first_param
+ < TemplateClass<T, P0, P1, P2, P3, P4, P5, P6> >
+ { typedef T type; };
+
+ template < template //8arg
+ <class,class,class,class,class,class,class,class,class
+ > class TemplateClass, class T
+ , class P0, class P1, class P2, class P3, class P4, class P5, class P6, class P7>
+ struct first_param
+ < TemplateClass<T, P0, P1, P2, P3, P4, P5, P6, P7> >
+ { typedef T type; };
+
+ template < template //9arg
+ <class,class,class,class,class,class,class,class,class,class
+ > class TemplateClass, class T
+ , class P0, class P1, class P2, class P3, class P4, class P5, class P6, class P7, class P8>
+ struct first_param
+ < TemplateClass<T, P0, P1, P2, P3, P4, P5, P6, P7, P8> >
+ { typedef T type; };
+
+#endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+template <typename T>
+struct has_internal_pointer_element
+{
+ template <typename X>
+ static char test(int, typename X::element_type*);
+
+ template <typename X>
+ static int test(...);
+
+ static const bool value = (1 == sizeof(test<T>(0, 0)));
+};
+
+template<class Ptr, bool = has_internal_pointer_element<Ptr>::value>
+struct pointer_element_impl
+{
+ typedef typename Ptr::element_type type;
+};
+
+template<class Ptr>
+struct pointer_element_impl<Ptr, false>
+{
+ typedef typename boost::movelib::detail::first_param<Ptr>::type type;
+};
+
+} //namespace detail{
+
+template <typename Ptr>
+struct pointer_element
+{
+ typedef typename ::boost::movelib::detail::pointer_element_impl<Ptr>::type type;
+};
+
+template <typename T>
+struct pointer_element<T*>
+{ typedef T type; };
+
+} //namespace movelib {
+} //namespace boost {
+
+#endif // defined(BOOST_MOVE_DETAIL_POINTER_ELEMENT_HPP)
diff --git a/boost/move/detail/to_raw_pointer.hpp b/boost/move/detail/to_raw_pointer.hpp
new file mode 100644
index 0000000000..7e89beb4db
--- /dev/null
+++ b/boost/move/detail/to_raw_pointer.hpp
@@ -0,0 +1,45 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2017-2017
+//
+// Distributed under 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)
+//
+// See http://www.boost.org/libs/move for documentation.
+//
+/////////////////////////////////////////////////////////////////////////////
+
+#ifndef BOOST_MOVE_DETAIL_TO_RAW_POINTER_HPP
+#define BOOST_MOVE_DETAIL_TO_RAW_POINTER_HPP
+
+#ifndef BOOST_CONFIG_HPP
+# include <boost/config.hpp>
+#endif
+
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+# pragma once
+#endif
+
+#include <boost/move/detail/config_begin.hpp>
+#include <boost/move/detail/workaround.hpp>
+#include <boost/move/detail/pointer_element.hpp>
+
+namespace boost {
+namespace movelib {
+
+template <class T>
+BOOST_MOVE_FORCEINLINE T* to_raw_pointer(T* p)
+{ return p; }
+
+template <class Pointer>
+BOOST_MOVE_FORCEINLINE typename boost::movelib::pointer_element<Pointer>::type*
+to_raw_pointer(const Pointer &p)
+{ return ::boost::movelib::to_raw_pointer(p.operator->()); }
+
+} //namespace movelib
+} //namespace boost
+
+#include <boost/move/detail/config_end.hpp>
+
+#endif //BOOST_MOVE_DETAIL_TO_RAW_POINTER_HPP
diff --git a/boost/move/detail/unique_ptr_meta_utils.hpp b/boost/move/detail/unique_ptr_meta_utils.hpp
index ac270a8fc0..e11124d898 100644
--- a/boost/move/detail/unique_ptr_meta_utils.hpp
+++ b/boost/move/detail/unique_ptr_meta_utils.hpp
@@ -446,7 +446,7 @@ class is_convertible
#define BOOST_MOVE_TT_DECL
#endif
-#if defined(_MSC_EXTENSIONS) && !defined(__BORLAND__) && !defined(_WIN64) && !defined(_M_ARM) && !defined(UNDER_CE)
+#if defined(_MSC_EXTENSIONS) && !defined(__BORLAND__) && !defined(_WIN64) && !defined(_M_ARM) && !defined(_M_ARM64) && !defined(UNDER_CE)
#define BOOST_MOVE_TT_TEST_MSC_FUNC_SIGS
#endif