`std::split()`: An algorithm for splitting strings

ISO/IEC JTC1 SC22 WG21 N3510 - 2013-01-10

Greg Miller, jgm@google.com

Introduction

Splitting strings into substrings is a common task in most general-purpose programming languages, and C++ is no exception. When the need arises, programmers need to search for an existing solution or write one of their own. A typical solution might look like the following:

    std::vector<std::string> my_split(const std::string& text, const std::string& delimiter);

A straightforward implementation of the above function would likely use std::string::find or std::string::find_first_of to identify substrings and move from one to the next, building the vector to return. This is a fine solution for simple needs, but it is deficient in the following ways:

Must be reimplemented by each individual/organization
Not adaptable to different types of delimiter, such as regular expressions
Not adaptable to different return types, such as std::set<string>

Google developed a flexible and fast string-splitting API to address these deficiencies. The new API has been very well received by internal engineers writing real code. The rest of this paper describes Google's string splitting API as it might appear as a C++ standard.

This proposal depends on the following proposals:

Changes in this revision

The previous version of this proposal is N3430. The std::split() function described in this proposal has been greatly simplified from the previous proposal. The following are the major changes in this revision:

No implicit type conversion. std::split() will return a Range, which itself can be used with range-aware STL containers per the Range proposal (N3513).
std::split() will return a range of std::string_ref objects only. Users will need to explicitly convert the returned values to std::string if desired.
No split-specific predicates for filtering split results (i.e., no std::skip_empty()). Operations to filter or transform the returned range can be implemented separately. Any generic Range Adapter library (e.g., Boost.RangeAdapters) will work on the range returned from std::split().

std::split() API

    namespace std {

      template <typename Delimiter>
      auto split(std::string_ref text, Delimiter d) -> split_range<Delimiter>;

    }

The std::split() algorithm takes a std::string_ref and a Delimiter as arguments, and it returns a Range of std::string_ref objects as output. The std::string_ref objects in the returned Range refer to substrings of the input text. The Delimiter object defines the boundaries between the returned substrings. This is fairly common splitting behavior that is followed in many programming languages.

Delimiters

The general notion of a delimiter (aka separator) is not new. A delimiter (little d) marks the boundary between two substrings in a larger string. With the std::split() API comes the generalized concept of a Delimiter (big D). A Delimiter is an object with a find() member function that can find the next occurrence of itself in a given std::string_ref. Objects that conform to the Delimiter concept represent specific kinds of delimiters, such as single characters, substrings, and regular expressions.

The result of a Delimiter's find() member function must be a std::string_ref referring to one of the following:

A substring of find()'s argument text. This is the delimiter/separator that was found.
An empty std::string_ref with a null data member (e.g., std::string_ref(nullptr, 0)). This indicates that the delimiter/separator was not found.

The following example shows a simple object that models the Delimiter concept. It has a find() member function that is responsible for finding the next occurrence of a char in the given text.

    struct char_delimiter {
      char c_;
      explicit char_delimiter(char c) : c_(c) {}
      std::string_ref find(std::string_ref text) {
        int pos = text.find(c_);
        if (pos == std::string_ref::npos)
          return std::string_ref(nullptr, 0);  // Not found, returns null std::string_ref.
        return std::string_ref(text, pos, 1);  // Returns a string_ref referring to the c_ that was found in the input string.
      }
    };

The following shows how the above delimiter could be used to split a string:

    std::vector<std::string_ref> v{std::split("a-b-c", char_delimiter('-'))};
    // v is {"a", "b", "c"}

The following are standard delimiter implementations that will be part of the splitting API.

std::literal_delimiter
std::any_of_delimiter

The split_range<T>

std::split() returns a Range (i.e. an object with begin() and end() methods returning iterators) whose value type is std::string_ref. The actual type returned by std::split() will not be exposed as part of the API.

Rvalue support

As described so far, std::split() may not work correctly if splitting a std::string_ref that refers to a temporary string. In particular, the following will not work:

    for (std::string_ref s : std::split(ReturnTemporaryString(), "-")) {
        // s now refers to a temporary string that is no longer valid.
    }

To address this, std::split() will move ownership of rvalues into the returned range.

API Synopsis

std::split()

The function called to split an input string into a range of substrings.

    namespace std {

      template <typename Delimiter>
      auto split(std::string_ref text, Delimiter d) -> split_range<Delimiter>;

    }

Requires:: the text to be split and a Delimiter on which to split the text. The Delimiter argument may be an object that models the Delimiter concept. Or, if the Delimiter argument is a std::string, std::string_ref, const char*, or a single char, the std::literal_delimiter will be used by default.
Returns:: a Range of std::string_ref objects, each referring to the split substrings within the given input text.

[Footnote:

One question at this point is: why is this constrained to strings/string_refs? One could imagine std::split() as an algorithm that transforms an input Range into an output Range of Ranges. This would make the algorithm more generally applicable.

However, this generalization may also make std::split() less convenient in the expected common case: that of splitting string data. For example, the logic for detecting when to auto-construct a std::literal_delimiter may be more complicated, and it may not be clear that that is a reasonable default delimiter anyway.

—end footnote]

Delimiter template parameter

The second argument to std::split() may be an object that models the Delimiter concept. A Delimiter object must have the following member function:

    std::string_ref find(std::string_ref text);

This function is responsible for finding the next occurrence of the represented delimiter in the given text.

Requires:: text is the remaining text to be split
Returns:: a std::string_ref referring to the found delimiter within the given input text. Or std::string_ref(nullptr, 0) if the delimiter was not found.

[Footnote: One could imagine a Delimiter implementation that needs more context into the overall string being split in order to work correctly. For example, a regex_delimiter might need this ability to correctly match word boundaries ("\\b") given that "\\b" will always match the beginning of the string. For this reason, it may be better to change the Delimiter API to require that Delimiter objects provide a member function like the following:

    std::string_ref find(std::string_ref text, size_t pos);

In this case, the delimiter will always be given the full input text being split along with the position in the text where it should start looking for the next delimiter. —end footnote]

std::literal_delimiter

A string delimiter. This is the default delimiter used if a string is given as the delimiter argument to std::split().

The delimiter representing the empty string (std::literal_delimiter("")) will be defined to return each individual character in the input string. This matches the behavior of splitting on the empty string "" in perl.

    namespace std {

      class literal_delimiter {
       public:
        explicit literal(string_ref sref)
        : delimiter_(static_cast<string>(sref)) {}
        string_ref find(string_ref text) const;

       private:
        const string delimiter_;
      };

    }

Requires:: text is the text to be split
Returns:: A std::string_ref referring to the first substring of text that matches delimiter_. Or std::string_ref(nullptr, 0) if not found.

std::any_of_delimiter

Each character in the given string is a delimiter.

    namespace std {

      class any_of_delimiter {
       public:
        explicit any_of(string_ref sref)
        : delimiters_(static_cast<string>(sref)) {}
        string_ref find(string_ref text) const;

       private:
        const string delimiters_;
      };

    }

Requires:: text is the text to be split
Returns:: A std::string_ref referring to the first occurrence of any character from delimiters_ that is found in text. In this case, the length of the returned std::string_ref will be 1. Or std::string_ref(nullptr, 0) if none are found.

API Usage

The following using declarations are assumed for brevity:

    using std::deque;
    using std::list;
    using std::set;
    using std::string_ref;
    using std::vector;

The default delimiter when not explicitly specified is std::literal_delimiter. The following two calls to std::split() are equivalent. The first form is provided for convenience.
```
    vector<string_ref> v1{std::split("a-b-c", "-")};
    vector<string_ref> v2{std::split("a-b-c", std::literal_delimiter("-"))};
    
```

Empty substrings are included in the output.

    vector<string_ref> v{std::split("a--c", "-")};
    assert(v.size() == 3);  // "a", "", "c"

The previous example showed that empty substrings are included in the output. Leading and trailing delimiters result in leading and trailing empty strings in the output.
```
    vector<string_ref> v{std::split("-a-b-c-", "-")};
    assert(v.size() == 5);  // "", "a", "b", "c", ""
    
```

Results can be assigned to STL containers that support the Range concept.

    vector<string_ref> v{std::split("a-b-c", "-")};
    deque<string_ref> v{std::split("a-b-c", "-")};
    set<string_ref> s{std::split("a-b-c", "-")};
    list<string_ref> l{std::split("a-b-c", "-")};

A delimiter of the empty string results in each character in the input string becoming one element in the output collection. This is a special case. It is done to match the behavior of splitting using the empty string in other programming languages (e.g., perl).
```
    vector<string_ref> v{std::split("abc", "")};
    assert(v.size() == 3);  // "a", "b", "c"
    
```

Iterating the results of a split in a range-based for loop.

    for (string_ref sref : std::split("a-b-c", "-")) {
      // use sref
    }

Splitting input text that is the empty string results in a collection containing one element that is the empty string.
```
    vector<string_ref> v{std::split("", "any delimiter")};
    assert(v.size() == 1);  // ""
    
```
[Footnote: This is logical behavior given that std::split() doesn't skip empty substrings. However, it might be surprising behavior to some users. Would it be better if the result of splitting an empty string resulted in an empty Range? —end footnote]

std::split(): An algorithm for splitting strings

Changes in this revision

Rvalue support

`std::split()`: An algorithm for splitting strings