Solved

binary_search with LessThanComparable prototype: compilation failure!

Posted on 2013-12-10
9
239 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 31

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 31

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
3 Use Cases for Connected Systems

Our Dev teams are like yours. They’re continually cranking out code for new features/bugs fixes, testing, deploying, testing some more, responding to production monitoring events and more. It’s complex. So, we thought you’d like to see what’s working for us.

 
LVL 33

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
 
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 31

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 33

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

Complete VMware vSphere® ESX(i) & Hyper-V Backup

Capture your entire system, including the host, with patented disk imaging integrated with VMware VADP / Microsoft VSS and RCT. RTOs is as low as 15 seconds with Acronis Active Restore™. You can enjoy unlimited P2V/V2V migrations from any source (even from a different hypervisor)

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Load and store *.pnm image file 1 86
how to understand recursion 12 226
mixing C++ & C# in Vis Studio 2013 7 176
Arduino EDI - Programming language 3 94
Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

777 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