std::set<> and predicates

[Rune Allnor]

Hi all.

I am a bit confused about std::set<> and associated predicates.
I have a std::set in my application where the predicate works
as expected when tested in isolation, but where the items inserted
in the set don't match the predicate, that is, the test

class predicate : public std::less {/*...*/};
predicate p;
std::set<size_t> s(p);
// Insert elements
std::set<size_t>::iterator i = s.begin();
std::set<size_t>::iterator j = i; j++;

bool b = p(*i,*j); // Should be true

results in b == false. The only reason I can think of why this
can happen is that std::set<size_t> actually uses some other
predicate to order its elements than I want it to do.

When I look up predicates in Josuttis' book on the C++ Standard
Library,
I find a rather naive predicate *function* defined on page 124.

When I look up in Stroustrup's The C++ Programming Language,
I fond a function *object* that inherits with template parameters
from
one of the predicates defined in header <functional>.

I suspect this might be the problem, that the way I let the predicate
class inherit from std::less<> is flawed.

But I can't find any descriptions of the template arguments.

Are there any obvious pitfalls I have missed here? What are the
differences between predicate _functions_ and _function_objects_?
For some reason I couldn't get std::set<> to accept the object
function unless the class inherited from std::less.

Could somebody please provide links to useful information on the
template arguments for std::less<>?

Thanks in advance,

Rune

 

[Alf P. Steinbach]

* Rune Allnor:

Are there any obvious pitfalls I have missed here?

Make sure that for any values A, B and C your predicate ensures that A<B && B<C
implies A<C, and that A<C implies !(C<A).


Cheers & hth.,

- Alf

 

[James Kanze]

I am a bit confused about std::set<> and associated
predicates. I have a std::set in my application where the
predicate works as expected when tested in isolation, but
where the items inserted in the set don't match the predicate,
that is, the test

class predicate : public std::less {/*...*/};
predicate p;
std::set<size_t> s(p);
// Insert elements
std::set<size_t>::iterator i = s.begin();
std::set<size_t>::iterator j = i; j++;

bool b = p(*i,*j); // Should be true

Knowing nothing about p, it's impossible to say much. But two
things are obvious: as declared above, your set doesn't use
predicate as an ordering function, it uses std::less<size_t>;
and if it did use predicate, the above expression could never be
true.

Also, even the extract of your code is illegal, since you can't
derive from std::less (which is a template, not a class).

[...]

Could somebody please provide links to useful information on
the template arguments for std::less<>?

There's only one, the type to be compared. What more
information do you need?

 

[Rune Allnor]

Knowing nothing about p, it's impossible to say much.   But two
things are obvious: as declared above, your set doesn't use
predicate as an ordering function, it uses std::less<size_t>;

Why is that?

According to Josuttis' table 6.20, the constructor std::set<>::set()
with the predicate as argument should use the predicate as ordering
criterion.

and if it did use predicate, the above expression could never be
true.

As I understand std::set and its predicates, the ordering of the
elements in the set is such that

less(*i,*j) == true

if i and j are iterators and initailized as above. If you are
right, I would have missed something very fundamental. Could you
elaborate, please?

Also, even the extract of your code is illegal, since you can't
derive from std::less (which is a template, not a class).

Actually, in my code the inheritance is

class p : public std::less<size_t> {
};

So how should this be done?

Rune

 

[Rune Allnor]

* Rune Allnor:




Make sure that for any values A, B and C your predicate ensures that A<B && B<C
implies A<C, and that A<C implies !(C<A).

As I said, the predicate works as expected when tested
in isolation outside the std::set<>.

Rune

 

[Francesco S. Carta]

As I said, the predicate works as expected when tested
in isolation outside the std::set<>.

How do you tell that it is not working when used by set?

The following code, adapted from your OP, proves that it works:
-------
#include <iostream>
#include <set>

class predicate : public std::less<size_t> {};

int main()
{
predicate p;
std::set<size_t> s(p);
s.insert(20);
s.insert(10);
std::set<size_t>::iterator i = s.begin();
std::set<size_t>::iterator j = i;
j++;
std::cout << "*i == " << *i << std::endl;
std::cout << "*j == " << *j << std::endl;
if(p(*i,*j)) {
std::cout << "true" << std::endl;
} else {
std::cout << "false" << std::endl;
}
}

 

[Rune Allnor]

How do you tell that it is not working when used by set?

The following code, adapted from your OP, proves that it works:

With your example, the user-defined prediacet gives the same
result as with the default predicate, so one can not tell which
predicate was actually used.

With a slight modification, you can see the problem (VS2008, if
that should matter):

-------
#include <iostream>
#include <set>

class predicate : public std::less<size_t>
{
public:
// Is this the correct function signatiure?
bool operator()(const size_t& a, const size_t& b)
{
return a > b; // Make sure the result is different
// with this prediacate compared to the
// default std::less<size_t> predicate
}
};


int main()
{
predicate p;
std::set<size_t> s(p);
s.insert(20);
s.insert(10);
std::set<size_t>::iterator i = s.begin();
std::set<size_t>::iterator j = i;
j++;
std::cout << "*i == " << *i << std::endl;
std::cout << "*j == " << *j << std::endl;
if(p(*i,*j)) {
std::cout << "true" << std::endl;
} else {
std::cout << "false" << std::endl;
}
return 0;
}
-------

Output:

-------
*i == 10
*j == 20
false
-------

So the elements are contained in the set in the same order
as with the default predicate, but the predicate test
conforms to expectations.

Of course, formally, one can specify the predicate as a
template parameter, like in this variation:

-------
#include <iostream>
#include <set>

class predicate : public std::less<size_t>
{
public:
bool operator()(const size_t& a, const size_t& b)
{
return a > b; // Make sure the result is different
// with this prediacate than with the
// default std::less<size_t> predicate
}
};


int main()
{
predicate p;
std::set<size_t,predicate> s(p);
s.insert(20);
s.insert(10);
std::set<size_t,predicate>::iterator i = s.begin();
std::set<size_t,predicate>::iterator j = i;
j++;
std::cout << "*i == " << *i << std::endl;
std::cout << "*j == " << *j << std::endl;
if(p(*i,*j)) {
std::cout << "true" << std::endl;
} else {
std::cout << "false" << std::endl;
}
return 0;
}
-------

in which case the result is as expected:

-------
*i == 20
*j == 10
true
-------

However, I can't use this variant (at least I don't know how),
because of certain properties with the predicate class
(quickly sketched directly into newsreader):

class predicate : public std::less<size_t>
{
public:
predicate(std::vector<size_t>& idxv,std::vector<someClass>&
itmv):
idxv_(idxv), itmv_(idxv){}

bool operator()(const size_t& a, const size_t& b)
{
return itmv_[idxv_[a]] > itmv_[idxv_];
}
private:
protected(){};
std::vector<size_t>& idxv_;
std::vector<someClass>& itmv_;
};

The predicate uses a nested look-up through the vectors idxv_
and itmv_ to find the actual values (properties of some sonmeClass
objects) to be compared. In order to ensure that instances of
the predicate always have access to two such vectors, I have
decided to hide the 'naive' ctor and only publish the initializing
ctor.

Because of this, I am not able to use the predicate as part of
the type declaration of the std::set, since the ctor of the set
wants access to the 'naive' ctor of the predicate.

So I guess I have two alternative questions:

1) How to use std::set<> with a predicate that is not part
of the type declaration?
2) How to use std::set<size_t,predicate> where the only
accessible ctor of the predicate takes arguments?

Rune

 

[Rune Allnor]

class predicate : public std::less<size_t>
{
public:
         predicate(std::vector<size_t>& idxv,std::vector<someClass>&
itmv):
             idxv_(idxv), itmv_(idxv){}

        bool operator()(const size_t& a, const size_t& b)
        {
                return itmv_[idxv_[a]] > itmv_[idxv_];
         }
private:
         protected(){};

This should, of course, be

private:
predicate(){};

Rune

 

[Alf P. Steinbach]

* Rune Allnor:

class predicate : public std::less<size_t>
{
public:
predicate(std::vector<size_t>& idxv,std::vector<someClass>&
itmv):
idxv_(idxv), itmv_(idxv){}

bool operator()(const size_t& a, const size_t& b)
{
return itmv_[idxv_[a]] > itmv_[idxv_];
}
private:
protected(){};

This should, of course, be

private:
predicate(){};

Rune

Have you considered how std::set stores the comparator object internally?

In C++ objects are often handled by value, not by reference, and then there is
the problem of "slicing" whereby a copying only retains a base class part...



Cheers & hth.,

- Alf ( he he )

 

[Victor Bazarov]

[..]
So I guess I have two alternative questions:

1) How to use std::set<> with a predicate that is not part
of the type declaration?

There is no way. Internally, when the set is constructed, it will
disregard the predicate you give it if it is not of the type specified.
Try not deriving your predicate from 'std::less' and you're going to
see why.

Why do you need to derive? By doing that you just mask the problem.
The 'operator()' is not a virtual function. What happens is that your
predicate is converted to 'std::less' and 'std::less:perator()' is
used for comparison, and not your implementation.

So, remove the base class from your predicate, and make it work.

2) How to use std::set<size_t,predicate> where the only
accessible ctor of the predicate takes arguments?

I don't understand what the problem is.

#include <iostream>
#include <set>

class predicate
{
double d;
public:
predicate(double d_) : d(d_) {}
// Is this the correct function signatiure?
bool operator()(const size_t& a, const size_t& b)
{
return a > b; // Make sure the result is different
// with this prediacate compared to the
// default std::less<size_t> predicate
}
};

typedef std::set<size_t,predicate> myset;

int main()
{
predicate p(3.1415926);
myset s(p);
s.insert(20);
s.insert(10);
myset::iterator i = s.begin();
myset::iterator j = i;
j++;
std::cout << "*i == " << *i << std::endl;
std::cout << "*j == " << *j << std::endl;
if(p(*i,*j)) {
std::cout << "true" << std::endl;
} else {
std::cout << "false" << std::endl;
}
return 0;
}


Output:
*i == 20
*j == 10
true

V

 

[Rune Allnor]

[..]
So I guess I have two alternative questions:

1) How to use std::set<> with a predicate that is not part
   of the type declaration?

There is no way.

OK... I'll have to contemplate the various technical aspects
why this has to be true.

 Internally, when the set is constructed, it will
disregard the predicate you give it if it is not of the type specified.
  Try not deriving your predicate from 'std::less' and you're going to
see why.

Why do you need to derive?  By doing that you just mask the problem.
The 'operator()' is not a virtual function.  What happens is that your
predicate is converted to 'std::less' and 'std::less:perator()' is
used for comparison, and not your implementation.

So, remove the base class from your predicate, and make it work.

My first attempt did not inherit from std::less<> at all, but
the compiler issued a type error, about not being able to convert

I don't understand what the problem is.

Now that I see your solution, I think it is a matter of me
not being sufficiently aware of when things are declared and
when they are initialized.

But then, once you show how it's done it's rather obvious.

Thanks.

Rune

 

[Michael Doubez]

Why is that?

According to Josuttis' table 6.20, the constructor std::set<>::set()
with the predicate as argument should use the predicate as ordering
criterion.

set<> constructor keeps a copy of the Comparator. In your case, you
have slicing at the less<size_t> base of predicate.

I could not find the related section in the standard. I will post it
if/when I find it.

As I understand std::set and its predicates, the ordering of the
elements in the set is such that

less(*i,*j) == true

if i and j are iterators and initailized as above. If you are
right, I would have missed something very fundamental. Could you
elaborate, please?


Actually, in my code the inheritance is

class p : public std::less<size_t> {

};

So how should this be done?

A way to do it is:

class predicate{
bool operator(size_t lhs,size_t rhs)const
{ /* ... */ }
};

std::set<size_t,predicate> p;

 

[Michael Doubez]

set<> constructor keeps a copy of the Comparator. In your case, you
have slicing at the less<size_t> base of predicate.

I could not find the related section in the standard. I will post it
if/when I find it.

I could not locate it and the standard says that it is 'using the
specified comparison object' which is IMHO a bit misleading because we
could think it is using the underlying object. The only hint that I
found is that set<>::key_comp() and set<>::value_comp() returns an
object of type Compare and we could infer from that it must have a
value semantic. IMO it fits with the design of the STL.

The new standard proposal doesn't modify the wording.

However std::less<> doesn't have virtual functions and is not intended
as a base class. You don't even need to make it an explicit binary
predicate (defining result_type ... ) because 25.3 states that is will
be used as a function object.

 

[Rune Allnor]

set<> constructor keeps a copy of the Comparator. In your case, you
have slicing at the less<size_t> base of predicate.

I could not find the related section in the standard. I will post it
if/when I find it.

No need to. I have already solved the problem with the help of
Victor's code. There were some other issues about the ctor of the
predicate, as my implementation required a copy-constructor of the
predicate which I had initially disabled. It took a little time to
sort that one out, but now everything works as desired.

Rune