c++ - 从结构 vector 中查找 vector 的子序列

Question

我试图从一个更大的 vector 中找到 vector 的子序列。

这是我的完整代码。

#include <iostream>
#include <vector>

using namespace std;

struct Elem {

    bool isString;
    float f;
    string s;
};

void getFounds(vector<Elem> &src, vector<Elem> &dst, vector<size_t> &founds)
{
    //what should be in here?
}

int main(int argc, const char * argv[]) {

    vector<Elem> elems1 = {{false, 1.f, ""}, {false, 2.f, ""}, {true, 0.f, "foo"},
                           {false, 1.f, ""}, {false, 2.f, ""}, {true, 0.f, "foo"}}; //the source vector
    vector<Elem> elems2 = {{false, 2.f, ""}, {true, 0.f, "foo"}}; //the subsequence to find
    vector<size_t> founds; //positions found

    getFounds(elems1, elems2, founds);

    for (size_t i=0; i<founds.size(); ++i)
        cout << founds[i] << endl; // should print 1, 4

    return 0;
}

如果我将它用于单一类型的 vector ，我可以使用 std::search 来做到这一点，但如果我将它用于结构的 vector ，它会显示错误信息

"invalid operands to binary expression ('const Elem' and 'const Elem')"

在这种情况下真的不可能使用std::search吗？在代码中实现 getFounds() 的好方法是什么？

编辑:我可以通过创建一个 operator 函数并使用 std::search

使其工作

bool operator==(Elem const& a, Elem const& b)
{
    return a.isString == b.isString && a.f == b.f && a.s == b.s;
}

void getFounds(vector<Elem> &src, vector<Elem> &dst, vector<size_t> &founds)
{
    for (size_t i=0; i<src.size(); ++i) {

        auto it = search(src.begin()+i, src.end(), dst.begin(), dst.end());

        if (it != src.end()) {

            size_t pos = distance(src.begin(), it);
            founds.push_back(pos);
            i += pos;
        }
    }
}

但是，如果有人能给我建议使代码更简单，我将不胜感激。

Answer 1

Is it really impossible to use std::search in this case?

不，您只需要在您的struct 中实现operator== 函数，就像您所做的那样。您也可以实现 operator!=，例如:

struct Elem
{
    bool isString;
    float f;
    std::string s;

    bool operator==(const Elem& other) const {
        return (this->isString == other.isString &&
                this->f == other.f &&
                this->s == other.s);
    }

    bool operator!=(const Elem& other) const {
        return !(*this == other);
    }
};

What would be the good way to implement getFounds() in the code? ... advice to make it simpler.

简单是相对的，特别是因为您已经在使用标准库来实现您想要的；但是，您也可以像这样实现 getFounds 函数:

void getFounds(const std::vector<Elem>& src, const std::vector<Elem>& sub, std::vector<size_t>& founds)
{
    size_t count = 0, tot = 0;
    auto beg = sub.begin();
    for (auto look = src.begin(); look != src.end();) {
        if (*look != *beg) { ++look; ++count; continue; }
        for (tot = 0; beg != sub.end(); ++beg, ++look, ++tot) {
            if (look == src.end()) { break; }
            if (*look != *beg) { break; }
        }
        if (tot == sub.size()) { founds.push_back(count); }
        count += tot;
        beg = sub.begin();
    }
}

我不知道这对您的需求是否“更简单”，因为它本质上做了 std::search 的工作算法会做(如果元素不匹配则循环并检查和中断等)，这只是“另一种”方式来做到这一点。

希望对您有所帮助。