Is std::string size() a O(1) operation?
The implementation of STL I'm using is the one built into VC++
A:
size_type __CLR_OR_THIS_CALL size() const
{ // return length of sequence
return (_Mysize);
}
So it eventually might be like this, but you can never be sure.
I think you were voted down because you didn't answer the question, you required the reader to connect the dots. And also your answer is cryptic.
Max Howell
2008-11-01 20:59:26
rephrased your answer and tossed in an upvote.
tfinniga
2008-11-03 20:22:18
+2
A:
Performance is guaranteed by the STL to be at least O(N) for containers, however many containers including std::string can implement this as O(1) and will. Usually it'll either return a simple variable or do something like _End - _Begin and return that.
Jasper Bekkers
2008-11-01 20:16:16
+5
A:
See Table 65 in Section 23.1 of the Standard. "a.size()" is listed as "(Note A)", which says that "Those entries ... should have constant complexity".
Section 21.3 says that strings conform to the requirements of a sequence (23.1), ipso facto, size() is constant time.
Don Wakefield
2008-11-01 20:39:14
+11
A:
If you're asking if MSVC's implementation of string::stize() 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 it's not required.
'Note A' was added to the standard specifically to appease those who believed that size() should be allowed to have linear complexity so there would be no need to maintain the size when 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().
Michael Burr
2008-11-02 00:21:36
As a side note, it is nonetheless possible to retrieve size of the string as an O(1) operation in a standard way: `(end() - begin())`. This is guaranteed to be \[amortized\] O(1) because both `begin()` and `end()` must be O(1) (Container requirements), string iterators are random-access (string requirements), and `operator-` must be O(1) for iterators that support it (iterator requirements).
Pavel Minaev
2009-07-12 08:22:29
+1
A:
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.
tfinniga
2008-11-03 20:20:09