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;

STL algorithm adopts coverage mode instead of placement mode;

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

algorithm	effect
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_element	Maximum 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;

  limit=first; std::advance(limit,std::distance(first,last)-count);

  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;
}

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;
}

adjacent_find

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);

algorithm	effect
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

algorithm	effect
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()	Remove adjacent duplicate elements
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;

algorithm	effect
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;

algorithm	effect
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(nlog(n)), otherwise O(nlogn*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
push_heap()	Add elements to 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

algorithm	effect
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

algorithm	effect
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;
}

adjacent_difference

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

Programming VIP