Re: lower_bound predicate for user defined type

On Dec 16, 1:20 pm, Nikola Smiljani? <popiz...@gmail.com> wrote:


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! ]