>From CD2:
25.1.9  Search                                        [lib.alg.search]
  template<class ForwardIterator1, class ForwardIterator2>
    ForwardIterator1
      search(ForwardIterator1 first1, ForwardIterator1 last1,
             ForwardIterator2 first2, ForwardIterator2 last2);
...
Complexity:
    At most (last1 - first1) * (last2 - first2) applications of the cor-
    responding predicate.

But there are well known algorithms to do any search in at most
(last1 - first1) + (last2 - first2)
applications of the corresponding predicate.

Does this requirement came from the fact the the algorithms require
an additional O(last2 - first)-size storage
and to give the possibility to work under the low memory conditions
the requirement is changed to the one in the standard?
Why not to specify this behavior explicitly?
Otherwise if I want to have a portable
fast search I have to write the algorithm myself, which can not be done
effectively. For example, the lack of alloca() in the standard causes to
use fixed size buffer and if its size is not enough use either the heap
or the simplest bruit force algorithm...


--
Regards, Igor Boukanov.
igor.boukanov@fi.uib.no
http://www.fi.uib.no/~boukanov/
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

While linear time Knuth-Morris-Pratt algorithm can be generalized, it is
not really useful in practice. A worst-case quadratic algorithm is
seldom quadratic. It would be indeed very nice if someone produced a
generic version of Boyer-Moore that could be used for specialization of
search for random-access iterators with "small" value types. I spent a
lot of time thinking about it, but could not find a satisfactory
generalization. If we cannot caome up with a generic version, it would
still be very useful to have a Boyer-Moore specialization:

const char* search(const char*, const char*, const char*, const char*);

Any volunteers?

Another example is nth_element. While it is possible to have a worst
case linear time algorithm - it is not really useful. The one in STL is
so much faster on the average, that it is not worth while replacing it.

The fact that bothers me the most is that many STL algorithms have an
overspecified requirements. For example, partition can be done for
forward iterators, etc. While it is quite trivial to relax these
requirements in the standard, I have been told by the competent people
that it is too late. (For the record, the algorithms are:
reverse, random_shuffle, partition, stable_partition, sort, stable_sort,
inplace_merge - all of them could be done for forward iterators.)

Igor Boukanov wrote:
>
> >From CD2:
> 25.1.9  Search                                        [lib.alg.search]
>   template<class ForwardIterator1, class ForwardIterator2>
>     ForwardIterator1
>       search(ForwardIterator1 first1, ForwardIterator1 last1,
>              ForwardIterator2 first2, ForwardIterator2 last2);
> ...
> Complexity:
>     At most (last1 - first1) * (last2 - first2) applications of the cor-
>     responding predicate.
>
> But there are well known algorithms to do any search in at most
> (last1 - first1) + (last2 - first2)
> applications of the corresponding predicate.
>
> Does this requirement came from the fact the the algorithms require
> an additional O(last2 - first)-size storage
> and to give the possibility to work under the low memory conditions
> the requirement is changed to the one in the standard?
> Why not to specify this behavior explicitly?
> Otherwise if I want to have a portable
> fast search I have to write the algorithm myself, which can not be done
> effectively. For example, the lack of alloca() in the standard causes to
> use fixed size buffer and if its size is not enough use either the heap
> or the simplest bruit force algorithm...
>
> --
> Regards, Igor Boukanov.
> igor.boukanov@fi.uib.no
> http://www.fi.uib.no/~boukanov/
> ---
> [ comp.std.c++ is moderated.  To submit articles: Try just posting with your
>                 newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
>   comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
>   Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
>   Comments? mailto:std-c++-request@ncar.ucar.edu
> ]

--
Alexander Stepanov
stepanov@mti.sgi.com

Silicon Graphics
2011 N. Shorline Boulevard
Mountain View, CA 94043-1389

tel.: (415)933-6121
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]