// If _Iterator has a base returns it otherwise _Iterator is returned
// untouched
template<typename _Iterator, bool _HasBase>
- struct __iter_base
+ struct _Iter_base
{
- static _Iterator
- __b(_Iterator __it)
+ typedef _Iterator iterator_type;
+ static iterator_type
+ _S_base(_Iterator __it)
{ return __it; }
};
template<typename _Iterator>
- struct __iter_base<_Iterator, true>
+ struct _Iter_base<_Iterator, true>
{
- static typename _Iterator::iterator_type
- __b(_Iterator __it)
+ typedef typename _Iterator::iterator_type iterator_type;
+ static iterator_type
+ _S_base(_Iterator __it)
{ return __it.base(); }
};
// If _Iterator is a __normal_iterator return its base (a plain pointer,
// normally) otherwise return it untouched. See copy, fill, ...
template<typename _Iterator>
- struct __niter_base
- : __iter_base<_Iterator, __is_normal_iterator<_Iterator>::__value>
+ struct _Niter_base
+ : _Iter_base<_Iterator, __is_normal_iterator<_Iterator>::__value>
{ };
+ template<typename _Iterator>
+ inline typename _Niter_base<_Iterator>::iterator_type
+ __niter_base(_Iterator __it)
+ { return std::_Niter_base<_Iterator>::_S_base(__it); }
+
// Likewise, for move_iterator.
template<typename _Iterator>
- struct __miter_base
- : __iter_base<_Iterator, __is_move_iterator<_Iterator>::__value>
+ struct _Miter_base
+ : _Iter_base<_Iterator, __is_move_iterator<_Iterator>::__value>
{ };
+ template<typename _Iterator>
+ inline typename _Miter_base<_Iterator>::iterator_type
+ __miter_base(_Iterator __it)
+ { return std::_Miter_base<_Iterator>::_S_base(__it); }
+
// All of these auxiliary structs serve two purposes. (1) Replace
// calls to copy with memmove whenever possible. (Memmove, not memcpy,
// because the input and output ranges are permitted to overlap.)
inline _OI
__copy_move_a2(_II __first, _II __last, _OI __result)
{
- return _OI(std::__copy_move_a<_IsMove>
- (std::__niter_base<_II>::__b(__first),
- std::__niter_base<_II>::__b(__last),
- std::__niter_base<_OI>::__b(__result)));
+ return _OI(std::__copy_move_a<_IsMove>(std::__niter_base(__first),
+ std::__niter_base(__last),
+ std::__niter_base(__result)));
}
/**
__glibcxx_requires_valid_range(__first, __last);
return (std::__copy_move_a2<__is_move_iterator<_II>::__value>
- (std::__miter_base<_II>::__b(__first),
- std::__miter_base<_II>::__b(__last), __result));
+ (std::__miter_base(__first), std::__miter_base(__last),
+ __result));
}
#ifdef __GXX_EXPERIMENTAL_CXX0X__
typename iterator_traits<_II>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- return (std::__copy_move_a2<true>
- (std::__miter_base<_II>::__b(__first),
- std::__miter_base<_II>::__b(__last), __result));
+ return std::__copy_move_a2<true>(std::__miter_base(__first),
+ std::__miter_base(__last), __result);
}
#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
__copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
{
return _BI2(std::__copy_move_backward_a<_IsMove>
- (std::__niter_base<_BI1>::__b(__first),
- std::__niter_base<_BI1>::__b(__last),
- std::__niter_base<_BI2>::__b(__result)));
+ (std::__niter_base(__first), std::__niter_base(__last),
+ std::__niter_base(__result)));
}
/**
__glibcxx_requires_valid_range(__first, __last);
return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value>
- (std::__miter_base<_BI1>::__b(__first),
- std::__miter_base<_BI1>::__b(__last), __result));
+ (std::__miter_base(__first), std::__miter_base(__last),
+ __result));
}
#ifdef __GXX_EXPERIMENTAL_CXX0X__
typename iterator_traits<_BI2>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- return (std::__copy_move_backward_a2<true>
- (std::__miter_base<_BI1>::__b(__first),
- std::__miter_base<_BI1>::__b(__last), __result));
+ return std::__copy_move_backward_a2<true>(std::__miter_base(__first),
+ std::__miter_base(__last),
+ __result);
}
#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
_ForwardIterator>)
__glibcxx_requires_valid_range(__first, __last);
- std::__fill_a(std::__niter_base<_ForwardIterator>::__b(__first),
- std::__niter_base<_ForwardIterator>::__b(__last), __value);
+ std::__fill_a(std::__niter_base(__first), std::__niter_base(__last),
+ __value);
}
template<typename _OutputIterator, typename _Size, typename _Tp>
__gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
__fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
{
- for (; __n > 0; --__n, ++__first)
+ for (__decltype(__n + 0) __niter = __n;
+ __niter > 0; --__niter, ++__first)
*__first = __value;
return __first;
}
__fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
{
const _Tp __tmp = __value;
- for (; __n > 0; --__n, ++__first)
+ for (__decltype(__n + 0) __niter = __n;
+ __niter > 0; --__niter, ++__first)
*__first = __tmp;
return __first;
}
// concept requirements
__glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)
- return _OI(std::__fill_n_a(std::__niter_base<_OI>::__b(__first),
- __n, __value));
+ return _OI(std::__fill_n_a(std::__niter_base(__first), __n, __value));
}
template<bool _BoolType>
__first2, __last2);
}
+ /**
+ * @brief Finds the first position in which @a val could be inserted
+ * without changing the ordering.
+ * @param first An iterator.
+ * @param last Another iterator.
+ * @param val The search term.
+ * @return An iterator pointing to the first element <em>not less
+ * than</em> @a val, or end() if every element is less than
+ * @a val.
+ * @ingroup binary_search_algorithms
+ */
+ template<typename _ForwardIterator, typename _Tp>
+ _ForwardIterator
+ lower_bound(_ForwardIterator __first, _ForwardIterator __last,
+ const _Tp& __val)
+ {
+ typedef typename iterator_traits<_ForwardIterator>::value_type
+ _ValueType;
+ typedef typename iterator_traits<_ForwardIterator>::difference_type
+ _DistanceType;
+
+ // concept requirements
+ __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
+ __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
+ __glibcxx_requires_partitioned_lower(__first, __last, __val);
+
+ _DistanceType __len = std::distance(__first, __last);
+ _DistanceType __half;
+ _ForwardIterator __middle;
+
+ while (__len > 0)
+ {
+ __half = __len >> 1;
+ __middle = __first;
+ std::advance(__middle, __half);
+ if (*__middle < __val)
+ {
+ __first = __middle;
+ ++__first;
+ __len = __len - __half - 1;
+ }
+ else
+ __len = __half;
+ }
+ return __first;
+ }
+
+ /// This is a helper function for the sort routines and for random.tcc.
+ // Precondition: __n > 0.
+ template<typename _Size>
+ inline _Size
+ __lg(_Size __n)
+ {
+ _Size __k;
+ for (__k = 0; __n != 0; __n >>= 1)
+ ++__k;
+ return __k - 1;
+ }
+
+ inline int
+ __lg(int __n)
+ { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); }
+
+ inline long
+ __lg(long __n)
+ { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
+
+ inline long long
+ __lg(long long __n)
+ { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
+
_GLIBCXX_END_NAMESPACE
_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
typename iterator_traits<_II2>::value_type>)
__glibcxx_requires_valid_range(__first1, __last1);
- return std::__equal_aux(std::__niter_base<_II1>::__b(__first1),
- std::__niter_base<_II1>::__b(__last1),
- std::__niter_base<_II2>::__b(__first2));
+ return std::__equal_aux(std::__niter_base(__first1),
+ std::__niter_base(__last1),
+ std::__niter_base(__first2));
}
/**
}
/**
- * @brief Performs 'dictionary' comparison on ranges.
+ * @brief Performs @b dictionary comparison on ranges.
* @ingroup sorting_algorithms
* @param first1 An input iterator.
* @param last1 An input iterator.
* @param last2 An input iterator.
* @return A boolean true or false.
*
- * 'Returns true if the sequence of elements defined by the range
+ * <em>Returns true if the sequence of elements defined by the range
* [first1,last1) is lexicographically less than the sequence of elements
- * defined by the range [first2,last2). Returns false otherwise.'
+ * defined by the range [first2,last2). Returns false otherwise.</em>
* (Quoted from [25.3.8]/1.) If the iterators are all character pointers,
* then this is an inline call to @c memcmp.
*/
__glibcxx_requires_valid_range(__first1, __last1);
__glibcxx_requires_valid_range(__first2, __last2);
- return std::__lexicographical_compare_aux
- (std::__niter_base<_II1>::__b(__first1),
- std::__niter_base<_II1>::__b(__last1),
- std::__niter_base<_II2>::__b(__first2),
- std::__niter_base<_II2>::__b(__last2));
+ return std::__lexicographical_compare_aux(std::__niter_base(__first1),
+ std::__niter_base(__last1),
+ std::__niter_base(__first2),
+ std::__niter_base(__last2));
}
/**
- * @brief Performs "dictionary" comparison on ranges.
+ * @brief Performs @b dictionary comparison on ranges.
* @ingroup sorting_algorithms
* @param first1 An input iterator.
* @param last1 An input iterator.
OSDN Git Service
