(C++) Algorithm

Algorithm has multiple meanings:

• an algorithm in general
• an STL algorithm
• the Boost.Algorithm library: see Boost.Algorithm

Algorithm (general)

An algorithm is a logical series of steps followed by a calculation.

Algorithms can be adapted by lambda expressions, adapters, binders and negaters.

Example: sorting a std::vector

#include <algorithm>
#include <cassert>
#include <vector>

int main()
{
  std::vector<int> v = {4, 2, 3, 1};
  std::sort(std::begin(v), std::end(v));
  const std::vector<int> expected = {1, 2, 3, 4};
  assert(v == expected);
}

Example: copy twice

#include <algorithm>
#include <cassert>
#include <vector>

int main()
{
  const std::vector<int> v = {1,2};
  std::vector<int> w;
  std::copy(std::begin(v), std::end(v),
    std::back_inserter(w)
  );
  std::copy(std::begin(v), std::end(v),
    std::back_inserter(w)
  );
  const std::vector<int> expected = {1, 2, 1, 2};
  assert(w == expected);
}

Example: copy if non-zero and positive

#include <algorithm>
#include <cassert>
#include <vector>

int main()
{
  const std::vector<int> v = {-9, -4, 0, 4, 9};
  std::vector<int> w;
  std::copy_if(
    std::begin(v), 
    std::end(v),
    std::back_inserter(w),
    [](const int i) { return i > 0; }
  );
  const std::vector<int> expected = { 4, 9 };
  assert(w == expected);
}

Example: CoutVector

#include <iterator>
#include <iostream>
#include <ostream>
#include <vector>

int main()
{
  //Create a std::vector
  const std::vector<int> v = {1, 4, 9, 16, 25};

  //Copy it to std::cout
  std::copy(std::begin(v), std::end(v), std::ostream_iterator<int>(std::cout,"\n"));
}

STL algorithms

Most algorithms can be found in the header file algorithm.h.

Non-standard algorithms lack the std prefix.

All C++11 algorithm names [3]:

1. std::accumulate
2. accumulate_if
3. std::adjacent_find
4. std::all_of
5. std::any_of
6. std::binary_search
7. std::copy
8. std::copy_backward
9. copy_if
10. std::copy_if
11. std::copy_n
12. std::count
13. std::count_if
14. std::equal
15. std::equal_range
16. std::fill
17. std::find
18. std::find_end
19. std::find_first_of
20. std::find_if
21. std::find_if_not
22. std::for_each
23. std::generate
24. std::generate_n
25. std::includes
26. std::inner_product
27. std::inplace_merge
28. std::iota
29. std::is_heap
30. std::is_heap_until
31. std::is_sorted
32. std::is_sorted_until
33. std::iter_swap
34. std::lexicographical_compare
35. std::lower_bound
36. std::make_heap
37. std::max
38. std::max_element
39. std::merge
40. std::min
41. std::min_element
42. std::minmax
43. std::minmax_element
44. std::mismatch
45. std::move
46. std::move_backward
47. std::next_permutation
48. std::none_of
49. std::nth_element
50. std::partial_sort
51. std::partial_sort_copy
52. std::partition
53. std::partition_copy
54. std::partition_point
55. std::pop_heap
56. std::prev_permutation
57. std::push_heap
58. std::random_shuffle
59. std::remove
60. std::remove_copy
61. std::remove_copy_if
62. std::remove_if
63. std::replace
64. std::replace_copy
65. std::replace_copy_if
66. std::replace_if
67. std::reverse
68. std::reverse_copy
69. std::rotate
70. std::rotate_copy
71. std::search
72. std::search_n
73. std::set_difference
74. std::set_intersection
75. std::set_symmetric_difference
76. std::set_union
77. std::sort
78. std::sort_heap
79. std::stable_partition
80. std::stable_sort
81. std::swap
82. std::swap_ranges
83. std::transform
84. std::unique
85. std::unique_copy
86. std::upper_bound

Advice

• Prefer algorithm calls over hand-written loops [1,2]
• Use templates to express algorithms that apply to many argument types [4]

External links

• C++ Weekly - Ep 105 - Learning "Modern" C++ - 5: Looping and Algorithms

References

• [1] Bjarne Stroustrup. The C++ Programming Language (3rd edition). ISBN: 0-201-88954-4. Chapter 18.12.1: 'Prefer algorithms to loops'.
• [2] Scott Meyers. Effective STL. ISBN: 0-201-74962-9. Item 43: 'Prefer algorithm calls over hand-written loops'
• [3] Bjarne Stroustrup's C++0x FAQ page
• [4] Bjarne Stroustrup. The C++ Programming Language (4th edition). 2013. ISBN: 978-0-321-56384-2. Chapter 23.8, page 698: '[1] Use templates to express algorithms that apply to many argument types'