Генераторы, копирования и перемещения (серия «114 алгоритмов C++»)

Добро пожаловать в шестую часть серии «114 алгоритмов C++». Сегодня мы поговорим об алгоритмах, генерирующих значения, и множестве вариантов копирования, предлагаемых стандартной библиотекой.

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

iota

iota выделяется, когда речь заходит о поддержке std::ranges в C++20. C++20 представил версию std::views::iota с ленивым представлением, а в C++23 мы получим только версию алгоритма с нетерпеливым диапазоном.

Алгоритм std::iota будет генерировать элементы, последовательно применяя оператор приращения префикса, начиная с начального значения.

std::vector<int> data(11, 0);

std::iota(data.begin(), data.end(), -5); 
// data == { -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5 }

std::vector<int> out;
std::ranges::transform(std::views::iota(1, 10), std::views::iota(5), 
                       std::back_inserter(out), std::plus<>{});
// out == { 6, 8, 10, 12, 14, 16, 18, 20, 22 }

Здесь мы используем конструктор конечного представления std::views::iota(1,10), чтобы установить размер вывода (строка 7), что позволяет нам использовать бесконечное представление std::views::iota(5) в качестве второго параметра. Функционально мы могли бы заменить даже второе представление на конечное. Однако это потребовало бы дополнительной (и ненужной) проверки границ.

fill, fill_n, generate, generate_n

Алгоритм std::fill заполняет указанный диапазон предоставленным значением, а std::generate заполняет указанный диапазон значениями, полученными в результате последовательных вызовов предоставленного вызываемого объекта.

std::vector<int> data(5, 0);
std::fill(data.begin(), data.end(), 11);
// data == (11, 11, 11, 11, 11)

std::ranges::generate(data, []() { return 5; });
// data == (5, 5, 5, 5, 5)

// iota-подобный вариант
std::ranges::generate(data, [i = 0]() mutable { return i++; });
// data == (0, 1, 2, 3, 4)

iota-подобное поведение (строка 9) возможно, потому что стандарт гарантирует последовательные (слева направо) вызовы предоставленного вызываемого объекта.

При работе с диапазонами, которые не поддерживают произвольный доступ, предоставление конечного итератора диапазона может быть медленным или невозможным. Стандарт предлагает варианты fill и generate, в которых диапазон указывается с использованием начального итератора и количества элементов для покрытия заданного случая.

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

std::vector<int> data;
std::fill_n(std::back_inserter(data), 5, 11);
// data == (11, 11, 11, 11, 11)

data.clear();
std::ranges::generate_n(std::back_inserter(data), 5, []() { return 5; });
// data == (5, 5, 5, 5, 5)

Адаптеры итераторов

Мы уже много раз использовали std::back_inserter в примерах из этой серии, поэтому давайте начнем с адаптеров для вставки.

back_inserter, front_inserter, inserter

Стандарт предлагает три адаптера, которые создают экземпляры back_insert_iterator, front_insert_iterator и insert_iterator. При присваивании эти итераторы вызывают для адаптированного контейнера соответствующие методы push_back, push_front и insert.

std::list<int> data;
auto back = std::back_inserter(data);
auto front = std::front_inserter(data);

*back = 10;
// data == { 10 }
*front = 20;
// data == { 20, 10 }

auto mid = std::inserter(data, std::next(data.begin()));
*mid = 5;
// data == { 20, 5, 10 }

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

istream_iterator, ostream_iterator

Эти два адаптера обеспечивают итерацию по istream и ostream соответственно.

istream_iterator будет считывать значение, вызывая соответствующий operator>> при инкременте.

std::stringstream input("10 20 30 40 50");
auto in = std::istream_iterator<int>(input);

int i = *in; // i == 10
++in;
int j = *in; // j == 20

ostream_iterator запишет значение, вызвав соответствующий operator<< при присваивании.

std::stringstream output;
auto out = std::ostream_iterator<int>(output, ", ");

*out = 10;
*out = 20;
// output == "10, 20,"

Дополнительный параметр для ostream_iterator указывает разделитель, добавляемый после каждого элемента.

istream_iterator моделирует входной итератор, а ostream_iterator моделирует выходной итератор.

move_iterator, make_move_iterator

Адаптер move_iterator наследует категорию итератора от адаптированного итератора, но будет возвращать rvalue при разыменовании, что позволяет использовать семантику перемещения.

std::vector<std::string> data = { "a", "b", "c" };
auto it = std::make_move_iterator(data.begin());

std::string str(*it); // конструктор перемещения
++it;
str = *it; // присваивание перемещением
// data == { ?, ?, "c" }
// str == "b"

reverse_iterator

Мы можем использовать адаптер reverse_iterator для двунаправленных итераторов, чтобы получить итератор для противоположного направления.

std::vector<int> data = { 1, 2, 3 };
auto mid = std::reverse_iterator(data.end());

int i = *mid; // i == 3
++mid;
int j = *mid; // j == 2

Обратите внимание, что обратный итератор сопоставляется с предыдущим элементом в исходном направлении. Следовательно, при реверсировании begin или rbegin результатом будет соответственно rend и end.

counted_iterator

При работе с диапазонами без произвольного доступа удобно указывать диапазон с помощью итератора begin и количества элементов. counted_iterator переносит этот функционал в диапазоны C++20 без необходимости использования специализированных вариантов алгоритмов, таких как std::fill_n.

std::list<int> data = { 1, 2, 3, 4, 5 };

std::ranges::fill(std::counted_iterator(data.begin(), 3), std::default_sentinel, 9);
// data == { 9, 9, 9, 4, 5 }

counted_iterator отслеживает количество элементов, и когда счетчик достигает нуля, counted_iterator будет сравниваться с равным std::default_sentinel, обозначая конец диапазона.

copy, move, copy_backwards, move_backwards

При копировании/перемещении диапазона нам необходимо избегать перезаписи еще не скопированных/перемещенных элементов из исходного диапазона. Стандарт предлагает два направления копирования, чтобы предотвратить эту проблему. Начнем с прямой версии:

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

std::vector<std::string> data{ "a", "b", "c", "d", "e", "f"};

std::copy(data.begin(), data.begin()+3, data.begin()+3);
// data = { "a", "b", "c", "a", "b", "c" }

// случай с перекрытием:
std::copy(std::next(data.begin()), data.end(), data.begin());
// data = { "b", "c", "a", "b", "c", "c" }

move работает точно так же, за исключением того, что он приводит каждый элемент перед присваиванием к rvalue, превращая копирования в перемещения.

std::vector<std::string> data{ "a", "b", "c", "d", "e", "f"};

std::move(data.begin(), data.begin()+3, data.begin()+3);
// data = { ?, ?, ?, "a", "b", "c" }

Примечательно, что перемещение std::move зависит от типа базового элемента. Если базовый тип предназначен только для копирования, std::move будет вести себя идентично std::copy.

struct CopyOnly {
    CopyOnly() = default;
    CopyOnly(const CopyOnly&) = default;
    CopyOnly& operator=(const CopyOnly&) { 
      std::cout << "Copy assignment.\n";
      return *this;
    };
};

std::vector<CopyOnly> test(6);

std::move(test.begin(), test.begin()+3, test.begin()+3);
// 3-кратное копирующее присваивание

Мы также можем эмулировать std::move, используя упомянутый ранее адаптер move_iterator.

std::vector<std::string> data{ "a", "b", "c", "d", "e", "f"};

std::copy(std::make_move_iterator(data.begin()), std::make_move_iterator(data.begin()+3), 
          data.begin()+3);
// data = { ?, ?, ?, "a", "b", "c" }

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

Выходной итератор не может находиться в пределах (first, last] и будет рассматриваться как конечный итератор для целевого диапазона, что означает, что алгоритм запишет первое значение в std::prev(end).

std::vector<std::string> data{ "a", "b", "c", "d", "e", "f"};

std::vector<std::string> out(9, "");
std::copy_backward(data.begin(), data.end(), out.end());
// "", "", "", "a", "b", "c", "d", "e", "f"

std::copy_backward(data.begin(), std::prev(data.end()), data.end());
// data = { "a", "a", "b", "c", "d", "e" }

Подобно fill_n и generate_n, стандарт также предоставляет вариант copy_n, подходящий для диапазонов без произвольного доступа.

Этот алгоритм не может проверить, корректен ли запрошенный счетчик и не выходит ли он за пределы, поэтому эта нагрузка ложится на вызывающего.

std::list<int> data{1, 2, 3, 4, 5, 6, 7, 8, 9};
std::vector<int> out;

std::copy_n(data.begin(), 5, std::back_inserter(out));
// out == { 1, 2, 3, 4, 5 }

copy_if, remove_copy, remove_copy_if

Когда нам нужно выбрать для копирования только некоторые элементы, мы можем использовать copy_if или remove_copy_if.

Эти два алгоритма обеспечивают одинаковую логику с противоположной семантикой: copy_if копирует элементы, для которых предикат возвращает true, а remove_copy_if копирует элементы, для которых предикат возвращает false. Наконец, remove_copy копирует элементы, не соответствующие предоставленному значению.

std::vector<int> data{ 1, 2, 3, 4, 5, 6, 7, 8, 9};
std::vector<int> even, odd, no_five;

auto is_even = [](int v) { return v % 2 == 0; };

std::ranges::copy_if(data, std::back_inserter(even), is_even);
// even == { 2, 4, 6, 8 }

std::ranges::remove_copy_if(data, std::back_inserter(odd), is_even);
// odd == { 1, 3, 5, 7, 9 }

std::ranges::remove_copy(data, std::back_inserter(no_five), 5);
// no_five == { 1, 2, 3, 4, 6, 7, 8, 9 }

sample

Другой вариант выборочного копирования – алгоритм sample.

Алгоритм sample скопирует случайную выборку из N элементов из исходного диапазона в целевой диапазон, используя предоставленный генератор случайных чисел.

std::vector<int> data{1, 2, 3, 4, 5, 6, 7, 8, 9};
std::vector<int> out;

std::sample(data.begin(), data.end(), std::back_inserter(out),
            5, std::mt19937{std::random_device{}()});
// e.g. out == {2, 3, 4, 5, 9}
// (гарантированно по возрастанию, потому что
// исходный диапазон идет по возрастанию)

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

Для этой функции требуется, чтобы либо входной диапазон был как минимум однонаправленным диапазоном, либо целевой диапазон должен быть диапазоном с произвольным доступом.

replace_copy, replace_copy_if

Мы обсуждали алгоритм replace в предыдущей статье данной серии. Вариации для copy работают аналогично, заменяя значения, соответствующие предикату или предоставленному значению. Однако результат выводится в целевой диапазон вместо замены, примененной на месте.

Вариант replace_copy_if заменяет элементы, для которых предикат возвращает значение true. replace_copy заменяет элементы, соответствующие предоставленному значению.

std::vector<int> data{1, 2, 3, 4, 5, 6, 7, 8, 9};
std::vector<int> out, odd;

std::ranges::replace_copy(data, std::back_inserter(out), 5, 10);
// out == { 1, 2, 3, 4, 10, 6, 7, 8, 9 }

auto even = [](int v) { return v % 2 == 0; };
std::ranges::replace_copy_if(data, std::back_inserter(odd), even, -1);
// odd == { 1, -1, 3, -1, 5, -1, 7, -1, 9 }

reverse_copy, rotate_copy

Последние два алгоритма из категории копирования меняют порядок копируемых элементов.

Не путайте с copy_backwards, которая сохраняет исходный порядок элементов, reverse_copy изменит порядок копируемых элементов на противоположный.

std::vector<int> data{1, 2, 3, 4, 5, 6, 7, 8, 9};
std::vector<int> out;

std::ranges::reverse_copy(data, std::back_inserter(out));
// out == { 9, 8, 7, 6, 5, 4, 3, 2, 1 }

Следуя логике алгоритма поворота, rotate_copy сначала скопирует элементы, начиная с назначенного среднего элемента, а затем оставшиеся элементы с начала диапазона.

std::vector<int> data{1, 2, 3, 4, 5, 6, 7, 8, 9};
std::vector<int> out;

std::ranges::rotate_copy(data, data.begin()+4, std::back_inserter(out));
// out == { 5, 6, 7, 8, 9, 1, 2, 3, 4 }

Спасибо за чтение

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

Теги