split string into container on char; efficiently?

Question

Here is my single parse code for splitting a std::string on a char into a std::vector<std::string>:

#include <iostream>
#include <vector>

std::vector<std::string> split_uri(std::string, unsigned chr='/');

int main() {
    std::vector<std::string> uri_v = split_uri(uri, '/');

    for (auto elem: uri_v)
         std::cout << elem << std::endl;
}

std::vector<std::string> split_uri(std::string uri, unsigned chr) {
    bool start=true;
    std::string part;
    std::vector<std::string> vec;
    vec.reserve(uri.length()/2);

    for(char c: uri) {
        switch(c) {
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
            case 'a':
            case 'b':
            case 'c':
            case 'd':
            case 'e':
            case 'f':
            case 'g':
            case 'h':
            case 'i':
            case 'j':
            case 'k':
            case 'l':
            case 'm':
            case 'n':
            case 'o':
            case 'p':
            case 'q':
            case 'r':
            case 's':
            case 't':
            case 'u':
            case 'v':
            case 'w':
            case 'x':
            case 'y':
            case 'z':
                part += c;
                break;
            default:
                if (c == chr) {
                    if (!start)
                        vec.push_back(part);
                    else start = false;
                    part.clear();
                    part += c;
                }
                else {
                    std::cerr << "Invalid URI; from: \'" << c << "\' (hex: " << std::hex << "0x" << (unsigned int)c << ")\n";
                    vec.clear();
                    return vec;
                }
        }
    }

    return vec;
}

What can I do to improve its efficiency?

Your edit is invalid: case chr: won't work since chr is not a constant expression. — Morwenn, Apr 4 at 8:58
That won't work either. case only accepts integer and char literals, not generalized constant expressions. — Morwenn, Apr 4 at 8:59
Actually you can create a hash table of sorts at compile time using constexpr and a switch/case. — A T, Apr 4 at 9:02

mrm · Accepted Answer · 2014-04-04 10:37:56Z

up vote 4 down vote accepted

First, consider passing potentially expensive-to-copy objects such as std::string as const reference rather than by-value. The obvious approach is to use std::istringstream and std::getline.

std::vector<std::string> split_uri(const std::string uri&, char chr)
{
    std::istringstream iss(uri);
    std::vector<std::string> vec;

    for(std::string token; getline(iss, token, chr); )
        vec.push_back(token);

    return vec;
}

With the input being \bar\can, the output is {"", "bar", "can"}.

However, std::istringstream is not known for its speed. If you don't want to use std::istringstream, you don't have to. The following should be much faster:

std::vector<std::string> split_uri(const std::string& uri, char chr)
{
    std::string::const_iterator first = uri.cbegin();
    std::string::const_iterator second = std::find(first+1, uri.cend(), chr);
    std::vector<std::string> vec;

    while(second != uri.cend())
    {
        vec.emplace_back(first, second);
        first = second;
        second = std::find(second+1, uri.cend(), chr);
    }

    vec.emplace_back(first, uri.cend());

    return vec;
}

With the input being \bar\can, the output is {"\bar", "\can"}.

edited Apr 4 at 10:37

answered Apr 4 at 9:17

mrm
1763

That's much more concise; and skips the string concatenation overhead. Is it more efficient overall? – A T Apr 4 at 9:23

@mrm That's indeed way more concise. However, I tried to benchmark that with g++ -O3 and it seems 1.5 times slower than the first version. It was even 2.5 times slower with clang++ -O3. – Morwenn Apr 4 at 9:29

@mrm Ok, that second version is like two to three times faster than the OP one on both compilers. It's even faster if you replace push_back(std::string(...)) by emplace_back(...). – Morwenn Apr 4 at 10:23

@Morwenn Cool! And yeah, of course. Let's do emplace_back too :-) – mrm Apr 4 at 10:36

Great; thanks. I've used your second one with a slight edit (for rather than while). – A T Apr 9 at 8:41

add comment

Loki Astari · Answer 2 · 2014-04-04 18:22:20Z

I would have done:

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

The Work

// A generic routine to split a string into pieces and put
// them into an array. The array is then returned (not expensive
// because of RVO).
//
// The Splitter merely needs to be convertible to the type Return
// and can be used with `operator>>` so you can read it from a stream.
// 
// In a user defined type this means:
// 1)  defining a cast operator
//       operator Return () const {return <A Return Type>;}
//
// 2)  defining operator>> as a function
//       that takes the class as a second parameter and reads 
//       it from the stream.
//
// Note: But it can be used by any types (not just custom types)
//   std::vector<int>         data1(splitString<int>("1 2 3 4 5 6"));
//   std::vector<std::string> data2(splitString<std::string>("A word per item"));
// 
template<typename Result, typename Spliter = Result>
std::vector<Result> splitString(std::stringstream input)
{
    typedef std::istream_iterator<Spliter>    Iterator;
    return std::vector<Result>(Iterator(input), Iterator());
}

Simple Utility class as an example

// A simple class that reads `split` separated string objects 
// from a stream. This is a simple utility class that works well
// with std::istream_iterator.
// 
template<char split>
struct Part
{
    std::string  part;
    operator std::string const& () const {return part;}
    friend std::istream& operator>>(std::istream& s, Part& data)
    {
        // This is a simple example.
        // It does not duplicate the functionality of the code
        // provided by the OP. But this is where it would go.

        return std::getline(s, data.part, split);
    }
};

Put it all together

int main()
{
    std::string  str("Part1/Part2/Part3/Part4");
    std::vector<std::string>    data(splitString<std::string, Part<'/'>>(str));

    std::copy(std::begin(data), std::end(data), std::ostream_iterator<std::string>(std::cout, "\n"));


}

asked	17 days ago
viewed	70 times
active	16 days ago

current community

your communities

more stack exchange communities

split string into container on char; efficiently?

2 Answers

The Work

Simple Utility class as an example

Put it all together

Your Answer

Not the answer you're looking for? Browse other questions tagged c++ performance memory-management vectors cyclomatic-complexity or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

split string into container on char; efficiently?

2 Answers

The Work

Simple Utility class as an example

Put it all together

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++ performance memory-management vectors cyclomatic-complexity or ask your own question.

Related

Hot Network Questions