This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of CD1 status.

### 714. `search_n` complexity is too lax

Section: 27.6.15 [alg.search] Status: CD1 Submitter: Matt Austern Opened: 2007-08-30 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [alg.search].

View all issues with CD1 status.

Discussion:

The complexity for `search_n` (27.6.15 [alg.search] par 7) is specified as "At most (last - first ) * count applications of the corresponding predicate if count is positive, or 0 otherwise." This is unnecessarily pessimistic. Regardless of the value of count, there is no reason to examine any element in the range more than once.

Proposed resolution:

Change the complexity to "At most (last - first) applications of the corresponding predicate".

>     template<class ForwardIterator, class Size, class T>
>       ForwardIterator
>         search_n(ForwardIterator first , ForwardIterator last , Size count ,
>                  const T& value );

>     template<class ForwardIterator, class Size, class T,
>              class BinaryPredicate>
>       ForwardIterator
>         search_n(ForwardIterator first , ForwardIterator last , Size count ,
>                  const T& value , BinaryPredicate pred );

> > Complexity: At most `(last - first ) * count` applications of the corresponding predicate if `count` is positive, or 0 otherwise.