Расширить алгоритмы, принимающие значение и бинарный предикат

h4tred
h4tred

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

Например:

  int myints[] = {1,2,3,4,5,4,3,2,1};
  std::vector<int> v(myints,myints+9);                         // 1 2 3 4 5 4 3 2 1

  // using default comparison:
  std::sort (v.begin(), v.end());

  auto it = std::binary_search(v.begin(), v.end(), 4, [](auto lhs, auto rhs) {
    // тут может быть куда более сложная проверка
    return lhs < rhs;
  });

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

Пример с использованием унарного предиката:

  auto it = std::binary_search(v.begin(), v.end(), [](auto value) {
    // тут может быть куда более сложная проверка
    return value < 4;
  });

К подобным алгоритмам относятся:

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

Понятна необходимость использования общего компаратора с std::sort (или другими), ведь работа алгоритмов бинарного поиска основана на условии сортировки. С другой стороны, часто для сортировки сложных структур используется одно-два поля и искать запись только по этому полю становится неудобно: нужно передавать целый объект, что бы передать только одно/два поля. В случае сортировки эти объекты уже есть, в случае поиска - его нужно создать и заполнить самому.

0
рейтинг
2 комментария
Павел Майоров
Дело в том, что произвольный предикат передавать в такие функции - нельзя. Тот же binary_search требует упорядоченности последовательности в терминах переданного предиката (более того - эта самая упорядоченность частично проверяется assert'ами в отладочной сборке). Если передать в функцию унарный предикат - то даже сам факт упорядоченности нельзя будет адекватно описать в документации.

Кроме того, сам факт что последовательность упорядоченна, обычно означает что нужный предикат где-то в другой функции уже передавался, например, в функцию сортировки. То есть надо лишь найти его и использовать повторно (DRY!) вместо того чтобы писать лямбду.

Для случая поиска по конкретному полю - можно просто перегрузить в компараторе оператор (), дав возможность сравнивать объекты не только друг с другом - но и со значением поля напрямую.

По части же изменений в языке - я бы предпочел варианты функций, принимающих компаратор, которые бы принимали еще и поле (функтор) для сортировки (sort_by, binary_search_by, lower_bound_by, ...) - такое решение будет намного красивее и полезней нежели перегрузки с унарными предикатами.
Павел Майоров
h4tred
Павел Майоров, что-то тут оказывается уведомления не прилетают при комментариях...

> Для случая поиска по конкретному полю - можно просто перегрузить в компараторе оператор (), дав возможность сравнивать объекты не только друг с другом - но и со значением поля напрямую.

Спасибо, об этом я не подумал. Причём для лямбды тоже работает, хотя предложение иметь в таком варианте функтор - очень стоящее. Дабы было сложнее нарушить условия сортировки и не давать искать по другому полю.

С другой стороны, особняком остаётся std::search_n - для неё критерий сортировки не имеет значения и по одной и той же коллекции можно бегать, используя разные поля и критерии поиска.
h4tred
Другие идеи
Группа создана, чтобы собирать предложения к стандарту C++, организовывать их внутренние обсуждения, помогать готовить их для отправки в комитет и защищать на общих собраниях в рабочей группе по С++ Международной организации по стандартизации (ISO).