Re: [boost] Accelerating algorithms with SIMD - Segmented iterators and alternatives

Subject: Re: [boost] Accelerating algorithms with SIMD - Segmented iterators and alternatives
From: Sebastian Redl (sebastian.redl_at_[hidden])
Date: 2010-10-13 12:55:56

On 13.10.2010, at 18:09, Mathias Gaunard wrote:

> On 13/10/10 16:00, David Abrahams wrote:
>> At Wed, 13 Oct 2010 10:52:36 +0100,
>> Mathias Gaunard wrote:
>>> 
>>> On 12/10/10 09:06, David Abrahams wrote:
>>> 
>>>> Nice for very linear things.  Not so great for sort, binary_search,
>>>> reverse, rotate, ...
>>> 
>>> Yes, since those require either bidirectional or random access iterators.
>> 
>> Actually, all of those can be done with bidirectional iterators
>> (although the standard over-constrains sort).  binary_search can be
>> done with forward iterators.
> 
> I didn't know binary_search (and similar functions) worked with forward iterators. I have trouble seeing how they could work effectively at all.

It's O(n) iterator movements, but only O(log n) comparisons and dereferences, which is valuable if comparison is expensive (e.g. long, similar strings).

Sebastian