C++17 STL Стандартная библиотека шаблонов — страница 42 из 119

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

  auto shell_it (ostream_iterator>{cout,
                                                     ", "});
  copy(begin(m), end(m), shell_it);
  cout << '\n';

6. Опустошим ассоциативный массив, чтобы подготовить его к следующему эксперименту. В этот раз мы переместим в него все элементы вектора:

  m.clear();
  move(begin(v), end(v), inserter(m, begin(m)));

7. Теперь снова выведем на экран содержимое ассоциативного массива. Более того, поскольку алгоритм std::move изменяет еще и источник данных, выведем на экран и содержимое вектора. Таким образом, можно увидеть, что с ним произошло, когда он стал источником данных.

  copy(begin(m), end(m), shell_it);
  cout << '\n';
  copy(begin(v), end(v), shell_it);
  cout << '\n';
}

8. Скомпилируем программу, запустим ее и посмотрим на результат. Первые две строки выглядят просто. Они отражают содержимое ассоциативного массива после применения алгоритмов copy_n и move. Третья строка выглядит интереснее, поскольку в ней показывается, что строки вектора, который мы использовали в качестве источника данных, теперь пусты. Это произошло потому, что содержимое строк было не скопировано, а перемещено (т.е. ассоциативный массив применяет данные строк из кучи, на которые ссылались объекты строк, размещенные в векторе).

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

$ ./copying_items
(1, one), (2, two), (3, three),
(1, one), (2, two), (3, three), (4, four), (5, five),
(1, ), (2, ), (3, ), (4, ), (5, ),

Как это работает

Поскольку алгоритм std::copy является одним их самых простых алгоритмов STL, его реализация очень короткая. Взглянем на то, как его можно было бы реализовать:

template 
OutputIterator copy(InputIterator it, InputIterator end_it,
                    OutputIterator out_it)
{
  for (; it != end_it; ++it, ++out_it) {
    *out_it = *it;
  }
  return out_it;
}

Этот код выглядит как попытка вручную реализовать копирование элементов из одного итерабельного диапазона в другой. Кто-то может задаться вопросом: «Почему бы и не реализовать его вручную? Цикл выглядит достаточно просто, и мне даже не понадобится возвращаемое значение». Это, конечно, хороший вопрос.

Хотя алгоритм std::copy не самый лучший пример и не может продемонстрировать, как код становится короче, другие алгоритмы выглядят гораздо сложнее. Это может быть неочевидно, но для алгоритмов STL выполняется скрытая оптимизация. Если мы будем пользоваться алгоритмом std::copy для структур данных, которые хранят свои элементы в непрерывной памяти (например, std::vector и std::array), и самим элементам будет легко присвоить копию, то компилятор выберет совершенно другую реализацию (предполагается, что типом итератора является указатель):

template 
OutputIterator copy(InputIterator it, InputIterator end_it,
                    OutputIterator out_it)
{
  const size_t num_items (distance(it, end_it));
  memmove(out_it, it, num_items * sizeof(*it));
  return it + num_items;
}

Перед вами упрощенная версия реализации алгоритма std::copy с помощью memmove. Она работает быстрее, чем стандартная версия с циклами, и в то же время не такая читабельная. Но тем не менее пользователи алгоритма std::copy автоматически получают от него выгоду, если типы их аргументов соответствуют требованиям, выполнение которых необходимо для оптимизации. Компилятор выбирает для заданного алгоритма самую быструю реализацию из возможных, а код пользователя выражает, что именно делает алгоритм, не обрастая ненужными деталями.

Алгоритмы STL зачастую предоставляют наилучшее сочетание читабельности и оптимальности реализации.

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

Кроме того, мы использовали алгоритм std::move. Он работает точно так же, как и алгоритм std::copy, но применяет std::move(*it) к итератору источника в цикле, чтобы преобразовать значения lvalues к значениям rvalues. Это позволяет компилятору выбрать оператор присваивания перемещением целевого объекта вместо оператора присваивания копированием. Для многих сложных объектов данный способ работает быстрее, но при этом уничтожается исходный объект.

Сортируем контейнеры

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

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

Как это делается

В этом примере мы поработаем с алгоритмами std::sort и std::partial_sort.

1. Сначала включим все необходимые заголовочные файлы и объявим об использовании пространства имен std:

#include 
#include 
#include 
#include 
#include 

using namespace std;

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

static void print(const vector&v)
{
  copy(begin(v), end(v), ostream_iterator{cout, ", "});
  cout << '\n';
}

3. Начнем с вектора, содержащего некоторые числа:

int main()
{
  vector v {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

4. Поскольку мы перемешаем значения вектора несколько раз, чтобы исследовать разные функции сортировки, нам понадобится генератор случайных чисел:

  random_device rd;
  mt19937 g {rd()};

5. Функция std::is_sorted говорит о том, было ли отсортировано содержимое контейнера. Эта строка должна вывести значение 1:

  cout << is_sorted(begin(v), end(v)) << '\n';

6. С помощью std::shuffle мы перемешаем содержимое вектора, чтобы позднее отсортировать его. Первые два аргумента указывают на диапазон данных, который будет перемешан, а третий — генератор случайных чисел:

  shuffle(begin(v), end(v), g);

7. Функция is_sorted должна теперь вернуть значение false, а на экране мы увидим значение 0, значения вектора должны остаться прежними, но их порядок изменится. Мы увидим это, когда выведем на экран его содержимое:

  cout << is_sorted(begin(v), end(v)) << '\n';
  print(v);

8. Теперь восстановим исходный порядок элементов с помощью алгоритма std::sort. Вызвав те же команды на консоли, мы увидим значения вектора, отсортированные по возрастанию:

  sort(begin(v), end(v));