Mutating Sequence Operations

Table G.14 summarizes the mutating sequence operations. Arguments are not shown, and overloaded functions are listed just once. A fuller description, including the prototypes, follows the table. Thus, you can scan the table to get an idea of what a function does and then look up the details if you find the function appealing.

Table G.14. Mutating Sequence Operations

Now let’s take a more detailed look at these mutating sequence operations. For each function, the discussion shows the prototype(s), followed by a brief explanation. As you saw earlier, pairs of iterators indicate ranges, with the chosen template parameter name indicating the type of iterator. As usual, a range in the form [first, last) goes from first up to, but not including, last. Functions passed as arguments are function objects, which can be function pointers or objects for which the () operation is defined. As in Chapter 16, a predicate is a Boolean function with one argument, and a binary predicate is a Boolean function with two arguments. (The functions need not be type bool, as long as they return 0 for false and a nonzero value for true.) Also as in Chapter 16, a unary function object is one that takes a single argument, and a binary function object is one that takes two arguments.

copy()

template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
                    OutputIterator result);

The copy() function copies the elements in the range [first, last) into the range [result, result + (last - first)). It returns result + (last - first)—that is, an iterator pointing one past the last copied-to location. The function requires that result not be in the range [first, last)—that is, the target can’t overlap the source.

copy_n() (C++11)

template<class InputIterator, class Size class OutputIterator>
OutputIterator copy(InputIterator first, Size n,
                    OutputIterator result);

The copy_n() function copies n elements, staring from the location first, into the range [result, result + n). It returns result + n—that is, an iterator pointing one past the last copied-to location. The function does not require that the target can’t overlap the source.

copy_if() (C++11)

template<class InputIterator, class OutputIterator,
         class Predicate>
OutputIterator copy_if(InputIterator first, InputIterator last,
        OutputIterator result, Predicate pred);

The copy_if() function copies those elements referred to by the iterator i in the range [first, last), for which pred(*i) is true, into the range [result, result + (last - first)). It returns result + (last - first)—that is, an iterator pointing one past the last copied-to location. The function requires that result not be in the range [first, last)—that is, the target can’t overlap the source.

copy_backward()

template<class BidirectionalIterator1,
         class BidirectionalIterator2>
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first,

BidirectionalIterator1 last, BidirectionalIterator2 result);

The copy_backward() function copies the elements in the range [first, last) into the range [result -(last - first), result). Copying begins with the element at last -1 being copied to location result - 1 and proceeds backward from there to first. It returns result - (last - first)—that is, an iterator pointing one past the last copied-to location. The function requires that result not be in the range [first, last). However, because copying is done backward, it is possible for the target and source to overlap.

move() (C++11)

template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
                    OutputIterator result);

The move() function uses std::move() to move the elements in the range [first, last) into the range [result, result + (last - first)). It returns result + (last - first)—that is, an iterator pointing one past the last copied-to location. The function requires that result not be in the range [first, last)—that is, the target can’t overlap the source.

move_backward() (C++11)

template<class BidirectionalIterator1,
         class BidirectionalIterator2>
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first,

BidirectionalIterator1 last, BidirectionalIterator2 result);

The move_backward() function uses std::move() to move the elements in the range [first, last) into the range [result -(last - first), result). Copying begins with the element at last -1 being copied to location result - 1 and proceeds backward from there to first. It returns result - (last - first)—that is, an iterator pointing one past the last copied-to location. The function requires that result not be in the range [first, last). However, because copying is done backward, it is possible for the target and source to overlap.

swap()

template<class T> void swap(T& a, T& b);

The swap() function exchanges values stored at two locations specified by references. (C++ moves this function to the utility header file.)

swap_ranges()

template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges(
                          ForwardIterator1 first1, ForwardIterator1 last1,
                          ForwardIterator2 first2);

The swap_ranges() function exchanges values in the range [first1, last1) with the corresponding values in the range beginning at first2. The two ranges should not overlap.

iter_swap()

template<class ForwardIterator1, class ForwardIterator2>
void iter_swap(ForwardIterator1 a, ForwardIterator2 b);

The iter_swap() function exchanges values stored at two locations specified by iterators.

transform()

template<class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator transform(InputIterator first, InputIterator last,
OutputIterator result, UnaryOperation op);
template<class InputIterator1, class InputIterator2, class OutputIterator,
         class BinaryOperation>
OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
                         InputIterator2 first2, OutputIterator result,
                         BinaryOperation binary_op);

The first version of transform() applies the unary function object op to each element in the range [first, last) and assigns the return value to the corresponding element in the range beginning at result. So *result is set to op(*first), and so on. It returns result + (last - first)—that is, the past-the-end value for the target range.

The second version of transform() applies the binary function object op to each element in the range [first1, last1) and to each element in the range [first2, last2) and assigns the return value to the corresponding element in the range beginning at result. So *result is set to op(*first1, *first2), and so on. It returns result + (last - first), the past-the-end value for the target range.

replace()

template<class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last,
             const T& old_value, const T& new_value);

The replace() function replaces each occurrence of the value old_value in the range [first, last) with the value new_value.

replace_if()

template<class ForwardIterator, class Predicate, class T>
void replace_if(ForwardIterator first, ForwardIterator last,
                Predicate pred, const T& new_value);

The replace()_if function replaces each value old in the range [first, last) for which pred(old) is true with the value new_value.

replace_copy()

template<class InputIterator, class OutputIterator, class T>
OutputIterator replace_copy(InputIterator first, InputIterator last,
     OutputIterator result,const T& old_ value, const T& new_ value);

The replace_copy() function copies the elements in the range [first, last) to a range beginning at result but substituting new_value for each occurrence of old_value. It returns result + (last - first), the past-the-end value for the target range.

replace_copy_if()

template<class Iterator, class OutputIterator, class Predicate, class T>
OutputIterator replace_copy_if(Iterator first, Iterator last,
    OutputIterator result, Predicate pred, const T& new_ value);

The replace_copy_if() function copies the elements in the range [first, last) to a range beginning at result but substituting new_value for each value old for which pred(old) is true. It returns result + (last - first), the past-the-end value for the target range.

fill()

template<class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, const T& value);

The fill() function sets each element in the range [first, last) to value.

fill_n()

template<class OutputIterator, class Size, class T>
void fill_n(OutputIterator first, Size n, const T& value);

The fill_n() function sets each of the first n elements beginning at location first to value.

generate()

template<class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last, Generator gen);

The generate() function sets each element in the range [first, last) to gen(), where gen is a generator function object—that is, one that takes no arguments. For example, gen can be a pointer to rand().

generate_n()

template<class OutputIterator, class Size, class Generator>
void generate_n(OutputIterator first, Size n, Generator gen);

The generate_n() function sets each of the first n elements in the range beginning at first to gen(), where gen is a generator function object—that is, one that takes no arguments. For example, gen can be a pointer to rand().

remove()

template<class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last,
                       const T& value);

The remove() function removes all occurrences of value from the range [first, last) and returns a past-the-end iterator for the resulting range. The function is stable, meaning that the order of the unremoved elements is unaltered.

remove_if()

template<class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
                          Predicate pred);

The remove_if() function removes all occurrences of values val for which pred(val) is true from the range [first, last) and returns a past-the-end iterator for the resulting range. The function is stable, meaning that the order of the unremoved elements is unaltered.

remove_copy()

template<class InputIterator, class OutputIterator, class T>
OutputIterator remove_copy(InputIterator first, InputIterator last,
                           OutputIterator result, const T& value);

The remove_copy() function copies values from the range [first, last) to the range beginning at result, skipping instances of value as it copies. It returns a past-the-end iterator for the resulting range. The function is stable, meaning that the order of the unremoved elements is unaltered.

remove_copy_if()

template<class InputIterator, class OutputIterator, class Predicate>
OutputIterator remove_copy_if(InputIterator first, InputIterator last,
                              OutputIterator result, Predicate pred);

The remove_copy_if() function copies values from the range [first, last) to the range beginning at result, skipping instances of val for which pred(val) is true as it copies. It returns a past-the-end iterator for the resulting range. The function is stable, meaning that the order of the unremoved elements is unaltered.

unique()

template<class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last);

template<class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ForwardIterator first, ForwardIterator last,
                       BinaryPredicate pred);

The unique() function reduces each sequence of two or more equivalent elements in the range [first, last) to a single element and returns a past-the-end iterator for the new range. The first version uses the == operator for the value type to compare elements. The second version uses the binary predicate function object pred to compare elements. That is, elements pointed to by it1 and it2 match if pred(*it1, *it2) is true.

unique_copy()

template<class InputIterator, class OutputIterator>
OutputIterator unique_copy(InputIterator first, InputIterator last,
                           OutputIterator result);

template<class InputIterator, class OutputIterator, class BinaryPredicate>
OutputIterator unique_copy(InputIterator first, InputIterator last,
                           OutputIterator result, BinaryPredicate pred);

The unique_copy() function copies elements from the range [first, last) to the range beginning at result, reducing each sequence of two or more identical elements to a single element. It returns a past-the-end iterator for the new range. The first version uses the == operator for the value type to compare elements. The second version uses the binary predicate function object pred to compare elements. That is, elements pointed to by it1 and it2 match if pred(*it1, *it2) is true.

reverse()

template<class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);

The reverse() function reverses the elements in the range [first, last) by invoking swap(first, last - 1), and so on.

reverse_copy()

template<class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy(BidirectionalIterator first,
                            BidirectionalIterator last,
                            OutputIterator result);

The reverse copy() function copies the elements in the range [first, last) to the range beginning at result in reverse order. The two ranges should not overlap.

rotate()

template<class ForwardIterator>
void rotate(ForwardIterator first, ForwardIterator middle,
            ForwardIterator last);

The rotate() function performs a left rotation on the elements in the range [first, last). The element at middle is moved to first, the element at middle + 1 is moved to first + 1, and so on. The elements preceding middle are wrapped around to the end of the container so that the element at first follows the element formerly at last - 1.

rotate_copy()

template<class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle,
                           ForwardIterator last, OutputIterator result);

The rotate_copy() function copies the elements in the range [first, last) to the range beginning at result, using the rotated sequence described for rotate().

random_shuffle()

template<class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);

This version of the random_shuffle() function shuffles the elements in the range [first, last). The distribution is uniform; that is, each possible permutation of the original order is equally likely.

random_shuffle()

template<class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
                    RandomNumberGenerator&& random);

This version of the random_shuffle() function shuffles the elements in the range [first, last). The function object random determines the distribution. Given n elements, the expression random(n) should return a value in the range [0,n). In C++98, the random argument was an lvalue reference; in C++11, it is an rvalue reference.

shuffle()

template<class RandomAccessIterator, class Uniform RandomNumberGenerator>
void shuffle(RandomAccessIterator first, RandomAccessIterator last,
                    UniformRandomNumberGenerator&& rgen);

This version of the random_shuffle() function shuffles the elements in the range [first, last). The type of the function object rgen should match the requirements of a uniform random number generator as defined in the C++11 standard. It (rgen) determines the distribution. Given n elements, the expression rgen(n) should return a value in the range [0,n).

is_partitioned() (C++11)

template<class InputIterator, class Predicate>
bool is_partitioned(InputIterator first,
                    InputIterator last, Predicate pred);

The is_partitioned() function returns true if the range is empty or if it is partitioned by pred—that is, arranged so that all elements satisfying pred precede all those that do not. Otherwise, the function returns false.

partition()

template<class BidirectionalIterator, class Predicate>
BidirectionalIterator partition(BidirectionalIterator first,
                                BidirectionalIterator last,
                                Predicate pred);

The partition() function places each element whose value val is such that pred(val) is true before all elements that don’t meet that test. It returns an iterator to the position following the last position holding a value for which the predicate object function was true.

stable_partition()

template<class BidirectionalIterator, class Predicate>
BidirectionalIterator stable_partition(BidirectionalIterator first,
                                       BidirectionalIterator last,
                                       Predicate pred);

The stable_partition() function places each element whose value val is such that pred(val) is true before all elements that don’t meet that test. This function preserves the relative ordering within each of the two groups. It returns an iterator to the position following the last position holding a value for which the predicate object function was true.

partition_copy() (C++11)

template<class InputIterator, class OutputIterator1,
         classs OutputIterator2, class Predicate>
pair<OutputIterator1, OutputIterator2> partition_copy(
     InputIterator first, InputIterator last,
     OutputIterator1 out_true, OutputIterator2 out_false
                                Predicate pred);

The partition_copy() function copies each element whose value val is such that pred(val) is true to the range beginning with out_true and the remaining elements to the range beginning with out_false. It returns a pair object containing an iterator to the end of the range that begins with out_true and an iterator to the end of the range that begins with out_false.

partition_point() (C++11)

template<class ForwardIterator, class Predicate>
ForewardIterator partition_point(ForwardIterator first,
                                 ForwardIterator last,
                                 Predicate pred);

The partition_point() function requires that the range be partitioned by pred. It returns an iterator to the position following the last position holding a value for which the predicate object function was true.