C++17 STL Стандартная библиотека шаблонов

Поскольку алгоритм 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';