STL: insert and find confusion

[Denis Remezov]

Two elements a and b are equal if less(a,b) and less(b,a) are both false.

^^^^^
Equivalent

It is conceivable that maps and sets using a strcmp style compare function


Wait a sec. Are you sure the above is correct? Should it be

bool Person:perator '<'(const Person & p) const
{
if (this->age < p.age)
return true;
if (this->salary > p.salary)
return false;
if (this->salary < p.salary)
return true;
return false;
}

No, that wouldn't work either. Here is my take:

bool Person:perator <(Person const& rhs) const {
return age < rhs.age? true :
rhs.age < age? false :
salary < rhs.salary;
}

Denis

 

[Denis Remezov]

I'm a bit confused as to how the STL set works with the <setname>.insert()
and <setname>.find() functions

Compiler used : CodeWarrior 5.0

My intial interpretation was that I needed to overload the '<' for the
insert() and '==' operator for find() however it doesn't seem to be the case

In fact it seems to only need to overload the '<' operator for BOTH
functions (it simply ignores the '==' operator)

for exemple if I have set<Person> onePerson
where the Classe Person simply contains an int age and float salary;

So in order to insert

onePerson.insert(tmpPerson)

I need to overload '<'

which can simply be done

by doing

bool Person:perator '<'(const Person & p) const
{
if (this->age < p.age || this->salary < p.salary)
return true;
else
return false;
}

now If I want to check if a Person exists in my set I would do
setPerson.find(tmpPerson) //which returns an iterator to the element if it
found

but the condition for two Persons is if the age and the salary are both
equal , so how can I implement it into the "," operator without affecting my
insertion process?

To establish an element order, the standard associative containers
rely on a comparison object, which behaves in a way "similar" to operator <.
As Siemel pointed out, two keys x and y are then equivalent if
!cmp(x, y) && !cmp(y, x). Operator == is not used.
By default, the comparison object is an object of type std::less, which
actually calls operator <. You can parameterise your container by an explicit
comparison predicate, or you can use the default, in which case, as you have
seen, you need to define operator < on the keys (class Person).

In either case, there is a requirement of strict weak ordering for the
comparison predicate (you have to fulfill it). You can read about it,
e.g., here:
http://www.sgi.com/tech/stl/StrictWeakOrdering.html

You may find that an easier (than doing it ad hoc) way to write this
predicate in a multidimensional case is to first think of a rule
for scanning or iterating through an abstract multidimensional matrix
of all possible keys (e.g. ||age, salary|| ).

Denis

 

[Rom]

I'm a bit confused as to how the STL set works with the <setname>.insert()
and <setname>.find() functions

Compiler used : CodeWarrior 5.0

My intial interpretation was that I needed to overload the '<' for the
insert() and '==' operator for find() however it doesn't seem to be the case

In fact it seems to only need to overload the '<' operator for BOTH
functions (it simply ignores the '==' operator)


for exemple if I have set<Person> onePerson
where the Classe Person simply contains an int age and float salary;

So in order to insert

onePerson.insert(tmpPerson)

I need to overload '<'

which can simply be done

by doing

bool Person:perator '<'(const Person & p) const
{
if (this->age < p.age || this->salary < p.salary)
return true;
else
return false;
}

now If I want to check if a Person exists in my set I would do
setPerson.find(tmpPerson) //which returns an iterator to the element if it
found

but the condition for two Persons is if the age and the salary are both
equal , so how can I implement it into the "," operator without affecting my
insertion process?

Is there any other way to efficiently insert and find items in a set ?

something else I tried but didn't work

set<Person>::iterator iter = find_if(onePerson.begin, onePerson.end, Exists)

thanks for any help

 

[Rom]

but the condition for two Persons is if the age and the salary are both
equal , so how can I implement it into the "," operator without affecting my
insertion process?

ooops this should have been the "<" operator instead of ","

 

[Siemel Naran]

I'm a bit confused as to how the STL set works with the <setname>.insert()
and <setname>.find() functions

My intial interpretation was that I needed to overload the '<' for the
insert() and '==' operator for find() however it doesn't seem to be the case

In fact it seems to only need to overload the '<' operator for BOTH
functions (it simply ignores the '==' operator)

Two elements a and b are equal if less(a,b) and less(b,a) are both false.
It is conceivable that maps and sets using a strcmp style compare function

bool Person:perator '<'(const Person & p) const
{
if (this->age < p.age || this->salary < p.salary)
return true;
else
return false;
}

Wait a sec. Are you sure the above is correct? Should it be

bool Person:perator '<'(const Person & p) const
{
if (this->age < p.age)
return true;
if (this->salary > p.salary)
return false;
if (this->salary < p.salary)
return true;
return false;
}

In your set, the Persons will be sorted by age then salary.

 

[Siemel Naran]

Siemel Naran wrote:

Sorry, made a cut and paste typo. The above line should be

if (this->age > p.age)

No, that wouldn't work either. Here is my take:

bool Person:perator <(Person const& rhs) const {
return age < rhs.age? true :
rhs.age < age? false :
salary < rhs.salary;
}

Thanks for pointing out!

 

[Andrew Koenig]

So in order to insert

onePerson.insert(tmpPerson)

I need to overload '<'

which can simply be done

by doing

bool Person:perator '<'(const Person & p) const
{
if (this->age < p.age || this->salary < p.salary)
return true;
else
return false;
}

No it can't. You must define < so that it is a strict order relation, and
this definition doesn't do it. To see why, consider two people:

p1: age = 20, salary = 50
p2: age = 18, salary = 60

Now p1 < p2 (because p1.salary < p2.salary) and p2 < p1 (because p2.age <
p1.age).

Here's one way of doing it that will work:

bool Person:perator< (const Person& p) const
{
return this->age < p.age || (this->age == p.age && this->salary <
p.salary);
}

The parentheses in the "return" statement aren't really necessary, but I
think they clarify the code.

 

[Rom]

Sorry, made a cut and paste typo. The above line should be

if (this->age > p.age)

I assume you mean this

if (this->age < p.age)
return true;
if (this->age > p.age)

return false;
if (this->salary < p.salary)
return true;
return false;



Ok I see the ordering being made first on the age and then on the salary,
now if I apply what you said concerning equivalency of two elements

"Two elements a and b are equal if less(a,b) and less(b,a) are both false."



and let say I have a set declared set<Person> setPerson;



and want to find onePerson using setPerson.find(onePerson);



Does it mean that my compiler implicitly does two comparisons : a < b
followed by b < a and if both results are false then this implies that a ==
b (which makes sens) ?

 

[Siemel Naran]

"Two elements a and b are equal if less(a,b) and less(b,a) are both false."

and let say I have a set declared set<Person> setPerson;
and want to find onePerson using setPerson.find(onePerson);

Does it mean that my compiler implicitly does two comparisons : a < b
followed by b < a and if both results are false then this implies that a ==
b (which makes sens) ?

Yes, this is true in principle. But when scanning the binary tree for an
element, do they do two comparisons on every node.value? I was thinking
about it, and in the worst case the answer seems to be yes.