binary_search of a vector of structures: Windows compilation failure!

i think you have the operators mixed up
it seems that you defined the () operator but actually ment to define < ?

Seems to be a VC++ 2008 issue - both VC++ 2005 and VC++ 2008 compile that snippet without any errors. And yes, I agree it's weird...

momi_sabag:

Thanks for commenting - I don't have the operators mixed up because operator() provides the necessary information as to whether one Human is "less than" another.

jkr:

"Seems to be a VC++ 2008 issue - both VC++ 2005 and VC++ 2008 compile that snippet without any errors"

I think there might be a typo there :)  Are you saying it does or doesn't work in 2008 on your machine?  I cannot get this to compile in VS 2005 - I don't have 2003 installed...did you try it on 2003 at all?

Either way, I still have a big problem.  I need to be able to binary_search my vector for a specific Human - how can I acheive this?  Any suggestions (anyone)?

Yes, it is a typo - should have been "Seems to be a VC++ 2008 issue - both VC++ 2005 and VC++ 2010 compile that snippet without any errors". And no, I don't have 2008 here to double-check that...

Thanks phoffric!

Before I checked back on this question I actually found a different workaround for VS 2008, which is to define all three of the operator() overloads (two of which you have commented in your code, the final required one being what you added).  I don't know exactly why this works (and made the decision that taking the time to learn how it works would not be of long term benefit) but it does.

However, your solution to use just one operator() is equally as good and may in fact save confusion as to why the three overloads are provided..

Thanks again!

Curiously, my suggestion above only works when the parameters are const, otherwise the same error is encountered.  Hmm...most likely a bug in the STL implementation.

In software engineering, less is more (unless you are a financial bean counter for the company to demonstrate progress to the customer). Nevertheless, I am curious to see your "more" approach (especially the one that still does not work, and time-permitting (which I have little of once this holiday period goes by), I will see if there is a real problem or just another VS 2008 fluke. So, if you want to post a working and non-compilable program, I'll take a look (eventually) and run them on VS 2010.

OK.  Appreciate in advance any time you spend looking into this :)

This does not work on VS 2008:

#include <algorithm>
#include <vector>
#include <string>

using namespace std;

struct Human
{
	std::string name;
};

struct Comparator
{

   bool operator() ( const Human& lhs, const std::string& rhs )
   {
      return lhs.name < rhs;
   }
   bool operator() ( const std::string& lhs, const Human& rhs )
   {
      return lhs < rhs.name;
   }

   //bool operator() ( const Human& lhs, const Human& rhs )
   //{
   //   return lhs.name < rhs.name;
   //}
};

int main(int argc, char * argv[])
{
	std::vector<Human> vec;
	Human myHuman;
	myHuman.name = "Joe"; vec.push_back(myHuman);
	myHuman.name = "Mary"; vec.push_back(myHuman);
	myHuman.name = "ss"; vec.push_back(myHuman);
	myHuman.name = "Calterine"; vec.push_back(myHuman);
	sort(vec.begin(), vec.end(), Comparator());

	std::string nameToFind = "ss";
	bool found = binary_search( vec.begin(), vec.end(), "ss", Comparator() );

	return 0;
}

Select allOpen in new window

This does work on VS 2008:

#include <algorithm>
#include <vector>
#include <string>

using namespace std;

struct Human
{
	std::string name;
};

struct Comparator
{

   bool operator() ( const Human& lhs, const std::string& rhs )
   {
      return lhs.name < rhs;
   }
   bool operator() ( const std::string& lhs, const Human& rhs )
   {
      return lhs < rhs.name;
   }

   bool operator() ( const Human& lhs, const Human& rhs )
   {
      return lhs.name < rhs.name;
   }
};

int main(int argc, char * argv[])
{
	std::vector<Human> vec;
	Human myHuman;
	myHuman.name = "Joe"; vec.push_back(myHuman);
	myHuman.name = "Mary"; vec.push_back(myHuman);
	myHuman.name = "ss"; vec.push_back(myHuman);
	myHuman.name = "Calterine"; vec.push_back(myHuman);
	sort(vec.begin(), vec.end(), Comparator());

	std::string nameToFind = "ss";
	bool found = binary_search( vec.begin(), vec.end(), "ss", Comparator() );

	return 0;
}

Select allOpen in new window

You can see that the only difference is the presence of  bool operator() ( const Human& lhs, const Human& rhs ).

>> Curiously, my suggestion above only works when the parameters are const, otherwise the same error is encountered.  Hmm...most likely a bug in the STL implementation.

Notice that binary_search has a const in its profile.
    http://www.cplusplus.com/reference/algorithm/binary_search/?kw=binary_search
and sort does not:
    http://www.cplusplus.com/reference/algorithm/sort/?kw=sort

You should be able to remove all the const in your functors except for the const std::string&; then you will be conforming to the binary_search requirement that your functors not alter the string. This explains why you should get an error message, but it doesn't explain why you got that particular error message.

In any case, even if you do not need a const formally, there is a useful coding guideline that suggests that you use const everywhere unless you cannot. This guideline helps with maintenance and with code optimization.

=======

re: http:#a39305227 - first code listing:

The sort() is comparing two objects pointed to by the Human iterators from vec.begin() to vec.end(). Since the sort is comparing Human objects, so you need your bool operator() at line 24.

Thanks for clarifying why I need the const qualifier.  It has also provided some food for thought about code optimisation which I will go and read about...

Regarding the compilation - yes, I can see why I need bool operator() (  Human& lhs,  Human& rhs ) for the sort; my example was poor - I should have removed the call to sort() as it was not necessary to prove my point.  

I have removed the sort() and my call to binary_search() still generates compilation errors without this operator.  I am aware that the binary_search would not work correctly unless the vector was sorted, but my concern is that it won't even compile on VS 2005/2008, but does on Solaris.

If you feel so inspired, here is code that does not compile on VS 2008/2005 without this operator.  This shows that its presence provides a workaround for the problem that this question is all about, which is apparently VS 2008/2005 specific.  

The problem seems to be in xutility; if you say the code compiles in VS 2010, then perhaps this has changed between the versions?

error C2664: 'bool Comparator::operator ()(const std::string &,Human &)' : cannot convert parameter 1 from 'Human' to 'const std::string &'      c:\program files\microsoft visual studio 8\vc\include\xutility      323

error C2664: 'bool Comparator::operator ()(const std::string &,Human &)' : cannot convert parameter 1 from 'Human' to 'const std::string &'      c:\program files\microsoft visual studio 8\vc\include\xutility      325

#include <algorithm>
#include <vector>
#include <string>

using namespace std;

struct Human
{
	std::string name;
};

struct Comparator
{

   bool operator() (  Human& lhs,  const std::string& rhs )
   {
      return lhs.name < rhs;
   }
   bool operator() (  const std::string& lhs,  Human& rhs )
   {
      return lhs < rhs.name;
   }

   // Uncomment this and the code compiles!
   //bool operator() (  Human& lhs,  Human& rhs )
   //{
   //   return lhs.name < rhs.name;
   //}
};

int main(int argc, char * argv[])
{
	std::vector<Human> vec;
	myHuman.name = "Joe"; vec.push_back(myHuman);
	myHuman.name = "Mary"; vec.push_back(myHuman);
	myHuman.name = "ss"; vec.push_back(myHuman);
	myHuman.name = "Calterine"; vec.push_back(myHuman);

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

	return 0;
}

Select allOpen in new window

I may have an unused PC at home that has 2008 on it. Be back in 1-2 weeks.