Modifying Algorithms

Section 21.12 Modifying Algorithms

One category of algorithms in the standard library are those that modify the contents of a collection. These algorithms can change, rearrange, or remove elements within the collection. In this section we will explore a few examples of these modifying algorithms.

🔗

Subsection 21.12.1 Copy and Copy If

The copy algorithm copies elements from one collection to another. Of course, we can usually copy an entire collection by using the = operator. But the copy algorithm gives us more flexibility. It allows us to copy only a portion of a collection or to copy elements to a different type of collection.

🔗

It takes three parameters: the beginning and end of the source range, and the beginning of the destination range:

🔗

copy( InputIt first, InputIt last, OutputIt destination_first );

These parameters are all iterators. The first two specify the start and end of the range to copy from the source collection. The third specifies the beginning of the destination range. (The destination range must be large enough to hold all the copied elements.) So in code, it generally looks like this:

🔗

copy(source.begin(), source.end(), destination.begin());

Say we wanted to copy the first half of a vector source to another vector destination. We would need to make sure that destination has enough space to hold half the elements of source and then set up iterators to specify the range to copy:

🔗

//source already exists and is filled with data
int lengthToCopy = static_cast<int>(source.size()) / 2;
vector<int> destination(lengthToCopy); // make destination half the size of source
copy(source.begin(), source.begin() + lengthToCopy, destination.begin());

Imagine that source has 10 elements. lengthToCopy will get set to 5. So we create destination with a size of 5 (it will start with 5 default-initialized elements). The range we pass to copy, from source.begin() to source.begin() + lengthToCopy, will cover the first 5 elements of source. The elements will be copied into destination starting at its beginning, replacing its initial default values.

🔗

The copy_if algorithm is similar to copy, but it only copies elements that satisfy a certain condition. It takes an additional parameter: a predicate function (or functor) that defines the condition. Only elements for which the predicate returns true will be copied.

🔗

Say we wanted to copy only strings that have a length greater than 3 from one vector to another. We could use copy_if like this:

🔗

std::copy_if(
  source.begin(),
  source.end(),
  destination.begin(),
  [](const string& str) { return str.length() > 3; }
);

As before, we have exaggerated the spacing to make the parameters, especially the lambda function, easier to read.

🔗

This raises an interesting question: how do we decide how big the destination vector should be before copying?

🔗

One approach is to first count how many elements will satisfy the condition, then create the destination vector with that size. But that requires iterating through the source collection twice: once to count and once to copy. Another approach would be to set destination to be as large as source, then after copying, resize destination to the actual number of elements copied. This avoids the double iteration but may use more memory than necessary during the copy operation.

🔗

A third approach is to use an insert iterator. These are iterators that know how to correctly insert elements into a container. One such tool is a std::back_inserter. It automatically will add each item to the back of the destination container, correctly resizing it as needed. This way, you don’t need to know the final size in advance.

🔗

std::copy_if(
  source.begin(),
  source.end(),
  std::back_inserter(destination),
  [](const string& str) { return str.length() > 3; }
);

Here is that technique in action:

🔗

Listing 21.12.1.

🔗

Subsection 21.12.2 Remove

The remove algorithm removes elements from a collection that match a certain value or satisfy a certain condition.

🔗

If we have a collection of strings, and we want to keep only the long ones, we could use copy_if to copy the long strings to another collection. But, if we do not care about keeping the old collection around, we could instead remove the short strings from the original collection.

🔗

Note 21.12.1.

The efficiency of the two approaches depends on the specific container and how many we are removing. In a vector, it is likely more efficient to copy just the elements we want to a new vector rather than trying to remove a large number of elements from the original.

🔗

The prototype for remove looks like either:

🔗

remove( ForwardIt first, ForwardIt last, const T& value );

or, we can specify what to remove using a function:

🔗

remove_if( ForwardIt first, ForwardIt last, UnaryPredicate p );

The second version removes all elements for which the predicate function p returns true. Thus, to remove all the short strings from a vector called words, you could write:

🔗

remove_if(
  words.begin(),
  words.end(),
  [](const string& str) { return str.length() <= 3; }
);

Here is a program that removes even numbers from a vector and then prints it out.

🔗

Listing 21.12.2.

🔗

What is wrong with the output???

🔗

If you look closely, you will see that the five odd numbers are now the first five elements in the vector, but the vector still has a size of 10. The last five elements appear to be unchanged. Why is that?

🔗

The remove and remove_if algorithms do not actually change the size of the collection. Instead, they rearrange the elements so that the elements to be kept are at the front of the collection, and return an iterator to the new logical end of the collection. The elements beyond that point are left in an unspecified state (there are no guarantees about their values).

🔗

This behavior feels odd in a vector, but it means that the algorithm can work with containers that do not support resizing, such as arrays. It also allows for more efficient implementations since resizing a container can be expensive. Better to do the rearrangement and let the caller decide if whey want to resize the container.

🔗

To actually remove the unwanted elements from a vector, we need to call the vector’s .erase() method, passing it the iterator returned by remove_if to specify the new end of the vector. Here is how we would modify the program to do that:

🔗

Listing 21.12.3.

🔗

Subsection 21.12.3 Transform

The transform algorithm applies a function to each element in a source range and stores the result in a destination range. We might use transform to turn a list of strings like {"one", "two", "three"} into a list of their lengths like {3, 3, 5}. Or we could transform them into uppercase versions of the strings like {"ONE", "TWO", "THREE"}.

🔗

The prototype for transform looks like this:

🔗

transform( InputIt first, InputIt last, OutputIt d_first, UnaryOperation unary_op );

It takes four parameters: the first three are iterators just like copy uses. The fourth is a unary operation (a function or functor that takes one argument) to apply to each element.

🔗

Here is an example that transforms a vector of strings into a vector of their lengths:

🔗

Listing 21.12.4.

🔗

Checkpoint 21.12.1.

copy(orig.begin(), orig.end, destination.begin()) requires what to be true about the destination?

🔗

It must already have enough space to hold all the copied elements.
It must be capable of growing to have enough space to hold all the copied elements.
It must be empty.
It must not be declared yet.

🔗

Checkpoint 21.12.2.

remove_if returns an iterator to the new end of the range after removing elements. erase can take either one or two iterators as parameters. If you give it just one parameter, it erases all elements from that iterator to the end of the container.

🔗

Arrange blocks to remove all negative numbers from a vector v and immediately use the iterator returned by remove_if as the parameter to erase to delete the unwanted elements.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next