## Algorithmes

template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f) {
while (first != last) f(*first++);
return f;
}

template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value) {
while (first != last && *first != value) ++first;
return first;
}

template <class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last,
Predicate pred) {
while (first != last && !pred(*first)) ++first;
return first;
}

template <class InputIterator, class T, class Size>
void count(InputIterator first, InputIterator last, const T& value,
Size& n) {
while (first != last)
if (*first++ == value) ++n;
}

template <class ForwardIterator1, class ForwardIterator2>
inline ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2)
{
return __search(first1, last1, first2, last2, distance_type(first1),
distance_type(first2));
}

template <class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator transform(InputIterator first, InputIterator last,
OutputIterator result, UnaryOperation op) {
while (first != last) *result++ = op(*first++);
return result;
}

template <class InputIterator1, class InputIterator2, class OutputIterator,
class BinaryOperation>
OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, OutputIterator result,
BinaryOperation binary_op) {
while (first1 != last1) *result++ = binary_op(*first1++, *first2++);
return result;
}

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result) {
while (first1 != last1 && first2 != last2)
if (*first2 < *first1)
*result++ = *first2++;
else
*result++ = *first1++;
return copy(first2, last2, copy(first1, last1, result));
}

template <class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2) {
while (first1 != last1 && first2 != last2)
if (*first2 < *first1)
return false;
else if(*first1 < *first2)
++first1;
else
++first1, ++first2;

return first2 == last2;
}

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result) {
while (first1 != last1 && first2 != last2)
if (*first1 < *first2)
*result++ = *first1++;
else if (*first2 < *first1)
*result++ = *first2++;
else {
*result++ = *first1++;
first2++;
}
return copy(first2, last2, copy(first1, last1, result));
}

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result) {
while (first1 != last1 && first2 != last2)
if (*first1 < *first2)
++first1;
else if (*first2 < *first1)
++first2;
else {
*result++ = *first1++;
++first2;
}
return result;
}

template <class InputIterator1, class InputIterator2, class OutputIterator,
class Compare>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp) {
while (first1 != last1 && first2 != last2)
if (comp(*first1, *first2))
*result++ = *first1++;
else if (comp(*first2, *first1))
++first2;
else {
++first1;
++first2;
}
return copy(first1, last1, result);
}

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_symmetric_difference(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
OutputIterator result) {
while (first1 != last1 && first2 != last2)
if (*first1 < *first2)
*result++ = *first1++;
else if (*first2 < *first1)
*result++ = *first2++;
else {
++first1;
++first2;
}
return copy(first2, last2, copy(first1, last1, result));
}

template <class ForwardIterator>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last) {
if (first == last) return first;
ForwardIterator result = first;
while (++first != last)
if (*result < *first) result = first;
return result;
}

template <class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init) {
while (first != last)
init = init + *first++;
return init;
}

template <class InputIterator1, class InputIterator2, class T>
T inner_product(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, T init) {
while (first1 != last1)
init = init + (*first1++ * *first2++);
return init;
}

template <class InputIterator, class OutputIterator>
OutputIterator partial_sum(InputIterator first, InputIterator last,
OutputIterator result) {
if (first == last) return result;
*result = *first;
return __partial_sum(first, last, result, value_type(first));
}

template <class ForwardIterator, class T>
void iota(ForwardIterator first, ForwardIterator last, T value) {
while (first != last) *first++ = value++;
}