[Dune-devel] [Dune-Commit] [Commit] dune-istl - 1ede1c9: Cleanup: don't hand-implement binary search -- use std::lower_bound instead

[Markus Blatt]

Hi Oliver,

On Wed, Jul 03, 2013 at 01:51:06PM +0200, Oliver Sander wrote:
> New commit, appeared at Wed Jul  3 13:51:06 2013 +0200
> as part of the following ref changes:
> 
>     branch refs/heads/master    updated from 06c5441 -> 477aac5
> 
> Browsable version: http://cgit.dune-project.org/repositories/dune-istl/commit/?id=1ede1c959a021e0fb232030cc25b815d91175e5c
> 
> ======================================================================
> 
> commit 1ede1c959a021e0fb232030cc25b815d91175e5c
> Author: Oliver Sander <sander at igpm.rwth-aachen.de>
> Date:   Wed Jul 3 13:48:24 2013 +0200
> 
>     Cleanup: don't hand-implement binary search -- use std::lower_bound instead
> 
>  dune/istl/basearray.hh | 32 ++++++--------------------------
>  1 file changed, 6 insertions(+), 26 deletions(-)
> 
> 
> 
> diff --git a/dune/istl/basearray.hh b/dune/istl/basearray.hh
> index 9c0c813..200dc32 100644
> --- a/dune/istl/basearray.hh
> +++ b/dune/istl/basearray.hh
> @@ -716,19 +716,9 @@ namespace Dune {
>      //! random access returning iterator (end if not contained)
>      iterator find (size_type i)
>      {
> -      if (n==0)
> -        return end();
> -
> -      size_type l=0, r=n-1;
> -      while (l<r)
> -      {
> -        size_type q = (l+r)/2;
> -        if (i <= j[q]) r=q;
> -        else l = q+1;
> -      }
> -
> -      return (i==j[l])
> -        ? iterator(p,j,l)
> +      const size_type* lb = std::lower_bound(j, j+n, i);
> +      return (lb != j+n and *lb == i)
> +        ? iterator(p,j,lb-j)
>          : end();

Couldn't we use std:find instead?
return iterator(p, j, std::find(j, j+n, i)-j);

In case the value is not foun find returns j+n, anyway. Or is there
some performance issue that I fail to see?

Markus

-- 
Do you need more support with DUNE or HPC in general? 

Dr. Markus Blatt - HPC-Simulation-Software & Services http://www.dr-blatt.de
Hans-Bunte-Str. 8-10, 69123 Heidelberg, Germany
Tel.: +49 (0) 160 97590858  Fax: +49 (0)322 1108991658