如何利用C++标准库实现单遍迭代器下的std::istream序列匹配读取？

Great question! Let’s unpack this scenario step by step.

First, the hard truth: the C++ standard library doesn’t provide a ready-to-use Boyer-Moore style searcher that works with input iterators like std::istreambuf_iterator. Both std::boyer_moore_searcher and std::boyer_moore_horspool_searcher explicitly require random-access iterators, which rules them out for single-pass input streams.

But that doesn’t mean you have to write a full search algorithm from scratch. You can leverage standard library components with minimal custom code, while keeping memory usage proportional to your pattern’s length (exactly what you asked for). Here’s how:

The Sliding Window Buffer Approach #

Since we can’t rewind the input stream, we need to maintain a fixed-size buffer that holds the most recent N characters (where N is the length of your target pattern). This lets us check for matches against the pattern using standard algorithms, without needing to re-read the stream.

Example Implementation #

This code uses a std::deque to keep the sliding window, and std::equal to check for matches. Memory usage is O(N), where N is the pattern’s length:

#include <iostream>
#include <sstream>
#include <iterator>
#include <deque>
#include <string_view>
#include <algorithm>

// Returns true if the pattern is found in the input stream
bool find_pattern(std::istream& is, std::string_view pattern) {
    if (pattern.empty()) return true;

    const std::size_t pattern_len = pattern.size();
    std::deque<char> buffer;
    buffer.reserve(pattern_len); // Preallocate to avoid reallocations

    std::istreambuf_iterator<char> stream_it(is), stream_end;

    for (; stream_it != stream_end; ++stream_it) {
        buffer.push_back(*stream_it);
        
        // Trim the buffer to match the pattern's length (sliding window)
        if (buffer.size() > pattern_len) {
            buffer.pop_front();
        }

        // Only check for matches once the buffer is full
        if (buffer.size() == pattern_len) {
            if (std::equal(buffer.begin(), buffer.end(), pattern.begin())) {
                // Pattern found! You can extend this to return the position or remaining stream
                return true;
            }
        }
    }

    // Handle edge case: input is shorter than the pattern
    return std::equal(buffer.begin(), buffer.end(), pattern.begin(), pattern.end());
}

// Test usage
int main() {
    std::istringstream test_stream("The quick brown fox jumps over the lazy dog");
    if (find_pattern(test_stream, "lazy dog")) {
        std::cout << "Pattern found!\n";
    } else {
        std::cout << "Pattern not found.\n";
    }
    return 0;
}

Tradeoffs #

• Memory: Perfectly fits your requirement—only O(N) memory, where N is the pattern length.
• Speed: Uses a naive comparison (std::equal) which runs in O(N) time per check, leading to an overall O(M*N) time complexity (M = input length). If you need faster performance (like Boyer-Moore’s O(M + N)), you’ll need to implement a custom search algorithm that works with the sliding buffer, since the standard library doesn’t offer this.

What if You Need Boyer-Moore Speed? #

If naive comparison isn’t fast enough for your use case, you’ll have to roll your own adaptation of Boyer-Moore for single-pass input. The core idea is to use the sliding buffer to simulate random access to the last N characters, then apply Boyer-Moore’s bad-character and good-suffix rules to skip unnecessary checks. This still keeps memory usage at O(N), but requires writing more custom code (though you can reuse standard library utilities for things like precomputing the bad-character table).

Final Verdict #

• For most cases: You don’t need to write a full search algorithm. Use the sliding window + standard library comparison approach—it’s simple, efficient enough for many scenarios, and stays within your memory constraints.
• For high-performance needs: You’ll need to implement a custom Boyer-Moore variant adapted for single-pass input, since the standard library doesn’t provide this out of the box.

内容的提问来源于stack exchange，提问作者levzettelin