c++ - 合并集合中满足谓词的元素

Question

我想知道是否有一种算法可以合并满足谓词的集合中的元素
类似于以下代码:

struct Element
{
  int size;
  constexpr static int maxSize = 150;
  enum Type { Mergeable, notMergeable } type;
};

auto predicate = [](const Element& el1, const Element& el2)
{
  //Done by the algorithm

  if(&el1 == &el2) // An element should not merge with itself obviously
    return false;

  if(el1.size == 0 || el2.size == 0) //element is marked for deletion
    return false; 

  //User predicate:
  bool isBelowMaxSize = el1.size + el2.size < Element::maxSize;
  bool isMergeable = el1.type  == Element::Type::Mergeable  && el2.type  == Element::Type::Mergeable;

  return isBelowMaxSize && isMergeable;
}

//User merge function
auto merge = [](Element& el1, Element& el2)
{
  el1 += el2;

  //Done by the algorithm
  el2.size = 0; //Marks for deletion
}

int main()
  std::vector<Element> els;
  //Let's assume els contains elements
  for(auto& el1 : els)
      for(auto& el2 : els)
          if(predicate(el1, el2))
            merge(el1, el2)

  //Merged elements are now removed
}

我以为我可以对范围做同样的事情:

    namespace rv = ranges::views;
    auto result = rv::cartesian_product(els, els) | rv::filter(predicate) | rv::for_each(merge);

但恐怕它无法正常工作，因为它可能会尝试合并已经合并的元素。

那么，有没有一种干净的方法来做到这一点？

Answer 1

您可以通过首先过滤所有 Element::Type::Mergeable 来避免 O(n2) 复杂度带有 size < Element::maxSize 的项目放入一个单独的容器(O(n))，并按大小排序(O(n log n))。

使用排序的候选容器，您可以轻松地从两端遍历它，直到您的迭代器在中间相遇。组合最大和最小元素将在线性时间内给出所有允许的合并。