Options to concatenate strings in std::string

Question

I have a requirement to concatenate multiple small strings into an std::string in an efficient manner.

Let's say there are five strings abc, def, ghi, lmn and pqr. These need to be concatenated thus: /abc/def/ghi/lmn/pqr

The strings would be received in the order opposite to their final positions in the concatenated string: pqr, lmn, ghi, def and abc.

To make this operation efficient, I use the reserve() API of std::string since I know the sizes of all the strings.

Given all this, which of the two is efficient:

Use a stack to store the strings and concatenate them by popping one by one.
Use insert() API of std::string to move the rest of the string to accommodate the new string at the beginning.

Please note that the number of strings to be concatenated can be up to two thousand.

Have a look at cplusplus.com/reference/sstream/stringstream. It overloads the "<<" operator. In terms of performance: Be careful about premature optimizations. Implement and profile. Reimplement when in doubt. — user2354690
– user2354690, Commented May 5, 2017 at 14:04
Method 1 if implemented properly should at least be not slower than method 2 — Slava
– Slava, Commented May 5, 2017 at 14:04
@mutex36 recommending std::stream for efficiency, are you in your mind? Why OP needs << if std::string::operator += is sufficient in this case? — Slava
– Slava, Commented May 5, 2017 at 14:06
Question unclear: "The strings would be received in the opposite order" / " I know the sizes of all the strings.". Either you have all the strings, and then you can walk through them in either order, or you receive them sequentially and do not know all sizes. — MSalters
– MSalters, Commented May 5, 2017 at 15:04

Partha Pratim Mukherjee · Accepted Answer · 2017-05-05 17:29:59Z

2

Just out of curiosity wrote this program to see the running time of various methods for this on Debian. To add 100,000 words in reverse order stack is the best option among these

// concatenate by + operator
real    0m2.286s
user    0m2.268s
sys     0m0.016s

// concatenate by insert
real    0m0.695s
user    0m0.692s
sys     0m0.000s

// concatenate by stack
real    0m0.051s
user    0m0.044s
sys     0m0.004s

#include <cstdio>
#include <iostream>
#include <string>
#include <random>
#include <algorithm>
#include <stack>

using namespace std;

int main() {
  random_device dev;
  mt19937 gen(dev());
  string chars = "abcdefghijklmnopqrstuvwxyz";
  uniform_int_distribution<> dis_index(0, chars.size()-1);
  int size = 3; // word size
  int count = 100000; // 100K words
  string out; // final string
  stack<string> st;

  int i = 0;
  while (i < count) {
    // create a random word of length = size
    string s;
    generate_n(back_inserter(s), size, [&](){return chars[dis_index(gen)];});
    //cout << s << endl;

    // concatenate by + operator
    // out = s + out;

    // concatenate by insert
    // out.insert(0, s);

    // concatenate by stack
    st.push(s);

    ++i;
  }
  while (!st.empty()) {
    out += st.top();
    st.pop();
  }
  //cout << out << endl;
}

answered May 5, 2017 at 17:29

Partha Pratim Mukherjee

1746 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Maddy Over a year ago

I wrote my own sample code, and found the stack approach to be slightly better for my use cases.

Collectives™ on Stack Overflow

Options to concatenate strings in std::string

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related