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

Public vs. protected vs. private inheritance

In C++ you have three kind of inheritance: public, protected and private. From a technical point of view, they differ in the visibility of methods of the derived class and therefore they influence the interface of the derived class. So, from technical point of view these inheritance types are easy to explain. But from a software design point of view, it may become more difficult to explain the different concepts. Within this article I want to give a short overview about these three inheritance types from a software design point of view and connect them with the underlying concepts of the object-oriented paradigm.

 

Public inheritance

This type of inheritance creates an “is-a” relationship between objects. The derived object will offer the base class interface and therefore the derived class type “is-a” base class type too. This reflects the ideas of inheritance within the object-oriented paradigm. Within a previous article you will find some more details about this concept.

 

Private inheritance

In contrast to public inheritance, which creates a logical relationship between classes, the private inheritance reflects a more technical point of view. It will create a “is implemented in terms of” relationship between classes. Therefore, this concept competes with composition, which creates the same kind of binding between classes. As your always should prefer composition over inheritance, private inheritance is only needed in case technical limitations omit the use of composition. Within a previous article you will find further information about this concept and some use cases for private inheritance.

 

Protected inheritance

From a technical point of view, protected inheritance is easy to understand. But from a software design point of view you will get in trouble very quickly. If you think about possible use cases you may come to the decision that public inheritance isn’t needed at all. But C++ offers this feature, as it makes sense from a technical point of view.

The reason for protected inheritance are the same as they for private inheritance. If you have reasons to inherit something privately and additional you want to make functionality accessible to derived classes, you have to use protected inheritance. Obviously, private inheritance should be used scarcely, and protected inheritance even more so. Private inheritance is some kind of a compromise solution were you intentionally violate against some base software design rules, due to technical limitations. Strictly speaking, with protected inheritance you will inherit these design violations from base class to derived class. From a software design point of view, you should never use protected inheritance. And in my opinion the same is true from a technical point of view. The technical limitations can be resolved by using private inheritance. Therefore, I don’t see any reason or any use case for protected inheritance.

 

Summary

As there are three access levels in C++, it makes sense, from a technical point of view, to provide these access levels for inheritance too. But from a software design point of view you need public inheritance only. Therefore, you should use private inheritance only if you have to deal with situations were technical limitations force you to do so. As these rare situations can be resolved with private inheritance, there is no need for protected inheritance at all.

Veröffentlicht unter C++ | Kommentar hinterlassen

Private inheritance creates a “is implemented in terms of” relationship

In C++ we have three kind of inheritance: public, protected and private. Within a previous article I have shown the concepts of public inheritance. By using public inheritance, you can implement your software according to the object-oriented paradigm and create an “is-a” relationship between two classes. In public inheritance, the derived class “is-a” base class.

In contrast, private inheritance creates some other kind of relationship. The derived class is no longer a base class as the public base class interface will be changed to a private interface. The following code shows an according example. A function expects a base class as input parameter. You can pass a derived class to this function if you use public inheritance. But if you try the same by using private inheritance, the compiler will show you an according error.

class Base {};
class DerivedPublic : public Base {};
class DerivedPrivate : private Base {};

void DoSomething(Base x)
{
}

int _tmain(int argc, _TCHAR* argv[])
{
  DerivedPublic derivedPublic;
  DerivedPrivate derivedPrivate;

  DoSomething(derivedPublic);   // OK, derived is a base
  DoSomething(derivedPrivate);  // Error, derived is not a base

  return 0;
}

 

“is implemented in terms of”

But why do we need private inheritance and what kind of relationship do we create? Private inheritance is done because the derived class wants to take advantage of the features of base class. There is no conceptual relationship between base and derived at all. So, private inheritance is a pure implementation technique and not a conceptual idea of the object-oriented paradigm.

In private inheritance, the implementation of the base class will be inherited and the public interfaces should be ignored. As the base class functions become private in derived class, these features are no longer important for a client and become just implementation detail. So, the derived class „is implemented in terms of“ the base class, nothing more.

Another short term to describe the relationship is: “has-a”. A derived class “has-a” base class and uses their features. If you prefer the shorter “has-a” term you should keep it in mind. I like the longer description “is implemented in terms of”, as it emphasizes the key point: private inheritance is a technical concept.

 

Private inheritance vs. composition

So far, we didn’t answer the question why we need private inheritance, or if we need it at all. Before I try to answer this question, I want to show an alternative to private inheritance. There is another common software design which creates a “has-a” relationship: composition. You can implement a class and use the features of another class by creating a member instance. The following example shows the two concepts.

class Engine {};

class Car1 : private Engine {};

class Car2
{
private:
  Engine mEngine;
};

int _tmain(int argc, _TCHAR* argv[])
{
  return 0;
}

We want to implement a car class. A car “has-a” engine but there is no “is-a” relationship between these two classes. So, we should not use public inheritance. But private inheritance is fine, as well as composition. As we have two ways to implement the same thing we must think about the differences to identify the right concept for our use case.

In object-oriented software, you write classes and you create relationships between the classes. Private inheritance as well as composition are ways to create such relationships. In object-oriented software, you can increase the code quality, if you reduce the relationships between classes. The software complexity grows with the number and the strength of relationships.

Private inheritance as well as composition creating one relationship. So, there is no difference in the number of connections. But the two concepts differ in the strength of their binding. Inheritance is the strongest kind of relationship between two objects. Composition instead is a looser form of binding. If you combine composition with the use of interfaces, you can define the class member as instance of some class which implements the interface. This interface based kind of composition is the loosest kind of relationship between objects. In summary, you should prefer composition over private inheritance, as composition will always create a looser coupling of objects.

 

Use cases for private inheritance

We should always prefer composition over private inheritance. So, we don’t need private inheritance any longer? Of course, it isn’t that easy. Each rule has their exceptions. We will find some (rare) cases were technical limitations will make it not possible to implement a class composition. Following, I want to show some of these most common use cases for private inheritance.

 

Use case: virtual functions

I think the most common use case for private inheritance is the need to overwrite virtual functions of some tool class. Let me explain this use case based on an example. Let’s say you want to implement an own button control class. So, amongst other things, you have to deal with mouse events. Within your existing application framework, you will find a mouse-event class. The following source code shows the class interface. To keep it simple I omitted the event parameters, like the mouse movement coordinates.

class MouseEvent{
public:
  MouseEvent();
  virtual void OnMouseMove() const; // automatically called 
  virtual void OnLeftButtonDown() const; // automatically called 
  virtual void OnLeftButtonUp() const; // automatically called 
  virtual void OnRightButtonDown() const; // automatically called 
};

 

The MouseMove class offers several virtual functions, which will be called on the according mouse event. You can overwrite these functions to handle the events. So, this class offers the functionality you need for your button class. As you start your implementation you think about the possible relationship for the button and the mouse event class. A button is not a mouse event. Therefore, you don’t have an inheritance relationship, in terms of the object-oriented paradigm. A button “has-a” mouse event. This kind of relationship should be implemented by using composition. But in this case it isn’t possible because you have to overwrite the virtual functions. This technical limitation makes it necessary to use the other possible implementation for a “has-a” or “is implemented in terms of” relationship: private inheritance.

class MouseEvent{
public:
  MouseEvent();
  virtual void OnMouseMove() const; // automatically called 
  virtual void OnLeftButtonDown() const; // automatically called 
  virtual void OnLeftButtonUp() const; // automatically called 
  virtual void OnRightButtonDown() const; // automatically called 
};

class MyButton : private MouseEvent
{
private:
  void OnLeftButtonDown() const override
  {
    // ...
  }
};

 

As you can see, private inheritance will offer a technical concept to deal with such situation. Even if it is not preferred to implement a “has-a” relationship by using inheritance, it is the only possible solution in this case.

There is another implementation pattern for such use cases. This pattern is also based on inheritance but this time we use a combination of public inheritance and composition. The resulting solution has a little more difficult design as one additional class is involved. But you will get the benefits of decoupling and therefore cleaner code with minimized compilation dependencies, which may become an important issue in large systems.

class MouseEvent{
public:
  MouseEvent();
  virtual void OnMouseMove() const; // automatically called 
  virtual void OnLeftButtonDown() const; // automatically called 
  virtual void OnLeftButtonUp() const; // automatically called 
  virtual void OnRightButtonDown() const; // automatically called 
};

class ButtonMouseEvent: public MouseEvent
{
public:

  //...here you may offer methods to consume the mouse events 
  // (e.g. callback or observer registration)

private:
  void OnLeftButtonDown() const
  {
    //...
  }
};

class MyButton
{
private:
  ButtonMouseEvent* pMouseEvent;
};

 

Nevertheless, the fact that there are several solutions to handle such use cases, we should try to prevent such a bad software design. In this use case, the design of the MouseEvent class was the cause of the issue. This class forces a client to overwrite functions. Therefore, it generates a technical limitation which inevitable leads to inheritance. So, the class designer forces a client to use the strictest kind of relationship between objects. This will result in the associated disadvantages and makes the resulting source code less changeable, expandable and maintainable.

 

Use case: Access protected members

In case a class needs access to protected members of another class, you cannot use composition too, as it is limited to the public interface. In such a case, you also have to use inheritance. For example, for our button class, we want to use some other already existing functionality. This functionality is implemented in a protected member function within an existing class in our framework. In this case we also have a “has-a” relationship but we cannot implement it by using composition. Again, because of technical limitations, we have to use private inheritance or as alternative a combination of public inheritance and composition. Therefore, from a software design point of view, this use case is to the previous one.

 

Use case: Empty base class optimization

There is another use case, known as “empty base class optimization”. Private inheritance is used to allow empty classes which do not need any memory. This use case is only interesting for library developers who wants to minimize object sizes. Therefore, I don’t want to go into detail here. If you are interested in this topic you will find a lot of nice articles out there. Search for “empty base class optimization”, “EBC” or “EBCO” in this case.

 

Use case: In terms of lifetime management, the tool class should enclose the client class

This sounds strange but if we look at an example it will become easy to understand. Let’s say you want to offer a tool class which locks an object during its lifetime. In this case your locking class should enclose the client which uses the locker. That means, the locker must be created right before the client and it must be destroyed after the client. C++ offers this lifetime management as standard build in feature in inheritance situations. A base class is always created right before the derived class and destroyed after derived class. Therefore, in such a case, inheritance can be used to manage the lifetime of the objects. Your locker class will be a private base class for the derived class which shall be locked.

Of course, this kind of implementation is still based on technical decisions. From a software design point of view, you will find some other possible solutions. For example, a factory class which manages the creation and therefore the lifetime of object instances.

 

Summary

Private inheritance creates a “is implemented in terms of” relationship between classes, also known as “has-a” relationship. By using composition, you can create the same kind of relationship but with a much looser coupling between the classes. Therefore, you should prefer composition and use private inheritance only of you must. This “must” is based on technical limitations in some rare use cases.

Veröffentlicht unter C++ | 1 Kommentar

Public inheritance always creates an “is-a” relationship

The object-oriented paradigm defines inheritance as a relationship between two classes, were the derived class is a kind of the base class. This logical concept is independent of the programming language. Therefore, object-oriented languages will offer different implementations of this concept. For example, some languages will allow multiple inheritance while other languages support single inheritance only. Furthermore, some languages will add additional kinds of inheritance. These kinds of inheritance add some implementation techniques. So, they extend the inheritance system and allow a logical inheritance, which follows the object-oriented paradigm, but also allows a technical inheritance. Both implementation techniques can be called “inheritance” but they are very different from a software design perspective.

Within this article I want to have a look on the C++ inheritance system. C++ supports logical and technical inheritance. If you define a derived class and set the base class, you can select between “public”, “protected” and “private” inheritance. These keywords do not only change the visibility of methods, they represent completely different programming paradigms. That’s an important difference which is sometimes underrated and misunderstood. Therefore, I want to introduce this topics within this and the next article. We will start with public inheritance, which allows a logical relationship, and within the next article we will continue with private and protected inheritance which is used to create a technical relationship between objects.

 

X “is-a” Y

Public inheritance in C++ creates a relationship between a base and a derived object. This relationship is, according to the object-oriented paradigm, a “is-a” relationship. You should keep this simple rule in mind and should always check whether the “is-a” rule is fulfilled. Otherwise inheritance may not be a good decision. For example, a SUV is a car and a SUV has an engine. The “is-a” relationship between SUV and car can be implemented by public inheritance. But in contrast, the SUV is not an engine. Here we have a “has-an” relationship. This can be implemented by using composition.

This simple rule sounds very easy, and it is, but unfortunately inheritance is sometimes overused and especially novice developers will often use inheritance instead of composition. This creates wrong and unnecessary strong dependencies between objects and makes the code harder to maintain.

 

Derived is-a Base, but not vice versa

As the derived class is-a base class too, it can be used whenever the base class is needed. The following example shows an according function call which expects a base class but we pass a derived object instance, which is totally fine.

class Animal {};
class Bird : public Animal {};

void DoSomething1(Animal x)
{
}

void DoSomething2(Bird x)
{
}

int _tmain(int argc, _TCHAR* argv[])
{
  Animal animal;
  Bird bird;

  DoSomething1(animal);   // OK
  DoSomething1(bird);     // OK, a bird is-a animal

  DoSomething2(animal);   // Error, a animal is not a bird
  DoSomething2(bird);     // OK

  return 0;
}

 

As you can see, the function calls will work like expected and the compiler detects whether a wrong type is used.

But there is an important question to answer: if we expect a base class and pass a derived class instead, will we then use the base class functionality or the derived class functionality?

Let’s answer this question with a little test. We add a function to the base class and overwrite it in the derived class.

class Animal 
{
public:
  virtual void WhoAreYou()
  {
    std::cout << "I am an Animal." << std::endl;
  }
};

class Bird : public Animal 
{
public:
  void WhoAreYou()
  {
    std::cout << "I am a Bird." << std::endl;
  }
};

void DoSomething(Animal x)
{
  x.WhoAreYou();
}

int _tmain(int argc, _TCHAR* argv[])
{
  Animal animal;
  Bird bird;

  DoSomething(animal);
  DoSomething(bird);  

  return 0;
}

 

In both cases, a function call with base class and a function call with derived class, the output is: “I am an Animal”. As the function parameter expects an instance of an animal, this behavior is like expected. On function call the bird class instance will be used to create an animal class instance.

But what will happen if we don’t create a copy and pass a reference instead.

class Animal
{
public:
virtual void WhoAreYou()
{
std::cout << "I am an Animal." << std::endl;
}
};

class Bird : public Animal
{
public:
void WhoAreYou()
{
std::cout << "I am a Bird." <DoSomething();
}

MyOtherDerived* y2 = dynamic_cast(x);
if (y2 != nullptr)
{
y2->DoSomethingOther();
}
}

int _tmain(int argc, _TCHAR* argv[])
{
MyOtherDerived myOtherDerived;

Execute(&myOtherDerived);

return 0;
}

 

Beside the terrible variable names “y1” and “y2” the source code contains a big issue, something I want to call: “lying interfaces”. The function declaration for “Execute” tells everyone that the functions expects a parameter of type “MyBase”. But that’s a lie! The function expects a “MyDerived” object or a “MyOtherDerived” object. Because of public inheritance both classes are-a “MyBase” but not vice versa. So “MyBase” is never-ever a “MyDerived” or “MyOtherDerived”. Of course, with pointers and casting you can implement such functionality but beside the violation of the inheritance rules you will create “lying interfaces” which may result in big issues, for example source code which is hard to maintain or even worse, results in undefined behavior.

The same is true for return values. You should not return a base class pointer in case you want to return a derived class pointer. I have seen this issue several times, especially in interfaces which return data. In such cases there is one function which returns a pointer to a base class data type. But that’s a “lying interface” too as the function returns data of derived classes and the developer of the interfaces expects that the client will do casting and convert the type into the derived class. That’s a terrible software design which will move work and errors to the client. To avoid such “lying interfaces”, the interface must offer type specific versions of the functions or as a better solution, the software design for the data classes should be adapted to fulfill the needs of the interface and therefore the needs of the client.

 

Interfaces

Within the examples of the article we have seen base class and derived class objects and functions which expect base class parameters. A special kind of base class is the interface. In C++ you can interfaces by implementing pure virtual classes. I would to recommend the use of interfaces. If your base class is an interface, you can create a loose coupling. The function call parameter or return value as well as class members can be of the interface type instead of a base class type. As the interface is more generic and independent of a real implementation, you create a loose relationship between objects. You expect something which offers the needed functionality instead of a concrete implementation. This dependency against functionality allows a more efficient software design.

 

Summary

In C++ you can implement inheritance according to the object-oriented paradigm by public inherit derived classes from base classes. This relationship is always an “is-a” relationship which means: the derived class “is-a” base class but not vice versa. Therefore, whenever a function expects a base class as parameter you can pass a derived class too.

This inheritance mechanism is well supported by the C++ compilers. Issues will occur only in case software developers ignore the rules of the object-oriented paradigm. In my opinion, the most common errors are a violation of the Liskov Substitution Principle and “lying interfaces”. Such interfaces will force the interface implementer or the interface client to implement against some (maybe written down) expectations. Such lying interfaces can be identified very easily as type casting will become necessary on interface and/or client side.

Veröffentlicht unter C++ | 2 Kommentare