RE: [boost] Re: Algorithms and Formal Reviews

From: Hartmut Kaiser (H.Kaiser_at_[hidden])
Date: 2001-01-17 07:36:10

The idea to extend the goal of boost to provide more algorithms supports one
of the central ideas of the STL: to make it possible to develop new
containers for stl-algorithms _and_ new algorithms for stl containers (or
both).

snip

As a seed here are two small (and very simple) bool-op algorithms, I've
used:

// returns true, if one of the predicate invocations returns true
template<class ForwardIterator, class UnaryOperation>
inline bool boolop_or (ForwardIterator first, ForwardIterator last,
UnaryOperation f)
{
        while (first != last) {
                if (f(*first))
                        return true;
                ++first;
        }
        return false;
}

// returns true, if all of the predicate invocations return true
template<class ForwardIterator, class UnaryOperation>
inline bool boolop_and (ForwardIterator first, ForwardIterator last,
UnaryOperation f)
{
        while (first != last) {
                if (!f(*first))
                        return false;
                ++first;
        }
        return true;
}

Hartmut

> -----Original Message-----
> From: Stephen Cleary [mailto:shammah_at_[hidden]]
> Sent: Thursday, January 11, 2001 7:48 AM
> To: boost_at_[hidden]
> Subject: [boost] Re: Algorithms and Formal Reviews
>
>
> --- In boost_at_[hidden], "John E. Potter" <jpotter_at_f...> wrote:
> >
> >
> > On Wed, 10 Jan 2001, Beman Dawes wrote:
> >
> > > I've been thinking about sequence algorithms because of several
> recent
> > > boost postings, and string algorithms because I've seen several
> nice onces
> > > recently.
>
> > How about algorithms templated on containers?  That would open the
> > door for many different ideas.  Much different from the stl style.
>
> No reason why we couldn't have our own algorithms library.  I like
> the idea.  copy_if could be a prospective member, too.
>
> What *I* would like to see, though, is more efficient binary-search-
> style algorithms (lower_bound, binary_search, etc).  The problem is
> that the STL definitions force them to use op< or an equivalent
> Pred.  These can be made more efficient in some cases through the use
> of a Unary Fobj that returns int: <0 if a<b, 0 if a==b, and >0 if a>b
> (similar to strcmp/memcmp).  This is especially a savings if the
> comparision is expensive (such as long, similar strings).
>
> I've written binary_search using this type of Unary Fobj (which I
> call CompareAll), and the other algorithms should be similar.  Tests
> indicate that it is indeed faster for comparing strings.
>
> I haven't tried timing the difference when used with arithmetic
> types, though.  On the old TODO list...
>
>         -Steve
>
>
>
>