Инструменты пользователя

Инструменты сайта


// 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:\n";
	for (const auto& i : vec) {
		cout << "  " << i.name << '\n';
	}
 
	std::sort(begin(vec), end(vec), [](const auto& left, const auto& right) {
		return left.name < right.name;
	});
 
	cout << "Sorted:\n";
	for (const auto& i : vec) {
		cout << "  " << i.name << '\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\n";
	} else {
		cout << "Item found: " << it->name << '\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:\n";
	for (const auto& i : vec) {
		cout << "  " << i.name << '\n';
	}
 
	std::sort(begin(vec), end(vec), FooComparator());
 
	cout << "Sorted:\n";
	for (const auto& i : vec) {
		cout << "  " << i.name << '\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\n";
	} else {
		cout << "Item found: " << it->name << '\n';
	}
 
	return 0;
}

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

Т.е.

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

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

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

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

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

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

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

  • std::search_n

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

Комментарии