11-修改式序列操作

G.5.2　修改式序列操作

表G.14对修改式序列操作进行了总结。其中没有列出参数，而重载函数也只列出了一次。表后做了更详细的说明，其中包括原型。因此，可以浏览该表，以了解函数的功能，如果对某个函数非常感兴趣，则可以了解其细节。

表G.14修改式序列操作

| 函数 | 描述 | | :----- | :----- | :----- | :----- | | copy() | 将一个区间中的元素复制到迭代器指定的位置 | | copy_n() | 从一个迭代器指定的地方复制n个元素到另一个迭代器指定的地方，这是C++11新增的 | | copy_if() | 将一个区间中满足谓词测试的元素复制到迭代器指定的地方，这是C++11新增的 | | copy_backward() | 将一个区间中的元素复制到迭代器指定的地方。复制时从区间结尾开始，由后向前进行 | | move() | 将一个区间中的元素移到迭代器指定的地方，这是C++11新增的 | | move_backward() | 将一个区间中的元素移到迭代器指定的地方；移动时从区间结尾开始，由后向前进行。这是C++11新增的 | | swap() | 交换引用指定的位置中存储的值 | | swap_ranges() | 对两个区间中对应的值进行交换 | | iter_swap() | 交换迭代器指定的位置中存储的值 | | transform() | 将函数对象用于区间中的每一个元素（或区间对中的每对元素），并将返回的值复制到另一个区间的相应位置 | | replace() | 用另外一个值替换区间中某个值的每个实例 | | replace_if() | 如果用于原始值的谓词函数对象返回true，则使用另一个值来替换区间中某个值的所有实例 | | replace_copy() | 将一个区间复制到另一个区间中，使用另外一个值替换指定值的每个实例 | | replace_copy_if() | 将一个区间复制到另一个区间，使用指定值替换谓词函数对象为true的每个值 | | fill() | 将区间中的每一个值设置为指定的值 | | fill_n() | 将n个连续元素设置为一个值 | | generate() | 将区间中的每个值设置为生成器的返回值，生成器是一个不接受任何参数的函数对象 | | generate_n() | 将区间中的前n个值设置为生成器的返回值，生成器是一个不接受任何参数的函数对象 | | remove() | 删除区间中指定值的所有实例，并返回一个迭代器，该迭代器指向得到的区间的超尾 | | remove_if() | 将谓词对象返回true的值从区间中删除，并返回一个迭代器，该迭代器指向得到的区间的超尾 | | remove_copy() | 将一个区间中的元素复制到另一个区间中，复制时忽略与指定值相同的元素 | | remove_copy_if() | 将一个区间中的元素复制到另一个区间中，复制时忽略谓词函数对象返回true的元素 | | unique() | 将区间内两个或多个相同元素组成的序列压缩为一个元素 | | unique_copy() | 将一个区间中的元素复制到另一个区间中，并将两个或多个相同元素组成的序列压缩为一个元素 | | reverse() | 反转区间中的元素的排列顺序 | | reverse_copy() | 按相反的顺序将一个区间中的元素复制到另一个区间中 | | rotate() | 将区间中的元素循环排列，并将元素左转 | | rotate_copy() | 以旋转顺序将区间中的元素复制到另一个区间中 | | random_shuffle() | 随机重新排列区间中的元素 | | shuffle() | 随机重新排列区间中的元素，使用的函数对象满足C++11对统一随机生成器的要求 | | is_partitioned() | 如果区间根据指定的谓词进行了分区，则返回true | | partition() | 将满足谓词函数对象的所有元素都放在不满足谓词函数对象的元素之前 | | stable_partition() | 将满足谓词函数对象的所有元素放置在不满足谓词函数对象的元素之前，每组中元素的相对顺序保持不变 | | partition_copy() | 将满足谓词函数对象的所有元素都复制到一个输出区间中，并将其他元素都复制到另一个输出区间中，这是C++11新增的 | | partition_point() | 对于根据指定谓词进行了分区的区间，返回一个迭代器，该迭代器指向第一个不满足该谓词的元素 |

下面详细地介绍这些修改型序列操作。对于每个函数，首先列出其原型，然后做简要的描述。正如前面介绍的，迭代器对指出了区间，而选择的模板参数名指出了迭代器的类型。通常，[first, last]区间指的是从first到last（不包括last）。作为参数传递的函数是函数对象，这些函数对象可以是指针，也可以是定义了()操作的对象。正如第16章介绍的，谓词是接受一个参数的布尔函数，二元谓词是接受两个参数的布尔函数（函数可以不是bool类型，只要它对于false返回0，对于true返回非0值）。另外，正如第16章介绍的，一元函数对象接受一个参数，而二元函数对象接受两个参数。

1．copy()

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

copy()函数将[first, last)区间中的元素复制到区间[result, result + (last – first))中，并返回result + (last – first)，即指向被复制到的最后一个位置后面的迭代器。该函数要求result不位于[first, last)区间中，也就是说，目标不能与源重叠。

2．copy_n()（C++11）

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

函数copy_n()从位置first开始复制n个元素到区间[result, result + n] 中，并返回result + n，即指向被复制到的最后一个位置后面的迭代器。该函数不要求目标和源不重叠。

3．copy_if()（C++11）

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

函数copy_if()将[first, last)区间中满足谓词pred的元素复制到区间[result, result + (last – first))中，并返回result + (last – first)，即指向被复制到的最后一个位置后面的迭代器。该函数要求result不位于[first, last)区间中，也就是说，目标不能与源重叠。

4．copy_backward()

template<class BidirectionalIterator1,
         class BidirectionalIterator2>
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first,
BidirectionalIterator1 last, BidirectionalIterator2 result);

函数copy_backward()将[first, last)区间中的元素复制到区间[result - (last - first), result)中。复制从last - 1开始，该元素被复制到位置result - 1，然后由后向前处理，直到first。该函数返回result - (last - first)，即指向被复制到的最后一个位置后面的迭代器。该函数要求result不位于[first, last)区间中。然而，由于复制是从后向前进行的，因此目标和源可能重叠。

5．move()（C++11）

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

函数move()使用std::move()将[first, last)区间中的元素移到区间[result, result + (last – first))中，并返回result + (last – first)，即指向被复制到的最后一个位置后面的迭代器。该函数要求result不位于[first, last)区间中，也就是说，目标不能与源重叠。

6．move_backward()（C++11）

template<class BidirectionalIterator1,
         class BidirectionalIterator2>
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first,
BidirectionalIterator1 last, BidirectionalIterator2 result);

函数move_backward() std::move()将[first, last)区间中的元素移到区间[result - (last - first), result)中。复制从last - 1开始，该元素被复制到位置result - 1，然后由后向前处理，直到first。该函数返回result - (last - first)，即指向被复制到的最后一个位置后面的迭代器。该函数要求result不位于[first, last)区间中。然而，由于复制是从后向前进行的，因此目标和源可能重叠。

7．swap()

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

swap()函数对引用指定的两个位置中存储的值进行交换（C++11将这个函数移到了头文件utility中）。

8．swap_ranges()

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

swap_ranges()函数将[first1, last1]区间中的值与从first2开始的区间中对应的值交换。这两个区间不能重叠。

9．iter_swap()

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

iter_swap()函数将迭代器指定的两个位置中存储的值进行交换。

10．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);

第一个版本的transform()将一元函数对象op应用到[first, last)区间中每个元素，并将返回值赋给从result开始的区间中对应的元素。因此，result被设置为op(first)，依此类推。该函数返回result + (last - first)，即目标区间的超尾值。

第二个版本的transform()将二元函数对象op应用到[first1, last1)区间和[first2, last2)区间中的每个元素，并将返回值赋给从result开始的区间中对应的元素。因此，result被设置成op(first1, *first2)，依此类推。该函数返回result + (last – first)，即目标区间的超尾值。

11．replace()

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

replace()函数将[first, last]中的所有old_value替换为new_value。

12．replace_if()

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

replace_if()函数使用new_value值替换[first, last]区间中pred（old）为true的每个old值。

13．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);

replace_copy()函数将[first, last]区间中的元素复制到从result开始的区间中，但它使用new_value代替所有的old_value。该函数返回result + (last - first)，即目标区间的超尾值。

14．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);

replace_copy_if()函数将[first, last]区间中的元素复制到从result开始的区间中，但它使用new_value代替pred(old)为true的所有old值。该函数返回result + (last - first)，即目标区间的超尾值。

15．fill()

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

fill()函数将[first, last]区间中的每个元素都设置为value。

16．fill_n()

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

fill_n()函数将从first位置开始的前n个元素都设置为value。

17．generate()

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

generate()函数将[first, last)区间中的每个元素都设置为gen()，其中gen是一个生成器函数对象，即不接受任何参数。例如，gen可以是一个指向rand()的指针。

18．generate_n()

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

generate_n()函数将从first开始的区间中前n个元素都设置为gen()，其中，gen是一个生成器函数对象，即不接受任何参数。例如，gen可以是一个指向rand()的指针。

19．remove()

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

remove()函数删除[first, last)区间中所有值为value的元素，并返回得到的区间的超尾迭代器。该函数是稳定的，这意味着未删除的元素的顺序将保持不变。

注意： 由于所有的remove()和unique()函数都不是成员函数，同时这些函数并非只能用于STL容器，因此它们不能重新设置容器的长度。相反，它们返回一个指示新超尾位置的迭代器。通常，被删除的元素只是被移到容器尾部。然而，对于STL容器，可以使用返回的迭代器和erase()方法来重新设置end()。

20．remove_if()

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

remove_if()函数将pred(val)为true的所有val值从[first, last)区间删除，并返回得到的区间的超尾迭代器。该函数是稳定的，这意味着未删除的元素的顺序将保持不变。

21．remove_copy()

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

remove_copy()函数将[first, last)区间中的值复制到从result开始的区间中，复制时将忽略value。该函数返回得到的区间的超尾迭代器。该函数是稳定的，这意味着没有被删除的元素的顺序将保持不变。

22．remove_copy_if()

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

remove_copy_if()函数将[first, last)区间中的值复制到从result开始的区间，但复制时忽略pred(val)为true的val。该函数返回得到的区间的超尾迭代器。该函数是稳定的，这意味着没有删除的元素的顺序将保持不变。

23．unique()

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

unique()函数将[first, last)区间中由两个或更多相同元素构成的序列压缩为一个元素，并返回新区间的超尾迭代器。第一个版本使用值类型的= =运算符对元素进行比较；第二个版本使用二元谓词函数对象pred来比较元素。也就是说，如果pred(it1, it2)为true，则it1和it2指向的元素是匹配的。

24．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);

unique_copy()函数将[first, last)区间中的元素复制到从result开始的区间中，并将由两个或更多个相同元素组成的序列压缩为一个元素。该函数返回新区间的超尾迭代器。第一个版本使用值类型的= =运算符，对元素进行比较；第二个版本使用二元谓词函数对象pred来比较元素。也就是说，如果pred(it1, it2)为true，则it1和it2指向的元素是匹配的。

25．reverse()

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

reverse()函数通过调用swap(first, last - 1)等来反转[first, last]区间中的元素。

26．reverse_copy

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

reverse_copy()函数按相反的顺序将[first, last)区间中的元素复制到从result开始的区间中。这两个区间不能重叠。

27．rotate()

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

rotate()函数将[first, last)区间中的元素左旋。middle处的元素被移到first处，middle + 1处的元素被移到first + 1处，依此类推。middle前的元素绕回到容器尾部，以便first处的元素可以紧接着last - 1处的元素。

28．rotate_copy()

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

rotate_copy()函数使用为rotate()函数描述的旋转序列，将[first, last)区间中的元素复制到从result开始的区间中。

29．random_shuffle()

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

这个版本的random_shuffle()函数将[first, last)区间中的元素打乱。分布是一致的，即原始顺序的每种可能排列方式出现的概率相同。

30．random_shuffle()

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

这个版本的random_shuffle()函数将[first, last)区间中的元素打乱。函数对象random确定分布。假设有n个元素，表达式random(n)将返回[0, n)区间中的一个值。在C++98中，参数random是一个左值引用，而在C++11中是一个右值引用。

31．shuffle()

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

函数shuffle()将[first, last)区间中的元素打乱。函数对象rgen确定分布，它应满足C++11指定的有关均匀随机数生成器的要求。假设有n个元素，表达式rgen(n)将返回[0, n]区间中的一个值。

32．is_partitioned()（C++11）

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

如果区间为空或根据pred进行了分区（即满足谓词pred的元素都在不满足该谓词的元素前面），函数is__partitioned()将返回true，否则返回false。

33．partition()

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

函数partition()将其值val使得pred(val)为true的元素都放在不满足该测试条件的所有元素之前。这个函数返回一个迭代器，指向最后一个使得谓词对象函数为true的值的后面。

34．stable_partition()

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

函数stable_partition()将其值val使得pred(val)为true的元素都放在不满足该测试条件的所有元素之前；在这两组中，元素的相对顺序保持不变。这个函数返回一个迭代器，指向最后一个使得谓词对象函数为true的值的后面。

35．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);

函数partition_copy()将所有这样的元素都复制到从out_true开始的区间中，即其值val使得pred(val)为true；并将其他的元素都复制到从out_false开始的区间中。它返回一个pair对象，该对象包含两个迭代器，分别指向从out_true和out_false开始的区间的末尾。

36．partition_point()（C++11）

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

函数partition_point()要求区间根据pred进行了分区。它返回一个迭代器，指向最后一个让谓词对象函数为true的值所在的位置。