The STL algorithms offer a powerful way to solve some base programming use cases. If you know and use these algorithms you can write more clean, efficient and robust code. But unfortunately, it isn’t that easy to know or find the right algorithm for a use case. In my opinion, this is a result of the not practical kind of documentation – especially grouping of the algorithms is not related to practice – and on the other hand the unfavorable naming of some functions. Therefore, I write this series of articles and want to give a more practice-related overview about the STL algorithms.

Within this article I want to give an overview about the STL algorithms for sorted containers. This is one of a series of articles. Within each of these blog post I want to summarize the STL algorithms regarding one kind of use case. This article shows the possibilities in case we have a container with sorted elements or in case we want to create such a container based on two sorted containers.

Each section contains a list of the according STL algorithms with a short description. Additional you will find an example implementation which will show some of these algorithms. If you copy and execute the examples, you will see the results within the console window. Additional, you will see the results as comment within the source code.

Most of the standard algorithms take half-open sequences. “Half-open” means the start iterator refers to the first element of the sequence and the end iterator refers to the element behind the last element. Returning the end iterator of the sequence to indicate “not found” is a standard-library convention.

Use elements of two containers

void Print(const std::vector& data)
{
  std::for_each(data.begin(), data.end(), [](int element){ std::cout << element << " "; });
  std::cout << std::endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
  std::vector source1{ 5, 7, 2, 2, 4 };
  std::vector source2{ 1, 1, 2, 5, 3, 5 };
  std::vector target;

  // transform
  std::transform(
    source1.begin(), source1.end(), 
    source2.begin(), 
    std::back_inserter(target),
    [](int a, int b){return a*b; });

  Print(target);  // output is '5 7 4 10 12'  

  // inner product (standard)
  int sumOfProducts = std::inner_product(source1.begin(), source1.end(), source2.begin(), 0);
  std::cout << sumOfProducts << std::endl;   // result is '38'

  // inner product (with own functions)  
  int productOfDifferences = std::inner_product(
    source1.begin(), source1.end(), source2.begin(), 
    0, std::plus(), std::minus());
  std::cout << productOfDifferences << std::endl;   // result is '8'

  int numberOfEqualPairs = std::inner_product(
    source1.begin(), source1.end(), source2.begin(), 
    0, std::plus(), std::equal_to());
  std::cout << numberOfEqualPairs << std::endl;   // result is '1'

  return 0;
}

Compare two containers

int _tmain(int argc, _TCHAR* argv[])
{
  std::vector v1{ 5, 7, 9, 2, 4 };
  std::vector v2{ 5, 7, 9, 2, 4 };  
  
  // equals  
  bool result = std::equal(v1.begin(), v1.end(), v2.begin());
  std::cout << result << std::endl;   // result is 'true'

  // mismatch
  v2 = { 5, 7, 0, 2, 0 };
  auto iterators = std::mismatch(v1.begin(), v1.end(), v2.begin());
  if ((iterators.first != v1.end()) && (iterators.second != v2.end()))
  {
    std::cout << "mismatch found at index " << std::distance(v1.begin(), iterators.first) << std::endl;
    // output is 'mismatch found at index index 2'
  }
  
  // search
  v2 = { 9, 2 };
  auto iterator = std::search(v1.begin(), v1.end(), v2.begin(), v2.end());  
  if (iterator != v1.end())
  {
    std::cout << "sub-sequence found at index " << std::distance(v1.begin(), iterator) << std::endl;
    // output is 'sub-sequence found at index index 2'
  }  

  return 0;
}