std::vector的区别

Question

如何确定两个向量的区别？

我有vector<int> v1和vector<int> v2；

我想要得到一个vector<int> vDifferences，其中只包含v1或v2中独有的元素。

是否有标准的方法来实现这一点？

- reza

---

std::set_difference函数原型：template <class InputIt1, class InputIt2, class OutputIt> OutputIt set_difference(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first);该函数计算两个已排序范围的元素差集，将结果存储在输出迭代器所指向的范围中。参数：

• first1, last1：表示第一个已排序范围的起始和结束位置。
• first2, last2：表示第二个已排序范围的起始和结束位置。
• d_first：输出迭代器，指向目标范围的起始位置。

返回值：输出迭代器，指向输出范围的尾部。注意事项：

• 该函数假定输入范围已排序。
• 输出范围必须足够大以容纳差异元素。

- Praetorian

我认为你正在寻找std::set_symmetric_difference函数。 - Blastfurnace

如果更改v1和v2的类型是一种选择，并且您只关心每个元素是否存在，请考虑在第一次使用std::vector之前使用std::unordered_set或std::set。 - aschepler

Answer 1

这里是完整且正确的答案。在使用set_symmetric_difference算法之前，源范围必须被排序：

  using namespace std; // For brevity, don't do this in your own code...

  vector<int> v1;
  vector<int> v2;

  // ... Populate v1 and v2

  // For the set_symmetric_difference algorithm to work, 
  // the source ranges must be ordered!    
  vector<int> sortedV1(v1);
  vector<int> sortedV2(v2);

  sort(sortedV1.begin(),sortedV1.end());
  sort(sortedV2.begin(),sortedV2.end());

  // Now that we have sorted ranges (i.e., containers), find the differences    
  vector<int> vDifferences;

  set_symmetric_difference(
    sortedV1.begin(),
    sortedV1.end(),
    sortedV2.begin(),
    sortedV2.end(),
    back_inserter(vDifferences));

  // ... do something with the differences

需要注意的是，排序是一项昂贵的操作（即对于常见STL实现，时间复杂度为O(n log n)）。特别是当一个或两个容器非常大（即数百万个整数或更多）时，基于算法复杂度的哈希表算法可能更可取。以下是此算法的高级描述：

1. 将每个容器加载到哈希表中。
2. 如果两个容器的大小不同，则较小的那个哈希表将用于步骤3中的遍历。否则，将使用两个哈希表中的第一个。
3. 遍历第2步中选择的哈希表，检查每个项目是否存在于两个哈希表中。如果是，则从两个哈希表中删除它。之所以优先选择较小的哈希表进行遍历，是因为无论容器大小如何，哈希表查找的平均时间复杂度都是O(1)。因此，遍历的时间是n的线性函数（即O(n)），其中n是正在遍历的哈希表的大小。
4. 对哈希表中剩余的项目进行并集，并将结果存储在差异容器中。

C++11为我们提供了一些能力，通过标准化unordered_multiset容器来实现此类解决方案。我还使用了auto关键字的新用法，以使以下基于哈希表的解决方案更加简洁：

using namespace std; // For brevity, don't do this in your own code...

// The remove_common_items function template removes some and / or all of the
// items that appear in both of the multisets that are passed to it. It uses the
// items in the first multiset as the criteria for the multi-presence test.
template <typename tVal>
void remove_common_items(unordered_multiset<tVal> &ms1, 
                         unordered_multiset<tVal> &ms2)
{
  // Go through the first hash table
  for (auto cims1=ms1.cbegin();cims1!=ms1.cend();)
  {
    // Find the current item in the second hash table
    auto cims2=ms2.find(*cims1);

    // Is it present?
    if (cims2!=ms2.end())
    {
      // If so, remove it from both hash tables
      cims1=ms1.erase(cims1);
      ms2.erase(cims2);
    }
    else // If not
      ++cims1; // Move on to the next item
  }
}

int main()
{
  vector<int> v1;
  vector<int> v2;

  // ... Populate v1 and v2

  // Create two hash tables that contain the values
  // from their respective initial containers    
  unordered_multiset<int> ms1(v1.begin(),v1.end());
  unordered_multiset<int> ms2(v2.begin(),v2.end());

  // Remove common items from both containers based on the smallest
  if (v1.size()<=v2.size)
    remove_common_items(ms1,ms2);
  else
    remove_common_items(ms2,ms1);

  // Create a vector of the union of the remaining items
  vector<int> vDifferences(ms1.begin(),ms1.end());

  vDifferences.insert(vDifferences.end(),ms2.begin(),ms2.end());

  // ... do something with the differences
}

为了确定哪种解决方案更适合特定情况，对两种算法进行分析是明智的做法。虽然基于哈希表的解决方案是O(n)，但它需要更多的代码并且在找到每个重复项时执行更多的操作（即哈希表删除）。不幸的是，它使用自定义差异函数而不是标准STL算法。

应该注意的是，两种解决方案都以最可能与元素在原始容器中出现顺序非常不同的顺序呈现差异。通过使用哈希表解决方案的变体可以解决这个问题。以下是高级描述（仅在第4步与前面的解决方案有所不同）：

1. 将每个容器加载到哈希表中。
2. 如果两个容器大小不同，则较小的哈希表将用于第3步的遍历。否则，将使用两者中的第一个。
3. 遍历在第2步中选择的哈希表，检查每个项目是否存在于两个哈希表中。如果存在，则从两个哈希表中删除它。
4. 为了形成差异容器，按顺序遍历原始容器（即先遍历第一个容器再遍历第二个容器）。在其各自的哈希表中查找每个容器中的项目。如果找到，则将该项添加到差异容器中并从其哈希表中删除。不在各自哈希表中的项目将被跳过。因此，只有出现在哈希表中的项目才会出现在差异容器中，并且它们的出现顺序与它们在原始容器中的顺序相同，因为这些容器规定了最终遍历的顺序。

为了保持原有的顺序，步骤4比之前的解决方案更加昂贵，特别是如果要移除的物品数量很大。这是因为：

1. 所有物品都将第二次进行测试，以确定它们是否应该出现在差异容器中，测试方式为对它们各自的哈希表进行存在性测试。
2. 当形成差异容器时，哈希表将逐个删除其余的物品，作为检查物品1是否“存在于差异中”的一部分。

- Michael Goldshteyn

Answer 2

您是否需要从v1和v2中获取唯一且不在另一个序列中的元素？这听起来像是std::set_symmetric_difference。

将不在范围[first2，last2)中的范围[first1，last1)的元素以及不在范围[first1，last1)中的范围[first2，last2)的元素复制到以result开头的范围中。所构建的范围内的元素已排序。

- Blastfurnace