5

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

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

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<Worker> workers;
//...
std::find_if(workers.begin(), workers.end(), DoWork(42));

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

2
  • 1
    Идея классная -- нестандартно использовать возможности инструмента, но всё же попробую Вас отговорить от нее: такой код будет тяжело поддерживать, это антипаттерн, потому что поведение не очевидное. Функция, созданная для поиска-если, должна использоваться для этого.
    – Arkady
    9 мар 2017 в 18:06
  • Если подумать. это можно сделать если метод doWork контстантен, состояние работника надо изменять через итератор возвращаемый find_if. Возможно у вас должен быть объект "накладная" , которая будет сохраняться в DoWork или хранится где-то еще и ее состояние будет меняться, а не состояние worker. По требованию стандарта doWork должен быть константен 10 мар 2017 в 12:50

3 ответа 3

3

Для унарного предиката функций 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<class InputIterator, class UnaryPredicate>
  InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred)
{
  while (first!=last) {
    if (pred(*first)) return first;
    ++first;
  }
  return last;
}

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

1
  • @ Abyx поправил. Задом наперед переведено. Насчет "ничего плохого не случится: это тоже неопределенное поведение, если если это противоречил опсанию. Для изменения коллекций есть алгортмы for_each, replace_if, remove_if и т.д. Коллекция может быть таковой, что изменение еще члена должно приводить к изменению порядка, что невозможно при передаче значения объекта по сслыке , то есть по идее итераторы меняться. 10 мар 2017 в 6:20
2

В требованиях к предикатам, передаваемым в 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. Опять же, в этом определении есть свои дыры, но идея, я думаю, ясна.

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

4
  • @Abyx en.cppreference.com/w/cpp/algorithm/find The signature does not need to have const &, but the function must not modify the objects passed to it. Нет никаких гарантий, как организован контейнер, а также особенность используемого вызываемого объекта может привести к нарушению правила сохранения псевдонимов, поэтому использовать модифицирующий предикат некорректно. 9 мар 2017 в 12:48
  • @Abyx: Понятно что невозможно придумать одно требование того, что делать можно, а что нельзя, которое хорошо подходило бы для всех алгоритмов. Либо детально описывать каждый индивидуально, либо идти по пути вот такой огульного запрета: нельзя вызывать неконстантные методы и точка. Авторы спецификации пошли по второму пути. То есть формально все таки этого делать нельзя. 9 мар 2017 в 18:53
  • @Abyx: Программист не станет игнорировать стандарт без пущей на то необходмости. В данном случае я такой необходимости не вижу. 9 мар 2017 в 20:17
  • @Abyx А контейнер может требовать использования итератора для изменения содержимового. ПОэтому The function object pred shall not apply any non-constant function through the dereferenced iterator и говорит что через разыменованный итератор этого делать нельзя. У таких контейнеров итератор разыменуется в объект , являющийся константным псеводонимом оригинала, который менять нельзя (или он просто не поменяется в коллекции) 10 мар 2017 в 6:32
2

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

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

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.