3

Possible Duplicate:
C++ string::find complexity

What is the time complexity of the find operation that comes built-in with the string library in STL?

Community
  • 1
  • 1
zer0nes
  • 175
  • 2
  • 3
  • 10
  • N3485 §21.4.7.2 if you want to look it up. – chris Dec 10 '12 at 11:22
  • @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
  • @tom, http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2012/n3485.pdf – chris Dec 10 '12 at 11:33
  • @tom: It refers (rather cryprically) to the C++ standard. N3485 is a publically available draft of the standard, which you can probably find by googling. 21.4.7.2 is the section of the standard that defines `std::string::find`. But it doesn't specify any complexity requirements. – Mike Seymour Dec 10 '12 at 11:34
  • @MikeSeymour, I suppose it is a bit cryptic when you don't know what it means ;) – chris Dec 10 '12 at 11:35
  • 1
    possible dup : http://stackoverflow.com/questions/8869605/c-stringfind-complexity – Caribou Dec 10 '12 at 11:39
  • @tom btw - that link was a couple down in the google results below your question... – Caribou Dec 10 '12 at 11:42

3 Answers3

3

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.

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
0

As pointed out in comments, standard doesn't specify that.

However, since std::string is a generalized container and it can't make any assumptions about the nature of the string it holds, you can reasonably assume that complexity will be O(n) in case when you search for a single char.

  • But if I wish to match a substring would it still be linear? – zer0nes Dec 10 '12 at 11:56
  • It will be linear, but not `O(n)`, rather `O(n*m)` where `m` is a length of substring being matched –  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 –  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 http://www.boost.org/doc/libs/1_52_0/libs/algorithm/doc/html/algorithm/Searching.html – Marshall Clow Dec 10 '12 at 18:25
-3

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

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

dmayola
  • 502
  • 5
  • 16