# STL [algorithm] | large collection of common algorithms

## 1, Introduction

STL algorithms are designed to handle one or more iterator intervals; In most cases, you only need to provide a starting point;

### 1.1 category

#### 1.1.1 _if end

When this kind of algorithm has two forms and the number of parameters is the same, the first form requires value transfer and the second form requires function transfer; Therefore, there is the required transfer function of the tail word, and there is no tail word to transfer the value;

#### 1.1.2 _copy suffix

The element will be copied;

#### 1.1.3 algorithm category

• Non variable algorithm;
• Variability algorithm;
• Removable algorithm;
• Variable order algorithm;
• Sorting algorithm;
• Ordered interval algorithm;
• Numerical algorithm;

## 2, Non variability algorithm

### 2.1 introduction

Neither the element order nor the element value is changed, which is completed through the input and forward iterators;

### 2.2 common algorithms

algorithmeffect
for_each()Operate on each element
count()Returns the number of elements
count_if()Returns the number of elements that meet a certain condition
min_element()Minimum element
max_elementMaximum element
find()Search for the first element equal to a value
find_if()Search for the first element that meets a condition
search_n()Search for the first n consecutive matching values
search()Search for the first occurrence position of a sub interval
find_end()Query the location of the last occurrence
find_first_of()Search for the first element of a number
adjacent_find()Search for two consecutive relative elements
equal()Judge whether the two intervals are equal
mismatch()Returns the first unequal element in each group of corresponding elements of two sequences
lexicographical_cpmpare()Judge whether a sequence is smaller than another sequence in dictionary order

#### 2.2.1 element count

count

```template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count (InputIterator first, InputIterator last, const T& val)
{
typename iterator_traits<InputIterator>::difference_type ret = 0;
while (first!=last) {
if (*first == val) ++ret;
++first;
}
return ret;
}
```

count_if

```template <class InputIterator, class UnaryPredicate>
typename iterator_traits<InputIterator>::difference_type
count_if (InputIterator first, InputIterator last, UnaryPredicate pred)
{
typename iterator_traits<InputIterator>::difference_type ret = 0;
while (first!=last) {
if (pred(*first)) ++ret;
++first;
}
return ret;
}
```

#### 2.2.2 maximum and minimum values

min_element

```template <class ForwardIterator>
ForwardIterator min_element ( ForwardIterator first, ForwardIterator last )
{
if (first==last) return last;
ForwardIterator smallest = first;

while (++first!=last)
if (*first<*smallest)    // or: if (comp(*first,*smallest)) for version (2)
smallest=first;
return smallest;
}
```

max_element

```template <class ForwardIterator>
ForwardIterator max_element ( ForwardIterator first, ForwardIterator last )
{
if (first==last) return last;
ForwardIterator largest = first;

while (++first!=last)
if (*largest<*first)    // or: if (comp(*largest,*first)) for version (2)
largest=first;
return largest;
}
```

#### 2.2.3 search elements

find

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

find_if

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

search_n

```template<class ForwardIterator, class Size, class T>
ForwardIterator search_n (ForwardIterator first, ForwardIterator last,
Size count, const T& val)
{
ForwardIterator it, limit;
Size i;

while (first!=limit)
{
it = first; i=0;
while (*it==val)       // or: while (pred(*it,val)) for the pred version
{ ++it; if (++i==count) return first; }
++first;
}
return last;
}
```

search

```template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2)
{
if (first2==last2) return first1;  // specified in C++11

while (first1!=last1)
{
ForwardIterator1 it1 = first1;
ForwardIterator2 it2 = first2;
while (*it1==*it2) {    // or: while (pred(*it1,*it2)) for version 2
++it1; ++it2;
if (it2==last2) return first1;
if (it1==last1) return last1;
}
++first1;
}
return last1;
}
```

find_end

```template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2)
{
if (first2==last2) return last1;  // specified in C++11

ForwardIterator1 ret = last1;

while (first1!=last1)
{
ForwardIterator1 it1 = first1;
ForwardIterator2 it2 = first2;
while (*it1==*it2) {    // or: while (pred(*it1,*it2)) for version (2)
++it1; ++it2;
if (it2==last2) { ret=first1; break; }
if (it1==last1) return ret;
}
++first1;
}
return ret;
}
```

find_first_of

```template<class InputIterator, class ForwardIterator>
InputIterator find_first_of ( InputIterator first1, InputIterator last1,
ForwardIterator first2, ForwardIterator last2)
{
while (first1!=last1) {
for (ForwardIterator it=first2; it!=last2; ++it) {
if (*it==*first1)          // or: if (pred(*it,*first)) for version (2)
return first1;
}
++first1;
}
return last1;
}
```

```template <class ForwardIterator>
ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last)
{
if (first != last)
{
ForwardIterator next=first; ++next;
while (next != last) {
if (*first == *next)     // or: if (pred(*first,*next)), for version (2)
return first;
++first; ++next;
}
}
return last;
}
```

equal

```template <class InputIterator1, class InputIterator2>
bool equal ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 )
{
while (first1!=last1) {
if (!(*first1 == *first2))   // or: if (!pred(*first1,*first2)), for version 2
return false;
++first1; ++first2;
}
return true;
}
```

mismatch

```template <class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2>
mismatch (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 )
{
while ( (first1!=last1) && (*first1==*first2) )  // or: pred(*first1,*first2), for version 2
{ ++first1; ++first2; }
return std::make_pair(first1,first2);
}
```

## 3, Variability algorithm

### 3.1 introduction

Change the element value directly, or change the element value in the process of copying to another interval;

### 3.2 common

for_each

```template <class InputIterator, class Function>
Function for_each (InputIterator first, InputIterator last, Function fn);

func: Be able to access, process and modify each element in different ways;

eg:
for_each(arr.begin(), arr.end(), func);
```

transform

```# Unary operation
template <class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator transform (InputIterator first1, InputIterator last1,
OutputIterator result, UnaryOperation op);

# Binary operation
template <class InputIterator1, class InputIterator2,
class OutputIterator, class BinaryOperation>
OutputIterator transform (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, OutputIterator result,
BinaryOperation binary_op);
func:
One yuan: will op Apply to each element in the scope and[first1,last1)The value returned by each operation is stored from result Within the scope of the beginning;
Binary: called with each element in the scope as the first parameter binary_op ，And use from first2[first1,last1)The corresponding parameter in the starting range is used as the second parameter. Return every call
The values returned are stored from result Within the scope of the beginning;

eg:
transform(arr.begin(), arr.end(), arr.begin(), func);
```
algorithmeffect
for_each()Perform actions on each element
copy()The first element starts copying an interval
copy_backward()Starting from the last, copy an interval
transform()Change and copy elements [slow, need to return assignment to elements]
merge()Merge two intervals [ordered]
swap_ranges()Exchange elements of two intervals
fill()Replace each element with the given value
fill_n()Replace n elements with the given value
generate()Replace each element with the result of an operation
generate_n()Replace n elements with the result of an operation
replace()Replace an element with a special value with another value
replace_if()Replace an element that meets a criterion with another value
replace_copy()Copy the entire interval and replace an element with a specific value with another value
replace_copy_if()Copy the entire interval and replace the element that meets one criterion with another value

copy

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

copy_backward

```template<class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2 copy_backward ( BidirectionalIterator1 first,
BidirectionalIterator1 last,
BidirectionalIterator2 result )
{
while (last!=first) *(--result) = *(--last);
return result;
}
```

merge

```template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result)
{
while (true) {
if (first1==last1) return std::copy(first2,last2,result);
if (first2==last2) return std::copy(first1,last1,result);
*result++ = (*first2<*first1)? *first2++ : *first1++;
}
}
```

swap_ranges

```template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges (ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2)
{
while (first1!=last1) {
swap (*first1, *first2);
++first1; ++first2;
}
return first2;
}
```

fill

```template <class ForwardIterator, class T>
void fill (ForwardIterator first, ForwardIterator last, const T& val)
{
while (first != last) {
*first = val;
++first;
}
}
```

fill_n

```template <class OutputIterator, class Size, class T>
OutputIterator fill_n (OutputIterator first, Size n, const T& val)
{
while (n>0) {
*first = val;
++first; --n;
}
return first;     // since C++11
}
```

generate

```template <class ForwardIterator, class Generator>
void generate ( ForwardIterator first, ForwardIterator last, Generator gen )
{
while (first != last) {
*first = gen();
++first;
}
}
```

generate_n

```template <class OutputIterator, class Size, class Generator>
void generate_n ( OutputIterator first, Size n, Generator gen )
{
while (n>0) {
*first = gen();
++first; --n;
}
}
```

replace

```template <class ForwardIterator, class T>
void replace (ForwardIterator first, ForwardIterator last,
const T& old_value, const T& new_value)
{
while (first!=last) {
if (*first == old_value) *first=new_value;
++first;
}
}
```

replace_if

```template < class ForwardIterator, class UnaryPredicate, class T >
void replace_if (ForwardIterator first, ForwardIterator last,
UnaryPredicate pred, const T& new_value)
{
while (first!=last) {
if (pred(*first)) *first=new_value;
++first;
}
}
```

replace_copy

```template <class InputIterator, class OutputIterator, class T>
OutputIterator replace_copy (InputIterator first, InputIterator last,
OutputIterator result, const T& old_value, const T& new_value)
{
while (first!=last) {
*result = (*first==old_value)? new_value: *first;
++first; ++result;
}
return result;
}
```

replace_copy_if

```template <class InputIterator, class OutputIterator, class UnaryPredicate, class T>
OutputIterator replace_copy_if (InputIterator first, InputIterator last,
OutputIterator result, UnaryPredicate pred,
const T& new_value)
{
while (first!=last) {
*result = (pred(*first))? new_value: *first;
++first; ++result;
}
return result;
}
```

### 3.3 removable algorithm

You can remove the elements of an interval, or copy the process to perform the removal action;

Commonly used

algorithmeffect
remove()All elements of a specific value are removed
remove_if()Remove all elements that meet a condition
remove_copy()Copy all elements that are not equal to a specific value to other places
remove_copy_if()Copy all elements that do not meet a certain condition to other places
unique_copy()Remove adjacent duplicate elements and copy them elsewhere

The element that does not need to be removed is overwritten with the removed element, and the size of the interval is not changed;

remove

```template <class ForwardIterator, class T>
ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val)
{
ForwardIterator result = first;
while (first!=last) {
if (!(*first == val)) {
if (result!=first)
*result = *first;
++result;
}
++first;
}
return result;
}
```

remove_if

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

remove_copy

```template <class InputIterator, class OutputIterator, class T>
OutputIterator remove_copy (InputIterator first, InputIterator last,
OutputIterator result, const T& val)
{
while (first!=last) {
if (!(*first == val)) {
*result = *first;
++result;
}
++first;
}
return result;
}
```

remove_copy_if

```template <class InputIterator, class OutputIterator, class UnaryPredicate>
OutputIterator remove_copy_if (InputIterator first, InputIterator last,
OutputIterator result, UnaryPredicate pred)
{
while (first!=last) {
if (!pred(*first)) {
*result = *first;
++result;
}
++first;
}
return result;
}
```

unique

```template <class ForwardIterator>
ForwardIterator unique (ForwardIterator first, ForwardIterator last)
{
if (first==last) return last;

ForwardIterator result = first;
while (++first != last)
{
if (!(*result == *first))  // or: if (!pred(*result,*first)) for version (2)
*(++result)=*first;
}
return ++result;
}
```

unique_copy

```template <class InputIterator, class OutputIterator>
OutputIterator unique_copy (InputIterator first, InputIterator last,
OutputIterator result)
{
if (first==last) return result;

*result = *first;
while (++first != last) {
typename iterator_traits<InputIterator>::value_type val = *first;
if (!(*result == val))   // or: if (!pred(*result,val)) for version (2)
*(++result)=val;
}
return ++result;
}
```

## 4, Variable order algorithm

Change the element order through the copy and exchange of element values;

algorithmeffect
reverse()Reverse the order of elements
reverse_copy()Reverse the order of elements while copying
rotate()Rotate element order
rotate_copy()While copying, rotate the element order
next_permutation()Get the next sort order of elements
prev_permutation()Get the last sort order of elements
random_shuffle()Disorganize elements
partition()Change the order of elements so that those that meet a certain criterion move to the front
stable_partition()Similar to the previous one, but maintain the relative position between the elements that meet the criteria and those that do not meet the criteria

reverse

```template <class BidirectionalIterator>
void reverse (BidirectionalIterator first, BidirectionalIterator last)
{
while ((first!=last)&&(first!=--last)) {
std::iter_swap (first,last);
++first;
}
}
```

reverse_copy

```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>
void rotate (ForwardIterator first, ForwardIterator middle,
ForwardIterator last)
{
ForwardIterator next = middle;
while (first!=next)
{
swap (*first++,*next++);
if (next==last) next=middle;
else if (first==middle) middle=next;
}
}
```

rotate_copy

```template <class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy (ForwardIterator first, ForwardIterator middle,
ForwardIterator last, OutputIterator result)
{
result=std::copy (middle,last,result);
return std::copy (first,middle,result);
}
```

next_permutation

```template <class BidirectionalIterator, class Compare>
bool next_permutation (BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
```

prev_permutation

```template <class BidirectionalIterator>
bool prev_permutation (BidirectionalIterator first,
BidirectionalIterator last );
template <class BidirectionalIterator, class Compare>
bool prev_permutation (BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
```

random_shuffle

```template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle (RandomAccessIterator first, RandomAccessIterator last,
RandomNumberGenerator& gen)
{
iterator_traits<RandomAccessIterator>::difference_type i, n;
n = (last-first);
for (i=n-1; i>0; --i) {
swap (first[i],first[gen(i+1)]);
}
}
```

partition

```template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator partition (BidirectionalIterator first,
BidirectionalIterator last, UnaryPredicate pred)
{
while (first!=last) {
while (pred(*first)) {
++first;
if (first==last) return first;
}
do {
--last;
if (first==last) return first;
} while (!pred(*last));
swap (*first,*last);
++first;
}
return first;
}
```

stable_partition

```template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator stable_partition (BidirectionalIterator first,
BidirectionalIterator last,
UnaryPredicate pred);
```

## 5, Sorting algorithm

A special variable order algorithm;

algorithmeffect
sort()Sorting; Quick sorting method has good average performance O(n*logn), but it also has the worst case
stable_sort()Sort and maintain the relative order between equal elements; Merge and sort, when there is enough memory O(n*log(n)), otherwise O(n*logn*logn)
partial_sort()Sort until the first n elements are in place; Heap sorting, in any case O(nlog(n)), is slower than fast sorting
partial_sort_copy()Sort until the first n elements are in place, and the results are copied to other places
nth_element()Sort by n th position
parition()Change the order of elements and put those that meet certain conditions first
stable_partition()It is the same as parition, but maintains the relative position between elements that meet and do not meet the criteria
make_heap()Convert an interval into a heap
pop_heap()Remove an element from heap
sort_heap()Sort heap, and it will no longer be heap after execution

[note]: List does not provide random access iterator, so only sort provided by itself is available;

sort

```template <class RandomAccessIterator>
void sort (RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
```

stable_sort

```template <class RandomAccessIterator>
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,
Compare comp );
```

partial_sort

```template <class RandomAccessIterator>
void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,
RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,
RandomAccessIterator last, Compare comp);
```

partial_sort_copy

```template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy (InputIterator first,InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
template <class InputIterator, class RandomAccessIterator, class Compare>
RandomAccessIterator
partial_sort_copy (InputIterator first,InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last, Compare comp);
```

nth_element

```template <class RandomAccessIterator>
void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, Compare comp);
```

stable_partition

```template <class BidirectionalIterator, class UnaryPredicate>
BidirectionalIterator stable_partition (BidirectionalIterator first,
BidirectionalIterator last,
UnaryPredicate pred);
```

make_heap

```template <class RandomAccessIterator>
void make_heap (RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void make_heap (RandomAccessIterator first, RandomAccessIterator last,
Compare comp );
```

push_heap

```template <class RandomAccessIterator>
void push_heap (RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void push_heap (RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
```

pop_heap

```template <class RandomAccessIterator>
void pop_heap (RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void pop_heap (RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
```

sort_heap

```template <class RandomAccessIterator>
void sort_heap (RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void sort_heap (RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
```

## 6, Ordered interval algorithm

algorithmeffect
binary_search()Judge whether an element is included in an interval
includes()Judge whether each element in an interval is covered in another interval
lower_bound()Search for the first element greater than the given value
upper_bound()Search for the first element greater than the given value
equal_range()Returns an interval consisting of all elements equal to a given value
merge()Merge the elements of two intervals
set_union()Find the union of two intervals
set_intersection()Find the intersection of two intervals
set_difference()Find all elements in the first interval but not in the second interval to form an ordered interval
set_symmetric_difference()Find out all elements that only appear in one of the two intervals to form an ordered interval
inplace_merge()Merge two consecutive ordered intervals

binary_search

```template <class ForwardIterator, class T>
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val)
{
first = std::lower_bound(first,last,val);
return (first!=last && !(val<*first));
}
```

includes

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

lower_bound

```template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
ForwardIterator it;
iterator_traits<ForwardIterator>::difference_type count, step;
count = distance(first,last);
while (count>0)
{
it = first; step=count/2; advance (it,step);
if (*it<val) {                 // or: if (comp(*it,val)), for version (2)
first=++it;
count-=step+1;
}
else count=step;
}
return first;
}
```

upper_bound

```template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
ForwardIterator it;
iterator_traits<ForwardIterator>::difference_type count, step;
count = std::distance(first,last);
while (count>0)
{
it = first; step=count/2; std::advance (it,step);
if (!(val<*it))                 // or: if (!comp(val,*it)), for version (2)
{ first=++it; count-=step+1;  }
else count=step;
}
return first;
}
```

equal_range

```template <class ForwardIterator, class T>
pair<ForwardIterator,ForwardIterator>
equal_range (ForwardIterator first, ForwardIterator last, const T& val)
{
ForwardIterator it = std::lower_bound (first,last,val);
return std::make_pair ( it, std::upper_bound(it,last,val) );
}
```

merge

```template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result)
{
while (true) {
if (first1==last1) return std::copy(first2,last2,result);
if (first2==last2) return std::copy(first1,last1,result);
*result++ = (*first2<*first1)? *first2++ : *first1++;
}
}
```

set_union

```template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result)
{
while (true)
{
if (first1==last1) return std::copy(first2,last2,result);
if (first2==last2) return std::copy(first1,last1,result);

if (*first1<*first2) { *result = *first1; ++first1; }
else if (*first2<*first1) { *result = *first2; ++first2; }
else { *result = *first1; ++first1; ++first2; }
++result;
}
}
```

set_intersection

```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;
++result; ++first1; ++first2;
}
}
return result;
}
```

set_difference

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

set_symmetric_difference

```template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result)
{
while (true)
{
if (first1==last1) return std::copy(first2,last2,result);
if (first2==last2) return std::copy(first1,last1,result);

if (*first1<*first2) { *result=*first1; ++result; ++first1; }
else if (*first2<*first1) { *result = *first2; ++result; ++first2; }
else { ++first1; ++first2; }
}
}
```

inplace_merge

```template <class BidirectionalIterator>
void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,
BidirectionalIterator last);
template <class BidirectionalIterator, class Compare>
void inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,
BidirectionalIterator last, Compare comp);
```

## 7, Numerical algorithm

algorithmeffect
accumulate()Combine all elements (sum, product, etc.)
inner_product()Combine all elements in two intervals
adjacent_difference()Combine each element with its previous element
partial_sum()Combine each element with all its previous elements

accumulate

```template <class InputIterator, class T>
T accumulate (InputIterator first, InputIterator last, T init)
{
while (first!=last) {
init = init + *first;  // or: init=binary_op(init,*first) for the binary_op version
++first;
}
return init;
}
```

inner_product

```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);
// or: init = binary_op1 (init, binary_op2(*first1,*first2));
++first1; ++first2;
}
return init;
}
```

```template <class InputIterator, class OutputIterator>
OutputIterator adjacent_difference (InputIterator first, InputIterator last,
OutputIterator result)
{
if (first!=last) {
typename iterator_traits<InputIterator>::value_type val,prev;
*result = prev = *first;
while (++first!=last) {
val = *first;
*++result = val - prev;  // or: *++result = binary_op(val,prev)
prev = val;
}
++result;
}
return result;
}
```

partial_sum

```template <class InputIterator, class OutputIterator>
OutputIterator partial_sum (InputIterator first, InputIterator last,
OutputIterator result)
{
if (first!=last) {
typename iterator_traits<InputIterator>::value_type val = *first;
*result = val;
while (++first!=last) {
val = val + *first;   // or: val = binary_op(val,*first)
*++result = val;
}
++result;
}
return result;
}
```

Keywords: C++ Algorithm STL

Added by mwichmann4 on Tue, 08 Mar 2022 10:29:16 +0200