How to check if string contains substring that matches given predicate?

Question

I'm trying to achieve the behavior similar to std::basic_string<CharT>::find(), except it has to accept a predicate that has to match the searched string.

The signature will look like this:

template <class StringType, class Predicate
size_t search(const StringType& where, Predicate pred, size_t pos, size_t n) {/*...*/}

template <class StringType, class Predicate
size_t search(const StringType& where, Predicate pred, size_t pos = 0) {/*...*/}

Note I'm using size_t instead of typename StringType::size_type to save space on screen.

e.g. calling the function will look something like this:

search("Hello world"s, [](auto&& str) { 
                          return str[0] == 'l' 
                             and str[1] == 'l' 
                             and str.size() > 3; 
                        });

and will return the value 2.

In this particular example, I can use a regex to find the substring, but I want to be able to write a general predicate.

Answer 1

Try something like this:

template <class StringType, class Predicate, class SizeType = typename StringType::size_type>
SizeType search(const StringType& where, Predicate pred, SizeType pos, SizeType n)
{
    if (n > 0 && pos < where.size())
    {
        auto start = where.c_str(),
             ptr = start + pos,
             stop = ptr + std::min(where.size() - pos, n);
        do
        {
            if (pred(ptr, stop - ptr))
                return ptr - start;
        }
        while (++ptr < stop);
    }
    return StringType::npos;
}

template <class StringType, class Predicate, class SizeType = typename StringType::size_type>
SizeType search(const StringType& where, Predicate pred, SizeType pos = 0)
{
    return search(where, pred, pos, where.size()-pos);
}

search("Hello world"s,
    [](auto&& str, auto n) { 
        return n > 3 &&
            str[0] == 'l' &&
            str[1] == 'l'; 
    }
);

Online Demo

Alternatively, using std::string_view for the predicate argument:

template <class StringType, class Predicate, class SizeType = typename StringType::size_type>
SizeType search(const StringType& where, Predicate pred, SizeType pos, SizeType n)
{
    if (n > 0 && pos < where.size())
    {
        std::basic_string_view<typename StringType::value_type> sv(where.c_str()+pos, std::min(where.size() - pos, n));
        do
        {
            if (pred(sv))
                return pos;
            ++pos;
            sv = sv.substr(1);
        }
        while (!sv.empty());
    }
    return StringType::npos;
}

template <class StringType, class Predicate, class SizeType = typename StringType::size_type>
SizeType search(const StringType& where, Predicate pred, SizeType pos = 0)
{
    return search(where, pred, pos, where.size()-pos);
}

search("Hello world"s,
    [](auto&& str) { 
        return str.size() > 3 &&
            str[0] == 'l' &&
            str[1] == 'l'; 
    }
);

Online Demo