Algorithms to use, find and check container elements

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 to use, find and check container elements. 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 want to use, find and check container elements but don’t want to change them.

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 the container elements

Algorithm Description
for_each Loop over container elements and use these them within a function.
for_each_n Loop from a starting element over the next n elements and use them within a function.
accumulate Accumulates the elements of a container by using a given accumulation function and a start value. If you want to create a sum of all elements you can ommit the accumulation function as sum up is the default one.
adjacent_difference Calculates the differences between adjacent elements and writes the result in a target container.

The function will loop over all elements and create the difference of the actual element and its predecessor. As the first element does not have a predecessor it will be written directly to the target container.

adjacent_difference (with operation) If you define an operation for this function, this operation will be used to calculate the result of all elements and their predecessors (see above function description).

But in this case the name “adjacent_difference” is misleading as because we don’t calculate a difference. In my opinion, a better name for this algorithm, based on “for_each”, would be “for_each_adjacent”.

partial_sum For each element, the sum of all previous elements is calculated and written to a target container. Therefore, the function calculates a partial accumulation for each element.
partial_sum (with operation) The function calculates a partial accumulation for each element and writes this value to the target container. The accumulation is calculated according to the given operation.

The name “partial_sum” is misleading as no sum is calculated. In my opinion, a better name would be “partial_accumulate”.

 

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 data{ 5, 7, 9, 2, 4 };
  std::vector target;

  // for each
  std::for_each(data.begin(), data.end(), [](int element){ std::cout << element << std::endl; });
  
  // accumulate
  int sum = std::accumulate(data.begin(), data.end(), 100);
  std::cout << sum << std::endl;   // output is '127'

  int product = std::accumulate(data.begin(), data.end(), 1, std::multiplies());
  std::cout << product << std::endl;   // output is '2520'

  // adjacent difference (without operation)
  std::adjacent_difference(data.begin(), data.end(), std::back_inserter(target));
  Print(target);    // output is '5 2 2 -7 2'

  // adjacent difference (with operation)
  target.clear();
  std::adjacent_difference(data.begin(), data.end(), std::back_inserter(target), std::multiplies());
  Print(target);    // output is '5 35 63 18 8'

  // partial sum (without operation)
  target.clear();
  std::partial_sum(data.begin(), data.end(), std::back_inserter(target));
  Print(target);    // output is '5 12 21 23 27'
    
  // partial sum (with operation)
  target.clear();
  std::partial_sum(data.begin(), data.end(), std::back_inserter(target), std::multiplies());
  Print(target);    // output is '5 35 315 630 2520'

  return 0;
}

 

Check the container elements

Algorithm Description
all_of Check whether all elements match a given condition.
any_of Check whether at least one element matches a given condition.
none_of Check whether none of the elements matches a given condition.
count Count the number of elements matching a given value.
count_of Count the number of elements matching a given condition.

 

int _tmain(int argc, _TCHAR* argv[])
{
  std::vector data{ 5, 7, 9, 2, 4 };
  
  // check whether all,any,none of the elements matches a condition
  bool result = std::all_of(data.begin(), data.end(), [](int element){ return (element > 4); });
  std::cout << result < 4); });
  std::cout << result < 4); });
  std::cout << result << std::endl;   // result is 'false'
	return 0;
}

 

Check the container

Algorithm Description
is_sorted Check whether the container is sorted ascending.
is_partitioned Check whether the container is partitioned. “Partitioned” means that the elements are spitted into two groups, regarding a partition-condition. The container is partitioned in case all elements which are “true” regarding this partition-condition are placed in front of the group of elements which are “false” regarding this condition.

 

int _tmain(int argc, _TCHAR* argv[])
{
  std::vector data{ 5, 7, 9, 2, 4 };
  
  // check whether list is sorted
  bool result = std::is_sorted(data.begin(), data.end());
  std::cout << result << std::endl;   // result is 'false'

  // check whether list is partitioned  
  result = std::is_partitioned(data.begin(), data.end(), [](int element){ return (element % 2) == 1; });
  std::cout << result << std::endl;   // result is 'true'
  
	return 0;
}

 

Find container elements

Algorithm Description
find Get iterator of first element matching a given value.
find_if Get iterator of first element matching a given condition.
find_if_not Get iterator of first element not matching a given condition.
find_first_of Get iterator of first element matching one of the given values.
partition_point Get iterator of the first element of the second group of a partitioned container. See “is_partitioned” in the previous list to get more information about partitioning.
adjacent_find Get iterator of first of an adjacent pair of same elements. So, the value must be available at least twice and these same values must be placed on consecutive indexes. Therefore, the function is not made to find elements which are not unique as it will find these elements only in case they are placed on adjacent indexes.

 

int _tmain(int argc, _TCHAR* argv[])
{
  std::vector data{ 5, 7, 9, 2, 4};

  // find elements
  auto iterator = std::find(data.begin(), data.end(), 9);
  if (iterator != data.end())
  {
    std::cout << *iterator << " found at index " << std::distance(data.begin(), iterator) < 6); });
  if (iterator != data.end())
  {
    std::cout << "matching element found at index " << std::distance(data.begin(), iterator) << std::endl;
    // output is 'matching element found at index 1'
  }

  std::vector dataToFind{ 1, 9, 3, 7 };
  iterator = std::find_first_of(data.begin(), data.end(), dataToFind.begin(), dataToFind.end());
  if (iterator != data.end())
  {
    std::cout << "matching element found at index " << std::distance(data.begin(), iterator) << std::endl;
    // output is 'matching element found at index 1'
  }

  // find adjacent and equal values 
  iterator = std::adjacent_find(data.begin(), data.end());
  if (iterator != data.end())
  {
    std::cout << "adjacent element found at index " << std::distance(data.begin(), iterator) << std::endl;
    // no output as the list does not contain equal adjacent elements
  }

  // find partition point
  iterator = std::partition_point(data.begin(), data.end(), [](int element){ return (element % 2) == 1; });
  if (iterator != data.end())
  {
    std::cout << "partition point found at index " << std::distance(data.begin(), iterator) << std::endl;
    // output is 'partition point found at index 3'
  }

  return 0;
}
Advertisements
Dieser Beitrag wurde unter C++ veröffentlicht. Setze ein Lesezeichen auf den Permalink.

Eine Antwort zu Algorithms to use, find and check container elements

  1. Pingback: STL Algorithms | coders corner

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden /  Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden /  Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden /  Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden /  Ändern )

w

Verbinde mit %s