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

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

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

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

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

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

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

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

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

#include <iostream>

#include <algorithm>

#include <vector>

#include <iterator>

#include <random>

using namespace std;

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

static void print(const vector<int> &v)

{

  copy(begin(v), end(v), ostream_iterator<int>{cout, ", "});

  cout << 'n';

}

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

int main()

{

  vector<int> 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));

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

  print(v);

9. Еще одна интересная функция — std::partition. Возможно, мы не хотим полностью сортировать список, поскольку достаточно поместить в начало те элементы, чье значение не превышает некий предел. Секционируем вектор, чтобы переместить все элементы, значение которых меньше 5, в начало, и выведем результат на экран:

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

  partition(begin(v), end(v), [] (int i) { return i < 5; });

  print(v);

10. Следующая функция, связанная с сортировкой, — std::partial_sort. Ее можно использовать для сортировки содержимого контейнера, но не в полной мере. Эта функция поместит N самых маленьких элементов в начало контейнера в отсортированном виде. Остальная часть элементов останется во второй половине, они не будут отсортированы.

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

  auto middle (next(begin(v), int(v.size()) / 2));

  partial_sort(begin(v), middle, end(v));

  print(v);

11. Что, если мы хотим отсортировать структуру данных, не поддерживающую оператора сравнения? Определим такую структуру и создадим следующий вектор элементов:

  struct mystruct {

    int a;

    int b;

  };

  vector<mystruct> mv {{5, 100}, {1, 50}, {-123, 1000},

                       {3, 70}, {-10, 20}};

12. Функция std::sort опционально принимает в качестве третьего аргумента функцию сравнения. Воспользуемся данным обстоятельством и передадим ей такую функцию. Для демонстрации того, что это возможно, мы будем сравнивать элементы на основе второго поля, b. Таким образом, элементы отсортируются на основе поля mystruct::b, а не поля mystruct::a:

  sort(begin(mv), end(mv),

    [] (const mystruct &lhs, const mystruct &rhs) {

      return lhs.b < rhs.b;

  });

13. Последним шагом будет вывод на экран упорядоченного вектора, содержащего элементы типа mystruct.

  for (const auto &[a, b] : mv) {

    cout << "{" << a << ", " << b << "} ";

  }

  cout << 'n';

}

14. Скомпилируем и запустим программу.

Первое значение 1 получено от вызова функции std::is_sorted call после инициализации упорядоченного вектора. Далее мы перемешали значения вектора и получили значение 0 после второго вызова функции is_sorted. В третьей строке показаны все элементы вектора после перемешивания. Следующее значение 1 — это результат вызова функции is_sorted после повторной сортировки с помощью алгоритма std::sort.

Далее мы снова перемешали вектор и секционировали его, задействовав алгоритм std::partition. Можно увидеть, что все элементы, чье значение не превышает 5, находятся слева от значения 5 в векторе. Остальные элементы, чье значение превышает 5, стоят справа. За исключением этого они выглядят упорядоченными.

В предпоследней строке показан результат вызова алгоритма std::partial_sort. Все элементы в первой половине вектора выглядят отсортированными, а остальные — нет.

В последней строке мы видим наш вектор, содержащий экземпляры типа mystruct. Они строго отсортированы по значению второго члена.

$ ./sorting_containers

1

0

7, 1, 4, 6, 8, 9, 5, 2, 3, 10,

1

1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

1, 2, 4, 3, 5, 7, 8, 10, 9, 6,

1, 2, 3, 4, 5, 9, 8, 10, 7, 6,

{-10, 20} {1, 50} {3, 70} {5, 100} {-123, 1000}

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

Мы использовали разные алгоритмы, связанные с сортировкой (табл. 5.1).

Для объектов, не