将向量中的元素与数组中的元素进行比较。

Question

我有两个包含数据的数据结构。

• 一个是向量std::vector<int> presentStudents，另一个是
• char数组char cAllowedStudents[256];

现在我必须比较这两个数据结构，以便检查每个元素在vector中是否与array中的所有元素都存在，否则如果vector中有一个元素不是数组的一部分，则返回false。

我想知道最有效且简单的解决方案。我可以将我的int vector转换为char array，然后逐个比较，但这将是冗长的操作。有没有更好的方法来实现这一点？

- user971741

---

这些集合是否已排序？char数组的长度是多少，我们知道大小为256。 - legends2k

虽然我提供了我个人认为在您的情况下最有效的答案，但有一件事我想提一下：尽管效率总是很好，但如果只涉及256名学生，则它应该是您优先考虑的最后一项。 只要这个函数不在一个巨大的循环中被调用，我相信在这种情况下代码清晰度和可维护性应该更重要。 - MikeMB

Answer 1

我建议您使用哈希映射（std :: unordered_map）。将字符数组的所有元素存储在哈希映射中。

然后，仅顺序检查向量中的每个元素是否存在于映射中，时间复杂度为O(1)。

Total time complexity O(N), extra space complexity O(N).

请注意，您需要在编译器中启用C++11。

- Abhishek Bansal

Answer 2

请参考C++ algorithm头文件中的set_difference()函数。您可以直接使用此函数，并检查结果diff集是否为空。如果不为空，则返回false。

更好的解决方案是调整set_difference()的实现，例如在这里：http://en.cppreference.com/w/cpp/algorithm/set_difference，在获取第一个不同元素后立即返回false。

示例调整如下：

while (first1 != last1)
{
    if (first2 == last2) 
        return false;

    if (*first1 < *first2)
    {
        return false;
    }
    else
    {
        if (*first2 == *first1)
        {
            ++first1;
        }
        ++first2;
    }
}
return true;

- Sheen

Answer 3

使用std::sort对两个列表进行排序，并在数组上迭代使用std::find。编辑：诀窍是将先前找到的位置用作下一次搜索的起点。

std::sort(begin(pS),end(pS))
std::sort(begin(aS),end(aS))

auto its=begin(aS);
auto ite=end(aS);

for (auto s:pS) {
    its=std::find(its,ite,s);
    if (its == ite) {
        std::cout << "Student not allowed" << std::cout;
        break;
    }
}

编辑：正如传说中所提到的那样，通常使用二分查找可能更有效（就像R Sahu的答案一样）。然而，对于小数组和如果向量包含阵列中相当比例的学生（我会说至少十分之一），二进制搜索的额外开销可能（或可能不）超过其渐近复杂度的好处。

- MikeMB

---

这样做效率会很低，不是吗？当它们被排序时为什么要使用std::find呢？ - legends2k

数组可能是向量中数字的超集。此外，您可以从上次找到元素的位置开始搜索。这样，在列表排序后，您就可以实现线性复杂度。 - MikeMB

@legends2k 但我承认，对于这样一个短列表来说，简单的暴力搜索所有元素可能会更有效。 - MikeMB

Answer 4

1. 使用 std::sort 对 cAllowedstudents 进行排序。
2. 使用 std::binary_search 遍历 presentStudents ，并在已排序的 cAllowedStudents 中查找每个学生。
3. 如果找不到向量中的任何项，则返回false。
4. 如果所有向量元素都被找到，则返回true。

这是一个函数：

bool check()
{
   // Assuming hou have access to cAllowedStudents
   // and presentStudents from the function.

   char* cend = cAllowedStudents+256;
   std::sort(cAllowedStudents, cend);

   std::vector<int>::iterator iter = presentStudents.begin();
   std::vector<int>::iterator end = presentStudents.end();
   for ( ; iter != end; ++iter )
   {
      if ( !(std::binary_search(cAllowedStudents, cend, *iter)) )
      {
         return false;
      }
   }
   return true;
}

另一种方法是使用 std::difference。

bool check()
{
   // Assuming hou have access to cAllowedStudents
   // and presentStudents from the function.

   char* cend = cAllowedStudents+256;
   std::sort(cAllowedStudents, cend);

   std::vector<int> diff;
   std::set_difference(presentStudents.begin(), presentStudents.end(),
                       cAllowedStudents, cend,
                       std::back_inserter(diff));
   return (diff.size() == 0);
}

- R Sahu

---

@billz std::set_difference 也可以使用。它将执行相同的计算，但还会创建另一个容器。 - R Sahu

@MikeMB，你对于binary_search的返回值是正确的。我已经更新了答案。 - R Sahu

我认为也会有比较..因为我的数组是char类型的，而向量包含int类型的数据？ - user971741

是的，我的错误，我想说的是“转换”，我正在使用x64 PC，并且编译器给出了这个错误：“error C2446：'=='：从'char *'到'int'没有转换”和“error C2040：'=='：'int'与'char *'的间接级别不同”。 - user971741

@maven 我的意思是，如果你复制了解决方案，那么你必须使数组在函数 check() 内可用。你是通过将数组作为全局变量还是通过将其作为参数传递给 check 来实现的？ - MikeMB

Answer 5

使用C++11。在您的情况下，size为256。请注意，我个人尚未测试过这个，甚至没有将其放入编译器中。但是，它应该能够给您一个很好的自我操作的想法。我强烈建议使用此测试边缘情况！

#include <algorithm>

bool check(const std::vector<int>& studs, 
char* allowed, 
unsigned int size){

    for(auto x : studs){
        if(std::find(allowed, allowed+size-1, x) == allowed+size-1 && x!= *(allowed+size))
            return false;
    }
    return true;
}

- druckermanly