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

Eine Antwort zu Algorithms to copy, move and remove 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 )

w

Verbinde mit %s