How can I make "str1 + str2 + str3 + ..." more efficient in C ++ 14?
std::string Concatenate(const std::string& s1,
const std::string& s2,
const std::string& s3,
const std::string& s4,
const std::string& s5)
{
return s1 + s2 + s3 + s4 + s5;
}
The default return s1 + s2 + s3 + s4 + s5;
can be equivalent to the following code:
auto t1 = s1 + s2; // Allocation 1
auto t2 = t1 + s3; // Allocation 2
auto t3 = t2 + s4; // Allocation 3
return t3 + s5; // Allocation 4
Is there an elegant way to reduce the posting time to 1? I mean it return s1 + s2 + s3 + s4 + s5;
doesn't change, but efficiency automatically improves. If possible, it also avoids misuse by the programmer std::string::operator +
.
Does member functions help ref-qualifier
source to share
The premise of the question is that:
s1 + s2 + s3 + s4 + s5 + ... + sn
a misallocation of n will be required.
Instead, it will require O (Log (n)) allocation. The first one s1 + s1
will generate temporary. Subsequently, the temporary (rvalue) will be the left argument for all subsequent operations +
. The standard states that when lhs a string +
is an rvalue, the implementation just appends to this temporary and moves it:
operator+(basic_string<charT,traits,Allocator>&& lhs,
const basic_string<charT,traits,Allocator>& rhs);
Returns: std::move(lhs.append(rhs))
The standard also states that line capacity will grow geometrically (a factor between 1.5 and 2 is common). Thus, with each allocation, the capacity will grow geometrically, and this capacity is distributed along the chain of operations +
. More specifically, the source code:
s = s1 + s2 + s3 + s4 + s5 + ... + sn;
is actually equivalent to:
s = s1 + s2; s += s3; s += s4; s += s5; // ... s += sn;
When geometrical capacity growth is combined with short string optimization, the "pre-reservation" value of the correct capacity is limited. I would only bother doing this if such code did show up as a hot spot in performance testing.
source to share
There is no engineering as above engineering.
In this case, I create a type string_builder::op<?>
that reasonably efficiently collects a stack of strings for concatenation, and when the conversion to std::string
.
It keeps copies of any temporary std::string
provided, and links to longer-lived ones, as part of the paranoia.
It ends up shortening to:
std::string retval;
retval.reserve(the right amount);
retval+=perfect forwarded first string
...
retval+=perfect forwarded last string
return retval;
but it wraps it all up with a lot of syntactic sugar.
namespace string_builder {
template<class String, class=std::enable_if_t< std::is_same< String, std::string >::value >>
std::size_t get_size( String const& s ) { return s.size(); }
template<std::size_t N>
constexpr std::size_t get_size( const char(&)[N] ) { return N; }
template<std::size_t N>
constexpr std::size_t get_size( char(&)[N] ) { return N; }
std::size_t get_size( const char* s ) { return std::strlen(s); }
template<class Indexes, class...Ss>
struct op;
struct tuple_tag {};
template<size_t... Is, class... Ss>
struct op<std::integer_sequence<size_t, Is...>, Ss...> {
op() = default;
op(op const&) = delete;
op(op&&) = default;
std::tuple<Ss...> data;
template<class... Tuples>
op( tuple_tag, Tuples&&... ts ): data( std::tuple_cat( std::forward<Tuples>(ts)... ) ) {}
std::size_t size() const {
std::size_t retval = 0;
int unused[] = {((retval+=get_size(std::get<Is>(data))), 0)..., 0};
(void)unused;
return retval;
}
operator std::string() && {
std::string retval;
retval.reserve( size()+1 );
int unused[] = {((retval+=std::forward<Ss>(std::get<Is>(data))), 0)..., 0};
(void)unused;
return retval;
}
template<class S0>
op<std::integer_sequence<size_t, Is..., sizeof...(Is)>, Ss..., S0>
operator+(S0&&s0)&& {
return { tuple_tag{}, std::move(data), std::forward_as_tuple( std::forward<S0>(s0) ) };
}
auto operator()()&& {return std::move(*this);}
template<class T0, class...Ts>
auto operator()(T0&&t0, Ts&&... ts)&&{
return (std::move(*this)+std::forward<T0>(t0))(std::forward<Ts>(ts)...);
}
};
}
string_builder::op< std::integer_sequence<std::size_t> >
string_build() { return {}; }
template<class... Strings>
auto
string_build(Strings&&...strings) {
return string_build()(std::forward<Strings>(strings)...);
}
and now we get:
std::string Concatenate(const std::string& s1,
const std::string& s2,
const std::string& s3,
const std::string& s4,
const std::string& s5)
{
return string_build() + s1 + s2 + s3 + s4 + s5;
}
or more general and effective:
template<class... Strings>
std::string Concatenate(Strings&&...strings)
{
return string_build(std::forward<Strings>(strings)...);
}
there are extraneous movements, but no extraneous discharge. And he works with raw at "strings"
no additional cost.
source to share
You can use code like:
std::string(s1) + s2 + s3 + s4 + s5 + s6 + ....
This will highlight one unnamed temporary (copy of the first line) and then add all other lines to it. A smart optimizer can optimize this in the same code as the reserved + extra code others have posted, since these functions are usually strict.
This works using an extended version of the + operator, which is defined as (roughly)
std::string operator+(std::string &&lhs, const std::string &rhs) {
return std::move(lhs.append(rhs));
}
when combined with RVO, this means that no additional objects string
need to be created or destroyed.
source to share
After some thought, I think it might be worth at least given a slightly different approach.
std::stringstream s;
s << s1 << s2 << s3 << s4 << s5;
return s.str();
Although it does not guarantee only one allocation, we can expect to stringstream
be optimized for accumulating relatively large amounts of data, so the likelihood that (unless the input strings are huge) will keep the allocation fairly minimal.
At the same time, especially if the individual lines are small enough, it certainly avoids the situation we expect with something like a + b + c + d
where (at least in C ++ 03) we expect to see multiple temporary objects created and destroyed in expression evaluation process. In fact, we can usually expect this to produce nearly the same result that we would expect from something like expression templates, but with much less complexity.
There is a bit of a downside: iostreams (in general) have enough baggage for such related locales, especially if the strings are small, there can be more stream creation overhead than we store in separate distributions.
With the current compiler / library, I expect the thread creation overhead to make it slower. With an older implementation, I'll have to test to be certain (and I don't have a sufficiently old compiler to do this).
source to share
How about this:
std::string Concatenate(const std::string& s1,
const std::string& s2,
const std::string& s3,
const std::string& s4,
const std::string& s5)
{
std::string ret;
ret.reserve(s1.length() + s2.length() + s3.length() + s4.length() + s5.length());
ret.append(s1.c_str());
ret.append(s2.c_str());
ret.append(s3.c_str());
ret.append(s4.c_str());
ret.append(s5.c_str());
return ret;
}
There are two allocations, one very small, to build std::string
another spare memory for data.
source to share