By sonu gupta

2019-08-13 18:13:12 8 Comments

I was reading online about C++ and came across this statement:

Predicates should not modify their state due to a function call.

I did not understand what does "state" mean here. Can someone please elaborate with an example?


@Caleth 2019-09-05 11:44:44

In addition to the other answers, many of the algorithms that take predicates don't promise any particular traversal order (the ExecutionPolicy overloads allow for interleaved traversal). You might get different answers to the same question.

If there are multiple threads calling1 the predicate and it changes some shared value, that's a data race, i.e. undefined behaviour.

  1. or one thread interleaving calls to

@formerlyknownas_463035818 2019-08-13 18:22:59

Let's consider the algorithm std::count_if as an example. It traverses a range and counts how often a given predicate evaluates to true. Further assume we want to check how many elements in a container are smaller than a given number, e.g. 5 or 15.

A predicate can be many things. It just has to be callable. It can be a functor:

struct check_if_smaller {
    int x;
    bool operator()(int y) { return y < x; }

You can create different instances of that predicate, e.g. these two

check_if_smaller a{5};
check_if_smaller b{15};

can be used to check if numbers are smaller than 5 or 15 respectively:

bool test1 = a(3);  // true because 3 < 5
bool test2 = b(20); // false because 20 is not < 15

The member x is the state of the predicate. Typically this should not change when the predicate is applied (by calling its operator()).

From wikipedia:

In mathematical logic, a predicate is commonly understood to be a Boolean-valued function P: X→ {true, false}, called the predicate on X. However, predicates have many different uses and interpretations in mathematics and logic, and their precise definition, meaning and use will vary from theory to theory.

Sloppy speaking, a predicate is a function mapping something to a boolean. The fact that we use a functor that is not just a function but a function object with a state can be considered as an implementation detail, and repeatedtly evaluating the same predicate for same input is commonly expected to yield the same result. Also, algorithms make this assumption and nothing really prevents them from copying the predicate you pass. If evaluating the predicate would alter its internal state, the algorithm may not work as expected.

@Gupta 2019-08-13 18:54:27

You mean anyone should avoid changing x while the predicate is executing, right? Is it OK to make x private and have a setX(...) method instead to control everything?

@formerlyknownas_463035818 2019-08-13 18:56:36

@Gupta a models the predicate "check if a number is smaller than 5". If you change its x member it is a different predicate. Of course you can make x private, though I dont see how this makes any difference or what would be the advantage

@Daniel says reinstate Monica 2019-08-20 07:13:10

I would additionally suggest to make the predicate function-call operator const, if it does not modify it's state: bool operator()(int y) const { return y < x; }.

@Daniel says reinstate Monica 2019-08-20 07:17:11

@formerlyknownas_463035818 2019-08-20 07:33:42

@DanielLangr awesome, I'll edit it into the answer, just dont have the time right now

@Swift - Friday Pie 2019-08-14 07:11:01

Essentially what standard says that predicate should act like a pure function (in mathematical terms), i.e. its returning value should be dependent on input alone.

The mention of state because predicates can be copied or can be invoked in different threads, which depends on implementation and platform behavior. For lambda's and other invokable objects which aren't functions this may mean unordered access to the storage, captured by reference, or access different values if they were captured by value. For a function, it means that any side-effects (including change of static variables) may result in problems.

If a predicate for sorting would return different results for same pair, then some sort algorithms become invalid.

@SergeyA 2019-08-13 18:19:43

In laymen terms, a state in a predicate is a data member. A predicate changing the state means that the member get's changed during the algorithm execution and that change is going to affect predicate behavior.

The reason to avoid this is the fact that algorithms are under no obligation to keep a single instance of a predicate. They might easily be copied around, and state changed in one copy, will not be shared with a state in another copy. As a result, program will behave unexpectedly (for someone expecting the state change to be in effect).

Related Questions

Sponsored Content

25 Answered Questions

[SOLVED] Why do we need virtual functions in C++?

8 Answered Questions

[SOLVED] When should I really use noexcept?

18 Answered Questions

[SOLVED] Why should C++ programmers minimize use of 'new'?

5 Answered Questions

[SOLVED] When to use extern in C++

24 Answered Questions

[SOLVED] Image Processing: Algorithm Improvement for 'Coca-Cola Can' Recognition

4 Answered Questions

[SOLVED] What does T&& (double ampersand) mean in C++11?

11 Answered Questions

[SOLVED] What does the explicit keyword mean?

6 Answered Questions

[SOLVED] GCC -fPIC option

  • 2011-03-15 12:12:16
  • Narek
  • 228799 View
  • 403 Score
  • 6 Answer
  • Tags:   c++ gcc options fpic

Sponsored Content