添加链接
link之家
链接快照平台
  • 输入网页链接,自动生成快照
  • 标签化管理网页链接

marked as duplicate by Fred Foo , WhozCraig , Nilesh , Fahim Parkar , hims056 Dec 11 '12 at 7:25

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question .

@chris: All that tells you is that the standard doesn't specify any complexity requirements. Mike Seymour Dec 10 '12 at 11:29 I didn't get your reference. I mean does it refer to some documentation? I googled it but it only referred me back to this question. zer0nes Dec 10 '12 at 11:31 @MikeSeymour, That's the point. You can't take a complexity value for a function when the standard gives none. chris Dec 10 '12 at 11:33

The Standard, §21.4.7.2, doesn't give any guarantees as to the complexity.

You can reasonably assume std::basic_string::find takes linear time in the length of the string being searched in, though, as even the naïve algorithm (check each substring for equality) has that complexity, and it's unlikely that the std::string constructor will build a fancy index structure to enable anything faster than that.

The complexity in terms of the pattern being searched for may reasonably vary between linear and constant, depending on the implementation.

It will be linear, but not O(n) , rather O(n*m) where m is a length of substring being matched user1773602 Dec 10 '12 at 11:59 So I could just use str.find instead of maybe say implementing the KMP algorithm to search for a substring? zer0nes Dec 10 '12 at 12:04 Your implementation could aleady be using KMP. Check it first. if it doesn't and performance is critical, then by all means roll your own user1773602 Dec 10 '12 at 12:09 Note that Boost has a Boyer-Moore, Boyer-Moore-Horspool, and Knuth-Morris-Pratt searching algorithms ready for your use. See boost.org/doc/libs/1_52_0/libs/algorithm/doc/html/algorithm/… Marshall Clow Dec 10 '12 at 18:25

At most, performs as many comparisons as the number of elements in the range [first,last).

http://cplusplus.com/reference/algorithm/find/

site design / logo © 2019 Stack Exchange Inc; user contributions licensed under cc by-sa 3.0 with attribution required . rev 2019.2.26.32943