Re: string::find complexity.

[Paolo Carlini <pcarlini at suse dot de>]

Dhruv Matani wrote:

> Here are the results for the tests on my system:
>
> 1. n^2 algo. re-implemented.
> 4. find in terms of std::search -> as suggested by Matt Austern.
>
> The numbers for (1) and (4) are the best in most cases. However, (1)
> does not come out a winner in all cases, whereas (4) seems to be the
> best for the general case.
>  
(4) is definitely the way to go, everything considered.

> string::size_type
> s_search(const string& data, const string& src)
> {
>  string::const_iterator i = 
>    std::search(src.begin(), src.end(), 
> 		data.begin(), data.end());
>  return (i - src.begin());
> }
>  
By the way, this implementation is incorrect, strictly speaking (not 
that this
changes considerably your numbers!), since doesn't deal correctly with the
various corner cases. Also, actually, we need the overload taking
(const charT*, size_type, size_type).

Thanks for your numbers! I'm finishing up implementing (4) and will include
in the patch your performance testcases.

Paolo.