c++ - 如何制作对象的范围迭代器以与 boost KMP 一起使用？

Question

我看过使用字符串的示例，但不确定如何使用 KMP 算法传入对象。我有一个定义为 circular_buffer< pair< time_t, MyObj>> 的循环缓冲区，其中 MyObj 是:

typedef struct MyObj 
{
    MyData data;
}

typedef struct MyData
{
    uint8_t ident[BYTE_COUNT];
}

我正在寻找一种使用 KMP 算法在 MyObj 的 circulur_buffer 中查找 MyObj.data.ident 的方法。 time_t 值是一个时间戳，我只希望从 CB 的后面搜索到缓冲区中向后的给定秒数(而不是整个缓冲区)。

boost::algorithm::knuth_morris_pratt_search ( cb.rbegin (), 
    cb.rend (), unknown, unknown);

非常感谢任何帮助。

Answer 1

假设针是出现在 ident 中的图案，下面是草图:

• 用于生成随机二进制数据的硬编码随机种子
• 硬编码“针”模式:0x1e 0x9a
• 在最后 2 秒内查看(假设增加时钟值)
• std::search 调用可以很容易地替换为 KMP 调用

Live On Coliru

#include <boost/circular_buffer.hpp>
#include <ctime>
#include <iomanip>
#include <iostream>

std::mt19937 prng{ 0x4e9d45ad };

namespace {
    static constexpr auto BYTE_COUNT = 32;

    struct MyData { uint8_t ident[BYTE_COUNT]; };
    struct MyObj { MyData data; };
}

using Buf = boost::circular_buffer<std::pair<std::time_t, MyObj> >;

Buf generate();
time_t time_offset(int offset_seconds);

template <typename Needle> auto search_for(Buf const& haystack, Needle const& needle) {
    auto const threshold = time_offset(-2);

    auto ubound = std::upper_bound(haystack.begin(), haystack.end(), threshold, [] (auto& a, auto& b) { return a <= b.first; });

    auto match  = std::find_if(ubound, haystack.end(), [&needle](auto& entry) {
            auto& ident = entry.second.data.ident;
            return std::end(ident) != std::search(
                    std::begin(ident), std::end(ident),
                    std::begin(needle), std::end(needle)
                );
            });

    return match;
}

int main() {
    auto haystack = generate();

    uint8_t needle[2] = { 0x1e, 0x9a };
    auto match = search_for(haystack, needle);

    if (haystack.end() != match)
    {
        auto tp = match->first;
        std::cout << "Matching entry at " << ctime(&tp);

        for (int ch : match->second.data.ident)
            std::cout << std::hex << std::showbase << std::setw(2) << std::setfill('0') << ch << " ";

        std::cout << "\n";
    }
}

#include <thread>
#include <random>
#include <functional>

Buf generate() {
    Buf cb(512);
    auto randchar = std::bind(std::uniform_int_distribution<>(0, 255), prng);

    for (auto i = 0u; i < 32; i++) {
        std::this_thread::sleep_for(std::chrono::milliseconds(prng() % 500));

        cb.push_back({ time(NULL), {} });

        auto &ident = cb.back().second.data.ident;
        std::generate(std::begin(ident), std::end(ident), randchar);
    }

    return cb;
}

time_t time_offset(int offset_seconds) {
    time_t now = time(NULL);
    struct tm now_tm = *localtime(&now);
    struct tm then_tm = now_tm;
    then_tm.tm_sec += offset_seconds;

    return mktime(&then_tm); // normalize it
}

打印:

Matching entry at Thu Sep 24 00:03:56 2015
0xb 0x5e 0xa3 0x5d 0x28 0x27 0xa5 0x34 0xa9 0x90 0x97 0x91 0xb2 0x8f 0x74 0xda 0x18 0xc 0x81 0x78 0xe 0x22 0x1e 0x9a 0xcf 0xa3 0x21 0x10 0xa9 0xfa 0xd1 0xe5 

注意匹配的子序列 0x1e 0x9a 出现了。