C++: алгоритмы с бинарным предикатом и значением

Или век живи - век учись.

Проблема описана здесь: https://stdcpp.ru/proposals/1386b162-0cde-49b7-a41e-90f2d9ee477c.

Суть: зачем передавать бинарный предикат и значение, если нужное значение можно временами захватить в лямбду и не передавать вторым аргументом компаратору.

В комментарии подсказали по поводу переопределения operator(), который будет принимать тип, соответствующий полю, по которому происходит поиск и сортировка. Это же решение работает и для лямбд:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Foo
{
	std::string name;
	int some_field0;
	int some_field1;
	// ..
	int some_fieldN;
};

int main() 
{
	vector<Foo> vec = {
		{"/tmp/alexd", 0, 0, 0},
		{"/tmp/vasya_pupkin", 0, 0, 0},
		{"/tmp/john_doe", 0, 0, 0},
	};
	
	cout << "Original:<br/>n";
	for (const auto& i : vec) {
		cout << "  " << i.name << '<br/>n';
	}
	
	std::sort(begin(vec), end(vec), [](const auto& left, const auto& right) {
		return left.name < right.name;
	});
	
	cout << "Sorted:<br/>n";
	for (const auto& i : vec) {
		cout << "  " << i.name << '<br/>n';
	}
	
	const string searchName = "/tmp/john_doe";
	
	// Бинарный поиск по полю: передаём не весь объект, а только значение для поля
	auto it = std::lower_bound(begin(vec), end(vec), searchName, [](const auto& item, const auto& name){
		return item.name < name;
	});
	
	if (it == vec.end() || it->name != searchName ) {
		cout << "Item not found<br/>n";
	} else {
		cout << "Item found: " << it->name << '<br/>n';
	}
	
	return 0;
}

Стоит отметить, что условия сортировки не стоит нарушать или вы получите непредсказуемый результат. Поэтому лучше сделать как рекомендовано в комментарии к предложению: определить функтор для таких типов и переиспользовать его:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Foo
{
	std::string name;
	int some_field0;
	int some_field1;
	// ..
	int some_fieldN;
};

struct FooComparator
{
	bool operator()(const Foo& left, const Foo& right) {
		return operator()(left, right.name);
	}
	
	bool operator()(const Foo& left, const std::string& field ) {
		return left.name < field;
	}
};

int main() 
{
	vector<Foo> vec = {
		{"/tmp/alexd", 0, 0, 0},
		{"/tmp/vasya_pupkin", 0, 0, 0},
		{"/tmp/john_doe", 0, 0, 0},
	};
	
	cout << "Original:<br/>n";
	for (const auto& i : vec) {
		cout << "  " << i.name << '<br/>n';
	}
	
	std::sort(begin(vec), end(vec), FooComparator());
	
	cout << "Sorted:<br/>n";
	for (const auto& i : vec) {
		cout << "  " << i.name << '<br/>n';
	}
	
	const string searchName = "/tmp/john_doe";
	
	// Бинарный поиск по полю
	auto it = std::lower_bound(begin(vec), end(vec), searchName, FooComparator());
	
	if (it == vec.end() || it->name != searchName ) {
		cout << "Item not found<br/>n";
	} else {
		cout << "Item found: " << it->name << '<br/>n';
	}
	
	return 0;
}

В сопровождении такая штука будет проще. Тем более, что алгоритмы бинарного поиска обязаны использовать тот же критерий сравнения, что и сортировка и напутать в таком виде будет сложнее, нежели использовать лямбду.

Т.е.

Если вам нужно только отсортировать сложные объекты по какому-то полю - вполне может подойти лямбда.
Если вам потребовалось (или как только потребовалось) ещё и искать, используя алгоритмы бинарного поиска, то стоит написать функтор с функцией сравнения по полю.

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

или делаете линейный поиск std::find_if, а ему не важна сортировка;
или сортируем по новому критерию, а для этого уже желателен свой компаратор.

В противном случае, повторюсь, результат непредсказуем.

Ну и список алгоритмов к которым это относится:

std::binary_search
std::lower_bound
std::upper_bound
std::equal_range

Чуть особняком:

std::search_n

для неё не нужно отсортированного входа, но подход с лямбдой с типом второго аргумента, соответствующего типу поля - применим.

Hatred's Log Place

DON'T PANIC!

C++: алгоритмы с бинарным предикатом и значением