Abou tstd::random_shuffle's RandomNumberGenerator

[Vladimir Grigoriev]

Why is the RandomNumber Generator parameter passed by reference in the
std::random_shuffle() while other algorithms take a function parameter by
value? What is the reason? When a function parameter is passed by reference
it can not be built on the fly.

For example

std::random_shuffle( first, last, UserRandomNumberGenerator() ); // is not
compiled

Vladimir Grigoriev

[Igor Tandetnik]

Post by Vladimir Grigoriev
Why is the RandomNumber Generator parameter passed by reference in the
std::random_shuffle() while other algorithms take a function parameter by
value?

Random number generators usually have state. Things like, say, predicates are typically stateless.

Post by Vladimir Grigoriev
What is the reason? When a function parameter is passed by reference
it can not be built on the fly.

Why would you want to?

[Vladimir Grigoriev]

However a state can be kept inside a functional class. So I think your
reason is not sufficient.

Vladimir Grigoriev

Post by Vladimir Grigoriev
Why is the RandomNumber Generator parameter passed by reference in the
std::random_shuffle() while other algorithms take a function parameter by
value?

Random number generators usually have state. Things like, say, predicates
are typically stateless.

Post by Vladimir Grigoriev
What is the reason? When a function parameter is passed by reference
it can not be built on the fly.

Why would you want to?

[Tamas Demjen]

Post by Vladimir Grigoriev
However a state can be kept inside a functional class. So I think your
reason is not sufficient.

Because you usually don't want to reset the seed of the random number
generator. Instead, you want to continue where your previous random
number was left off.

Imagine that you are writing a card game, and random_shuffle's last
parameter is passed by value in the following code:

UserRandomNumberGenerator rand(initial_seed);
while(!quit)
{
int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
random_shuffle(A, A + N, rand);
PlayCardGame(A, A + N);
}

So if this is a solitaire game, the player would see the exact same
order of cards in every single game. :-)

However, since random_shuffle's last argument is a reference, this
problem does not exist.

Tom

[Stephan T. Lavavej [MSFT]]

There's a little more to the story than this.

First, I want to correct an earlier reply:

[Igor Tandetnik]

Post by Igor Tandetnik
Things like, say, predicates are typically stateless.

This is incorrect. Some predicates are stateless, like is_even. Other
predicates are stateful, like bind(less<int>(), _1, 1729). Predicates (and
comparators) almost never *modify* their state as they are invoked, because
they must return consistent answers, but constructing a stateful predicate
and giving it to an STL algorithm is a common and useful thing to do.

Tamas explained most of the story below - PRNGs modify their state, and
typically you want to keep using the modified state instead of discarding
it. However, the STL has an algorithm that takes a functor by value,
invokes it on every element of a sequence, and *returns* that functor,
allowing the functor to modify its state along the way so that it can be
inspected later. This algorithm is called for_each().

So why doesn't random_shuffle() behave like for_each()? I can think of a
couple of reasons. First, taking the PRNG by reference makes it difficult
to drop the modified state on the floor. (This was probably the most
important reason during C++98's standardization.) Second, PRNGs often
maintain a lot of state, unlike other functors which are expected to be
lightweight (the STL usually passes functors by value). For example (an
anachronistic example), mersenne_twister maintains a lot of state. Copying
that around, in the absence of move semantics, is undesirable.

STL

Post by Igor Tandetnik

Post by Vladimir Grigoriev
However a state can be kept inside a functional class. So I think your
reason is not sufficient.

Because you usually don't want to reset the seed of the random number
generator. Instead, you want to continue where your previous random
number was left off.
Imagine that you are writing a card game, and random_shuffle's last
UserRandomNumberGenerator rand(initial_seed);
while(!quit)
{
int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
random_shuffle(A, A + N, rand);
PlayCardGame(A, A + N);
}
So if this is a solitaire game, the player would see the exact same
order of cards in every single game. :-)
However, since random_shuffle's last argument is a reference, this
problem does not exist.
Tom

[Vladimir Grigoriev]

However if a functor must maintain his states across its copies it can make
them static or use another paradigm of defining inside the class pointers to
a state class. So I do not see a problem It seems that someone created an
example of a partial case and this partial case overwrites the common and
very useful approach of defining functors on the fly.

Vladimir Grigoriev

Post by Stephan T. Lavavej [MSFT]
There's a little more to the story than this.
[Igor Tandetnik]

Post by Igor Tandetnik
Things like, say, predicates are typically stateless.

This is incorrect. Some predicates are stateless, like is_even. Other
predicates are stateful, like bind(less<int>(), _1, 1729). Predicates
(and comparators) almost never *modify* their state as they are invoked,
because they must return consistent answers, but constructing a stateful
predicate and giving it to an STL algorithm is a common and useful thing
to do.
Tamas explained most of the story below - PRNGs modify their state, and
typically you want to keep using the modified state instead of discarding
it. However, the STL has an algorithm that takes a functor by value,
invokes it on every element of a sequence, and *returns* that functor,
allowing the functor to modify its state along the way so that it can be
inspected later. This algorithm is called for_each().
So why doesn't random_shuffle() behave like for_each()? I can think of a
couple of reasons. First, taking the PRNG by reference makes it difficult
to drop the modified state on the floor. (This was probably the most
important reason during C++98's standardization.) Second, PRNGs often
maintain a lot of state, unlike other functors which are expected to be
lightweight (the STL usually passes functors by value). For example (an
anachronistic example), mersenne_twister maintains a lot of state.
Copying that around, in the absence of move semantics, is undesirable.
STL

Post by Igor Tandetnik

Post by Vladimir Grigoriev
However a state can be kept inside a functional class. So I think your
reason is not sufficient.

Because you usually don't want to reset the seed of the random number
generator. Instead, you want to continue where your previous random
number was left off.
Imagine that you are writing a card game, and random_shuffle's last
UserRandomNumberGenerator rand(initial_seed);
while(!quit)
{
int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
random_shuffle(A, A + N, rand);
PlayCardGame(A, A + N);
}
So if this is a solitaire game, the player would see the exact same
order of cards in every single game. :-)
However, since random_shuffle's last argument is a reference, this
problem does not exist.
Tom

[Stephan T. Lavavej [MSFT]]

Post by Vladimir Grigoriev
However if a functor must maintain his states across its copies it can
make them static

That would prevent having functors with different states.

Post by Vladimir Grigoriev
or use another paradigm of defining inside the class pointers to a state
class.

That requires dynamic memory allocation.

Post by Vladimir Grigoriev
So I do not see a problem It seems that someone created an example of a
partial case and this partial case overwrites the common and very useful
approach of defining functors on the fly.

PRNGs are typically *not* constructed as temporaries and then thrown away.

STL

Post by Vladimir Grigoriev
However if a functor must maintain his states across its copies it can
make them static or use another paradigm of defining inside the class
pointers to a state class. So I do not see a problem It seems that someone
created an example of a partial case and this partial case overwrites the
common and very useful approach of defining functors on the fly.
Vladimir Grigoriev

Post by Stephan T. Lavavej [MSFT]
There's a little more to the story than this.
[Igor Tandetnik]

Post by Igor Tandetnik
Things like, say, predicates are typically stateless.

This is incorrect. Some predicates are stateless, like is_even. Other
predicates are stateful, like bind(less<int>(), _1, 1729). Predicates
(and comparators) almost never *modify* their state as they are invoked,
because they must return consistent answers, but constructing a stateful
predicate and giving it to an STL algorithm is a common and useful thing
to do.
Tamas explained most of the story below - PRNGs modify their state, and
typically you want to keep using the modified state instead of discarding
it. However, the STL has an algorithm that takes a functor by value,
invokes it on every element of a sequence, and *returns* that functor,
allowing the functor to modify its state along the way so that it can be
inspected later. This algorithm is called for_each().
So why doesn't random_shuffle() behave like for_each()? I can think of a
couple of reasons. First, taking the PRNG by reference makes it
difficult to drop the modified state on the floor. (This was probably
the most important reason during C++98's standardization.) Second, PRNGs
often maintain a lot of state, unlike other functors which are expected
to be lightweight (the STL usually passes functors by value). For
example (an anachronistic example), mersenne_twister maintains a lot of
state. Copying that around, in the absence of move semantics, is
undesirable.
STL

Post by Igor Tandetnik

Post by Vladimir Grigoriev
However a state can be kept inside a functional class. So I think your
reason is not sufficient.

Because you usually don't want to reset the seed of the random number
generator. Instead, you want to continue where your previous random
number was left off.
Imagine that you are writing a card game, and random_shuffle's last
UserRandomNumberGenerator rand(initial_seed);
while(!quit)
{
int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
random_shuffle(A, A + N, rand);
PlayCardGame(A, A + N);
}
So if this is a solitaire game, the player would see the exact same
order of cards in every single game. :-)
However, since random_shuffle's last argument is a reference, this
problem does not exist.
Tom

[Vladimir Grigoriev]

However I'd like to point out that there are such algorithms as
std::generate and std::generate_n in C++. They use also a random generator.
The only difference between these algorithms and the std::random_shuffle is
that the first two generate an initial distribution of data while the second
makes a rearrangement of data. But the first two uses a generator by value
while the last uses a generator by reference. However there is no a
principal difference because the first two may be used in similar situations
as the last one when a new distribution is needed but a generator should
keep its states.

Vladimir Grigoriev
.

Post by Stephan T. Lavavej [MSFT]

Post by Vladimir Grigoriev
However if a functor must maintain his states across its copies it can
make them static

That would prevent having functors with different states.

Post by Vladimir Grigoriev
or use another paradigm of defining inside the class pointers to a state
class.

That requires dynamic memory allocation.

Post by Vladimir Grigoriev
So I do not see a problem It seems that someone created an example of a
partial case and this partial case overwrites the common and very useful
approach of defining functors on the fly.

PRNGs are typically *not* constructed as temporaries and then thrown away.
STL

Post by Vladimir Grigoriev
However if a functor must maintain his states across its copies it can
make them static or use another paradigm of defining inside the class
pointers to a state class. So I do not see a problem It seems that
someone created an example of a partial case and this partial case
overwrites the common and very useful approach of defining functors on
the fly.
Vladimir Grigoriev

Post by Stephan T. Lavavej [MSFT]
There's a little more to the story than this.
[Igor Tandetnik]

Post by Igor Tandetnik
Things like, say, predicates are typically stateless.

This is incorrect. Some predicates are stateless, like is_even. Other
predicates are stateful, like bind(less<int>(), _1, 1729). Predicates
(and comparators) almost never *modify* their state as they are invoked,
because they must return consistent answers, but constructing a stateful
predicate and giving it to an STL algorithm is a common and useful thing
to do.
Tamas explained most of the story below - PRNGs modify their state, and
typically you want to keep using the modified state instead of
discarding it. However, the STL has an algorithm that takes a functor
by value, invokes it on every element of a sequence, and *returns* that
functor, allowing the functor to modify its state along the way so that
it can be inspected later. This algorithm is called for_each().
So why doesn't random_shuffle() behave like for_each()? I can think of
a couple of reasons. First, taking the PRNG by reference makes it
difficult to drop the modified state on the floor. (This was probably
the most important reason during C++98's standardization.) Second,
PRNGs often maintain a lot of state, unlike other functors which are
expected to be lightweight (the STL usually passes functors by value).
For example (an anachronistic example), mersenne_twister maintains a lot
of state. Copying that around, in the absence of move semantics, is
undesirable.
STL

Post by Igor Tandetnik

Post by Vladimir Grigoriev
However a state can be kept inside a functional class. So I think your
reason is not sufficient.

Because you usually don't want to reset the seed of the random number
generator. Instead, you want to continue where your previous random
number was left off.
Imagine that you are writing a card game, and random_shuffle's last
UserRandomNumberGenerator rand(initial_seed);
while(!quit)
{
int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
random_shuffle(A, A + N, rand);
PlayCardGame(A, A + N);
}
So if this is a solitaire game, the player would see the exact same
order of cards in every single game. :-)
However, since random_shuffle's last argument is a reference, this
problem does not exist.
Tom

[Vladimir Grigoriev]

Post by Stephan T. Lavavej [MSFT]

Post by Vladimir Grigoriev
However if a functor must maintain his states across its copies it can
make them static

That would prevent having functors with different states.

However you can place each function or functor or only the part which
responsible to generate numbers in its own namespace.

Vladimir Grigoriev