What is the complexity of the std :: string :: substr member function?

Question

What is the complexity of the member function std::string::substr ? Is it standard or implementation specific?

Answer 1

The naive implementation will be O (k), where k is the length of the resulting substring. std :: string does not support copy-on-write. If you want to perform O (1) substring operations, use a data structure such as Rope .

Answer 2

The C ++ 11 standard does not define substr performance, either in 21.4.7.8, or anywhere else that I could find. In practice, you almost certainly expect O(n) performance with n be the length of the result.

Answer 3

That's all the standard has to say about it:

n3242, 21.4.7.8

• Requires: pos <= size()
• Throws: out_of_range if pos > size()
• Effects: determines the effective length of the rlen string to copy as less than n and size() - pos
• Returns: basic_string<charT,traits,Allocator>(data()+pos,rlen) .

Thus, the answer will be negative, the complexity is not defined.

EDIT: Fixed according to n3242, pos> size not pos> = size