f



lower_bound predicate for user defined type

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
ISO
12/16/2008 12:20:34 PM
comp.lang.c++.moderated 10738 articles. 1 followers. allnor (8506) is leader. Post Follow

3 Replies
598 Views

Similar Articles

[PageSpeed] 18

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
mzdude
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
Gil
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
David
12/19/2008 7:05:11 PM
Reply: