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

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 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).