//---------------------------15/03/30----------------------------
//min_element
template<class ForwardIterator>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last)
{
if(first == last)
return first;
ForwardIterator result = first;
while(++first != last)
if(*first < *result) //自定义版本if(comp(*first, *result))
result = first;
return result;
}
//partition
//快排的基本步骤：划分，让判断true的元素放在区间前，让判断为false的元素放在区间后
//返回第一个非true的位置：第一种情况 end。第二种情况 元素被判断为flase
//这是不稳定的。
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator partition(BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred)
{
while (true)
{
while (true)
{
if(first == last)
return first;
else if(pred(*first))
++first;
else
break;
}
--last; //第一次指向的事end所以-- 之后指向的是判断过的数，所以要--
while (true)
{
if(first == last)
return first;
else if(!pred(*last))
--last;
else
break;
}
iter_swap(first, last);
++first; //接下来要判断下一个
}
}
//remove
template<class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last,
const T& value)
{
first = find(first, last, value);
ForwardIterator next = first;
return first == last ? first : remove_copy(++next, last, first, value);
}
template<class InputIterator, class OutputIterator, class T>
OutputIterator remove_copy(InputIterator, first, InputIterator last,
OutputIterator result, const T& value)
{
for(; first != last; ++first)
if(*first != value) //remove_copy_if版本 if(!pred(*first))
{
*result = *first;
++result;
}
return result;
}
//replace
template<class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last,
const T& old_value, const T& new_value)
{
for(; first != last; ++first)
if(*first == old_value)
*first = new_value;
//replace_if版本 if(pred(*first)) *first = new_value;
}
template<class InputIterator, class OutputIterator, class T>
OutputIterator replace_copy(InputIterator first, InputIterator last,
OutputIterator result, const T& old_value,
const T& new_value)
{
for(; first != last; ++first, ++result)
*result = *first == old_value ? new_value : *first;
//replace_copy_if版本 *result = pred(*first) ? new_value : *first;
return result;
}
//reverse
template<class BidirectionalIterator>
inline void reverse(BidirectionalIterator first, BidirectionalIterator last)
{
__reverse(first, last, iterator_category(first));
}
template<class BidirectionalIterator>
void __reverse(BidirectionalIterator first, BidirectionalIterator last,
bidirectional_iterator_tag)
{
while (true)
{
if(first == last || first == --last)
return;
else
iter_swap(first++, last);
}
}
//随机迭代器的版本只需要判断一次 而非随机迭代器要判断两次，故效率上有差距，所以分开写
template<class RandomAccessIterator>
void __reverse(RandomAccessIterator first, RandomAccessIterator last,
random_access_iterator_tag)
{
while(first < last)
iter_swap(first++, --last);
}
template<class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy(BidirectionalIterator first,
BidirectionalIterator last,
OutputIterator result)
{
while (first != last)
{
--last;
*result = *last;
++result;
}
return result;
}
//rotate
template<class ForwardIterator>
inline void rotate(ForwardIterator first, ForwardIterator middle,
ForwardIterator last)
{
if(first == middle || middle == last)
return;
__rotate(first, middle, last, distance_type(first),
iterator_category(first));
}
//单向的迭代器走这边
//只能单向行走，效率最低，要赋值起码1.5n次(当两者区间相同时)。
//调用一次swap就要赋值3次
template<class ForwardIterator, class Distance>
void __rotate(ForwardIterator first, ForwardIterator middle,
ForwardIterator last, Distance*, forward_iterator_tag)
{
for(ForwardIterator i = middle; ;)
{
iter_swap(first, i);
++first;
++i;
if(first == middle)
{
if(i == last)
return;
middle = i;
}
else if(i ==last)
i = middle;
}
}
//三次反转 固定赋值1.5n次
template<class BidirectionalIterator, class Distance>
void __rotate(BidirectionalIterator first, BidirectionalIterator middle,
BidirectionalIterator last, Distance*,
bidirectional_iterator_tag)
{
reverse(first, middle);
reverse(middle, last);
reverse(first, last);
}
template<class RandomAccessIterator, class Distance>
void __rotate(RandomAccessIterator first, RandomAccessIterator middle,
RandomAccessIterator last, Distance*,
random_access_iterator_tag)
{
Distance n = __gcd(last - first, middle - first);
while (n--)
__rotate_cycle(first, last, first + n, middle - first,
value_type(first));
}
template<class EuclideanRingElement>
EuclideanRingElement __gcd(EuclideanRingElement m, EuclideanRingElement n)
{
while (n != 0)
{
EuclideanRingElement t = m % n;
m = n;
n = t;
}
return m;
}
//最差的情况赋值1.5n次(当区间相等时)，最少赋值n＋1次(第一个或第二个区间为1时)。
template<class RandomAccessIteratorm, class Distance, class T>
void __rotate_cycle(RandomAccessIterator first, RandomAccessIterator last,
RandomAccessIterator initial, Distance shift, T*)
{
T value = *initial;
RandomAccessIterator ptr1 = initial;
RandomAccessIterator ptr2 = ptr1 + shift;
while (ptr2 != initial)
{
*ptr1 = *ptr2;
ptr1 = ptr2;
if(last - ptr2 > shift)
ptr2 += shift;
else
ptr2 = first + (shift - (last - ptr2));
}
*ptr1 = value;
}
//rotate_copy
template<class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle,
ForwardIterator last, OutputIterator result)
{
return copy(first, middle, copy(middle, last, result));
}
//search
template<class ForwardIterator1, class ForwardIterator2>
inline ForwardIterator search(ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator last2)
{
return __search(first1, last1, first2, last2,distance_type(first1),
distance_type(first2));
}
template<class ForwardIterator1, class ForwardIterator2, class distance1,
class Distance2>
ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
Distance1*, Distance2*)
{
Distance1 d1 = 0;
distance(first1, last1, d1);
Distance2 d2 = 0;
distance(first2, last2, d2);
if(d1 < d2) return last1;
ForwardIterator1 current1 = first1;
ForwardIterator2 current2 = first2;
while (current2 != last2)
{
if (*current1 == *current2)
{
++current1;
++current2;
}
else
{
if (d1 == d2)
return last1;
else
{
current1 = ++first1;
current2 = first2;
--d1;
}
}
}
return first1;
}
//search_n
template<class ForwardIterator, class Interger, class T>
ForwardIterator search_n(ForwardIterator first,
ForwardIterator last,
Interger count, const T& value)
{
if(count <= 0)
return first;
else
{
//先找到第一个
first = find(first, last, value);
while (first != last)
{
Interger n = count - 1;
ForwardIterator i = first;
++i;
//找连续符合的元素，都找到了的话 n会等于0；
while (i != last && n != 0 && *i == value)
{
++i;
--n;
}
if(n == 0)
return first;
else
first = find(i, last, value);
}
return last;
}
}
template<class ForwardIterator, class Interger, class T,
class BinaryPredicate>
ForwardIterator search_n(ForwardIterator first,
ForwardIterator last,
Interger count, const T& value,
BinaryPredicate binary_pred)
{
if(count <= 0)
return first;
else
{
//自己实现find，其实可以使用find_if版本的 不过需要使用bind函数
while (first != last)
{
if(binary_pred(*first, value))
break;
++first;
}
while (first != last)
{
Interger n = count - 1;
ForwardIterator i = first;
++i;
//找连续符合的元素，都找到了的话 n会等于0；
while (i != last && n != 0 && *i == value)
{
++i;
--n;
}
if(n == 0)
return first;
else
{
while (i != last)
{
if(binary_pred(*first, value))
break;
++i;
}
first = i;
}
}
return last;
}
}
//swap_ranges
//区间不能重叠，不然会产生未知结果
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges(ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2)
{
for(; first != last1; ++first1, ++first2)
iter_swap(first1, first2);
return first2;
}
//transform
//对每个元素执行op操作后，复制到目的区间
template<class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator transform(InputIterator first1, InputIterator last,
OutputIterator result, UnaryOperation op)
{
for(; first != last; ++first, ++result)
*result = op(*first);
return result;
}
template<class InputIterator1, class InputIterator2, class OutputIterator,
class BinaryOperation>
OutputIterator transform(InputIterator1 first1, InputIterator last1,
InputIterator2 first2, InputIterator last2,
BinaryOperation binary_op)
{
for(; first1 != last1; ++first1, ++first2, ++result)
*result = binary_op(*first1, *first2);
return result;
}
//unique
//只能移除相邻的重复元素(首先要有相邻元素才会开始删除，相邻元素后面如果还有同样的元素也会被删除)
//要移除所有重复元素必须先排序
template<class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last)
{
first = adjacent_find(first, last);
return unique_copy(first, last, first);
}
template<class InputIterator, class ForwardIterator>
inline OutputIterator unique_copy(InputIterator first,
InputIterator last,
OutputIterator result)
{
if(first == last) return result;
return __unique_copy(first, last, result, iterator_category(result));
}
template<class InputIterator, class ForwardIterator>
ForwardIterator __unique_copy(InputIterator first,
InputIterator last,
ForwardIterator result,
forward_iterator_tag)
{
*result = *first;
while (++first != last)
{
if(*result != *first)
*++result = *first;
}
return ++result;
}
template<class InputIterator, class OutputIterator>
inline OutputIterator __unique_copy(InputIterator first,
InputIterator last,
ForwardIterator result,
output_iterator_tag)
{
return __unique_copy(first, last, result, value_type(first));
}
template<class InputIterator, class OutputIterator, class T>
OutputIterator __unique_copy(InputIterator first, InputIterator last,
OutputIterator result, T*)
{
T value = *first;
*result = value;
while (++first != last)
{
if(value != *first) //如果result为只读，这里就只能通过值判断 而不能使用(*result != *first)
{
value = *first;
*++result = value;
}
}
return ++result;
}