One of my programs is exceeding the time limit when I am using fans = fans + s[i]
, while when I am using fans += s[i]
it is being accepted... Why does this happen?
To Explain more , fans is a string and s is also a string so while iterating over string s i want only some characters of s so i am creating a new string fans.Now there are two ways in which i can add character to my new string fans. The Problem is mentioned below
fans = fans + s[i]; // gives Time limit exceeded
fans += s[i]; // runs successfully
std::string
has membersoperator +
andoperator +=
. The former is usually implemented with the latter by way of an intermediate temporary. Effectively looking something like this (check your implementation source if you want to know exactly what yours does):The setup of
tmp
is expensive. The overall function can (and usually is) made better with move-assignment semantics to the final destination on the caller-side, but the expense of the temporary is none-the-less still there. Do it a few times and you won't notice the difference. Do it thousands, or millions, etc. of times, and it can mean a world of difference.For fundamental types,
a = a + b
anda += b
mean the same thing.For arbitrary class types,
a = a + b
anda += b
are unrelated; they look up different operators, and those operators can do arbitrary things. Them being actually unrelated is code smell, a sign of a design problem.a = a + b
becomesoperator=( a, operator+( a, b ) )
roughly; the actual lookup rules are a bit more complex (involving member operators and non-member operators, and the fact that=
doesn't have a non-member operator, etc), but that is the core of it.a += b
becomesoperator+=( a, b )
in a similar sense.Now, it is a common pattern to implement
+
in terms of+=
; if you do this, you get:becomes
where
(auto)
is the new c++20/c++23 "create a temporary copy of the argument" feature.Fundamentally,
a+=b
can reuse the contents ofa
directly, whilea = a + b
cannot; at the momenta+b
is evaluated, it doesn't know thata
will be soon overwritten.Some libraries deal with this using a technique known as "expression templates";
a+b
isn't a value, but rather a compile-time description of the expressiona+b
, which when assigned toa
is actually used to populatea
with data. With expression templates, the fundamental issue ofa+=b
knowing more thana=a+b
is eliminated.Now, for
std::string
specifically,a+b
creates a temporary string object, thena=(a+b)
moves that intoa
(it can reuse the buffer of the temporary string object or the buffer ofa
, the standard is silent on this matter).a+=b
must reuse any excess capacity in thea
buffer. So if youa.reserve(1<<30)
(1 billion),a+=b
cannot allocate more.If you use
fans=fans+s[i]
, the string will be copied in every loop pass. The new element will be added to the copy of the string and the result will be reassigned to the variablefans
. After this the old string will have to be removed because it is not referenced anymore. This takes a whole lot of time.If you use the augmented assignment
fans+=s[i]
the string will not be copied in every loop pass and there is no need of removing the reference variable as there is no reference variable here. This saves a lot of time.I hope now you can understand!!
For built-in types
a += b
is exactly the same asa = a + b
(except thata
is evaluated only once), but for classes, those operators are overloaded and call different functions.In your example
fans = fans + s[i]
creates a temporary string, and assigns (moves) it tofans
, butfans += s[i]
does not create that temporary, hence it may be faster.