Type Functors

[desktop]

I have this class:

class test {
public:
int getpp()
{
return pp;
}

void setpp(int i) {
pp = i;
}
private:
int pp;
};
Now I would like to insert it into a set:

std::set<test, std::less<test my_set;
test t1;
my_set.insert(t1);

This does not work (missing a '<' operator) so I add the following to test:
class test {
public:
int getpp()
{
return pp;
}

void setpp(int i) {
pp = i;
}

bool operator <(test const& t) const {

return (*this).getpp() < t.getpp();
}

private:
int pp;
};

Which does not work either.

std::less implements something like:

bool operator() (T const& x, T const& y) const {
return x < y;
}
So I don't quite see why I need to define '<' in 'test' when I supply
std::less<testto my_set. It seems like double work. What is wrong in
the body of:

test::operator<(test const& t) const

[Alan Johnson]

desktop wrote:

I have this class:

class test {
public:
int getpp()
{
return pp;
}

void setpp(int i) {
pp = i;
}
private:
int pp;
};
Now I would like to insert it into a set:

std::set<test, std::less<test my_set;

std::less<Tis the default for that template parameter. You do not
need to explicitly specify it (though it doesn't hurt). The only time
you'll use the second template parameter is if your type does not
implement operator< or you want an ordering other than that imposed by
operator<. Because you are implementing operator< below you can change
this to just:

std::set<testmy_set;

test t1;
my_set.insert(t1);

This does not work (missing a '<' operator) so I add the following to test:
class test {
public:
int getpp()

This function does not change the state of the class. It should be
declared 'const':
int getpp() const

{
return pp;
}

void setpp(int i) {
pp = i;
}

bool operator <(test const& t) const {

return (*this).getpp() < t.getpp();

Without the above change, you cannot do this. operator< has been
declared const, so you cannot call non-const member functions.

}

private:
int pp;
};

Which does not work either.

std::less implements something like:

bool operator() (T const& x, T const& y) const {
return x < y;
}
So I don't quite see why I need to define '<' in 'test' when I supply
std::less<testto my_set. It seems like double work. What is wrong in
the body of:

test::operator<(test const& t) const

--
Alan Johnson

[desktop]

Alan Johnson wrote:

desktop wrote:

>I have this class:

class test {
public:
int getpp()
{
return pp;
}
void setpp(int i) {
pp = i;
}

private:
int pp;
};
Now I would like to insert it into a set:

std::set<test, std::less<test my_set;

std::less<Tis the default for that template parameter. You do not
need to explicitly specify it (though it doesn't hurt). The only time
you'll use the second template parameter is if your type does not
implement operator< or you want an ordering other than that imposed by
operator<.

The problem seems to occur when I do an insert:

test t1;
my_set.insert(t1);

as long as I don't insert I can make a set with or without specifying
std::less<testand without implementing the '<' in test.

When doing an insert I must implement the '<' operator in test and it
makes no difference if I specify std::less<testor not.

But I am not sure what to put in the body of '<'. Currently I have:

bool operator <(test const& t) const {
return (*this).getpp() < t.getpp();
}

but that was just to fill in the body.

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

On 2007-06-08 18:30, desktop wrote:

I have this class:

class test {
public:
int getpp()
{
return pp;
}

void setpp(int i) {
pp = i;
}
private:
int pp;
};
Now I would like to insert it into a set:

std::set<test, std::less<test my_set;
test t1;
my_set.insert(t1);

This does not work (missing a '<' operator) so I add the following to test:
class test {
public:
int getpp()
{
return pp;
}

void setpp(int i) {
pp = i;
}

bool operator <(test const& t) const {

return (*this).getpp() < t.getpp();
}

private:
int pp;
};

Which does not work either.

std::less implements something like:

bool operator() (T const& x, T const& y) const {
return x < y;
}
So I don't quite see why I need to define '<' in 'test' when I supply
std::less<testto my_set. It seems like double work.

By using std::less as the comparator in the set you say that you want
the objects sorted using your < operator, (since std::less will call
your < operator).

--
Erik Wikström

[Rolf Magnus]

desktop wrote:

std::less implements something like:

bool operator() (T const& x, T const& y) const {
return x < y;
}
So I don't quite see why I need to define '<' in 'test' when I supply
std::less<testto my_set. It seems like double work.

You just provided the reason. std::less uses operator<, so you need to have
an operator< for your class.

What is wrong in the body of:

test::operator<(test const& t) const

It uses a non-const member function (getpp) on a const object.

[V.R. Marinov]

On Jun 8, 8:10 pm, desktop <[e-mail]:

The problem seems to occur when I do an insert:

test t1;
my_set.insert(t1);

as long as I don't insert I can make a set with or without specifying
std::less<testand without implementing the '<' in test.

When doing an insert I must implement the '<' operator in test and it
makes no difference if I specify std::less<testor not.

OK. So std::set<sorts the elements when they are inserted. In order
to sort them it needs
a criteria. The default criteria used by std::sort is the template
function (or functor/function object) called std::less<>. Here is how
std::less<might look like:

template <class _Tp>
struct less : public binary_function<_Tp, _Tp, bool>
{
bool
operator()(const _Tp& __x, const _Tp& __y) const
{ return __x < __y; }
};

So as you can see the std::less<testuses the < operator.
So *you* need to provide < operator in way possible for std::less to
use it.

But I am not sure what to put in the body of '<'. Currently I have:

bool operator <(test const& t) const {
return (*this).getpp() < t.getpp();
}

but that was just to fill in the body.

The thing is that if you decide to std::greater<testinstead of
std::less<test>
you would have to provide a operator.
Plus you might need to provide some more operators,
so I would suggest you create a separate header
file (e.g. test_op.h) and provide all operators needed.
This is how the < operator might look like
if you decide your class not have friend operators ;)

bool operator<(const test& lhs, const test& rhs)
{
return lhs.get() < rhs.get();
}

[V.R. Marinov]

On Jun 8, 9:19 pm, "V.R. Marinov" <[e-mail]:

OK. So std::set<sorts the elements when they are inserted. In order
to sort them it needs
a criteria. The default criteria used by std::sort is the template
function (or functor/function object) called std::less<>. Here is how
std::less<might look like:

Sorry it must be "std::set<>" instead of "std::sort()".

[Alan Johnson]

desktop wrote:

Alan Johnson wrote:

>desktop wrote:

>>I have this class:

class test {
public:
int getpp()
{
return pp;
}
void setpp(int i) {
pp = i;
}

private:
int pp;
};
Now I would like to insert it into a set:

std::set<test, std::less<test my_set;

std::less<Tis the default for that template parameter. You do not
need to explicitly specify it (though it doesn't hurt). The only time
you'll use the second template parameter is if your type does not
implement operator< or you want an ordering other than that imposed by
operator<.

The problem seems to occur when I do an insert:

test t1;
my_set.insert(t1);

as long as I don't insert I can make a set with or without specifying
std::less<testand without implementing the '<' in test.

When doing an insert I must implement the '<' operator in test and it
makes no difference if I specify std::less<testor not.

But I am not sure what to put in the body of '<'. Currently I have:

bool operator <(test const& t) const {
return (*this).getpp() < t.getpp();
}

but that was just to fill in the body.

One more, you cannot call a non-const member function from within a
const member function. To implement operator< the way you are trying to
do it, you need to make getpp const.

#include <set>

class test {
public:
int getpp() const
{
return pp;
}

void setpp(int i) {
pp = i;
}

bool operator<(const test & t) const
{
return getpp() < t.getpp();
}

private:
int pp;
};

int main()
{
std::set<testmy_set;
test t1;
my_set.insert(t1);
}

--
Alan Johnson

[desktop]

V.R. Marinov wrote:

On Jun 8, 8:10 pm, desktop <[e-mail]:

>The problem seems to occur when I do an insert:

test t1;
my_set.insert(t1);

as long as I don't insert I can make a set with or without specifying
std::less<testand without implementing the '<' in test.

When doing an insert I must implement the '<' operator in test and it
makes no difference if I specify std::less<testor not.

OK. So std::set<sorts the elements when they are inserted. In order
to sort them it needs
a criteria. The default criteria used by std::sort is the template
function (or functor/function object) called std::less<>. Here is how
std::less<might look like:

template <class _Tp>
struct less : public binary_function<_Tp, _Tp, bool>
{
bool
operator()(const _Tp& __x, const _Tp& __y) const
{ return __x < __y; }
};

So as you can see the std::less<testuses the < operator.
So *you* need to provide < operator in way possible for std::less to
use it.

>But I am not sure what to put in the body of '<'. Currently I have:

bool operator <(test const& t) const {
return (*this).getpp() < t.getpp();
}

but that was just to fill in the body.

The thing is that if you decide to std::greater<testinstead of
std::less<test>
you would have to provide a operator.
Plus you might need to provide some more operators,
so I would suggest you create a separate header
file (e.g. test_op.h) and provide all operators needed.
This is how the < operator might look like
if you decide your class not have friend operators ;)

bool operator<(const test& lhs, const test& rhs)
{
return lhs.get() < rhs.get();
}

I get an error that the operator must take exactly one argument. But I
still don't understand how each of my test objects get a unique key that
the std::less function can use to insert the object the correct place.

[V.R. Marinov]

On Jun 9, 12:40 am, desktop <[e-mail]:

I get an error that the operator must take exactly one argument.

If you decide that your operator should be a member
function of the test class, you don't need the second argument.
Because every member function gets as a first ("hidden")
argument a pointer to the current object AKA *this.
So all you need is to specify the second argument only.

struct test{
...
bool operator<(const test& rhs) const
{
return this->pp < rhs.pp;
}
};

OTOH if you decide to use a global function (not a member function of
class test)
You need to point out both arguments. Note that the global function
does not have
access to the private/protected variable pp.

bool operator<(const test& lhs, const test& rhs)
{
return lhs.getpp() < rhs.getpp();
}

But I
still don't understand how each of my test objects get a unique key that
the std::less function can use to insert the object the correct place.

This is implementation specific.

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

On 2007-06-08 23:40, desktop wrote:

V.R. Marinov wrote:

>On Jun 8, 8:10 pm, desktop <[e-mail]:

>>The problem seems to occur when I do an insert:

test t1;
my_set.insert(t1);

as long as I don't insert I can make a set with or without specifying
std::less<testand without implementing the '<' in test.

When doing an insert I must implement the '<' operator in test and it
makes no difference if I specify std::less<testor not.

OK. So std::set<sorts the elements when they are inserted. In order
to sort them it needs
a criteria. The default criteria used by std::sort is the template
function (or functor/function object) called std::less<>. Here is how
std::less<might look like:

template <class _Tp>
struct less : public binary_function<_Tp, _Tp, bool>
{
bool
operator()(const _Tp& __x, const _Tp& __y) const
{ return __x < __y; }
};

So as you can see the std::less<testuses the < operator.
So *you* need to provide < operator in way possible for std::less to
use it.

>>But I am not sure what to put in the body of '<'. Currently I have:

bool operator <(test const& t) const {
return (*this).getpp() < t.getpp();
}

but that was just to fill in the body.

The thing is that if you decide to std::greater<testinstead of
std::less<test>
you would have to provide a operator.
Plus you might need to provide some more operators,
so I would suggest you create a separate header
file (e.g. test_op.h) and provide all operators needed.
This is how the < operator might look like
if you decide your class not have friend operators ;)

bool operator<(const test& lhs, const test& rhs)
{
return lhs.get() < rhs.get();
}

I get an error that the operator must take exactly one argument. But I
still don't understand how each of my test objects get a unique key that
the std::less function can use to insert the object the correct place.

There is no unique key, the tree does not need any key. All the tree/
algorithm is concerned with is nodes and in connecting them in a
specific order, this order is determined by comparing the value of each
node with the value of all the other nodes. and This is where the <
operator comes in, it compares a value with another and tells the tree
if it is greater or less than the other, and from that information a
decision is made of where to place the node.

This is why you can store anything in a set/map since the container does
not care what it is, just it's relation (as defined by a comparison
operation) to the other stuff you put in. From this we can see that the
difference between a set and a map is quite small, the only difference
is that in a map you insert a key-value pair and perform all comparisons
on the key, whereas in the set you insert only the value and perform all
the comparisons on that (you can think of it as a map with a key-key pair).

--
Erik Wikström

[V.R. Marinov]

On Jun 9, 12:40 am, desktop <[e-mail]:

But I
still don't understand how each of my test objects get a unique key that
the std::less function can use to insert the object the correct place.

On Jun 9, 1:50 am, Erik Wikström <[e-mail]:

There is no unique key, the tree does not need any key. All the tree/
algorithm is concerned with is nodes and in connecting them in a
specific order, this order is determined by comparing the value of each
node with the value of all the other nodes. and This is where the <
operator comes in, it compares a value with another and tells the tree
if it is greater or less than the other, and from that information a
decision is made of where to place the node.

And there is that thing called Strict Weak Ordering that allows the
algorithm to check if the key that's to be inserted is unique.
So you don't need to provide the '==' operator. Given
Strict weak ordering is enforced the equality of two operands can
be proven like that:
if (!(a<b || b<a))
// a==b

[desktop]

Erik Wikström wrote:

On 2007-06-08 23:40, desktop wrote:

>V.R. Marinov wrote:

>>On Jun 8, 8:10 pm, desktop <[e-mail]:

The problem seems to occur when I do an insert:

test t1;
my_set.insert(t1);

as long as I don't insert I can make a set with or without specifying
std::less<testand without implementing the '<' in test.

When doing an insert I must implement the '<' operator in test and it
makes no difference if I specify std::less<testor not.

OK. So std::set<sorts the elements when they are inserted. In order
to sort them it needs
a criteria. The default criteria used by std::sort is the template
function (or functor/function object) called std::less<>. Here is how
std::less<might look like:

template <class _Tp>
struct less : public binary_function<_Tp, _Tp, bool>
{
bool
operator()(const _Tp& __x, const _Tp& __y) const
{ return __x < __y; }
};

So as you can see the std::less<testuses the < operator.
So *you* need to provide < operator in way possible for std::less to
use it.

But I am not sure what to put in the body of '<'. Currently I have:

bool operator <(test const& t) const {
return (*this).getpp() < t.getpp();
}

but that was just to fill in the body.

The thing is that if you decide to std::greater<testinstead of
std::less<test>
you would have to provide a operator.
Plus you might need to provide some more operators,
so I would suggest you create a separate header
file (e.g. test_op.h) and provide all operators needed.
This is how the < operator might look like
if you decide your class not have friend operators ;)

bool operator<(const test& lhs, const test& rhs)
{
return lhs.get() < rhs.get();
}

I get an error that the operator must take exactly one argument. But I
still don't understand how each of my test objects get a unique key
that the std::less function can use to insert the object the correct
place.

There is no unique key, the tree does not need any key. All the tree/
algorithm is concerned with is nodes and in connecting them in a
specific order, this order is determined by comparing the value of each
node with the value of all the other nodes. and This is where the <
operator comes in, it compares a value with another and tells the tree
if it is greater or less than the other, and from that information a
decision is made of where to place the node.

I have implemented insert as described in Cormen section 13:
my_red_black_tree::insert(value_type const& e) {

....
....

if (e == value[x]) {
return std::make_pair(x, false);
}
if (e < value[x]) {
x = left[x];
}
else {
x = right[x];
}
....
....
}

Which does a lot of comparisons based on the key 'e' (have only shown a
fragment of the code). Since set does only support unique keys it
returns if 'e' is already in the tree.

It all works fine if I only use integers. But if I try to insert my
'test' objects I somehow need to extract an int key and use that as 'e'
to do the comparison.

I know this is not correct and that insert should somehow use std::less
instead and each time a '<' appears in the code call this operator in
the 'test' object. But I have some difficulty seeing how it actually works.

Another thing besides from '<' it also seems that '==' should be defined.

[desktop]

V.R. Marinov wrote:

On Jun 9, 12:40 am, desktop <[e-mail]:

>I get an error that the operator must take exactly one argument.

If you decide that your operator should be a member
function of the test class, you don't need the second argument.
Because every member function gets as a first ("hidden")
argument a pointer to the current object AKA *this.
So all you need is to specify the second argument only.

struct test{
...
bool operator<(const test& rhs) const
{
return this->pp < rhs.pp;
}
};

OTOH if you decide to use a global function (not a member function of
class test)
You need to point out both arguments. Note that the global function
does not have
access to the private/protected variable pp.

bool operator<(const test& lhs, const test& rhs)
{
return lhs.getpp() < rhs.getpp();
}

>But I
still don't understand how each of my test objects get a unique key that
the std::less function can use to insert the object the correct place.

This is implementation specific.

But I am doing the implementation from scratch so this is what I am
trying to figure out. In set no duplicate keys are allowed. So each time
I make an 'test' object that I would like to insert in the tree I would
like to generate an unique key for each test object.

I have also considered to make the comparison between 2 objects instead
of a number in the object like:

test t1;
test t2;

t1 < t2;

where '<' is defined like

bool operator<(const test& t) const
{
return (*this) < t;
}

then I just compare the pointers to t and this, since no two pointers
can be identical to 2 different objects this should also work.

[Charles Bailey]

On 2007-06-09, desktop <ff*@sss.comwrote:

>
test t1;
test t2;

t1 < t2;

where '<' is defined like

bool operator<(const test& t) const
{
return (*this) < t;
}

then I just compare the pointers to t and this, since no two pointers
can be identical to 2 different objects this should also work.

Assuming this is "bool test::operator<(const test& t) const" then this
function looks very recursive.

If you mean:
bool test::operator<(const test& t) const
{
return this < &t;
}

Even if this did not, in general, cause undefined behaviour it would
still noe work, as code like this fragment should not assert as t1 and
t2 should have the same value:

test t1;
test t2(t1);

assert(!(t1 < t2));
assert(!(t2 < t1));

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

On 2007-06-09 09:24, desktop wrote:

Erik Wikström wrote:

>On 2007-06-08 23:40, desktop wrote:

>>V.R. Marinov wrote:
On Jun 8, 8:10 pm, desktop <[e-mail]:

The problem seems to occur when I do an insert:
>
test t1;
my_set.insert(t1);
>
as long as I don't insert I can make a set with or without specifying
std::less<testand without implementing the '<' in test.
>
When doing an insert I must implement the '<' operator in test and it
makes no difference if I specify std::less<testor not.

OK. So std::set<sorts the elements when they are inserted. In order
to sort them it needs
a criteria. The default criteria used by std::sort is the template
function (or functor/function object) called std::less<>. Here is how
std::less<might look like:

template <class _Tp>
struct less : public binary_function<_Tp, _Tp, bool>
{
bool
operator()(const _Tp& __x, const _Tp& __y) const
{ return __x < __y; }
};

So as you can see the std::less<testuses the < operator.
So *you* need to provide < operator in way possible for std::less to
use it.

But I am not sure what to put in the body of '<'. Currently I have:
>
bool operator <(test const& t) const {
return (*this).getpp() < t.getpp();
}
>
but that was just to fill in the body.

The thing is that if you decide to std::greater<testinstead of
std::less<test>
you would have to provide a operator.
Plus you might need to provide some more operators,
so I would suggest you create a separate header
file (e.g. test_op.h) and provide all operators needed.
This is how the < operator might look like
if you decide your class not have friend operators ;)

bool operator<(const test& lhs, const test& rhs)
{
return lhs.get() < rhs.get();
}

I get an error that the operator must take exactly one argument. But I
still don't understand how each of my test objects get a unique key
that the std::less function can use to insert the object the correct
place.

There is no unique key, the tree does not need any key. All the tree/
algorithm is concerned with is nodes and in connecting them in a
specific order, this order is determined by comparing the value of each
node with the value of all the other nodes. and This is where the <
operator comes in, it compares a value with another and tells the tree
if it is greater or less than the other, and from that information a
decision is made of where to place the node.

I have implemented insert as described in Cormen section 13:
my_red_black_tree::insert(value_type const& e) {

...
...

if (e == value[x]) {
return std::make_pair(x, false);
}
if (e < value[x]) {
x = left[x];
}
else {
x = right[x];
}
...
...
}

Which does a lot of comparisons based on the key 'e' (have only shown a
fragment of the code). Since set does only support unique keys it
returns if 'e' is already in the tree.

It all works fine if I only use integers. But if I try to insert my
'test' objects I somehow need to extract an int key and use that as 'e'
to do the comparison.

Do you understand how templates work? If not you need to read up on that
before you can get any further. I don't know how Cormen did but if you
are lucky you should be able to just replace any mentioning of int with
T and it should work. If I were you I would consider trying to create a
simpler generic container first (like a vector) since you then don't
have to bother with the Red-Black tree problem along with the problem of
creating a generic container.

--
Erik Wikström