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\$
  • \$\begingroup\$ Your edit is invalid: case chr: won't work since chr is not a constant expression. \$\endgroup\$ – Morwenn Apr 4 '14 at 8:58
  • \$\begingroup\$ Yeah; was just looking into constexpr for that. \$\endgroup\$ – A T Apr 4 '14 at 8:58
  • \$\begingroup\$ That won't work either. case only accepts integer and char literals, not generalized constant expressions. \$\endgroup\$ – Morwenn Apr 4 '14 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 '14 at 9:02
  • 1
    \$\begingroup\$ PS: A URI is a bit more complex than that. \$\endgroup\$ – Martin York Apr 4 '14 at 15:19
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\$
  • \$\begingroup\$ That's much more concise; and skips the string concatenation overhead. Is it more efficient overall? \$\endgroup\$ – A T Apr 4 '14 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 '14 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 '14 at 10:23
  • \$\begingroup\$ @Morwenn Cool! And yeah, of course. Let's do emplace_back too :-) \$\endgroup\$ – Juho Apr 4 '14 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 '14 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, privacy policy and cookie policy

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