Стандартные алгоритмы std::copy_backward и std::reverse_copy

Фактически, стандартные алгоритмы std::copy и std::copy_backward логически тесно связаны со стандартными строковыми C-функциями strcpy и memmove.

Первая строковая функция strcpy не допускает пересечения исходного диапазон и диапазона, куда происходит копирование.

Вторая строковая функция memmove позволяет работать с пересекающимися диапазонами.

Рассмотрите следующую демонстрационную C-программу.

#include <stdio.h>
#include <string.h>
int main( void ) 
{
    enum { N = 10 };
    char s[N] = "12344321";
    puts( s );
    memmove( s + 5, s + 4, 4 );
    s[4] = '5';
    puts( s );
    return 0;
}

Ее вывод на консоль

12344321
123454321

То есть чтобы вставить цифру 5 в середину строки, необходимо переместить вторую половину исходной строки на одну позицию вправо.

В этой программе нельзя заменить вызов memmove на вызов strcpy,

Как ту же самую операцию выполнить с помощью стандартных алгоритмов?

Соответствующая программа, к примеру, может выглядеть следующим образом.

#include <iostream>
#include <iterator>
#include <algorithm>
int main() 
{
    const size_t N = 10;
    char s[N] = "12344321";
    std::cout << s << '\n';
    std::copy_backward( std::next( s, 4 ), std::next( s, 8 ), std::next( s, 9 ) );
    s[4] = '5';
    std::cout << s << '\n';
    return 0;
}

Ее вывод на консоль будет таким же, как показано выше

12344321
123453321

Хотя указатели являются частными случаями итераторов произвольного доступа, но чтобы использовать приведенные программы, достаточно, чтобы указатели поддерживали пост-декрементную операцию --. То есть достаточно иметь двунаправленные итераторы.

И,действительно, алгоритм std::copy_backward определяется как

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

Это означает, что алгоритм может применяться к последовательностям, которые имеют двусторонние итераторы. Например, стандартный класс std::forward_list имеет лишь последовательные итераторы. А это означает, что вы не можете использовать алгоритм std::copy_backward с объектами этого шаблонного класса.

С другой стороны, алгоритм std::reverse_copy определяется как

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

Как видно из объявления алгоритма, второй шаблонный параметр допускает входной итератор. Поэтому, опять-таки, если используемый шаблонный аргумент для второго шаблонного параметра не является в то же время двусторонним итератором, то этот алгоритм нельзя будет использовать вместо алгоритма std::copy_backward, так как второй итератор этого алгоритма должен быть двусторонним для пересекающихся диапазонов (как это будет видно из представленной ниже демонстрационной программы).

Теперь допустим, что имеется контейнер, как, например, обычный массив, который имеет двусторонние итераторы (на самом деле указатели, которые используются в качестве итераторов для массивов, являются итераторами произвольного доступа).

Как можно было бы заменить вызов алгоритма std::copy_backward на вызов алгоритма std::copy_reverse?

Сделать это очень просто!

Ниже показана соответствующая демонстрационная программа.

#include <iostream>
#include <iterator>
#include <algorithm>
int main() 
{
    const size_t N = 10;
    int a[N] = { 1, 2, 3, 4, 4, 3, 2, 1 };
    int b[N] = { 1, 2, 3, 4, 4, 3, 2, 1 };
    for ( const int *p = a; *p; ++p ) std::cout << *p << ' ';
    std::cout << '\n';
    for ( const int *p = b; *p; ++p ) std::cout << *p << ' ';
    std::cout << '\n';
    std::copy_backward( std::next( a, 4 ), 
                        std::next( a, 8 ), 
                        std::next( a, 9 ) );
    a[4] = 5;
    std::reverse_copy( std::next( b, 4 ),
                       std::next( b, 8 ), 
                       std::reverse_iterator( std::next( b, 9 ) ) );
    b[4] = 5;
    std::cout << '\n';
    for ( const int *p = a; *p; ++p ) std::cout << *p << ' ';
    std::cout << '\n';
    for ( const int *p = b; *p; ++p ) std::cout << *p << ' ';
    std::cout << '\n';
}    

Вывод этой программы на консоль

1 2 3 4 4 3 2 1 
1 2 3 4 4 3 2 1 
1 2 3 4 5 4 3 2 1 
1 2 3 4 5 4 3 2 1 

Однако, вышеприведенная программа некорректная! В требованиях к алгоритму std::reverse_copy указывается, что

4 Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.

То есть этот алгоритм, как и стандартная C-функция strcpy (и как стандартный алгоритм std::copy) не допускает пересечение диапазонов.

А, следовательно, не всегда алгоритм std::copy_backward можно заменить на алгоритм std::copy_reverse.

Эти две функции делают разные вещи.

std::copy_backward не меняет порядок элементов в диапазоне, а std::reverse_copy меняет. Кроме того, один копирует в конец целевого диапазона, а другой в начало.

Например:

std::vector<int> mas1 = {1, 2, 3, 4, 5};
std::vector<int> mas2(8, 0);
std::vector<int> mas3(8, 0);
std::copy_backward(mas1.begin(), mas1.end(), mas2.end()); 
std::reverse_copy(mas1.begin(), mas1.end(), mas3.begin()); 
// mas2 = {0, 0, 0, 1, 2, 3, 4, 5}
// mas3 = {5, 4, 3, 2, 1, 0, 0, 0}