ilyachalov (ilyachalov) wrote,
ilyachalov
ilyachalov

Category:

C++: алгоритм copy() на одном контейнере STL

В учебнике Лафоре в упражнении 8 к 15-й главе (глава называется «Стандартная библиотека шаблонов (STL)») требуется написать программу, которая копирует указанную последовательность элементов в массиве (или контейнере STL) из исходного места в другое место того же массива (или контейнера STL) с помощью алгоритма copy.

В конце задания сказано следующее, цитата из оригинала (стр. 798):

Use the program to verify that you can shift a sequence that overlaps its destination to the left, but not to the right. (For example, you can shift several items from 10 to 9, but not from 10 to 11.) This is because copy() starts with the leftmost element.

Переведу на русский:

Используйте эту программу, чтобы удостовериться, что вы можете передвинуть последовательность элементов (при наложении места назначения на исходное место последовательности) влево, но не вправо. (Например, вы можете передвинуть последовательность элементов, начинающуюся с 10-го элемента, влево на один элемент, к 9-му элементу, но не вправо на один элемент, к 11-му элементу.) Причина этого в том, что алгоритм copy начинает копирование с самого левого элемента последовательности.


Если место назначения и исходное место при копировании не пересекаются, проблемы не возникает. Вот как это выглядит на рисунке:


Здесь показан массив из 20 элементов. Значение элемента совпадает с его индексом (так получается более наглядно). Индексы изображены мелким шрифтом серого цвета. Исходная последовательность — элементы с индексами 10, 11, 12, 13.

Пусть место назначения и исходное место при копировании пересекаются. Копируем ту же исходную последовательность {10, 11, 12, 13} в место назначения, начинающееся с элемента с индексом 9 (то есть передвигаем исходную последовательность влево на один элемент). В программе эта операция выполняется одним выражением, вызывающим алгоритм копирования, но мы посмотрим, как копирование выполняется поэлементно:


Тоже никаких проблем не возникает.

Пусть место назначения и исходное место при копировании пересекаются. Но теперь пробуем копировать исходную последовательность {10, 11, 12, 13} в место назначения, начинающееся с элемента с индексом 11 (то есть передвигаем исходную последовательность вправо на один элемент). Опять рассматриваем копирование поэлементно. Что может пойти не так?


Как видно из рисунка, проблемы начались уже на втором шаге копирования. Из-за того, что копирование первого элемента последовательности затёрло значение второго элемента последовательности до момента, как второй элемент последовательности успели скопировать, с каждым шагом копируется только значение первого элемента. То есть при поэлементном копировании (сдвиге) исходной последовательности вправо, если место назначения накладывается на исходное место последовательности, выполнить копирование корректно не получится (часть последовательности будет потеряна).

Однако, Лафоре не совсем прав в своих ожиданиях! В справочнике по стандарту C++ про алгоритм copy сказано следующее, цитата:

Copies all elements in the range [first, last) starting from first and proceeding to last – 1. The behavior is undefined if d_first is within the range [first, last). In this case, std::copy_backward may be used instead.

(источник: https://en.cppreference.com/w/cpp/algorithm/copy)

В случае копирования (сдвига) вправо, если место назначения последовательности накладывается на исходное место в одном и том же контейнере, поведение алгоритма стандартом не определено. Другими словами, отдано на откуп конкретной реализации.

С чем я и столкнулся. В моей среде разработки «Visual Studio Community 2017» и операционной системе «Windows 7» алгоритм copy работает корректно и в указанном выше случае при сдвиге вправо.

Полный текст программы по указанному упражнению можно посмотреть тут.

Результат работы программы в рассматриваемом выше случае с копированием (сдвигом) последовательности вправо на один элемент:

Tags: Образование, Программирование
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments