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

#cpp #алгоритм

Не смог найти пример, когда удобнее использовать   std::copy_backward вместо   std::reverse_copy.
 И чем же  существование второго не заставляет забывать о первом?   Можете привести
такой пример(любой)?
    

Ответы

Ответ 1

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

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

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

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

#include 
#include 

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 
#include 
#include 

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
constexpr BidirectionalIterator2 copy_backward( BidirectionalIterator1 first, 
                                                BidirectionalIterator1 last,
                                                BidirectionalIterator2 result );


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

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

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


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

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

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

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

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

#include 
#include 
#include 

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.


Ответ 2

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

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

Например:

std::vector mas1 = {1, 2, 3, 4, 5};
std::vector mas2(8, 0);
std::vector 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}