Solved

binary_search with LessThanComparable prototype: compilation failure!

Posted on 2013-12-10
9
234 Views
Last Modified: 2013-12-10
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
Comment
Question by:mrwad99
  • 4
  • 3
  • 2
9 Comments
 
LVL 30

Assisted Solution

by:Zoppo
Zoppo earned 166 total points
ID: 39708487
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
 
LVL 19

Author Comment

by:mrwad99
ID: 39708524
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
 
LVL 30

Assisted Solution

by:Zoppo
Zoppo earned 166 total points
ID: 39708626
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
 
LVL 32

Accepted Solution

by:
sarabande earned 84 total points
ID: 39708741
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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 19

Author Comment

by:mrwad99
ID: 39709023
Yes Sara I was, but thanks for participating anyway.
0
 
LVL 19

Author Closing Comment

by:mrwad99
ID: 39709025
Thanks ZOPPO!
0
 
LVL 19

Author Comment

by:mrwad99
ID: 39709033
Umm I accepted the wrong answer there; many apologies ZOPPO - I can request CS to get it changed if you want...?
0
 
LVL 30

Expert Comment

by:Zoppo
ID: 39709045
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
 
LVL 32

Expert Comment

by:sarabande
ID: 39709070
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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

747 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

8 Experts available now in Live!

Get 1:1 Help Now