Various of the searching algorithms (find, find end, search_n, search,
etc) specify their complexity in terms of applications of the
corresponding predicate. There are two major problems I have with the
current specifications:

1) Their requirements are not in terms of the result.

For example, I would perfer find's complexity to be:
At most "i - first + 1" applications of the corresponding predicate
where such an iterator i exists, or last - first applications otherwise.

2) They don't place a limit on the number of "other things" the
algorithm can do (this would be more imporant if (1) was fixed).

Some implementations tend to write something like:

Dist = std::distance(first1, last1);

At the beginning of algorithms which take forward or bidirectional
iterators, meaning even if there was a match near the start then the
algorithm still takes O(n).

Was there a reason not to place stronger requirements, or was it simply
thought the existing requirements would be strong enough for most people?

Out of curiousity, is people considered this reasonable, would it be
feasable to add these tightened requirements to TR2? (I'm not asking
someone else to write it for me, I'm asking if any experts think there
is a reasonable choice such an application would be accepted).

Another similar thing I'd like to see in TR2 is a weakening of the
requirements of various algorithms (in particular, seeing sort and
stable_sort only require bidirectional iterators being the most
important, but other weakenings have been discussed in this group). Does
this sound reasonable? or would it be necessary to add a new algorithm,
tr2::bidirectional_stable_sort, or something similar (which seems messy).

Chris

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]