Create own STL algorithms wrapper

Within the previous articles about STL algorithms I introduced the main algorithms sorted by their use case. This analysis of the actual STL algorithms has shown the power of the algorithms but also their issues. The main issues are misleading names and a sometimes-cumbersome notation.

Of course, it is easy to write source code by using the algorithms, but it is sometimes hard to read and understand existing code. Notation matters more than we usually like to believe. Therefore, it may be useful to create an own algorithm wrapper and hide the misleading names and the cumbersome notation behind an easy to use interface.

Within this article I want to show some examples for algorithms wrapper. These wrapper functions add a self-explaining interface and therefore you don’t have to write comments to explain the algorithms. If you use these algorithms without a wrapper, you must write comments to each algorithm to explain its behavior.

 

Example: remove elements from container

The algorithm “remove” is used to remove elements from a container. But unfortunately, this algorithm will not remove the elements. Instead it will shift the elements to delete to the end of the container and returns an iterator to the new logical end. So, you always must explicitly erase the elements after calling the algorithm. I think that’s a perfect candidate for a wrapper function.

template
void RemoveElement(C& container, E element) 
{ 
  // remove (shifts elements but dont deletes them)
  auto newEndIterator = std::remove(container.begin(), container.end(), element);
  
  // delete elements
  container.erase(newEndIterator, container.end());
}

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, 9, 3 };

  RemoveElement(data, 9);

  Print(data);  // output is '5 7 2 4 3'

  return 0;
}

 

Example: count equal pairs in two containers

With the algorithm “inner_product” you can – like the name reveals – calculate an inner product. But you can specify own operations and then the function will offer a common map/reduce functionality according to the given algorithm. So, if you set an algorithm the name “inner_product” is wrong as the function no longer calculates the inner product.

The following example shows how to count the equal pairs of two containers. If you put this function into a self-explaining wrapper function, the code will become much easier to understand.

template
int CountEqualPairs(C& container1, C& container2)
{
  return std::inner_product(
    container1.begin(), container1.end(), container2.begin(),
      0, std::plus(), std::equal_to());    
}

int _tmain(int argc, _TCHAR* argv[])
{
  std::vector data1{ 5, 7, 9, 2, 4, 9, 3 };
  std::vector data2{ 1, 0, 9, 8, 4, 3, 3 };
  
  int result = CountEqualPairs(data1, data2);

  std::cout << result << std::endl;   // result is '3'

  return 0;
}

 

Example: pairwise multiplication

The algorithm “transform” is another good candidate for a wrapper. This algorithm can be used for a wide range of use cases and therefore it has a cumbersome notation. So, if you read an implementation using this algorithm you must stop for a short (or sometimes long) moment and think about the purpose of the source code. In such cases you are happy if the developer has written a comment and explains the behavior of the algorithm. But often such a comment is missing.

As explained above, a self-explaining wrapper can help to write clean code which is easy to understand and to maintain. The following example shows a possible implementation for a pairwise multiplication.

template
C PairwiseMultiply(C& container1, C& container2)
{
  C target;

  std::transform(
    container1.begin(), container1.end(),
    container2.begin(),
    std::back_inserter(target),
    std::multiplies());  

  return target;
}

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 data1{ 5, 7, 9, 2, 4, 9, 3 };
  std::vector data2{ 1, 0, 9, 8, 4, 3, 3 };
  std::vector target;
  
  target = PairwiseMultiply(data1, data2);

  Print(target);  // output is '5 0 81 16 16 27 9'

  return 0;
}

 

Summary

The STL algorithms are sometimes hard to understand. If you read source code and you find an algorithm, you have to stop for a moment and think about its purpose. A wrapper library helps to hide these implementation details behind a self-explaining interface. This will allow you to create more readable and maintainable source code.

Advertisements
Veröffentlicht unter C++ | 1 Kommentar

Operations which can be used in STL algorithms

Within the previous articles about STL algorithms I introduced the main algorithms sorted by their use case. Within this article I want to give an overview about the STL operations. These operations can be used stand-alone and within STL algorithms. The combination of the existing algorithms and operations will allow to solve complex implementations of some standard use cases in an easy way.

 

Compare two elements

Algorithm Description
equal_to Check whether the two elements are equal.
not_equal_to Check whether the two elements are not equal.
greater Check whether the first element is greater than the second one.
less Check whether the first element is smaller than the second one.
greater_equal Check whether the first element is greater or equal to the second one.
less_equal Check whether the first element is smaller or equal to the second one.
max Returns the larger one of the two elements.
min Returns the smaller one of the two elements.
minmax Returns a pair which contains the smaller element followed by the larger element.

 

Within the examples the operations “greater” and “less” are used to sort a container. The third example makes use of “max” operator to merge two containers by taking the maximum value of each element pair.

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

  // greater
  std::sort(data.begin(), data.end(), std::less());
  Print(data);  // output is '2 4 5 7 9'

  // less
  std::sort(data.begin(), data.end(), std::greater());
  Print(data);  // output is '9 7 5 4 2'

  // max
  std::vector data1{ 5, 7, 9, 2, 4 };
  std::vector data2{ 3, 8, 1, 5, 8 };
  std::vector target;
  std::transform(data1.begin(), data1.end(), 
    data2.begin(), std::back_inserter(target), 
    [](int a, int b) {return std::max(a, b); });
  Print(target);  // output is '5 8 9 5 8'

  return 0;
}

 

Search elements in container

Algorithm Description
max_element Returns an iterator to the largest element of the container.
min_element Returns an iterator to the smallest element of the container.
minmax_element Returns a pair which contains an iterator to the smallest element of the container followed by an iterator to the largest element of the container.

 

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

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

  return 0;
}

 

Calculations with one input

Algorithm Description
negate Returns the negation of the element.
clamp Returns the given element with respect to a value range. If the given element is outside of the range the returned value will be equal to the lowest or highest boundary.

Example: “clamp(x,20,30)” means the returned value must be in range 20 to 30. If x is less than 20 “20” will be returned. If x is between 20 to 30 “x” will be returned. If x is larger than 30 “30” will be returned.

 

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 };
  
  // negate
  std::transform(data.begin(), data.end(), data.begin(), std::negate());
  Print(data);  // output is '-5 7 -9 2 -4'

  return 0;
}

 

Calculations with two inputs

Algorithm Description
plus Returns the sum of the two elements.
minus Returns the difference of the two elements.
multiplies Returns the product of the two elements.
divides Returns the quotient of the two elements.
modulus Returns the residual value of the division of first element by second element.
logical_and Returns the result of a logical-and calculation of the two elements.
logical_or Returns the result of a logical-or calculation of the two elements.
logical_not Returns the result of a logical-not calculation of the two elements.
bit_and Returns the result of a bitwise-and calculation of the two elements.
bit_or Returns the result of a bitwise-or calculation of the two elements.
bit_xor Returns the result of a bitwise-xor calculation of the two elements.
bit_not Returns the result of a bitwise-not calculation of the two 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, 9, 2, 4 };
  std::vector source2{ 3, 1, 2, 5, 7 };
  std::vector target;

  std::vector source3{ 1, 1, 0, 0 };
  std::vector source4{ 1, 0, 1, 0 };

  // sum
  std::transform(source1.begin(), source1.end(), source2.begin(),
    std::back_inserter(target), std::plus());

  Print(target);  // output is '8 8 11 7 11'

  // logical or
  target.clear();

  std::transform(source3.begin(), source3.end(), source4.begin(),
    std::back_inserter(target), std::logical_or());

  Print(target);  // output is '1 1 1 0'

  // bitwise xor
  target.clear();

  std::transform(source3.begin(), source3.end(), source4.begin(),
    std::back_inserter(target), std::bit_xor());

  Print(target);  // output is '0 1 1 0'
  
  return 0;
}
Veröffentlicht unter C++ | 1 Kommentar

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;
}
Veröffentlicht unter C++ | 1 Kommentar

Algorithms for sorted 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.

 

Check elements within a sorted container

Algorithm Description
binary_search Check whether an element is found within the container.
includes Check whether all elements of the given list are found within the container.

 

int _tmain(int argc, _TCHAR* argv[])
{
  std::vector data{ 1, 2, 3, 3, 4, 5, 5 };
  
  // search one element
  bool found = std::binary_search(data.begin(), data.end(), 3);
  std::cout << found << std::endl;    // result is 'true'

  // search several elements
  std::vector elementsToFind{ 4, 5 };
  found = std::includes(data.begin(), data.end(), elementsToFind.begin(), elementsToFind.end());
  std::cout << found << std::endl;    // result is 'true'

	return 0;
}

 

Find elements within a sorted container

Algorithm Description
lower_bound Get iterator of first element matching a given value.
upper_bound Get iterator of element behind last element matching a given value.

Therefore, the function will not return the element iterator but the end-iterator of the section with the given value. As a side effect, this function is not suitable to check whether a value exist or not because if it returns the container end you cannot distinguish whether the value was found at last position or not found at all.

equal_range Get iterator of first element matching a given value and iterator behind the last element matching this value. Therefore, this function is a combination of “lower_bound” and “upper_bound”.

 

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

  // iterator of element
  auto iterator1 = std::lower_bound(data.begin(), data.end(), 3);
  std::cout << *iterator1 << " found at index " << std::distance(data.begin(), iterator1) << std::endl;
  // output is '3 found at index 2'

  auto iterator2 = std::upper_bound(data.begin(), data.end(), 3);
  std::cout << "element found till index " << std::distance(data.begin(), iterator2) << std::endl;
  // output is 'element found till index 4'

  auto range = std::equal_range(data.begin(), data.end(), 3);
  std::cout << *range.first << " found from index " 
    << std::distance(data.begin(), range.first) 
    << " till index " 
    << std::distance(data.begin(), range.second) << std::endl;
  // output is '3 found from index 2 till index 4'
  
	return 0;
}

 

Combine two sorted containers

Algorithm Description
merge Create a new container which contains all elements of container A and all elements of container B. The elements which are available in both containers will all be copied – so the intersection is used twice.

(A + B)

set_union Create a new container which contains all elements of container A and all elements of container B. The elements which are available in both containers will be copied only once – so the intersection is used once.

(A + B – intersection)

set_intersection Create a new container which contains elements which are available in both containers – which is the intersection.
set_difference Create a new container which contains all elements of container A which are not in container B.

(A – intersection)

set_symmetric_difference Create a new container which contains all elements of container A which are not in container B and all elements of container B which are not in container A.

(A + B – 2 x intersection)

 

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 v1{    1, 2, 3, 3, 4, 5, 5 };
  std::vector v2{ 0,    2, 3,       5, 5, 5, 5, 6 };

  // merge
  std::vector vMerge;
  std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(vMerge));
  // resulting container: '0 1 2 2 3 3 3 4 5 5 5 5 5 5 6'

  // union
  std::vector vUnion;
  std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(vUnion));
  // resulting container: '0 1 2 3 3 4 5 5 5 5 6'

  // intersection
  std::vector vIntersection;
  std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(vIntersection));
  // resulting container: '2 3 5 5'

  // difference
  std::vector vDifference;
  std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(vDifference));
  // resulting container: '1 3 4'

  // symmetric difference
  std::vector vSymmetricDifference;
  std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(vSymmetricDifference));
  // resulting container: '0 1 3 4 5 5 6'

  //output
  Print(vMerge);
  Print(vUnion);
  Print(vIntersection);
  Print(vDifference);  
  Print(vSymmetricDifference);
  
	return 0;
}
Veröffentlicht unter C++ | 1 Kommentar

Algorithms to change and sort 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 change and sort 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.

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.

 

Change container elements

Algorithm Description
replace Exchanges elements with a new element if they match a given value.
replace_if Exchanges elements with a new element if they match a given predicate.
transform Exchanges elements with new elements according a transformation function.
iota Fill the container with increasing values, e.g. fill a container with 10 elements with the value 1 to 10.

The function starts with a given value and increases the value with “++value”.

In my opinion, the name “iota” is a bad choice. A function name should be self-explaining and you will describe parameters and results only. If you must explain the function name itself, something is terribly wrong.

 

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

  // replace if
  std::replace_if(data.begin(), data.end(), [](int element){return element < 7; }, 0);
  Print(data);    // output is '0 7 9 0 0'

  // transform
  std::transform(data.begin(), data.end(), data.begin(), [](int element) {return element + 20; });
  Print(data);    // output is '20 27 29 20 20'

  return 0;
}

 

Sort container elements

Algorithm Description
sort Sort the elements ascending or according a given comparison function. The order of equal elements is not guaranteed to be preserved.
stable_sort Works like “sort”. Additional, the order of equal elements is preserved.
partial_sort Sorts the elements till a given index. The order of sorted equal elements is not guaranteed to be preserved. The order of the remaining unsorted elements is unspecified.
nth_element You can use this function if you want to get the nth element of the container.

Like in “partial_sort” you set the index within a range and the elements will be sorted ascending or according a given comparison function. In contrast to “partial_sort” the elements in front of this index may not be sorted but they are lower than the element on given index. So, if you want to get the nth-element of a container you may use “partial_sort” or “nth_element” and read the element at the given index after sorting. “nth_element” may be faster as it does not have to ensure sort order of the elements.

Example: You have a container with elements “3 5 0 1 7 9” and you want to get the third element. The result after “nth_element” may be “0 1 3 5 7 9” but may be also “1 0 3 7 5 9” or any other combination. But in all cases the third element within the resulting container is “3”.

reverse Reverses the order of the elements.
rotate Rotates the elements by a given new start-iterator.

It is also possible to rotate to right if you use “rstart” and “rend” for the range.

partition Sorts the elements into two groups (partitions) according to the given partition-predicate. The first group contains all elements for which the predicate is “true” and the second group contains all elements for which the predicate is “false”. The relative order of the elements within each group is not preserved.
stable_partition Works like “partition”. Additional, the order of equal elements is preserved.
shuffle Reorders the elements by randomly.

The random number generator must be a UniformRandomBitGenerator whose result type is convertible to std::iterator_traits::difference_type.

 

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

  // sort
  std::sort(data.begin(), data.end());
  Print(data);    // output is '2 4 5 7 9'
    
  // partial sort
  data = { 5, 7, 9, 2, 4 };  
  std::partial_sort(data.begin(), data.begin()+2, data.end());
  Print(data);    // output is '2 4 9 7 5'

  // rotate to right
  data = { 5, 7, 9, 2, 4 };
  std::rotate(data.rbegin(), data.rbegin() + 1, data.rend());
  Print(data);    // output is '4 5 7 9 2'

  // partition
  data = { 5, 7, 9, 2, 4 };
  std::partition(data.begin(), data.end(), [](int element){return element > 6; });
  Print(data);    // output is '9 7 5 2 4'

  // stable partition
  data = { 5, 7, 9, 2, 4 };
  std::stable_partition(data.begin(), data.end(), [](int element){return element > 6; });
  Print(data);    // output is '7 9 5 2 4'

  // shuffle
  data = { 5, 7, 9, 2, 4 };
  std::random_device randomDevice;
  std::mt19937 randomNumberGenerator(randomDevice());
  std::shuffle(data.begin(), data.end(), randomNumberGenerator);
  Print(data);    // output is different on each execution

  return 0;
}
Veröffentlicht unter C++ | 1 Kommentar

Algorithms to copy, move and remove 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 copy, move and remove 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.

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.

 

Copy container elements

Algorithm Description
copy Copy elements to new location. The elements are given by start-iterator and end-iterator.
copy_n Copy elements to new location. The elements are given by a start-iterator and an element number.
copy_if Copy elements to new location if they match the given condition.
copy_backward Copy elements to the new location.

The new location is given as end-iterator and the elements will be placed in front of this end-iterator. The element order is not changed. Therefore, the name “copy_backward” is some kind of misleading and one may mix up “copy_backward” and “reverse_copy”. In my opinion, a better name would be “copy_to_end”.

reverse_copy Copy elements in reverse order to new location.
rotate_copy Copy elements to new location and rotate elements according a given new start-iterator.

Example: Rotate copy of container “1 2 3 4” with new start-iterator “3” results in “3 4 1 2”.

unique_copy Copy elements to new location and exclude consecutive equal elements.

The name of the function is misleading as the target container may contain an element several times. “unique_copy” only removes equal elements if they are placed in consecutive order.

Example: Unique copy of container “1 2 2 2 3 2” will result in “1 2 3 2”.

remove_copy Copy elements to new location. Does not copy elements according a given comparison element.
remove_copy_if Copy elements to new location. Does not copy elements according a given comparison predicate.
replace_copy Copy elements to new location. Replaces elements according a given comparison element with a new element.
replace_copy_if Copy elements to new location, replaces elements according a given comparison predicate with a new element.
transform Copy elements to new location. The new element will be created according the given transformation function.

The naming isn’t consistent in this case. The function should be named “transform_copy” but in this case the “transform” function exists which can be used for other use cases too.

partial_sort_copy copy elements to new location and sorts them ascending or according given sort function, the new location may be smaller than the sorce container, in this case only the first x elements are copied

-> e.g. source: 1,4,3,2,5 -> target container has size 3 -> result is „1,2,3“

partition_copy Copy elements to two new locations. Each target contains one of the two partitions. The first target container contains all elements where the partition predicate is “true” and the second target container contains all elements where the partition predicate is “false”.

 

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

  // copy if
  std::copy_if(source.begin(), source.end(), std::back_inserter(target), [](int element){return element > 5; });
  Print(target);  // output is '7 9'

  // copy backward
  target.clear();
  target.resize(8);
  std::copy_backward(source.begin(), source.end(), target.end());
  Print(target);  // output is '0 0 0 5 7 9 2 4'

  // reverse copy
  target.clear();
  std::reverse_copy(source.begin(), source.end(), std::back_inserter(target));
  Print(target);  // output is '4 2 9 7 5'

  // replace copy if
  target.clear();
  std::replace_copy_if(source.begin(), source.end(), std::back_inserter(target), [](int element){return element > 5; }, 99);
  Print(target);  // output is '5 99 99 2 4'

  // transform
  target.clear();
  std::transform(source.begin(), source.end(), std::back_inserter(target), [](int element) {return element + 20; });
  Print(target);    // output is '25 27 29 22 24'

  return 0;
}

 

Move container elements

Algorithm Description
move Move elements to new location.
move_backward Move elements to new location.

The new location is given as end-iterator and the elements will be placed in front of this end-iterator. The element order is not changed. Therefore, the name “move_backward” is some kind of misleading as one may think the function will reverse the order of the elements. In my opinion, a better name would be “move_to_end”.

 

The move algorithms will copy elements – so they remain within the source container – but they will use move semantic. Therefore, the origin elements within the source container may get changed. For example, the move ctor of the elements could be implemented in a way to steal resources and set the element member of the origin element to nullptr. Therefore, a move will normally be implemented in case the source container is no longer needed.

 

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

  // move
  std::move(source.begin(), source.end(), std::back_inserter(target));
  Print(source);  // output is '5 7 9 2 4'
  Print(target);  // output is '5 7 9 2 4'

  // move backward
  target.clear();
  target.resize(8);
  std::move_backward(source.begin(), source.end(), target.end());
  Print(source);  // output is '5 7 9 2 4'
  Print(target);  // output is '0 0 0 5 7 9 2 4'

  return 0;
}

 

Remove container elements

Algorithm Description
remove Removes the elements matching a given value.

Removing is done by shifting. The function returns an according new end iterator.

remove_if Removes the elements matching a given condition.

Removing is done by shifting. The function returns an according new end iterator.

unique Removes equivalent consecutive elements except the first one.

Removing is done by shifting. The function returns an according new end iterator.

Attention: The name “unique” is misleading. After a call of this function the container may still contains equal elements. The unique algorithms delete them only if they are placed in on consecutive positions.

 

Attention: All remove algorithms do not really delete elements. They shift the elements only and return a new end-iterator. The elements between this new logical end-iterator and the physical end are still accessible but have unspecified values. Therefore, after call of a remove algorithm you must call erase to delete the unspecified values. So, the remove algorithms are dangerous as they are incomplete functions. You must call erase explicitly to finish the deletion procedure.

 

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

  // remove
  auto newEndIterator = std::remove(data.begin(), data.end(), 9);
  std::cout << data.size() << std::endl;    // size is '5'

  data.erase(newEndIterator, data.end());  
  std::cout << data.size() << std::endl;    // size is '4'

  // unique
  std::vector data2{ 5, 7, 5, 2, 2, 8 };
  
  newEndIterator = std::unique(data2.begin(), data2.end());
  std::cout << data2.size() << std::endl;    // size is '6'

  data2.erase(newEndIterator, data2.end());
  std::cout << data2.size() << std::endl;    // size is '5'

  return 0;
}
Veröffentlicht unter C++ | 1 Kommentar

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;
}
Veröffentlicht unter C++ | 1 Kommentar