c++ - 找出指向同一对象的两组指针之间的差异

Question

如何找到指向同一对象的两组指针之间的差异？

有没有一种有效的方法而不遍历两组的所有对象。

我有两套这样的：

std::set<Object*>

如果对象私有成员（名称）与其他对象名称相同，则表示该对象相同。

Answer 1

STL 的算法库非常棒、可扩展且未被充分利用。

这将为您提供作为向量的集合差异（我想您可以将其转换为集合，但没有必要，至少对于您所要求的而言，并且向量更快，因为集合已经排序）。

template<typename T>
std::vector<T> set_diff(std::set<T> const &a, std::set<T> const &b) {
    std::vector v<T>;
    std::set_difference(a.begin(), a.end(), b.begin(), b.end(), v.begin());
    return v;
}

可选地，放在构造函数之后

    v.reserve(a.size() + b.size());

和返回之前 (C++11)

    v.shrink_to_fit();

注意：这会产生 ina中没有的项目b。要查找两者之一而不是另一个中的所有项目，请std::set_symmetric_difference改用。

Answer 2

我认为你的意思不同的是找到只出现在一组中的指针元素。最有效的方法是同步迭代这两个集合，这将仅花费 O(n+m) 时间，其中 n，m 表示两个集合的大小，通常是问题的下限。

幸运的是，STL 容器集以平衡二叉搜索树为基，我们可以在线性时间内按顺序迭代所有元素，因此可以实现 O(n+m)。

template<typename T>
std::vector<T> set_diff(std::set<T> const &a, std::set<T> const &b) {
  std::vector<T> v;
  auto ita = a.begin();
  auto itb = b.begin();
  while (ita != a.end() && itb != b.end()) {
    if (*ita == *itb) {
      ++ita, ++itb;
    } else if (*ita < *itb) {
      v.push_back(*ita);
      ++ita;
    } else {
      v.push_back(*itb);
      ++itb;
    }
  }
  for (; ita != a.end(); v.push_back(*ita), ++ita);
  for (; itb != b.end(); v.push_back(*itb), ++itb);
  return v;
}