How to construct a std::string from a std::vector<string>?

Question

I'd like to build a std::string from a std::vector<std::string>.

I could use std::stringsteam, but imagine there is a shorter way:

std::string string_from_vector(const std::vector<std::string> &pieces) {
  std::stringstream ss;

  for(std::vector<std::string>::const_iterator itr = pieces.begin();
      itr != pieces.end();
      ++itr) {
    ss << *itr;
  }

  return ss.str();
}

How else might I do this?

Pickaninny

Perhaps std::string res; for (...) { res += *it; }? – Hetrick

Answer 1

C++03

std::string s;
for (std::vector<std::string>::const_iterator i = v.begin(); i != v.end(); ++i)
    s += *i;
return s;

C++11 (the MSVC 2010 subset)

std::string s;
std::for_each(v.begin(), v.end(), [&](const std::string &piece){ s += piece; });
return s;

C++11

std::string s;
for (const auto &piece : v) s += piece;
return s;

Don't use std::accumulate for string concatenation, it is a classic Schlemiel the Painter's algorithm, even worse than the usual example using strcat in C. Without C++11 move semantics, it incurs two unnecessary copies of the accumulator for each element of the vector. Even with move semantics, it still incurs one unnecessary copy of the accumulator for each element.

The three examples above are O(n).

std::accumulate is O(n²) for strings.

You could make std::accumulate O(n) for strings by supplying a custom functor:

std::string s = std::accumulate(v.begin(), v.end(), std::string{},
    [](std::string &s, const std::string &piece) -> decltype(auto) { return s += piece; });

Note that s must be a reference to non-const, the lambda return type must be a reference (hence decltype(auto)), and the body must use += not +.

C++20

In the current draft of what is expected to become C++20, the definition of std::accumulate has been altered to use std::move when appending to the accumulator, so from C++20 onwards, accumulate will be O(n) for strings, and can be used as a one-liner:

std::string s = std::accumulate(v.begin(), v.end(), std::string{});

Calash

I like the FP way, but it's a bit weird looking at the moment. Really looking forward to c++20 to clear things up! – Trichocyst

How do you come up with the idea that calling operator+= would result in linear growth? Unless you reserve the capacity string might need to relocate the content for every single append-operation. That is the same for +=, append and accumulate - they all can be O(n²) – Elisabethelisabethville

@Elisabethelisabethville Appending a single character is amortized O(1) in all major implementations. They grow the capacity by an exponential growth factor, so that the frequency of reallocation shrinks as the string grows. So after appending many characters, the total number of characters copied due to reallocation is proportional to the number of characters appended. accumulate being O(n²) would be a very pathological worst case, with O(n) being the average case. Summing the sizes to call reserve could be an optimization or a pessimization depending on the circumstances. – Calash

@Calash "in all major implementations." But it is not guaranteed by the standard so your claimed O(n) can very well be O(n²). On the other hand with reserve you would guarantee it to be O(n) – Elisabethelisabethville

Is it confirmed C++20 std::accumulate uses std::move ? – Formyl

@Formyl Yes: timsong-cpp.github.io/cppwp/n4868/accumulate#2 – Calash

Answer 2

You could use the std::accumulate() standard function from the <numeric> header (it works because an overload of operator + is defined for strings which returns the concatenation of its two arguments):

#include <vector>
#include <string>
#include <numeric>
#include <iostream>

int main()
{
    std::vector<std::string> v{"Hello, ", " Cruel ", "World!"};
    std::string s;
    s = accumulate(begin(v), end(v), s);
    std::cout << s; // Will print "Hello, Cruel World!"
}

Alternatively, you could use a more efficient, small for cycle:

#include <vector>
#include <string>
#include <iostream>

int main()
{
    std::vector<std::string> v{"Hello, ", "Cruel ", "World!"};
    std::string result;
    for (auto const& s : v) { result += s; }
    std::cout << result; // Will print "Hello, Cruel World!"
}

Predicament

Cute, but careless. It's going to allocate a new string for every single operation, because it uses operator+ and generates a new string, instead of operator+= to modify an existing one. – Barrelhouse

I've written a library using which it would be just s = v | sum(); that internally uses += instead of + ;-) – Maddie

@BenjaminLindley actually not for every since most implementations just twice capability each realloc – Lumpy

+1 for using free begin() end() instead of .begin .end member functions. – Liggins

@PSIAlt: Huh? Is that sentence missing some words? Because I don't understand it. – Barrelhouse

@PSIAlt: Read it again, it allocates a new string for every operation because every operations generates a new string. The doubling-size-optimization doesn't affect this. BenjaminLindley: he's talking about how string "doubles" it's capacity when you put too much in it. – Pitre

@BenjaminLindley actually if your dataset is very big, you may first want to iterate a first time and accumulate all the string sizes, reserve() the target string a single time and then iterate again using operator +=. This can avoid a lot of useless reallocations. – Bidle

@Bidle but this introduces useless vector iteration – Lumpy

@PSIAlt which is why I mentioned that it depends on your dataset. Given enough (long) strings in the vector, the cost for iterating twice (with allows us to have a single memory allocation) will be much lower than iterating only once and reallocating the memory several times. How useless and costly do you think it is to copy the same data over and over into larger and larger buffers? ;) – Bidle

Using GNU C++ 2011 v5.3.1, I got an error using said example: ' In function 'int main()' error: 's' was not declared in this scope std::cout << s; // Will print "Hello, Cruel World!"' – Mott

its result += s + " " if your vector doesn't have spaces between elements. – Crandell

Answer 3

My personal choice would be the range-based for loop, as in Oktalist's answer.

Boost also offers a nice solution:

#include <boost/algorithm/string/join.hpp>
#include <iostream>
#include <vector>

int main() {

    std::vector<std::string> v{"first", "second"};

    std::string joined = boost::algorithm::join(v, ", ");

    std::cout << joined << std::endl;
}

This prints:

first, second

Nihon

Answer 4

Why not just use operator + to add them together?

std::string string_from_vector(const std::vector<std::string> &pieces) {
   return std::accumulate(pieces.begin(), pieces.end(), std::string(""));
}

std::accumulate uses std::plus under the hood by default, and adding two strings is concatenation in C++, as the operator + is overloaded for std::string.

Namesake

I would name the function as to_string instead of string_from_vector. – Maddie

I probably would too, but that's the name that was used in the original question. – Namesake

Answer 5

Google Abseil has function absl::StrJoin that does what you need.

Example from their header file. Notice that separator can be also ""

//   std::vector<std::string> v = {"foo", "bar", "baz"};
//   std::string s = absl::StrJoin(v, "-");
//   EXPECT_EQ("foo-bar-baz", s);

Plummer

Answer 6

A little late to the party, but I liked the fact that we can use initializer lists:

std::string join(std::initializer_list<std::string> i)
{
  std::vector<std::string> v(i);
  std::string res;
  for (const auto &s: v) res += s;
  return res;   
}

Then you can simply invoke (Python style):

join({"Hello", "World", "1"})

Ite

Why are you taking a std::initializer_list instead of a std::vector? Also, I don't think you need to make a copy of the vector so could pass by const reference. – Nannana

@jb both initlist or vectors are wrong. what functions working with collections should take in are ranges. by application of duck typing principle, minimum requirement principle and decoupling principle. – Gelsemium

@Gelsemium what do you mean by "ranges" in this context? – Nannana

@Gelsemium that looks very cool, but in the context of this answer I think it's unfair to say a const std:vector<std::string>& is "wrong" when using range introduces a substantial third party dependency to solve the problem. If it is accepted into the standard library, then it becomes a different matter. – Nannana

@jb yes I'm thinking ahead of current standardization status. but there was an unsaid supplementary reason why I allowed myself this leap of faith, it's that you can replace "range" mentally with the next best thing we have right now and that is "two iterators". Squint your eyes to believe they are a range until it's true in c++20. Under this hypothesis it's still reasonable to say that init_list and vector are both wrong. It needs to be a template on some iterator type and take in begin and end. – Gelsemium

@Gelsemium that's an interesting approach I hadn't considered before. I always find myself wishing C++ had Python's iterables, the "two iterators" approach is kind of a way of achieving a similar pattern – Nannana

@jb yes, and this is the choice made by the library standard committee. You will find that all functions here en.cppreference.com/w/cpp/algorithm conform to the "two iterators" pattern. And probably will be ported to range in C++20. – Gelsemium

@jb I just finished writing an article that talks about that :) If you want to take a quick glance at it motsd1inge.wordpress.com/2019/03/22/… – Gelsemium

Answer 7

If requires no trailing spaces, use accumulate defined in <numeric> with custom join lambda.

#include <iostream>
#include <numeric>
#include <vector>

using namespace std;


int main() {
    vector<string> v;
    string s;

    v.push_back(string("fee"));
    v.push_back(string("fi"));
    v.push_back(string("foe"));
    v.push_back(string("fum"));

    s = accumulate(begin(v), end(v), string(),
                   [](string lhs, const string &rhs) { return lhs.empty() ? rhs : lhs + ' ' + rhs; }
    );
    cout << s << endl;
    return 0;
}

Output:

fee fi foe fum

Statist

Answer 8

With c++11 the stringstream way is not too scary:

#include <vector>
#include <string>
#include <algorithm>
#include <sstream>
#include <iostream>

int main()
{
    std::vector<std::string> v{"Hello, ", " Cruel ", "World!"};
   std::stringstream s;
   std::for_each(begin(v), end(v), [&s](const std::string &elem) { s << elem; } );
   std::cout << s.str();
}

Lumpy

Why not use for (auto &i: v) { s << i; } instead of the for_each line? – Bolyard

Why even use a stringstream at all? Make s a string, and make the lambda { s += elem } – Calash

@Calash no! it's the schoolbook example of Schlemiel the painter pessimization. joelonsoftware.com/2001/12/11/back-to-basics – Gelsemium

@Gelsemium It's not a Schlemiel the painter, as std::string knows its own length. It doesn't have to iterate over s to find the null terminator. It could be improved, though, by using std::string::reserve to avoid repeated allocations for s. See also my top-voted (but not accepted) answer above. – Calash

@Calash I also upvoted your answer, it's great. But "knows its own size" doesn't appear to be guaranteed https://mcmap.net/q/102725/-is-std-string-size-a-o-1-operation – Gelsemium

@Calash ok apparently it IS guaranteed when considering end()-begin() #256533 so don't mind my blabber. – Gelsemium