2
\$\begingroup\$

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?

\$\endgroup\$
9
  • \$\begingroup\$ Your edit is invalid: case chr: won't work since chr is not a constant expression. \$\endgroup\$
    – Morwenn
    Apr 4, 2014 at 8:58
  • \$\begingroup\$ Yeah; was just looking into constexpr for that. \$\endgroup\$
    – A T
    Apr 4, 2014 at 8:58
  • \$\begingroup\$ That won't work either. case only accepts integer and char literals, not generalized constant expressions. \$\endgroup\$
    – Morwenn
    Apr 4, 2014 at 8:59
  • \$\begingroup\$ Actually you can create a hash table of sorts at compile time using constexpr and a switch/case. \$\endgroup\$
    – A T
    Apr 4, 2014 at 9:02
  • 1
    \$\begingroup\$ PS: A URI is a bit more complex than that. \$\endgroup\$ Apr 4, 2014 at 15:19

2 Answers 2

4
\$\begingroup\$

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"}.

\$\endgroup\$
5
  • \$\begingroup\$ That's much more concise; and skips the string concatenation overhead. Is it more efficient overall? \$\endgroup\$
    – A T
    Apr 4, 2014 at 9:23
  • \$\begingroup\$ @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. \$\endgroup\$
    – Morwenn
    Apr 4, 2014 at 9:29
  • \$\begingroup\$ @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(...). \$\endgroup\$
    – Morwenn
    Apr 4, 2014 at 10:23
  • \$\begingroup\$ @Morwenn Cool! And yeah, of course. Let's do emplace_back too :-) \$\endgroup\$
    – Juho
    Apr 4, 2014 at 10:36
  • \$\begingroup\$ Great; thanks. I've used your second one with a slight edit (for rather than while). \$\endgroup\$
    – A T
    Apr 9, 2014 at 8:41
1
\$\begingroup\$

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"));


}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.