Is std::string size() a O(1) operation?

Question

Is std::string size() a O(1) operation?

The implementation of STL I'm using is the one built into VC++

Answer 1

If you're asking if MSVC's implementation of string::size() has constant complexity, then the answer is yes. But Don Wakefield mentioned Table 65 in 23.1 of the C++ Standard where it says that the complexity of size() should follow what's said in 'Note A'. Note A says:

Those entries marked ‘‘(Note A)’’ should have constant complexity.

However, that does not mean that those entries shall have constant complexity. Standards use very specific terminology, and "should" means that it is not mandatory.

'Note A' was added to the standard specifically to appease those who believed that size() should be allowed to have linear complexity so it would not be necessary to keep the size when the containers were modified.

So you can't rely on size() having constant complexity, but I'm honestly not sure if there are any implementations that do not have a constant string::size().

Answer 2

Here's an easy way to answer that question for msvc++.

Write some code in a project:

string happy;
happy.size();

Hilight the .size call, right-click, go to definition.

On my install (vs2005sp1) this sends me to xstring:1635, which looks like this:

size_type __CLR_OR_THIS_CALL size() const
    {   // return length of sequence
    return (_Mysize);
    }

So it looks like the string has a member called _Mysize, and it's just returning that.

In other words, this is a O(1) implementation.

Answer 3

Yes, std::string::size() is O(1).