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

Kommentar verfassen

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

WordPress.com-Logo

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

Google+ Foto

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

Twitter-Bild

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

Facebook-Foto

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

w

Verbinde mit %s