[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 252
  • Last Modified:

binary_search with LessThanComparable prototype: compilation failure!

Ah hello.

Please consider the following code, which some may see as familiar due to my earlier questions:
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

class Human
{
public:
	Human(std::string strName, int nAge) : m_strName(strName), m_nAge(nAge) {}
	std::string GetName() const { return m_strName; }
	int GetAge() const { return m_nAge; }

	bool operator<(const Human& rhs) const { return m_strName < rhs.GetName(); }
	bool operator<(const std::string& rhs) const { return m_strName < rhs; }

protected:
	std::string m_strName;	
	int m_nAge;
};

int main(int argc, char * argv[])
{
	std::vector<Human> vec;
	vec.push_back(Human("Joe", 20));
	vec.push_back(Human("Mary", 21));
	vec.push_back(Human("Arnold", 44));
	vec.push_back(Human("Calterine", 21));
	vec.push_back(Human("Calterine", 45));

	sort(vec.begin(), vec.end());
	std::vector<Human>::iterator iter = vec.begin(), iter2 = vec.end();

	bool found = binary_search( vec.begin(), vec.end(), "Mary" );

	return 0;
}

Open in new window

I was previously using the version of binary_search which took a predicate as the fourth argument (see http://www.sgi.com/tech/stl/binary_search.html - the second prototype) but after reading more about LessThanComparable I thought I would investigate this.

On VS 2005, I get the compilation error

binary '<' : no operator found which takes a right-hand operand of type 'Human' (or there is no acceptable conversion)
could be 'built-in C++ operator<(const char [5], const char [5])'
while trying to match the argument list '(const char [5], Human)'

Open in new window


on the call to binary_search.

How can I use binary_search in this manner?

TIA
0
mrwad99
Asked:
mrwad99
  • 4
  • 3
  • 2
3 Solutions
 
ZoppoCommented:
Hi mrwad,

IMO the problem is the value passed to binary_search as last argument has to be of the same type as the elements pointed to by the iterators. I.e. at http://www.cplusplus.com/reference/algorithm/binary_search/ you can find:

val
    Value to search for in the range ...shall be a type supporting being compared with elements of the range [first,last] as either operand of operator<.

IMO you can get it work by implementing a global operator which can compare a < b in case a is a string and b a Human, i.e.:
bool operator < ( const std::string& l, const Human& r )
{
	return l < r.GetName();
}

Open in new window

Hope that helps,

ZOPPO
0
 
mrwad99Author Commented:
Hi ZOPPO, good to see you are still active on EE after all these years :)

Yes, I tried that (that is, I had the global operator and the member operator: two global operators of (const std::string& lhs, const Human& rhs) and (const Human& lhs, const std::string& rhs) is the same and removes the need for the member version) and it does indeed work.  I figured it would, since defining the global operator< is essentially the version of binary_search() which accepts a StrictWeakOrdering object, but wanted to see if there was any way I could do away with this altogether and define everything as members of the Human class...I guess there isn't, since we, when it boils down, need an operator<(Human&) within std::string to make this work, I believe...

Please correct me if this is wrong...

As a second question related to this, the documentation for StrictWeakOrdering at http://www.sgi.com/tech/stl/StrictWeakOrdering.html is very clear on what it should return:

"A Strict Weak Ordering is a Binary Predicate that compares two objects, returning true if the first precedes the second"

However, the documentation for LessThanComparable (http://www.sgi.com/tech/stl/LessThanComparable.html) does not have anything of the sort from what I can see.  So, how do I know if I am supposed to (in the example I have given) code
bool operator<(const Human& rhs) const { return m_strName < rhs.GetName(); }

Open in new window

or

bool operator<(const Human& rhs) const { return rhs.GetName() < m_strName ; }

Open in new window


Can anyone advise on this?
0
 
ZoppoCommented:
Hi mrwad99,

thanks. And well, I like it here, I think I'll stay here :o)

I agree, I don't think it's possible without such a global operator simply because there's no other way to add a less-than operator with std::string on the left side.

If you really want to keep it in one class the only way I see is to go back to the previous implementation with a compare function which can be implemented as a static class function in Human.

About the Strict Weak Ordering: Here first means the object the operator is called against, i.o.w. the this within the operator, second is rhs.

So, using the first version you posted will sort the vector by names in alphabetical order, the second one in reversed alphabetical order.

ZOPPO
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
sarabandeCommented:
to add to above comments:

IMO the problem is the value passed to binary_search as last argument has to be of the same type as the elements pointed to by the iterators

you probably already were aware that you could solve the issue by converting the search value to a Human like

bool found = binary_search( vec.begin(), vec.end(), Human("Mary", -1) );

Open in new window


by providing a second constructor which takes a const char * you could avoid the age argument.

Sara
0
 
mrwad99Author Commented:
Yes Sara I was, but thanks for participating anyway.
0
 
mrwad99Author Commented:
Thanks ZOPPO!
0
 
mrwad99Author Commented:
Umm I accepted the wrong answer there; many apologies ZOPPO - I can request CS to get it changed if you want...?
0
 
ZoppoCommented:
No problem at all :o)

Sara's comment even is a possible solution, so it's not wrong to accept it ...

Have a nice day,

best regards,

ZOPPO
0
 
sarabandeCommented:
Sara's comment even is a possible solution, so it's not wrong to accept it ...
you are very kind, ZOPPO.

thanks to both of you.

Sara
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

  • 4
  • 3
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now