Re: std::set<> and predicates
On 5 Okt, 13:29, "Francesco S. Carta" <entul...@gmail.com> wrote:
On 5 Ott, 12:36, Rune Allnor <all...@tele.ntnu.no> wrote:
On 5 Okt, 06:29, "Alf P. Steinbach" <al...@start.no> wrote:
* 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).
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:
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_[b]];
}
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