Разделение диапазона на две группы

Для разделения диапазона предназначены следующие функции:

  • nth_element() — переставляет элементы из диапазона между first и last, таким образом, чтобы перед позицией, заданной итератором nth, были элементы с меньшими значениями, а после — со значениями больше. При этом элементы не сортируются. Формат функции:
#include <algorithm>
void nth_element(first, nth, last[, comp]);

Пример:

std::vector<int> arr = {4, 5, 3, 2, 6, 1, 8, 7};
std::nth_element(arr.begin(), arr.begin() + 4, arr.end());
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 2 1 3 4 5 6 8 7

По умолчанию сравнение производится с помощью оператора <. В последнем параметре можно указать пользовательскую функцию сравнения. Выполним перестановку в обратном порядке:

std::vector<int> arr = {4, 5, 3, 2, 6, 1, 8, 7};
std::nth_element(arr.begin(), arr.begin() + 4, arr.end(),
         [](const int &a, const int &b){ return a > b; });
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 6 7 8 5 4 1 3 2
  • partition() — разделяет диапазон между first и last на две группы. В первую группу попадут элементы, для которых пользовательская функция pred вернула значение true. Во вторую группу попадут элементы, для которых пользовательская функция pred вернула значение false. Функция возвращает итератор, указывающий на первый элемент второй группы. При этом элементы не сортируются. Формат функции:
#include <algorithm>
iterator partition(first, last, pred);

Пример:

std::vector<int> arr = {4, 5, 3, 2, 6, 1, 8, 7};
auto it = std::partition(arr.begin(), arr.end(),
                         [](const int &x){ return x < 5; } );
if (it != arr.end()) {
   std::cout << *it << std::endl;         // 6
   std::cout << std::distance(arr.begin(), it)
             << std::endl;                // 4
}
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 4 1 3 2 6 5 8 7
  • stable_partition() — аналогична функции partition(), но сохраняет относительный порядок следования элементов. Формат функции:
#include <algorithm>
iterator stable_partition(first, last, pred);

Пример:

std::vector<int> arr = {4, 5, 3, 2, 6, 1, 8, 7};
auto it = std::stable_partition(arr.begin(), arr.end(),
                      [](const int &x){ return x < 5; } );
if (it != arr.end()) {
   std::cout << *it << std::endl;         // 5
   std::cout << std::distance(arr.begin(), it)
             << std::endl;                // 4
}
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 4 3 2 1 5 6 8 7
  • partition_copy() — копирует элементы, для которых пользовательская функция pred вернула значение true, в диапазон, начинающийся с позиции result_true. Элементы, для которых пользовательская функция pred вернула значение false, копируются в диапазон, начинающийся с позиции result_false. Функция возвращает экземпляр класса pair. Через свойство first будет доступен итератор, указывающий на конец первой группы, а через свойство second — итератор, указывающий на конец второй группы. Формат функции:
#include <algorithm>
pair<iterator1, iterator2> partition_copy(first, last,
                              result_true, result_false, pred);

Пример:

std::vector<int> arr = {4, 5, 3, 2, 6, 1, 8, 7},
                 res_true(8, -1), res_false(8, -1);
auto pr = std::partition_copy(arr.begin(), arr.end(),
                      res_true.begin(), res_false.begin(),
                      [](const int &x){ return x < 5; } );
if (pr.first != res_true.end()) {
   res_true.resize(std::distance(res_true.begin(), pr.first));
}
if (pr.second != res_false.end()) {
   res_false.resize(std::distance(res_false.begin(), pr.second));
}
for (int &el : res_true) std::cout << el << ' ';
std::cout << std::endl; // 4 3 2 1
for (int &el : res_false) std::cout << el << ' ';
std::cout << std::endl; // 5 6 8 7
  • partition_point() — возвращает итератор, указывающий на позицию разделяющую две группы. Предварительно диапазон нужно разделить на две группы, например, с помощью функции partition(). Пользовательская функция pred в обоих случаях должна быть одинаковой. Формат функции:
#include <algorithm>
iterator partition_point(first, last, pred);

Пример:

// #include <functional>
std::function<bool(const int&)> pred =
              [](const int &x){ return x < 5; };
std::vector<int> arr = {4, 5, 3, 2, 6, 1, 8, 7};
std::partition(arr.begin(), arr.end(), pred);
auto it = std::partition_point(arr.begin(), arr.end(), pred);
if (it != arr.end()) {
   std::cout << *it << std::endl;         // 6
   std::cout << std::distance(arr.begin(), it)
             << std::endl;                // 4
}
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 4 1 3 2 6 5 8 7
  • is_partitioned() — возвращает значение true, если диапазон между first и last разделен на две группы, например, с помощью функции partition(), и false — в противном случае. Пользовательская функция pred в обоих случаях должна быть одинаковой. Формат функции:
#include <algorithm>
bool is_partitioned(first, last, pred);

Пример:

// #include <functional>
std::function<bool(const int&)> pred =
              [](const int &x){ return x < 5; };
std::vector<int> arr = {4, 5, 3, 2, 6, 1, 8, 7};
std::cout << std::boolalpha;
std::cout << std::is_partitioned(
                  arr.begin(), arr.end(), pred); // false
std::partition(arr.begin(), arr.end(), pred);
std::cout << std::is_partitioned(
                  arr.begin(), arr.end(), pred); // true

Учебник C++ (Qt Creator и MinGW)
Учебник C++ (Qt Creator и MinGW) в формате PDF

Помощь сайту

ЮMoney (Yandex-деньги): 410011140483022

ПАО Сбербанк:
Счет: 40817810855006152256
Реквизиты банка:
Наименование: СЕВЕРО-ЗАПАДНЫЙ БАНК ПАО СБЕРБАНК
Корреспондентский счет: 30101810500000000653
БИК: 044030653
КПП: 784243001
ОКПО: 09171401
ОКОНХ: 96130
Скриншот реквизитов