Allocation in making copy of std::string

Question

Which implementation do you think is better?

std::string ToUpper( const std::string& source )
{
    std::string result;
    result.resize( source.length() );
    std::transform( source.begin(), source.end(), result.begin(), 
        std::ptr_fun<int, int>( std::toupper ) );
    return result;
}

and...

std::string ToUpper( const std::string& source )
{
    std::string result( source.length(), '\0' );
    std::transform( source.begin(), source.end(), result.begin(), 
        std::ptr_fun<int, int>( std::toupper ) );
    return result;
}

Difference is that the first one uses reserve method after the default constructor, but the second one uses the constructor accepting the number of characters.

EDIT 1. I cannot use boost lib. 2. I just wanted to compare between the allocation-during-constructor and the allocation after-constructor.

Have a look at http://stackoverflow.com/questions/735204/convert-a-string-in-c-to-upper-case — DaveN, Mar 09 '11 at 08:10
I made a mistake using `reserve()` method. I updated the first code to use `resize()` instead. — Daniel K., Mar 09 '11 at 08:24

Nikko · Answer 1 · 2011-03-09T09:00:47.807

5

what about a simple :

std::string result;
result.reserve( source.length() );

std::transform( source.begin(), source.end(), 
                std::back_inserter( result ),
                ::toupper );

?

Then personally I'd use boost instead.

edited Mar 09 '11 at 09:00

answered Mar 09 '11 at 08:20

Nikko

4,182
1
26
44

The `reserve` would be nice to avoid reallocations in the middle, though at least GNU stdlibc++ will find out the iterators support difference and call `reserve` inside `transform` automatically. – Jan Hudec Mar 09 '11 at 08:24
I've added the reserve keyword – Nikko Mar 09 '11 at 09:43

score 3 · Answer 2 · answered Mar 09 '11 at 08:18

The first of these two implementations is incorrect. The string::reserve function does not change the size of the string; rather it just allocates internal buffer space for it. This means that if you start writing into the string, you're overwriting characters that are physically part of the string but not logically part of the string. That is, the characters are there, but the string's length won't report them as being a part of the string.

However, I see why it is that you're trying to use reserve this way: If you use resize to make the string larger, then all the characters will have to have some value assigned to them, and this can contribute some inefficiency to the program. Therefore, you're looking for some way to avoid this cost. If you want to do this, consider using the following code:

string ToUpper(const std::string& source) {
    std::string result;
    result.reserve(source.length());

    for (string::const_iterator itr = source.begin(); itr != source.end(); ++itr)
        result += std::toupper(*itr);

    return result;
}

This first calls reserve on the result string to preallocate storage space for it. We then just walk across the elements of the first string, converting each to upper case and appending it to the resulting string using operator +=. Since space already exists in the string because of the call to reserve, there shouldn't be any new allocations involved, and the buffer will just be written to with the characters that you want.

Hope this helps!

score 3 · Answer 3 · answered Mar 09 '11 at 08:18

3

#include <boost/algorithm/string.hpp>

std::string copy = boost::to_upper_copy(original);

answered Mar 09 '11 at 08:18

Matthieu M.

287,565
48
449
722

score 2 · Answer 4 · answered Mar 09 '11 at 08:13

2

The second one is better because it is less likely to write through an undereferencable iterator. If you've only reserved the storage, you need to append characters. The string is still empty. Consider std::back_insert_iterator.

answered Mar 09 '11 at 08:13

CB Bailey

755,051
104
632
656

you mean that the second one is better because the first one is buggy :) – davka Mar 09 '11 at 08:36

Maxim Egorushkin · Accepted Answer · 2011-03-10T15:53:29.450

A straight-forward loop would be the simplest:

std::string toUpper(std::string s)
{
    for(size_t i = 0, j = s.size(); i != j; ++i)
        s[i] = toupper(s[i]);
    return s;
}

No need to use standard algorithms and functors here just for the sake of using them.

[Update]

You mentioned you can't use boost. I benchmarked just for fun the above version which writes to the result string twice against the following one that only writes once:

struct ToUpper
{
    typedef char result_type;
    char operator()(char c) const { return toupper(c); }
};

std::string toUpper2(std::string const& s)
{
    boost::transform_iterator<ToUpper, std::string::const_iterator> beg(s.begin());
    return std::string(beg, beg + s.size());
}

The results are:

500000 calls
toUpper : 414nsec/call
toUpper : 414nsec/call
toUpper : 414nsec/call
toUpper2: 301nsec/call
toUpper2: 302nsec/call
toUpper2: 302nsec/call

Yikes. You're right. This method was way faster than using `std::transform()`. Thanks. — Daniel K., Mar 10 '11 at 01:23

score 1 · Answer 6 · answered Mar 09 '11 at 14:14

Since you're returning a transformed copy, why not pass-by-value and transform the already constructed temporary you receive?

std::string ToUpper( std::string source )
{
    std::transform( source.begin(), source.end(), source.begin(), ::toupper );
    return source;
}

score 0 · Answer 7 · answered Mar 09 '11 at 08:31

The first one has a bug of copying onto an empty string (as already mentioned). Another way to correct this is to use back_inserter(result).

Given that, the first version seems marginally faster as it does not copy the initializing value to the result; however, there is a question of efficiency of regular insertion (as in 2) vs. insertion via back_inserter, i.e. push_back (as in 1).

In general, I'd suggest to prefer what you feel is a better style, and to be bothered with such such fine-grain optimization at this point, until you have a real evidence that you have a performance problem and this could be one of the bottlenecks. Pre-allocating the result is good enough. Beware Premature Optimization

score -2 · Answer 8 · answered Mar 09 '11 at 08:09

-2

The first one is better... the second is misleading in making it appear significant that the characters are set to NUL.

answered Mar 09 '11 at 08:09

Tony Delroy

102,968
15
177
252

The first of these implementations is incorrect; see my post for an explanation. – templatetypedef Mar 09 '11 at 08:18
@templatetypedef: as per DanielK's edit to his question (now corrected to avoid reserve), I'm addressing what he was trying to contrast... it's true that both his options do needless default-initialisation - explicitly or implicitly - but that's not the thrust of his question. From a style / maintainability perspective, of the two options he offers, I stand by my prefererence to avoid the explicit NUL. – Tony Delroy Mar 09 '11 at 08:42

Allocation in making copy of std::string

8 Answers8