Tokeniser which yields a Range of string views

Question

In my answer to string_view tokenizer function template I suggested that a flexible tokeniser would yield a Range that could be iterated over. This is my implementation of such a tokeniser.

#include <concepts>
#include <cstddef>
#include <functional>
#include <iterator>
#include <ranges>
#include <string_view>
#include <utility>

namespace parser
{
    template<typename T>
    using search_func = std::function<typename T::size_type(T)>;

    template<typename StringView>
    class token_iter
    {
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = StringView;
        using reference = value_type const&;
        using pointer = value_type const*;
        using difference_type = std::ptrdiff_t;

        using token_search = search_func<value_type>;

    private:
        value_type input = {};

        token_search find_start = {};
        token_search find_end = {};

        value_type current_token = {};

    public:
        token_iter(token_search find_start, token_search find_end,
                   value_type input = {})
            : input{input},
              find_start{find_start},
              find_end{find_end},
              current_token{get_next()}
        {}
        token_iter() = default;
        ~token_iter() = default;

        token_iter(token_iter const&) = default;
        token_iter(token_iter&&) = default;
        token_iter& operator=(token_iter const&) = default;
        token_iter& operator=(token_iter&&) = default;

        reference& operator*()
        {
            return current_token;
        }

        pointer operator->()
        {
            return &current_token;
        }

        token_iter& operator++()
        {
            current_token = get_next();
            return *this;
        }

        token_iter operator++(int)
        {
            auto const it = *this;
            ++*this;
            return it;
        }

        // it's undefined to compare iterators into different strings
        bool operator==(token_iter const& other) const
        {
            return current_token.empty() ? other.current_token.empty()
                :  current_token.begin() == other.current_token.begin();
        }

    private:
        value_type get_next()
        {
            auto start = find_start(input);
            if (start > input.size()) {
                // not found
                return {};
            }
            input = input.substr(start);
            auto end = find_end(input);
            if (end > input.size()) {
                return std::exchange(input, {});
            }

            auto token = input.substr(0, end);
            input = input.substr(end);
            return token;
        }
    };


    template<typename CharT, typename Traits>
    auto as_string_view(std::basic_string_view<CharT, Traits> s)
    {
        return s;
    }

    template<typename CharT, typename Traits>
    auto as_string_view(std::basic_string<CharT, Traits> const& s)
    {
        return std::basic_string_view<CharT, Traits>{s};
    }

    template<typename CharT, typename Traits = std::char_traits<CharT>>
    auto as_string_view(CharT const* s)
    {
        return std::basic_string_view<CharT, Traits>{s};
    }


    template<typename StringView>
    auto tokenize(search_func<StringView> find_start, search_func<StringView> find_end,
                  StringView input)
    {
        auto iter = token_iter{find_start, find_end, StringView(input)};
        decltype(iter) sentinel = {};
        return std::ranges::subrange{iter, sentinel};
    }

    auto tokenize(auto delim_chars, auto input)
    {
        auto delim_chars_view = as_string_view(delim_chars);
        auto input_view = as_string_view(input);
        using StringView = decltype(input_view);

        search_func<StringView> find_start =
            [delim_chars_view](auto in) {
                return in.find_first_not_of(delim_chars_view);
            };
        search_func<StringView> find_end =
            [delim_chars_view](auto in) {
                return in.find_first_of(delim_chars_view);
            };
        return tokenize(find_start, find_end, input_view);
    }
}

I wrote these unit tests (slightly cluttered by the demand of EXPECT_EQ to have arguments of the same type):

#include <gtest/gtest.h>

using parser::tokenize;

TEST(Tokenize, EmptyInput)
{
    EXPECT_TRUE(tokenize(" ", "").empty());
}

TEST(Tokenize, WhitespaceInput)
{
    EXPECT_TRUE(tokenize(" ", "    ").empty());
    EXPECT_TRUE(tokenize(" \n\t", "  \n  \t  ").empty());
}

TEST(Tokenize, OneWord)
{
    auto results = tokenize(" ", "  One  ");
    auto expected = std::vector<std::string_view>{"One"};
    EXPECT_EQ(std::vector(results.begin(), results.end()), expected);

    results = tokenize("-", "--One--");
    EXPECT_EQ(std::vector(results.begin(), results.end()), expected);

    results = tokenize(" ", "One");
    EXPECT_EQ(std::vector(results.begin(), results.end()), expected);
}

TEST(Tokenize, TwoWords)
{
    auto results = tokenize(" \n\t", "  One\nTwo  ");
    auto expected = std::vector<std::string_view>{"One", "Two"};
    EXPECT_EQ(std::vector(results.begin(), results.end()), expected);

    results = tokenize(" \n\t", "One\nTwo");
    EXPECT_EQ(std::vector(results.begin(), results.end()), expected);
}


static auto shell_token_start(std::string_view in)
{
    return in.find_first_not_of(" \t\n");
}
static auto shell_token_end(std::string_view in)
{
    bool in_single_quote = false;
    bool in_double_quote = false;
    std::size_t i;
    for (i = 0; i < in.size();  ++i) {
        auto const c = in[i];
        if (in_single_quote) {
            if (c == '\'') {
                in_single_quote = false;
            }
            continue;
        }
        // Backslash is escape in unquoted and double-quoted, but not
        // single-quoted
        if (c == '\\') {
            ++i; continue;      // skip next character
        }
        if (in_double_quote) {
            if (c == '"') {
                in_double_quote = false;
            }
            continue;
        }
        switch (c) {
        case '\'': in_single_quote = true; continue;
        case '"': in_double_quote = true; continue;
        case ' ':
        case '\n':
        case '\t': return i;
        default: continue;
        }
    }
    return in.npos;
}
static auto shell_tokenize(std::string_view input)
{
    return tokenize<std::string_view>(shell_token_start, shell_token_end, input);
}

TEST(TokenizeShell, TwoWords)
{
    auto results = shell_tokenize(R"('a b c'  \ "\"1 2\"")");
    auto expected = std::vector<std::string_view>{R"('a b c')", R"(\ "\"1 2\"")"};
    EXPECT_EQ(std::vector(results.begin(), results.end()), expected);
}

A practical use: find the most frequent words of a book, without creating thousands of std::string objects:

#include <boost/iostreams/device/mapped_file.hpp>
#include <iostream>
#include <map>
#include <ranges>
#include <vector>

int main()
{
    auto source = boost::iostreams::mapped_file_source{"moby-dick.txt"};
    std::clog << "Input contains " << source.size() << " bytes.\n";
    auto input = std::string_view{source.data(), source.size()};
    std::unordered_map<std::string_view,std::size_t> histogram;
    for (auto word: parser::tokenize(" \n.,\";:-[]#?!", input)) {
        ++histogram[word];
    }
    std::clog << "Input contains " << histogram.size() << " distinct words.\n";
    std::vector<std::pair<std::string_view, std::size_t>> ranked(histogram.begin(), histogram.end());
    std::ranges::sort(ranked, std::greater{}, &decltype(ranked)::value_type::second);
    for (auto [val, count]: ranked | std::views::take(50)) {
        std::cout << count << ' ' << val << '\n';
    }
}

Answer 1

tokenize() makes copies unnecessarily

Remember that auto on its own will never deduce a reference. That means tokenize() takes its parameters by value, and that can cause undesired copies to be made in some cases. Consider:

std::string delim_chars = …;
std::string input = …;
auto tokens = tokenize(delim_chars, input);

To avoid this, make it take parameters by const reference:

auto tokenize(const auto& delim_chars, const auto& input)
{
    …
}

That is maybe a bit silly if you want to pass in std::string_views which are better passed by value, but since it's a template anyway, the compiler will very likely be able to optimize out the reference.

Avoid unnecessary default constructors and operators

There is no need to explicitly default the destructor and the copy and move constructors and assignment operators. Prefer not declaring them; the compiler will do the right thing based on the types of member variables, and this way there is less chance of making errors yourself.

Consider tokenizing streams

The reason for the suggestion of making a tokenizer that returns a range is so you don't need to tokenize all of the input up front into a container. This saves memory, and possibly CPU time if you didn't need to tokenize everything. However, your tokenizer still assumes that all of the input is available in memory. What if you want to tokenize say, lines in a file? Instead of requiring the whole file to be loaded into memory first, it would be nice if you could stream the file into the tokenizer.

There are several approaches to this. You could make tokenizer() take a std::istream as a parameter, or you could somehow add a way (perhaps via a callback function) to either push new data into the tokenizer, or have the tokenizer pull more data when necessary.