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

我已经看过使用字符串的示例，但是不确定如何使用KMP算法传递对象。我有一个定义为circle_buffer >的循环缓冲区，其中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);

任何帮助，不胜感激。

最佳答案

假设针是ident中出现的模式，这是一个草图:

用于生成随机二进制数据的硬编码随机种子

硬编码的“针”模式:0x1e 0x9a

在最近2秒内查看(假设时钟值增加)

可以用KMP调用

轻松替换std::search调用

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出现。

关于c++ - 如何使对象的范围迭代器与boost KMP一起使用？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32749749/