I wrote the equivalent to the split() in python for C++. I would like to know how I can make it better:

static constexpr auto whitespace = " \t\v\r\n\f";
static constexpr auto npos = std::string::npos;

std::vector<std::string> split(std::string_view str, std::string_view sep = "", std::size_t maxsplit = std::numeric_limits<std::size_t>::max())
{
    std::vector<std::string> result;
    if (sep.empty())
    {
        for (std::size_t start = str.find_first_not_of(whitespace), splits = 0; start != npos; ++splits)
        {
            if (auto end = str.find_first_of(whitespace, start); end != npos && splits < maxsplit)
            {
                result.emplace_back(str.substr(start, end - start));
                start = str.find_first_not_of(whitespace, end);
            }
            else
            {
                result.emplace_back(str.substr(start));
                break;
            }
        }
    }
    else
    {
        for (std::size_t start = 0, splits = 0; start < str.size(); ++splits)
        {
            if (auto end = str.find(sep, start); end != npos && splits < maxsplit)
            {
                result.emplace_back(str.substr(start, end - start));
                start = end + sep.size();
            }
            else
            {
                result.emplace_back(str.substr(start));
                break;
            }
        }
    }
    return result;
}

I tried to keep all variables as local as possible and use standard algorithms.

up vote 3 down vote accepted

Your function has two different behaviors:

  • either you split the input string using each of characters as possible separator (spaces case)
  • or you use a bunch of characters as a whole delimiter.

That's why you can not refactor in one branch, separate it into two functions:

  • split_any: which takes a list of characters as multiple separators possible. And as fallback if no separator given, take whitespace as default parameter.
  • split: which takes a string of one to several characters as whole separator. And if no separator given, you can either return the whole string as unique element of the vector, or fallback calling split_any without separator.

(the names are for the example)

I tried to keep all variables as local as possible and use standard algorithms.

Except that you declare two global variables in the global namespace. Especially since you do not really need these variables:

  • npos: It's just an alias of std::string::npos that you use like it was a std::string_view::npos, although they have the same value (basically std::size_t{ -1} so the biggest unisigned integer possible), you should not, they don't have the same type (std::string::size_type and std::string_view::size_type), it's a bad habit. Finally, you don't need it outside of your function, so, simply use std::string_view::npos directly in your function.
  • whitespace: Since you use it as a default fallback value, why don't simply using it as a default value for sep instead of an empty std::string_view?

unlike @MartinYork, I would not have set the parameters to const & but only to const since the purpose of astd :: string_view is already to avoid copying. But marking the non-mutable parameters const is the way to go.

maxsplit/splits: Instead of declaring a "splits" variable and checking it not reached maxsplit, simply decrease maxsplit and check if it fall to zero.

It would be nice to have an overload to be able to pass a char as a separator, it is a very common case.

If you're targeting performance there is a comparative benchmark of different methods.

  • whitespace can't simply be the fallback value - splitting on whitespace really means splitting an any number of any of the whitespace characters, not on the exact string " \t\v\r\n\f". – Toby Speight Nov 5 at 11:25
  • Yeah, read my comment from the beginning. So whitespace can by a fallback through a function split_any. It might not be clear. – Calak Nov 5 at 11:54
  • Accepted because I find the benchmark interesting as well, but all answers were good. However, I think the way he splits strings is hardly useful - he neither splits at a separator with multiple characters, nor does he remove consecutive characters for a "split_any" approach. – smoothware Nov 8 at 22:01
  • @smoothware And for splitting by a single char, his versions are still much slower than using str.find(char). – smoothware Nov 8 at 22:37

We're doing two distinct things in this function:

  • finding the start and end of the substrings of interest
  • packaging the results into a container.

We might be able to get a more flexible implementation by using the Strategy pattern to allow us to choose each part independently. That would allow us to support different kinds of splitting (fixed string, whitespace, set of characters, regular expression, or more), and would allow us to return different types (set of std::string, vector of std::string_view, or others) without a combinatorial explosion in the amount of code we write.

I'd start with the interface of the strategy function itself. I think a good start would be to pass the string view and beginning position, and have it return the positions of the start and end positions of the next token or next separator (one or both could be the appropriate npos, of course). Equivalently, pass it the trailing substring to avoid the need for the beginning position argument, and return offset and count for compatibility with standard string and string-view functions:

std::pair<std::string_view::size_type, std::string_view::size_type>
find(std::string view s);

The way we can generalize the return of results is the same way that it's done in the standard library - pass an output iterator. Then we can give results to any kind of container we like, or use them immediately, without need for a container.

This gets a bit harder when we want to construct strings from the views, since the necessary constructor is declared explicit. I needed to create a proxy iterator to perform this construction.

Finally, we might want to accept wide strings, and it would be good to match all known whitespace rather than just the portable subset - we can use std::isspace() for that, but we do need to launder its argument via unsigned char before promotion.


My version

#include <algorithm>
#include <cctype>
#include <iterator>
#include <limits>
#include <regex>
#include <string>
#include <vector>

// Split the input view according to chunks identified by the specified
// finder, and write the results to the output iterator.
template<typename Iter, typename View, typename Finder>
Iter split_impl(Iter out,
                View str,
                Finder finder,
                std::size_t maxsplit = std::numeric_limits<typename View::size_type>::max())
{
    for (std::size_t splits = 1;  splits < maxsplit && !str.empty();  ++splits) {
        auto [start,end] = finder(str);
        if (start == 0) {
            // ignore consecutive separators
            --splits; 
        } else if (start == str.npos) {
            // last part of string
            *out++ = str;
            return out;
        } else {
            // separator found
            *out++ = str.substr(0, start);
            str = str.substr(end);
        }
    }
    // Have we a final match?  Ignore the end.
    if (!str.empty()) {
        *out++ = str;
    }
    return out;
}


template<typename View, typename Finder>
auto split_to_vector(View str,
                     Finder finder,
                     std::size_t maxsplit = std::numeric_limits<typename View::size_type>::max())
{
    std::vector<View> result;
    split_impl(result.back_inserter(), str, finder, maxsplit);
    return result;
}


template<typename View, typename Finder>
auto split_to_strings(View str,
                     Finder finder,
                     std::size_t maxsplit = std::numeric_limits<typename View::size_type>::max())
{
    using String = std::basic_string<typename View::value_type>;
    using Container = std::vector<String>;

    // An iterator wrapper to construct strings from views
    struct inserter : std::back_insert_iterator<Container> {
        using base_inserter = std::back_insert_iterator<Container>;
        inserter(Container& c) : base_inserter(c) {}
        // automatically construct string from view
        inserter& operator=(View v) {
            String s(v);
            base_inserter::operator=(std::move(s));
            return *this;
        }
        inserter& operator++() { base_inserter::operator++(); return *this; }
        inserter operator++(int i) { base_inserter::operator++(i); return *this; }
        inserter& operator*() { return *this; }
    };

    Container result;
    split_impl(inserter{result}, str, finder, maxsplit);
    return result;
}


std::vector<std::string> split(std::string_view str,
                               std::size_t maxsplit = std::numeric_limits<std::size_t>::max())
{
    auto finder = [](std::string_view str) {
        static auto const isspace = [](unsigned char c){ return std::isspace(c); };
        auto start = std::find_if(str.begin(), str.end(), isspace);
        auto end = std::find_if_not(start, str.end(), isspace);
        return std::pair{start == str.end() ? str.npos : start - str.begin(),
                end == str.end() ? str.npos : end - str.begin()};
    };

    return split_to_strings(str, finder, maxsplit);
}

std::vector<std::string> split(std::string_view str,
                               std::string_view sep,
                               std::size_t maxsplit = std::numeric_limits<std::size_t>::max())
{
    auto finder = [sep,len=sep.size()](std::string_view str) {
        auto start = str.find(sep);
        return start == str.npos
            ? std::pair{str.npos, str.npos}
            : std::pair{start,start+len};
    };

    return split_to_strings(str, finder, maxsplit);
}

std::vector<std::string> split(std::string_view str,
                               std::regex const& sep,
                               std::size_t maxsplit = std::numeric_limits<std::size_t>::max())
{
    auto finder = [sep](std::string_view str) -> std::pair<std::size_t, std::size_t> {
        std::match_results<std::string_view::iterator> loc;
        if (std::regex_search(str.begin(), str.end(), loc, sep)) {
            return {std::distance(str.begin(), loc.prefix().second),
                    std::distance(str.begin(), loc.suffix().first)};
        } else {
            return {str.npos, str.npos};
        }
    };

    return split_to_strings(str, finder, maxsplit);
}


#include <iostream>
int main()
{
    auto *alice =
        "Alice was beginning to get very tired of sitting by her sister on the "
        "bank, and of having nothing to do: once or twice she had peeped into the "
        "book her sister was reading, but it had no pictures or conversations in "
        "it, ‘and what is the use of a book,’ thought Alice ‘without pictures or "
        "conversations?’";

    //auto words = split(alice);
    auto words = split(alice, std::regex{"\\W+"});

    std::size_t total_len = 0;
    for (auto const& w: words) { total_len += w.size(); }

    std::cout << "Average word length = "
              << 1.0 * total_len / words.size()
              << '\n';
}

There's a bit more code here, and it's overkill if you're not going to make use of the generalization, but it might help improve your insight if nothing else!

I've made a few choices here that you might reasonably make differently - you could return match and remainder views from your Finder instead of start and end positions, or you might return iterators. It may be worth experimenting to see which are easiest to work with.


Opportunities

Although I've made the code above quite general, I did hold back from supporting different string types (e.g. std::wstring). Doing so might make a good exercise!

  • Thank you for showing a quite different version to learn from. – smoothware Nov 8 at 22:01

I would use a const reference here:

static constexpr auto npos = std::string::npos;

// I would do this.
static constexpr auto const& npos = std::string::npos;

No point in duplicating storage.
Also declaring global variables is a frowned upon. Especially if they are in the global namespace. At a minimum these should be inside your own namespace, but preferably they should be inside the function.

Dyslexia strikes.
I read the next part to have std::string not std::string_view.
Prefer to pass parameters (especially those that are not mutated) by const reference. This prevents a copy.

std::vector<std::string> split(std::string_view const& str, std::string_view const& sep = "", std::size_t maxsplit = std::numeric_limits<std::size_t>::max())

                                               ^^^^^^^^                     ^^^^^^^^

I don't like this:

if (auto end = str.find_first_of(whitespace, start); end != npos && splits < maxsplit)

I did find that this is a C++17 extension. But it puts way too much information on one line. Personally I would split this across two lines.

auto end = str.find_first_of(whitespace, start);
if (end != npos && splits < maxsplit)

As a side note splitting the line by white space can be written more simply as:

 std::stringstream  stream(str);
 return std::vector<std::string>(std::istream_iterator<std::string>(stream),
                                 std::istream_iterator<std::string>());
  • I thought that std::string_view is intentionally cheap to copy? It's usually implemented as a pair of pointers or similar, so likely cheaper to pass by value than to use via a reference (and if inlined and optimized, should result in identical code). – Toby Speight Nov 5 at 10:58
  • I disagree with you a little on the if with assignment. Yes, I'd add a line-break after the semicolon, but splitting into two statements loses a small benefit, of restricting the scope of end. – Toby Speight Nov 5 at 11:00
  • @TobySpeight Somehow I missed it was a string view and only saw string. – Martin York Nov 5 at 22:26
  • @TobySpeight I sought of see the scope argument. But that makes for a very ugly if statement. In this context I don't see the need or that it buys you anything. – Martin York Nov 5 at 22:30
  • Yes, the scope is already small enough that there's no problem with splitting it here - I think you changed my mind. Still, it can be a consideration in other code, and splitting the line between the initializer and condition could be a helpful way to wrestle the program into a sensible line length (and the line length here definitely needed some attention). – Toby Speight Nov 5 at 22:46

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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