Разница между добавлением символа в строку против строки в символ

Question

Какая разница в производительности между:

string s="";
//stk is std::stack<char>
 while(!stk.empty()){
            s+=stk.top();
            stk.pop();
        }            
        reverse(s.begin(),s.end());

и

 while(!stk.empty()){
            s=stk.top()+s;
            stk.pop();
        }            

Почему вышеописанное является более эффективным? При необходимости могу привести пример.

Проблема LeetCode

Answer 1

s+=stk.top(), что в данном случае эквивалентно s.push_back(stk.top()), амортизирует сложность с постоянным временем. s=stk.top()+s, по существу эквивалентно s.insert(s.begin(), 1, stk.top()), который является линейным по длине s.