Re: Algorithms and Formal Reviews

From: Stephen Cleary (shammah_at_[hidden])
Date: 2001-01-11 01:48:27

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