Re: Use of swap in the standard library
Am 14.12.2010 20:52, schrieb Nikolay Ivchenkov:
On 13 Dec, 20:07, Daniel Kru"gler<daniel.krueg...@googlemail.com>
wrote:
Am 13.12.2010 12:33, schrieb Nikolay Ivchenkov:
I don't understand what "swappable expression" should mean. Let's
consider the following example:
#include<algorithm>
#include<iostream>
#include<iterator>
int main()
{
int *arr[2] = {};
{
int i;
arr[1] =&i;
}
std::reverse(std::begin(arr), std::end(arr));
std::cout<< arr[1]<< std::endl;
}
When std::reverse is called, arr[0] holds the null pointer value and
arr[1] holds an invalid pointer value (Note: effect of using an
invalid pointer value is undefined - see N3225 - 3.7.4.2/4).
At this point we need to halt, because [swappable.requirements] p. 2 . b. 1
already requires that the "expressions swap(t, u) and swap(u, t) are valid when
evaluated in the context described below". This is a basic requirement that you
will find in all requirement tables/descriptions. Anything that violates the
basic requirements cannot be considered to satisfy the requirement set as a
whole thing.
Now let's
consider the following questions:
1) Is arr[0] swappable with arr[1]?
It cannot be, because the expression swap(arr[0], arr[1]) "is not a valid when
evaluated".
2) Is arr[0] swappable?
No, see above.
Are you sure?
Yes ;-)
What can you say about the evaluation of
std::reverse(arr + 0, arr + 1)? And what can you say about the
evaluation of std::reverse(a + 0, a + 2) in the example below?
These are both questions different from the original one. The original
example is one, where std::swap(arr[0], arr[1]) *is* evaluated. In this
context the expression is clearly no valid expression.
The library requirement sets have at least two different purposes:
They require that an expression is valid, even if it is not evaluated -
informally I denote that as a "static" requirement (or the
"well-formed"-criterion).
In this case we cannot argue about effects and it is perfectly OK to say
that the expression std::swap(arr[0], arr[1]) is valid. This is
important, because that means that the standard does not impose overly
strict requirements on implementations to prevent those expressions
occurring at all.
The second important requirement of the requirement sets is a "dynamic"
(also my informal notation) or runtime requirement: If the corresponding
expressions are required *or* allowed to be evaluated for given
arguments for a correspondingly constrained function, the expression
must also be well-defined. This requirement is not satisfied in your
original example, but - since there is no actually allowed evaluation of
similarly critical (that would cause undefined behaviour) expressions in
your second example std::reverse(a + 0, a + 2), were there is no
violation of the client contract.
Let me emphasize that this is nothing special about the swappable
requirements. It applies to all other requirements set if they are
imposed on algorithms. I already mentioned the example of an assignment
that is not evaluated in my previous reply.
Returning to you "a-example": The evaluation of
std::reverse(a + 0, a + 2)
is well-formed and well-defined, because the correspondingly evaluated
swap expression satisfies both the static and the dynamic requirements
(well-formed and well-defined). I see no magic here.
What exactly
A type X satisfying any of the iterator requirements (24.2) is
ValueSwappable if, for any dereferenceable object x of type X, *x is
swappable.
is supposed to mean:
1) A type X satisfying any of the iterator requirements (24.2) is
ValueSwappable if _there can exist_ a dereferenceable object x of type
X _such that_ *x _would be_ swappable.
Looks too strict to me. There could be a type satisfying the iterator
requirements where no object of this type could be dereferencable.
Typically examples where these types are valid are degenerate (empty)
ranges. I see no evidence that the standard imposes this strictness for
any other requirement set or language concept.
or
2) A type X satisfying any of the iterator requirements (24.2) is
ValueSwappable if for _every_ dereferenceable object x of type X, *x
is swappable.
This is surely incorrect. The preconditions of both dereferencing and
swap operation must be satisfied in a particular evaluation context.
3) something else?
I already tried to explain it. Here a last attempt to present it
differently: The answer is that there is a static and a dynamic
requirement. If the dynamic requirement is never allowed to be evaluated
as part of some particular algorithm there is no reason why a type does
not satisfy these requirements if the static requirements are satisfied
because there is no way to prove the contrary. This also nicely shows,
that we cannot only speak of type properties but also of runtime
behaviour. This is the reason why referring to expressions (and not only
on types) is important. This also shows that the swappable requirements
are not different from other expression-based requirement sets.
I don't see any _correct_ rationale for presence of such definitions.
Sorry for that, but that judgment seems to go beyond a normal criticism
on Swappable requirements. This seems to be an overall and general
criticism on expression-based requirement sets. But I believe that we
have to live with them for C++0x.
In general, for a given expression t, there are 2 subsets of
expressions with the same type and value category (lvalue/rvalue):
1) subset of expressions which are swappable with t and
2) subset of expressions which are not swappable with t.
Both subsets may be non-empty. For example, in the sample above a[0]
is swappable with a[1], but a[0] is not swappable with a[2].
This interpretation exceeds what the standard says. There is no
*specific* requirement that a[0] is swappable. What you are presenting
here is your interpretation of what the standard says. I argue this
interpretation goes too far based on the general way of how the
requirements on algorithms are imposed. Otherwise every algorithm would
need to describe dynamic situations where these requirements are not
necessary. Just one example: In [alg.is_permutation] the requirement exists:
"The comparison function shall be an equivalence relation."
The intention clearly is that of an dynamic requirement. We can easily
construct examples where for some argument values - that are out of the
domain of a specific comparison function - this requirement would not
hold but still this comparison function can be used as valid argument of
such a constrained function, *unless* the dereferenced iterator values
would cause to enter this out-of-domain situation.
If, for a library component, the preconditions are defined in terms
of simply
swappable (not "swappable with") expressions or ValueSwappable types,
we have either:
1) unreasonable violation of preconditions - when the 2-nd subset is
required to be empty (e.g., in std::reverse(a + 0, a + 2)), or
2) undefined behavior of the library component having its
preconditions satisfied - when the 2-nd subset is not required to be
empty (e.g. in std::reverse(a + 0, a + 3)).
I believe I already answered on this above.
The definition of "swappable with" consists of two parts:
1) description of well-formed expressions and
2) description of required effects.
... in a context where the evaluation is allowed or required, yes.
A definition for ValueSwappable types can be introduced only in terms
of well-formed expressions.
Nope. It has also effect requirements, when the corresponding algorithm
requires a corresponding swap call with specific arguments.
Required effects are meaningful only with
regard to concrete pair of expressions,
Correct, similar for any other expression-based requirements that is
binary. For n-ary expression based operations, these are relevant for
the actually invoked or allowed to be invoked operation. Again: There is
nothing special in regard to swappable requirements here.
so required effects shall not be a part of a type classification.
This is a false conclusion, sorry. They are *very* important, because
otherwise a given algorithm that evaluates the corresponding expression
where it is allowed to do that, cannot make reasonable assumptions on
the effects and without such assumption an algorithm does not make
sense. The CopyConstructible requirements are not very much helpful
without effects requirements as well.
The same conclusions can be
applied to abstract lvalues or rvalues of some types.
void f(int **i, int **j)
{
std::swap(*i, *j);
}
Even if we know that i and j are dereferenceable, we can't say whether
*i is swappable with *j without additional knowledge about passed
arguments.
This is true for many if not most standard algorithms, believe it or not.
It is already used at several places, e.g. [nullablepointer.requirements] p. 1 b. 2:
"lvalues of type P are swappable (20.2.2),"
It seems, the problem is systematic:
I see it differently as a systematic misunderstanding ;-) [I could not
resist, but I'm kidding of-course]
A type P meets the requirements of NullablePointer if:
[...]
the expressions shown in Table 41 are valid and have the indicated
semantics
I believe that such method of description is far from being perfect.
Good point, the standard is not perfect. I don't deny that.
etc. This short-cut says exactly the same as if I would write that
"With lv1 and lv2 being lvalues of type T, lv1 shall be swappable with lv2" for
lvalues or "With rv1 and rv2 being rvalues of type T, rv1 shall be swappable
with rv2".
Both options are incorrect if the semantics shall be under
consideration.
It is not incorrect as explained before.
We don't want to repeat these lengthy sentences
Happily, some descriptions have correct form:
std::swap for arrays:
Requires: a[i] shall be swappable with (20.2.2) b[i] for all i in
the range [0,N).
I'm happy to see that there are at least some sentences in the standard
that are satisfactory for you ;-) [Kidding again]
The requirement that
the arguments must be valid, is already part of the basic requirements. It is
also part of the basic library requirements, as mentioned in 17.6.3.9 Function
arguments [res.on.arguments], in particular for p. 1 b 1 (for library functions)
and [res.on.functions] p. 2 b. 3.
How this is related to my examples?
I think I explained it above.
3) change "Requres" paragraph for std::reverse as described below:
Requires: For each non-negative integer i< distance(first, last)/2,
*next(first, i) shall be swappable with *prev(prev(last, i)).
The short-cuts where introduced to prevent this. They have the same meaning.
I strongly disagree with that. My wording clearly states that for
every pair of iterators {x, y}, to which std::iter_swap(x, y) is
applied, *x shall be swappable with *y. It imposes no requirements on
any values outside the specified range (to which std::reverse
applies).
I did not deny that. Please be careful when interpreting my response. We
must consider the requirement of an algorithm as a whole. If you start
dissecting it, this can be a different example.
In particular, the call std::reverse(a + 0, a + 2) in the
example above is well-defined in spite of the fact that a[0] is not
swappable with a[2].
Sure, I don't disagree with that. And I don't think that the wording
which is used by the standard contradicts with that.
In contrast, use of generalized forms "swappable
expression" and "ValueSwappable type" does not allow to consider
concrete subset of expressions.
I disagree with that interpretation and I think I have given enough
evidence for that.
This is clearly incorrect style of description. It would be really
funny to see such specification in an International Standard.
You are free to laugh about it ;-)
HTH & Greetings from Bremen,
Daniel Kr?gler
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]