std :: vector差异

Question

如何确定2个向量的差异是什么？

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

我正在寻找的是vector<int> vDifferences仅包含仅在v1或中的元素v2.

有没有标准的方法来做到这一点？

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 的差异测试中的当前部分.