Использование std::find_if не для поиска

#cpp #алгоритм #stl

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

Допустим у нас есть некий класс, выполняющий какую-то работу:

class Worker{
public:
    bool doWork(int arg);
};


Метод doWork возвращает true если работа выполнена успешно.
Нужно чтобы кто-то из имеющихся работников выполнил работу. Для этого хочу воспользоваться
std::find_if

struct DoWork{
    int arg;
    explicit DoWork(int arg):
        arg(arg)
    {}
    bool operator()(Worker &worker) const{
        return worker.doWork(arg);
    }
};

std::vector workers;
//...
std::find_if(workers.begin(), workers.end(), DoWork(42));


Идея такая. Алгоритм будет перебирать работников до тех пор пока один не выполнит
работу или они не закончатся. Но меня терзают смутные сомнения что так делать можно.
Нет ли здесь неопределенного поведения? Будет ли этот код всегда одинаково работать
на разных реализациях stl?
    

Ответы

Ответ 1

В требованиях к предикатам, передаваемым в std::find_if, указано, что параметр предиката
не обязательно должен быть константной ссылкой, но тем не менее при этом предикату
запрещается модифицировать передаваемый в него объект.


  25.1 General [algorithms.general]
  
  4 For purposes of determining the existence of data races, algorithms shall not
modify objects referenced through an iterator argument unless the specification requires
such modification.


Для алгоритм std::find_if как раз таки такого разрешения не дается (в отличие, скажем,
от std::for_each). Как формально определяется модифицирующая операция я навскидку не
скажу, но если ваша функция DoWork модифицирует элемент контейнера, то есть вероятность,
что так делать формально нельзя.

Дополнительно далее там же


  8 The Predicate parameter is used whenever an algorithm expects a function object
(20.9) that, when applied to the result of dereferencing the corresponding iterator,
returns a value testable as true. [...] The function object pred shall not apply any
non-constant function through the dereferenced iterator.


Параметром std::find_if как раз является Predicate pred, т.е. эта часть уже однозначно
запрещает ваш вариант, если DoWork является неконстантным членом класса Worker. Опять
же, в этом определении есть свои дыры, но идея, я думаю, ясна.

Навскидку, конечно, трудно представить себе, что тут может пойти не так, если реализация
специально не заточена на злостное вредительство и ловлю нарушителей стандарта...


Ответ 2

Для унарного предиката функций std::find, std::find_if, std::find_if_not четко определено
следующее:

1) Функция должна возвращать true для требуемого элемента

2) Прототип функции должен быть схож с записью:

bool pred(const Type &a);


const может быть опущен, но функция ни в коем случае не должна изменять данных,доступных
через передаваемый объект.

3) Type должен быть таким, что итератор может быть разыменован (can be derefenced)
и неявно конвертирован в Type.

Почему так? Компилятор, соответствующий С++11,  допускает распараллеливание и оптимизацию,
организуемую самим компилятором. Что будет если предикат может менять значение величины?
Это может привести к тому, что другой проход предиката даст другой, то есть неоднозначный,
результат. Коллекция может быть таковой, что изменение еще члена должно приводить к
изменению порядка, что невозможно при передаче значения объекта по сслыке , то есть
по идее итераторы должны меняться - является ли элемент первым по счету из встреченных
после изменения (и находится ли на  корректном месте) оказывается неизвестным.

find_if должен быть схож по поведению со следующей реализацией.

template
  InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred)
{
  while (first!=last) {
    if (pred(*first)) return first;
    ++first;
  }
  return last;
}


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


Ответ 3

Никакого неопределенного поведения - пока вы будете передавать корректные итераторы
начала и конца, и предикат с корректным поведением - не вижу.

Пока реализация STL соответствует стандарту - код будет работать.

"По-моему, так" (с) Пух