有效 std::search 用于查找子序列的所有出现（避免无限循环）

Question

我正在尝试查找序列中子序列的所有次出现。我的想法是使用 std::search 然后推进生成的迭代器，直到我到达集合的末尾。

这是有效的代码：

#include <algorithm>
#include <vector>

using namespace std;

int main ()
{
    vector<int> MainSequence {2,3,1,2,3,4,-5,8,2,4,3,2,3,6,2,3,2,3};
    //for the sake of simplicity assume MainSequence is always non-empty

    vector<int> SubSequence {2,3}; // this will always be of length 2
    auto it = MainSequence.begin();
    int Count = 0;
  
    while (it < MainSequence.end() - 1)
    {
        it = search(it, MainSequence.end(), SubSequence.begin(),SubSequence.end()) + 2;
        Count++;
    }
    
    // Count = 5   

    return 0;

}

我已经测试了各种组合并且它似乎有效，但我感觉我已经做了很多调整才能使这样的东西起作用。

你能帮我理解为什么这个 while 循环会变成无限循环吗：

条件改为it < MainSequence.end()或it != MainSequence.end()?

and/or

在循环体中，如果 it 递增 1 而不是 2?

非常感谢！

Answer 1

the condition is changed to it < MainSequence.end() or it != MainSequence.end()

都对，个人更喜欢第二种

但可以肯定的是 (it < MainSequence.end() - 1) 永远不会成立，您必须使用上述两个建议之一

in the loop body, if it is incremented by 1 instead by 2?

要决定需要知道在{1,1,1,1}中搜索{1, 1}的预期结果是什么，如果你想要2就加2，如果你想要3就加1

警告无条件地执行 Count++; 结果将为 1 即使 SubSequence 不在 MainSequence

比如做

#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

int main ()
{
    vector<int> MainSequence {2,3,1,2,3,4,-5,8,2,4,3,2,3,6,2,3,2,3};
    //for the sake of simplicity assume MainSequence is always non-empty

    vector<int> SubSequence {2,3}; // this will always be of length 2
    auto it = MainSequence.begin();
    int Count = 0;
  
    while ((it = search(it, MainSequence.end(), SubSequence.begin(),SubSequence.end()))
           != MainSequence.end())
    {
      it += SubSequence.size(); // or += 1 depending on what you expect searching  {1, 1} in {1,1,1,1}
      Count++;
    }
    
    cout << Count << endl;

    return 0;
}

编译与执行：

pi@raspberrypi:/tmp $ g++ -Wall s.cc
pi@raspberrypi:/tmp $ ./a.out
5
pi@raspberrypi:/tmp $

Answer 2

更通用的方法是：

std::size_t count_subsequence(const std::vector<T>& mainSequence, const std::vector<T>& subSequence)
{
    assert(!subSequence.empty());
    std::size_t count = 0;
    auto it = mainSequence.begin();
    while (it != mainSequence.end())
    {
        it = search(it, mainSequence.end(), subSequence.begin(), subSequence.end());
        if (it != mainSequence.end()) {
             count++;
             std::advance(it, subSequence.size()); // or 1 depending how you want to count {1, 1} in {1, 1, 1, 1}
        } 
    }
    return count;
}

std::search(..) + 2 未找到时调用未定义的行为 (end() + 2)

Can you help me understand why will this while loop become infinite if:

the condition is changed to it < MainSequence.end() or it != MainSequence.end()?

因为你增加了不止一个你必须确保你有一个有效的迭代器而不是像 MainSequence.end() + 1 这样的迭代器在循环体中，如果它增加 1 而不是增加 2?

有效 std::search 用于查找子序列的所有出现（避免无限循环）

Valid std::search use to find all occurences of a subsequence (avoid infinite loop)

c++

std