Issue 714: search_n complexity is too lax (original) (raw)

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: 26.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 (26.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 predicateif count is positive, or 0 otherwise.