Re: [boost] New Library Proposal: dual_state

From: Rob Stewart (stewart_at_[hidden])
Date: 2005-07-19 09:19:06

From: "Jost, Andrew" <Andrew_Jost_at_[hidden]>
> From: boost-bounces_at_[hidden] 
> [mailto:boost-bounces_at_[hidden]] On Behalf Of Fernando Cacciola
> 
> > IMO you still need to show that the adpator is indeed a good 
> > thing; if you do that we can start discussing a proper design 
> > and implementation for it.
> 
> Okay, I'll try.  How about finding the max_element (or min_element) of a
> series of optional integers?  Using the ?: operator, we might do this in
> two steps, the first to filter out non-existent values, the second to
> apply the max_element algorithm.  Another way would be to write a custom
> predicate function that knows how to compare "full" and "empty"
> Boost::Optional objects or that duplicates the functionality of adaptor.

Interesting.  That does seem like a good use case.

> However, by using an adaptor in conjunction with
> boost::transform_iterator, the job can be accomplished in one loop
> without the difficulty of writing a custom predicate.  Here is some
> example code (BTW, others seem to prefer the spelling "adaptor," which
> is more consistent with other standardized names like "iterator," so
> I'll conform to that):

I took a look at "adapter" and "adaptor" at dictionary.com.  Most
dictionaries list "adapter" as the main entry and "adaptor" as a
variant.  WordNet at Princeton University makes the two
synonymous only for this usage.

A quick Google search showed 18.2 million hits for "adapter" and
4.1 million for "adaptor."

I think "adapter" is the right spelling in this case.

> // METHOD #1a: copy to a new vector
> std::vector<int> tmp;
> for( cIter p = v.begin(); p != v.end(); ++p ) {
>     if( *p ) tmp.push_back( p->get() );
> }
> max = *std::max_element( tmp.begin(), tmp.end() );
> 
> // METHOD #1b: copy using ?: to provide a signal value for undefined
> elements (similar to adaptor)
> tmp.clear();
> for( cIter p = v.begin(); p != v.end(); ++p ) {
>     tmp.push_back( *p ? p->get() : -1 );
> }
> max = *std::max_element( tmp.begin(), tmp.end() );

Both of those variants are clear and understandable.

> // METHOD #2a: define a custom predicate
> template< class T, class Pred, T Def = T() >
> class optPred : public std::binary_function<boost::optional<T>,
> boost::optional<T>, bool> {
>     Pred f;
>     T _eval( const boost::optional<T>& x ) const {
>         return ( x ? x.get() : Def );
>     }
> public:
>     optPred() : f( Pred() ) {}
>     bool operator()( const first_argument_type& a, const
> second_argument_type& b ) const {
>         return f( _eval(a), _eval(b) );
>     }
> };
> opt_int opt_max;
> opt_max= *std::max_element( v.begin(), v.end(), optPred< int,
> std::less<int>, -1 >() );

That's a lot of work.  You'd want to use something like
Boost.Lambda to make this more reasonable.

> // METHOD #2b: use an adaptor-like predicate
> template< class T >
> class adaptor_substitute : public std::unary_function<
> boost::optional<T>, T > {
>     T Def;
> public:
>     _adaptor_() : Def( T() ) {}
>     _adaptor_(T def) : Def( def ) {}
>     T operator()(const argument_type& x ) {
>         return ( x ? x.get() : Def );
>     }
> };
> max = *std::max_element(
>     boost::make_transform_iterator( v.begin, adaptor_substitute<int>(-1)
> ),
>     boost::make_transform_iterator( v.end,   adaptor_substitute<int>(-1)
> )
> );

This isn't really an adapter substitute.  It is an adapter,
adapted (pun intended) to be a predicate.

> // METHOD #3: use an adaptor
> max = *std::max_element(
>     boost::make_transform_iterator( v.begin,
> boost::optional<int>::adaptor(-1) ),   // NOTE:
> boost::optional<int>::adaptor does not currently exist
>     boost::make_transform_iterator( v.end,
> boost::optional<int>::adaptor(-1) )
> );

That is clearly the most straightforward of the bunch, but I'd
like to see a proper Boost.Lambda or Boost.Function variant for
comparison.

BTW, why have you shown the adapter as a nested type of
boost::optional?  Do you not think it is applicable to anything
else?  I can envision adapting pointers or even floating point
types (where NaN is the "empty" value), to name just two more
types adapter might support.

-- 
Rob Stewart                           stewart_at_[hidden]
Software Engineer                     http://www.sig.com
Susquehanna International Group, LLP  using std::disclaimer;