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

Eine Antwort zu Algorithms to change and sort container elements

  1. Pingback: STL Algorithms | coders corner

Kommentar verfassen

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

WordPress.com-Logo

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

Google+ Foto

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

Twitter-Bild

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

Facebook-Foto

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

Verbinde mit %s