comparison object's operator()() must be const

[Ralf Goertz]

Hi,

why is it necessary to declare the operator()() in a comparison object
const in order to find elements in const std::set<T>?:


#include <set>

struct cmp_int {
bool operator()(const int &x,const int &y) const //const necessary
{
return x>y;
}
};

int main()
{
const std::set<int,cmp_int> s={{47,11}};
if (s.find(815)!=s.end()) return 1;
return 0;
}

Shouldn't the std::set<int> be happy with the fact that both parameters
are const references? I guess the answer is going to be that cmp_int is
part of the const declaration and must therefore be const. But IMHO
cmp_int is not part of the *data* that the std::set holds. The const
declaration is not necessary when the std::set itself is non const. So I
could flip the order used for the comparison object every other call,
which would be devastating for both const and non const std::set.

[Chris Vine]

I didn't even know that was a requirement, but it seems a sensible
one so as to maintain referential transparency: that is, so that
ordering is correctly maintained. If the operator could mutate the
state of the object of type cmp_int of which it is a member, different
invocations of the operator with the same arguments could yield
different results. Your cmp_int type does not have non-static data
members; but it might have.

Chris

[Ralf Goertz]

Am Tue, 24 Jan 2017 16:24:34 +0000
schrieb Chris Vine <chris@cvine--nospam--.freeserve.co.uk>:

But that's exactly my point. If cmp_int were something like this:

struct cmp_int {
static bool counter;

bool operator()(const int &x,const int &y) const

{
counter=!counter;
return (counter ? x < y : x > y);
}
};

it would compile for const and non const variables of type
std::set<int,cmp_int>. So I don't see how the const declaration of the
operator helps. So why is it necessary?

[Alf P. Steinbach]

On 24.01.2017 16:50, Ralf Goertz wrote:
>
> why is it necessary to declare the operator()() in a comparison object
> const in order to find elements in const std::set<T>?:

The short answer, if I could find this requirement in the standard,
would be that the standard requires it. That's fundamentally different
from the requirement being imposed by a given implementation. It would
mean that all standard-conforming implementations had this requirement.

I can't find it though, but it seems reasonable that it's there.

Assuming it is, then regarding the /rationale/ that rule supports an
implementation where the comparison object is directly part of the
`std::set` object, instead of being dynamically allocated and just
referred to. With the comparison object as a direct part it's `const`
when the `std::set` is const. And in particular it's `const`, so that
only its `const` members can be used, in a call of a `const` `std::set`
member function such as `std::set::find`.

[snip]


Cheers & hth.,

- Alf

[Chris Vine]

On Tue, 24 Jan 2017 17:54:25 +0100
Ralf Goertz <m...@myprovider.invalid> wrote:
> Am Tue, 24 Jan 2017 16:24:34 +0000
> schrieb Chris Vine <chris@cvine--nospam--.freeserve.co.uk>:

[snip]

> > I didn't even know that was a requirement, but it seems a sensible
> > one so as to maintain referential transparency: that is, so that
> > ordering is correctly maintained. If the operator could mutate the
> > state of the object of type cmp_int of which it is a member,
> > different invocations of the operator with the same arguments could
> > yield different results. Your cmp_int type does not have
> > non-static data members; but it might have.
>
> But that's exactly my point. If cmp_int were something like this:
>
> struct cmp_int {
> static bool counter;
> bool operator()(const int &x,const int &y) const
> {
> counter=!counter;
> return (counter ? x < y : x > y);
> }
> };
>
> it would compile for const and non const variables of type
> std::set<int,cmp_int>. So I don't see how the const declaration of the
> operator helps. So why is it necessary?

So far as the ability of a const member function to mutate static
member data is concerned, or its ability to mutate global or static
data at namespace scope as well for that matter, I guess you just have
to accept that as a matter of language specification in C++ 'const' does
not mean 'pure'.

But on your larger point about std::set, on reflection I think you are
right. The requirement to maintain referential transparency for the
comparison operator type should apply irrespective of whether the
std::set object is const or not. There may be an argument that for a
non-const set, the comparison operator should be able to arbitrarily
mess around with ordering, but that doesn't seem a very good argument.
This may be just a miscellaneous wart in C++.

Chris