Функция partition

Функция partition из заголовочного файла algorithm выполняет разделение диапазона на две группы. В первую группу попадают элементы, для которых предикат возвращает true, а во вторую - все остальные. В первый параметр мы передаем итератор начала диапазона, во второй - итератор конца, а в третий - унарный предикат, задающий условие разделения. Функция возвращает итератор, указывающий на первый элемент второй группы (то есть на границу раздела). Относительный порядок элементов внутри каждой из групп не сохраняется.

Синтаксис

#include <algorithm>

It partition(It first, It last, UnaryPredicate p);

Пример

Давайте разделим вектор чисел так, чтобы все четные числа оказались в начале:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool isEven(int n)
{
	return n % 2 == 0;
}

int main()
{
	vector<int> vec = {1, 2, 3, 4, 5};
	partition(vec.begin(), vec.end(), isEven);
	
	for (int elem : vec) {
		cout << elem << " ";
	}
	cout << endl;
	return 0;
}

Результат выполнения кода:

4 2 3 1 5

Пример

Давайте разделим вектор чисел так, чтобы все числа, большие 3, оказались в начале, и выведем границу раздела:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool greaterThanThree(int n)
{
	return n > 3;
}

int main()
{
	vector<int> vec = {1, 2, 3, 4, 5};
	auto bound = partition(vec.begin(), vec.end(), greaterThanThree);
	
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		if (it == bound) {
			cout << "| ";
		}
		cout << *it << " ";
	}
	cout << endl;
	return 0;
}

Результат выполнения кода:

"5 4 | 3 2 1"

Смотрите также

функция stable_partition,
которая сохраняет относительный порядок элементов
функция is_partitioned,
которая проверяет, разделен ли диапазон
функция sort,
которая сортирует элементы диапазона
функция find_if,
которая ищет первый элемент, удовлетворяющий условию