Re: [boost] [String algorithm] is_any_of hasinefficient implementation

From: David Abrahams (dave_at_[hidden])
Date: 2008-02-16 09:00:44

on Thu Feb 14 2008, "Martin Bonner" <Martin.Bonner-AT-pi-shurlok.com> wrote:

> ----Original Message----
> From: boost-bounces_at_[hidden]
> [mailto:boost-bounces_at_[hidden]] On Behalf Of Sebastian Redl
> Sent: 14 February 2008 17:59 To: boost_at_[hidden]
> Subject: Re: [boost] [String algorithm] is_any_of hasinefficient
> implementation 
>
>> Phil Endecott wrote:
>>> Further investigation with other workloads suggests that this bitset
>>> really works very well, and I note that it would be possible to
>>> write a specialisation of std::set<char> using it.  This is probably
>>> worth pursuing. 
>>> 
>> You can't specialize std::set<char> this way. It loses ordering.
>
> Why does it lose ordering?  If I add 'b' and 'a' and then iterate over
> the set, I would expect the specialization to return 'a' and then 'b'
> (because it would find the bit corresponding to 'a' set before the bit
> corresponding to 'b').
>
> Of course WE can't specialize std::set<char> this way, but an
> implementor could.

Assuming you're willing to play fast-and-loose with the big-O of
iterator increment (I am).

-- 
Dave Abrahams
Boost Consulting
http://boost-consulting.com