vector binary search with or without using function

euklid

Hi,
I am trying to use binary_search for my vector but it does not work properly if
I use

template <class ForwardIterator, class T>
  bool binary_search ( ForwardIterator first, ForwardIterator last,
                       const T& value );

However, if I use the following template using a compare function, it works.

template <class ForwardIterator, class T, class Compare>
  bool binary_search ( ForwardIterator first, ForwardIterator last,
                       const T& value, Compare comp );

Why is it there a difference ? Could anyone explain me the reason please?

Thge code I have written as for an example is follows.

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
template<class A, class B>
bool myfun (A s1, A s2){ return (s1==s2);} 
int main (){ 
	bool b=true;
	vector<string> v;
	v.push_back("test"); v.push_back("--ped");	v.push_back("test.ped");
	v.push_back("--map");
	cout << "starting bool value : " <<b<<endl;

	cout << "|----------------------------------------|\n";
	for(int i=0; i<v.size();++i){
		b = binary_search(v.begin(),v.end(), v[i] );
		cout << "bool value after  binary search: "<< b<<endl;
		if(b) cout << "vector element is: "<< v[i] <<endl;
		else cout<< "coundn't be dispalyed!\n";

	}
	cout << "|----------------------------------------|\n";
	for(int i=0; i<v.size();++i){

		b = binary_search(v.begin(),v.end(), v[i],myfun<string, string> );
		cout << "bool value after  binary search with function: "<< b<<endl;
		if(b) cout << "vector element is: "<< v[i] <<endl;
		else cout<< "coundn't be dispalyed!\n";
	}

	cout<< "With integers: "<<endl;
	cout << endl;
	cout << "|----------------------------------------|\n";
	vector<int> vint(4);
	for(int i=0; i<vint.size();++i){ 
		vint[i]=i;
		b = binary_search(vint.begin(),vint.end(), i );
		cout << "bool value after  binary search with function: "<< b<<endl;
		if(b) cout << "binary search has found "<< vint[i]<< endl;
		else cout<< " coundn't be dispalyed!\n";
	}
	cout << "|----------------------------------------|\n";
	// binary search using function 
	// trying with integers
	cout << "|----------------------------------------|\n";
	for(int i=0; i<vint.size();++i){ 
		cout << "bool value after  binary search with function: "<< b<<endl;
		b = binary_search(vint.begin(),vint.end(), vint[i],myfun<int , int> );
		if(b) cout << "binary search has found "<< vint[i]<< endl;
		else cout<< " coundn't be dispalyed!\n";
	}
	cout << "|----------------------------------------|\n";

	vector<string>::iterator it;
	it=find(v.begin(), v.end(), "--ped");
	cout << *it <<endl;
	int x =int(distance(v.begin(),it));
	cout << x <<endl;
	cout << "v[x]: " <<v[x]<<endl;
	++it;
	cout<< *it<<endl;

return 0;}
/*
The result is like : 
starting bool value : 1
|----------------------------------------|
bool value after  binary search: 0
coundn't be dispalyed!
bool value after  binary search: 0
coundn't be dispalyed!
bool value after  binary search: 1
vector element is: test.ped
bool value after  binary search: 0
coundn't be dispalyed!
|----------------------------------------|
bool value after  binary search with function: 1
vector element is: test
bool value after  binary search with function: 1
vector element is: --ped
bool value after  binary search with function: 1
vector element is: test.ped
bool value after  binary search with function: 1
vector element is: --map
With integers: 

|----------------------------------------|
bool value after  binary search with function: 1
binary search has found 0
bool value after  binary search with function: 0
 coundn't be dispalyed!
bool value after  binary search with function: 1
binary search has found 2
bool value after  binary search with function: 1
binary search has found 3
|----------------------------------------|
|----------------------------------------|
bool value after  binary search with function: 1
binary search has found 0
bool value after  binary search with function: 1
binary search has found 1
bool value after  binary search with function: 1
binary search has found 2
bool value after  binary search with function: 1
binary search has found 3
|----------------------------------------|
*/

SeppJ

You somehow managed to make two errors that cancel each other. Quite remarkable and I did not yet figure out what happens exactly. But at least I can tell you what you are doing wrong:
1. binary_search expects the range to be sorted. Both your vectors^* are not sorted according to the string operator< which is the default comparison function for binary_search.
2. The comparison function that the second version of binary_search takes should define a strict weak ordering (Think: A relation like < or > ). Your custom comparison function (that behaves literaly like an equality relation) does not fulfill this requirement.

^*: Your vector<int> has the contents (0, 1, 0 ,0) when you try the second search as you did not fill it before the search.

camper

The behaviour isn't actually very surprising, but given that a) the searched ranges aren't sorted and b) the comparision function doesn't induce a total weak ordering over the elements of those ranges and the search key it is undefined in any case.

A binary search considers two values to be equivalent (thus the key to be found) if both f(key,x) and f(x,key) return false for some element x. Incidentally, that's what your function does for every value except the one you're searching for. It shouldn't be surpising now that you always get a true result, but that true-value actually derives from an element you weren't searching for!