C++ Split string into a vector

Question

While profiling parts of my code, I noticed that my Split( ... ) function is rather slow, (about 50% of the time). I was wondering if there was a more efficient way of Splitting a string into a vector.

My subject string can be anything between 2 words to well over 1000 words, hence the reason why I would like to speed it up.

Here is an example program with the function.

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

void Split(const std::string& subject, std::vector<std::string>& container)
{
  container.clear();
  size_t len = subject.length() + 1;
  char* s = new char[ len ];
  memset(s, 0, len*sizeof(char));
  memcpy(s, subject.c_str(), (len - 1)*sizeof(char));
  for (char *p = strtok(s, " "); p != NULL; p = strtok(NULL, " "))
  {
    container.push_back( p );
  }
  delete[] s;
}

int main()
{
  std::vector<std::string> container;
  Split( "Hello World", container );

  for( std::vector<std::string>::const_iterator it = container.begin(); it != container.end();++it)
  {
    std::cout << *it << "!\n";
  }
}

Any suggestions on how I could speed it up.

Of course any other general comments are more than welcome.

Edit profiling is very simple.

...
clock_t t = clock (); 
std::vector<std::string> container;
Split( "actus non facit reum nisi mens sit rea", container );
t = clock() - t;
std::cout << (((float)t)/CLOCKS_PER_SEC) << "ms\n";
...

Answer 1

I haven't attempted to measure the timing of this, in part because I don't know how you're planning to use it, but here are some ideas for improving your code.

Consider returning something useful from functions

Your Split function doesn't return anything, which isn't an error, but it's an odd design. I'd expect it to be declared like this instead:

std::vector<std::string> Split(const std::string& subject)

Understand sizeof

The sizeof operator is defined as always returning 1 for sizeof(char), so having that expression as part of your code probably isn't useful.

Use "range for" to simplify your code

The code to print the vector could be made much simpler and shorter by using a "range for" that was introduced in C++11:

for(const auto &item : container) {
    std::cout << item << "!\n";
}

Use standard library algorithms

I'd be inclined to write this using C++ rather than C functions. One way to do this is to use std::copy and std::stringstream:

std::vector<std::string> Split(const std::string& subject)
{
    std::istringstream ss{subject};
    using StrIt = std::istream_iterator<std::string>;
    std::vector<std::string> container{StrIt{ss}, StrIt{}};
    return container;
}

I've also been playing with std::sregex_token_iterator lately. Here's how that might look:

std::vector<std::string> Split(const std::string& subject) {
    static const std::regex re{"\\s+"};
    std::vector<std::string> container{
        std::sregex_token_iterator(subject.begin(), subject.end(), re, -1), 
        std::sregex_token_iterator()
    };
    return container;
}

Answer 2

Avoid unnecessary dynamic allocations

Right now, you're dynamically allocating memory, and copying the input data into that dynamically allocated buffer, almost exclusively so you can use strtok to do the tokenizing.

Avoid unnecessary work

You're also zeroing that entire block of dynamically allocated memory, then immediately copying the data from the input over the zeros you just wrote into the block.

If you're going to mess with something like this at all, you can probably speed it up at least a little just by avoiding that unnecessary zeroing.

auto *s = new char [strlen(input)+1];
strcpy(s, input);

Get from input to output as directly as possible

I'd rather avoid that amount of copying, and create results directly from the input data instead, something like this:

std::vector<std::string> tokenize(std::string const &in) {
    char sep = ' ';
    std::string::size_type b = 0;
    std::vector<std::string> result;

    while ((b = in.find_first_not_of(sep, b)) != std::string::npos) {
        auto e = in.find_first_of(sep, b);
        result.push_back(in.substr(b, e-b));
        b = e;
    }
    return result;
}

Although it's difficult to be certain without profiling, my guess is that this has less overhead than using a stringstream or a regex token iterator to do the job. A heavily optimized regex library might get pretty close (possibly even close enough to make differences irrelevant). stringstreams can make for neat code, so as long as you don't care about the overhead, they're often an excellent choice--but at a guess, using a stringstream is going to end up slower than your current code.

Consider using string_view instead of string

If you can afford to restrict your code to C++17 (or later), consider using a string_view for the input, rather than an std::string. A string_view gives you string-like access to some data, but without actually storing that data in the string_view object itself. At least in the typical implementation, it stores only the location and length of the data.

The same principle can be applied to the result: instead of each result being a string that holds a copy of the data from the input, you might be able to use a string_view that holds only a location and length for each. This can be a little tricky though. In particular, it makes you responsible for lifetime issues--since you're storing references to the original input data, you need to ensure that the original input data remains valid for as long as you might use the tokens you've created from that input. In your case (string literals) that's pretty trivial (they have static storage duration, so they're always valid). For real use, where you're tokenizing some string that came from user input, it may be more difficult (but if you can do it, it can be a substantial win).

Be sure you're using a current standard library

Many older implementations of the standard library used implementations of std::string that always allocated storage for the string's data dynamically. This typically means creating a string has a fairly substantial amount of overhead, regardless of its size.

More recent implementations of the standard library typically use what's called a "short string optimization". This means they allocate enough storage for a short string (for some arbitrary definition of short, but usually around 16-32 characters) inside the string object itself. This avoids a dynamic allocation for the buffer space when you're storing lots of small strings (e.g., your result tokens/words, probably). The speed difference can be pretty dramatic (I've seen around 10:1 pretty routinely).