在C++中查找向量是否为子向量

Question

假设我有以下内容：

假设我有：

std::vector<string> group;
std::vector<string> subGroup;

关于这两个向量的一些属性：

1）所有元素都是唯一的。

2）它们没有排序，也不能排序。

我需要检查组是否包含子组。如果包含，则返回true，否则返回false。

举例：

group = {"A","B","C","D"}，subGroup = {"A","D","E"} -> 答案为false

group = {"A","E","C","D"}，subGroup = {"A","D","E"} -> 答案为true

我的当前实现方式是：

int cont=0;
if(subGroup.size() > group.size())
    return false;
else{
    for(int i=0; i<subGroup.size(); i++){
        for(int j=0; j<group.size(); j++){
            if(subGroup[i] == group[j]{
                cont++;
            }
        }
    }
    if (cont == subGroup.size())
            return true;
    return false;
}

我在这里查看了这篇文章locate sub-vector<string> in another vector<string>，但我不能使用C++11功能，而且这个答案也没有解决我的问题（例如，对于我的示例2，它会返回false）。

两件事：我的实现是否正确？是否有更简单的方法使用STL功能或类似的东西来实现它？

- woz

---

为什么排序不是一个选项？ - user1084944

如果顺序很重要，那么如果子组是A、E、D，它们全部都返回false吗？ - UpAndAdam

woz，请在您的问题中明确指出。函数不关心其他部分。重要的是如何将它们传递给函数。如果您需要在函数外部保持它们不变，请按值传递并让它们被复制。 （不要告诉我们我们不能对它们进行排序）。如果它们不能被排序，因为说顺序对于这个函数很重要，请说明。 :-) - UpAndAdam

性能是一个复杂的话题。一般来说，试图推理出一件事情是否比另一件更有效率会得到很差的结果，特别是如果你没有对你正在实现的东西以及你正在实现它的机器进行优化的广泛经验。最好的结果来自于实际实现替代方案并在各种使用情况下进行测试。 - user1084944

@woz，如果他/她不允许你使用C++11/14，那对我来说他/她似乎不是一个非常实用的老师。 - Alejandro

Answer 1

最直观的两种解决方案是：

• 复制向量，对它们进行排序，然后使用includes
• 将一组元素复制到一个set或unordered_set中，然后检查subgroup的每个元素，看它是否在集合中（如果C++11是一个选项，你可以使用all_of和lambda来实现循环）
  • 同样想法的一个变体：从subgroup的元素中创建一个set或unordered_set，然后循环遍历group的元素，如果存在则从集合中删除。当集合为空时返回true。

无论哪种情况，为了获得合理的最坏情况性能保证，如果subgroup的大小大于group，应立即返回false。

后者，使用unordered_set，具有可能期望的最佳渐近复杂度（即O(n)，其中n是group的大小），但我想第一种选项对于“典型”的示例来说更有效率。

- user1084944

---

可能将迭代顺序反转会有所帮助...紧密地迭代您的候选组，并通过较大的group向量/集合等进行单次遍历。 - UpAndAdam

@UpAndAdam：嗯。你的意思是将subgroup的元素制作成一个集合，然后创建一个循环，遍历group的元素并从集合中删除它们（如果存在），最后如果集合为空，则声明成功？是的，这样可能会更好。 - user1084944

是的。搜索较小的集合更有可能在缓存中保持热度，这很好，因为我们将重复访问相同的元素...即使这也取决于数据的维度/大小。 - UpAndAdam

Answer 2

这个问题有一个简单的解决方案，使用std:find函数即可：std:find。

bool            in(std::vector<std::string> const &group,
                   std::vector<std::string> const &subGroup) {
  std::size_t const     subSize = subGroup.size();
  int                   i = 0;

  while (i < subSize && std::find(group.begin(), group.end(), subGroup[i]) != group.end()) {
    i++;
  }
  return (i == subSize);
}

- Unda

Answer 3

可以使用 std::set。

std::set<std::string> group ; // Fill it first !

std::vector<std::string> subgroups  {"A","D","E"} ;
std::vector<std::string>::iterator i = subgroups.begin() ;

std::pair<std::set<std::string>::iterator,bool> p;

for( ; i != subgroups.end(); ++i )
{
    p = group.insert( *i );
    if( p.second ) // Present in group
    {
             break;
    }
}

if( i == subgroups.end() )
    std::cout << std::boolalpha << true ;
else
    std::cout << std::boolalpha << false ;

- P0W

---

尝试使用它，但在包括<set>后出现了错误：error: no matching member function for call to 'insert' p = group.insert( *i );。有什么建议吗？ - woz

@woz，你让我为你编码，所以在这里。 - P0W