Algorithms for two containers

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

Algorithm Description
transform Create a resulting container by using the elements of two containers within a transformation function.

The first container is the controlling one. Therefore, the resulting container has same size as the first source container and the second source container must not be smaller than the first one.

inner_product Calculate the inner product of two containers. The inner product is the sum of all element pair products.
inner_product (with own operations) The default version of this function, without operations, calculates the inner product, like described above. But if you set specific operations, you can create several very different map/reduce algorithms. Therefore, the name “inner product” is misleading in this case.

If you set the operations, you must define two of them. The second one will be used on the pairwise elements of the containers and returns the result of an according calculation based these two given elements. The returned value will then be used within the first operation. This accumulation operation gets this result and the actual accumulation value as input and calculates a new accumulation value.

Within the example you see two implementations. The first one calculates the product of all pairwise differences and the second one counts the pairs of equal elements.

 

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

Algorithm Description
equal Check whether both containers are equal. They are equal if they have the same size and the same elements with same sort order.
mismatch Find the first difference within the two containers.

The function returns an iterator-pair of first position with different elements within the two containers. The resulting pair contains the iterators to the element of each list. The result contains one or two end-iterator if no mismatch was found. Till c++14 the second container must not be shorter than the first one. Since c++14 the second container may be shorter and if no mismatch was found the iterator pair contains the end-iterator of the shorter container and corresponding iterator of the other container.

is_permutation Checks whether a container is a permutation of the other one.

That means, it checks whether the containers have the same elements but the sort order may be different.

For example: “2 4 3 1 5” is a permutation of “1 2 3 4 5”.

lexicographical_compare Checks whether the first container is lexicographically less than the second one and return “true” in this case. Therefore, if the function returns “false” the containers either equal or the second one is less than the first one. In this case you can execute the lexicographical comparison again with changed containers or call the “equal” function to finish the comparison.

The containers are compared element by element. The first mismatching element defines which container is less or greater than the other one. If there are no mismatch, the smaller container is the less one. If the elements are equal and the containers sizes are equal, the containers are equal and the function will return “false”.

The function name is misleading as it isn’t a complete and finished comparison. In such a case, a three-state return value is needed. This function checks whether the first container is less and therefore, in my opinion, the function name should be “is_lexicographical_less” or even “is_less” as a function name should not reflect the technical details of its implementation.

C++20 may contain the function “lexicographical_compare_3way” which is a real comparison and returning the three-state return value.

search Searches a sub-sequence within a container and returns the iterator of the first position found or returns end-iterator if the sub-sequence isn’t found.
find_end Like “search”, this function searches a sub-sequence within a container. But in searches from the end and returns the last position found.

 

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;
}
Advertisements
Dieser Beitrag wurde unter C++ veröffentlicht. Setze ein Lesezeichen auf den Permalink.

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