Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I've been doing some needed optimizations lately. One thing I've been doing is changing some ostringstreams -> sprintfs. I'm sprintf'ing a bunch of std::strings to a c style array, ala

char foo[500];
sprintf(foo, "%s+%s", str1.c_str(), str2.c_str());

It turns out that Microsoft's std::string::c_str() implementation runs in constant time (it just returns an internal pointer). It appears that libstdc++ does the same. I realize the std makes no guarantees for c_str, but its hard to imagine another way of doing this. If, for example, they copied into memory they'd either have to allocate memory for a buffer (leaving it up to the caller to destroy it -- NOT part of the STL contract) OR they'd have to copy to an internal static buffer (probably not threadsafe, and you have no guarantees on its lifetime). So simply returning a pointer to an internally maintained null terminated string seems to be the only realistic solution.

share|improve this question

3 Answers 3

up vote 6 down vote accepted

If I recall, the standard allows string::c_str() to return pretty much anything that satisfies:

  • Storage which is large enough for the contents of the string and the terminating NULL
  • Must be valid until a non-const member of the given string object is called

So in practice, this means a pointer to the internal storage; as there is no way to externally track the life of the returned pointer. I think your optimisation is safe to assume this is (small) constant time.

On a related note, if string formatting is performance limiting; you may find better luck deferring the evaluation until absolutely needed with something like Boost.Phoenix.

Boost.Format I believe defers the formatting internally until the result is required, and you can use the same format object repeatedly without re-parsing the format string, which I've found to make a significant difference for high-frequency logging.

share|improve this answer
2  
It may be possible for an implementation to create a new or secondary internal buffer - large enough to add on the null terminator. Even though c_str is a const method (or at least has a const overload - I forget which), this doesn't change the logical value, so may be a reason for mutable. It would break pointers from other calls to c_str, except that any such pointers must refer to the same logical string (so there's no new reason to reallocate - there must already be a null terminator) or else there must have already been a call to a non-const method in-between. –  Steve314 Dec 13 '11 at 5:06
    
If this really is valid, c_str calls can be O(n) time for the reallocation and copying. But it's also possible that there's extra rules in the standard that I'm unaware of that would prevent this. The reason I suggest it - calls to c_str aren't really meant to be common AFAIK, so it may not be considered important to ensure they're fast - avoiding that extra byte of storage for a normally unnecessary null terminator in string instances that never use c_str may have taken precedence. –  Steve314 Dec 13 '11 at 5:07
    
Boost.Format internally goes through streams which internally go through sprintf ending up with rather big overhead. The documentation says it's about 8 times slower than plain sprintf. If you want performance and type-safety, try Boost.Spirit.Karma. –  Jan Hudec Dec 13 '11 at 10:14
    
Boost.Spirit.Karma is a good tip for performance, but beware that it has a vastly different methodology that can be tricky to adapt existing printf style code (and coders). I've largely stuck with Boost.Format because our I/O is asynchronous; but a big factor is that I can convince my colleagues to use it consistently (still allows any type with an ostream<< overload - which nicely side-steps the .c_str() debate) The Karma peformance numbers. –  rvalue Dec 13 '11 at 13:37

In the c++11 standard (I am reading N 3290 version), chapter 21.4.7.1 speaks about the c_str() method :

const charT* c_str() const noexcept; const charT* data() const noexcept;

Returns: A pointer p such that p + i == &operator for each i in [0,size()].
Complexity: constant time.
Requires: The program shall not alter any of the values stored in the character array.

So, yes: the constant time complexity is guaranteed by the standard.

I just checked c++03 standard, and it has no such requirements, nor it tells the complexity.

share|improve this answer

In theory C++03 doesn't require that,and hence the string can be an array of char where the presence of the null terminator is added just at the time c_str() is called. This may require a reallocation (it doesn't violate the const-ness, if the internal private pointer is declared as mutable).

C++11 is stricter: it require time costantness, so no relocation can be done and the array must always be wide enough to store the null at end. c_str(), by itself, can still do "ptr[size()]='\0'" to enshure the null is really present. It doesn't violate the const-ness of the array since the range [0..size()) is not changed.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.