Variadic function to find the first matching (string) argument in a larger array

Question

Playing around with parsing a data buffer I wrote a small search function to find the first complete match out of a set of (string) arguments.

The (simplified) buffer class with the find function:

// buffer_simple.hpp
#pragma once

#include <cstddef>
#include <utility>

template <typename T, size_t S>
class buffer {
public:
    constexpr buffer() {}
    template <size_t Si>
    constexpr buffer(const T (&arr)[Si]) {
        for (size_t i = 0, l = (S < Si ? S : Si); i < l; ++i) {
            values[i] = arr[i];
        }
    }

    /**
     * Find the first matching array in a larger array and return the argument index and buffer end index of the match.
     * @param   str One or many strings to search for
     * @returns std::pair<argument index, end of match index in buffer>
     */
    template <size_t... SS>
    constexpr std::pair<int, size_t> find_first(const T (&...str)[SS]) const {
        size_t matching[] { (SS - 1)... }; // Amount of remaining 'characters to match'
        for (size_t i = 0; i < S; ++i) { // Loop over the dataset
            int mi = 0;
            ((matching[mi++] = (str[(SS - 1) - matching[mi]] == values[i]) ? (matching[mi] - 1) : ((str[0] == values[i]) ? (SS - 2) : (SS - 1) )), ...); // Nasty pseudo loop for width first search
            for (mi = 0; mi < sizeof...(SS); ++mi) { // See if we have any full matches
                if (matching[mi] == 0) return { mi, i };
            }
        }
        return { -1, 0 };
    }

    constexpr T& operator[](const size_t i) { return values[i]; }
    constexpr const T& operator[](const size_t i) const { return values[i]; }
private:
    T values[S] {0};
};

An example use case:

#include <iostream>
#include "buffer_simple.hpp"

buffer<char, 256> b { "find mefind me:gehoehgioewghowieanother string:" };

int main () {
    const auto result = b.find_first("find me:", "bla", "another string:");
    // switch (result.first) {
    // case 0:
    //     break;
    // case 1:
    //     break;
    // case 2:
    //     break;
    // }
    std::cout << "Result index: " << result.first << ", offset: " << result.second << std::endl;
}

This will return:

Result index: 0, offset: 14

Despite the extremely nasty fold expression this actually works. During runtime that is. As a test I tried declaring the buffer and search result constexpr and things blew up with GCC reporting an Array out of bounds error. I'm curious to see which other pitfalls might be lurking.

Answer 1

Good stuff!

I only see one big issue (which is actually what's preventing you from using this as a constexpr).

Errors:

UB: Unsequenced modification

matching[mi++] = (str[(SS - 1) - matching[mi]]
         ^^                               ^^

Which value does mi take for that second indexing? The C++ standard says: either the pre or post increment value is legal. You have undefined behavior here.

You can solve this by separating out the mi incrementation as a separate statement. Using the evil comma operator would allow you to do it as a fairly small modification of your existing code:

(
  ((matching[mi] = (str[(SS - 1) - matching[mi]] == values[i])
     ? (matching[mi] - 1) 
     : ((str[0] == values[i]) ? (SS - 2) : (SS - 1))
  ), ++mi), 
...);

This actually makes the constexpr version work!

Style

1. I think find_first should be a free-floating function, since you already have the [] accessors.

2. I would definitely try to format that fold expression in a more readable manner. See my version of it above for an example.

Improvements

3. Add a template deduction guide:

Something like this:

template<typename T, size_t LEN>
buffer(const T(&)[LEN]) -> buffer<T, LEN>;

So then your declare buffers in a cleaner manner, and have the buffer be perfectly sized:

buffer<char, 256> b { "find mefind me:gehoehgioewghowieanother string:" };
//becomes
buffer b { "find mefind me:gehoehgioewghowieanother string:" };

Answer 2

To build on Frank's answer...

---

#pragma once

Be aware of the pitfalls of #pragma once. Despite the widespread support of #pragma once, the compiler extension is non-standard (rejected by committee) and not guaranteed to have the same behavior across all supported compilers. The #pragma once extension allows the compiler to figure out which files should and should not be read for compilation. This is a difficult task and can easily be defeated by symlinks/build systems. The #include guard idiom forces you to decide on an identifier that defines your intent the file you are working with. It does require a unique name and you do have to type it out twice across three lines, but you control what is included and not included. Until the Modules TS is standardized (soon^tm) or another approach becomes standardized, prefer the #include guard idiom.

---

template <typename T, size_t S>

size_t is not guaranteed to be defined. Prefer the qualified std::size_t which is guaranteed to be defined by the C++ standard.

---

    constexpr buffer() {}

Use = default; to be explicit to readers that your intent is to use the default semantics. By defining a user-written default constructor ({}), buffer becomes a non-aggregate and is therefore non-trivial. The user-written default constructor also has an empty exception specification, whereas the compiler-generated default constructor would have an implicitly generated exception specification.

---

    constexpr buffer(const T (&arr)[Si]) {

When reading from non-owning references to character sequences, prefer std::basic_string_view and friends. They provide simple and safe access to character sequences independently from how the sequence is allocated/stored.

---

    constexpr std::pair<int, size_t> find_first(const T (&...str)[SS]) const {

You should also prefer to return a std::basic_string_view to the found buffered substring.

---

        for (size_t i = 0, l = (S < Si ? S : Si); i < l; ++i) {
            values[i] = arr[i];
        }

Prefer std::copy as it's self-documenting and will appropriately use bulk copy instructions like memcopy/memmove instead of multiple individual assignments.

---

    T values[S] {0};

Prefer std::array as they are pretty much zero-cost safety wrappers around fixed-sized C arrays with additional functionality.

---

Instead of implementing a naive search, have you considered using a constexpr boyer moore search?