I would like to use lower_bound version with predicate on container with user defined type. The problem is that my predicate isn't comparing two user defined types, but one user defined type and one built in type. Note that predicate knows how to compare these two. Here is a code to demonstrate my problem: struct FirstLast { FirstLast(size_t first, size_t last) : first(first), last(last) {} size_t first; size_t last; }; std::vector<FirstLast> vec; vector is sorted using predicate: struct CompareByLast : std::binary_function<bool, FirstLast, FirstLast> { bool operator()(const FirstLast& left, const FirstLast& right) const { return left.last < right.last; } }; I try to use lower_bound like this: size_t val = 4; std::vector<FirstLast>::const_iterator iter = std::lower_bound (vec.begin(), vec.end(), val, FindByLast()); struct FindByLast : std::binary_function<bool, FirstLast, size_t> { bool operator()(const FirstLast& left, size_t right) const { return left.last < right; } }; the error I get is: error C2664: 'bool FindByLast::operator ()(const FirstLast &,size_t) const' : cannot convert parameter 1 from 'const size_t' to 'const FirstLast &' Reason: cannot convert from 'const size_t' to 'const FirstLast' No constructor could take the source type, or constructor overload resolution was ambiguous \include\algorithm(2300) : see reference to function template instantiation 'bool std::_Debug_lt_pred<_Pr,FirstLast,_Ty> (_Pr,_Ty1 &,const _Ty2 &,const wchar_t *,unsigned int)' being compiled with [ _Pr=FindByLast, _Ty=size_t, _Ty1=FirstLast, _Ty2=size_t ] include\algorithm(2314) : see reference to function template instantiation '_FwdIt std::_Lower_bound<std::_Vector_iterator<_Ty,_Alloc>,unsigned int,__w64 int,_Pr>(_FwdIt,_FwdIt,const unsigned int &,_Pr,_Diff *)' being compiled with [ _FwdIt=std::_Vector_iterator<FirstLast,std::allocator<FirstLast>>, _Ty=FirstLast, _Alloc=std::allocator<FirstLast>, _Pr=FindByLast, _Diff=__w64 int ] projects\lowerbound\lowerbound.cpp(22) : see reference to function template instantiation '_FwdIt std::lower_bound<std::_Vector_iterator<_Ty,_Alloc>,size_t,FindByLast> (_FwdIt,_FwdIt,const unsigned int &,_Pr)' being compiled with [ _FwdIt=std::_Vector_iterator<FirstLast,std::allocator<FirstLast>>, _Ty=FirstLast, _Alloc=std::allocator<FirstLast>, _Pr=FindByLast ] STL implementation is calling predicate with Predicate(FirstLast, size_t) and Predicate(size_t, FirstLast) but defining one more operator () in my predicate doesn't help. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]

0 |

12/16/2008 12:20:34 PM

On Dec 16, 1:20 pm, Nikola Smiljani� <popiz...@gmail.com> wrote: > <snip> > struct FirstLast > { > FirstLast(size_t first, size_t last) : first(first), last(last) {} > > size_t first; > size_t last; > > }; > <snip> > > I try to use lower_bound like this: > > size_t val = 4; > std::vector<FirstLast>::const_iterator iter = std::lower_bound > (vec.begin(), vec.end(), val, FindByLast()); > This is your first problem. Lower doesn't want val(size_t) it wants val (FirstLast). You would need to define FirstLast val(0,4); > struct FindByLast : std::binary_function<bool, FirstLast, size_t> > { > bool operator()(const FirstLast& left, size_t right) const > { > return left.last < right; > } > > }; > This is your second problem. Your third template parameter needs to changed from size_t to FirstLast. Then the operator() needs it's third type to be const FirstLast &. HTH -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]

0 |

12/16/2008 5:29:20 PM

On Dec 16, 1:20 pm, Nikola Smiljani� <popiz...@gmail.com> wrote: > I try to use lower_bound like this: > > size_t val = 4; > std::vector<FirstLast>::const_iterator iter = std::lower_bound > (vec.begin(), vec.end(), val, FindByLast()); > > the error I get is: > > error C2664: 'bool FindByLast::operator ()(const FirstLast &,size_t) > const' : cannot convert parameter 1 from 'const size_t' to 'const > FirstLast &' > Reason: cannot convert from 'const size_t' to 'const > FirstLast' start with: http://www.sgi.com/tech/stl/StrictWeakOrdering.html the first argument type and second argument type of a StrictWeakOrdering function object must be the same. the compiler is trying to convert the second one (std::size_t) to your FirstLast. for your simple example, just add a conversion constructor to FirstLast and you should be golden: FirstLast::FirstLast( std::size_t first ) : first( first ), last( last ) { } do not make it explicit so FirstLast can be created from a single size_t arg. you might also want to derive from appropriate binary function respecting the concept checks on StrictWeakOrdering: struct FindByLast : std::binary_function<bool, FirstLast, FirstLast> { ... }; I have attached a fully functional example with these modifications, please look at it below to see the corrected code. however, I'd like to mention that often in real world programming you need a more flexible approach than just conversion constructors. I have implemented complex and generic run time (as in built by users at run time) predicates and I can show you the door. for starters just think on using external polymorphism or a simple holder like boost::any. for more advanced things (like binding predicates on custom data and constraints using arbitrary argument lists to binary StrictWeakOrdering predicates according to a set of intersection policies) I suggest you use for starters boost::tuple as second argument and provide a facet based on a given intersection policy (or set of policies) to a StrictWeakOrdering. imagine this: template< class Constraint > class Base { Constraint constraint( ) const; }; template< class Data > struct ByLast : std::binary_function< bool, boost::any, boost::any > { typedef typename base_traits< Data >::base_type base_type; typedef typename base_traits< Data >::constraint_type constraint_type; bool operator ()( const boost::any & a, const boost::any & b ) { return ( boost::any_cast< base_type >( a ) ).constraint( ) < ( boost::any_cast< constraint_type >( b ) ); } }; note how knowing the Base data type (that actually spawns different hierarchies of data types based on constraint type) and assuming Data is convertible to Base you can manipulate any kind of Data that matches the Base interface with any kind of constraint by delegating the operator (the less than above) to Constraint type. Data doesn't need to know how Constraints are compared but it just needs to implement a constraint() method to show a Constraint type. of course the operator itself can become a template argument etc. anyway, good luck. gil /* * lower_bound.cpp * * Created on: Dec 16, 2008 * Author: vnicula */ #include <functional> #include <iostream> #include <vector> #include <iterator> struct FirstLast { FirstLast(size_t first, size_t last) : first( first ), last( last ) { } FirstLast( std::size_t first ) : first( first ), last( last ) { } friend std::ostream & operator <<( std::ostream & o, const FirstLast & f ) { return o << "( " << f.first << ", " << f.last << " ) "; } size_t first; size_t last; }; struct CompareByLast : std::binary_function< bool, FirstLast, FirstLast > { bool operator ()( const FirstLast& left, const FirstLast& right ) const { return left.last < right.last; } }; struct FindByLast : std::binary_function<bool, FirstLast, FirstLast> { bool operator ()( const FirstLast& left, const FirstLast& right) const { return left.last < right.first; } }; int main( ) { std::size_t val = 4; std::vector< FirstLast > vec; for ( int i = 1; i < 20; i++ ) { vec.push_back( FirstLast( i, ( i - 10 ) * ( i-10 ) ) ); } std::sort( vec.begin( ), vec.end( ), CompareByLast() ); std::cout << "Sorted vector:" << std::endl; std::copy( vec.begin( ), vec.end( ), std::ostream_iterator< FirstLast >( std::cout ) ); std::cout << std::endl; std::vector< FirstLast >::const_iterator iter = std::lower_bound( vec.begin(), vec.end(), val, FindByLast() ); if ( iter != vec.end( ) ) { std::cout << "Lower bound with " << val << " is:" << *iter << std::endl; } else { std::cout << "Logic error: couldn't find lower bound with " << val << "." << *iter << std::endl; } return EXIT_SUCCESS; } -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]

0 |

12/16/2008 5:30:57 PM

on Tue Dec 16 2008, Gil <ivnicula-AT-yahoo.com> wrote: > On Dec 16, 1:20 pm, Nikola Smiljanić <popiz...@gmail.com> wrote: >> I try to use lower_bound like this: >> >> size_t val = 4; >> std::vector<FirstLast>::const_iterator iter = std::lower_bound >> (vec.begin(), vec.end(), val, FindByLast()); >> >> the error I get is: >> >> error C2664: 'bool FindByLast::operator ()(const FirstLast &,size_t) >> const' : cannot convert parameter 1 from 'const size_t' to 'const >> FirstLast &' >> Reason: cannot convert from 'const size_t' to 'const >> FirstLast' > > start with: > > http://www.sgi.com/tech/stl/StrictWeakOrdering.html > > the first argument type and second argument type of a > StrictWeakOrdering function object must be the same. That's no longer exactly current. It depends whether your implementation is keeping up with the times, but see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2495.html#270 FWIW'ly, -- Dave Abrahams BoostPro Computing http://www.boostpro.com [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]

0 |

12/19/2008 7:05:11 PM