c++ - 是否存在以下列方式对两个范围进行排序和划分的标准算法？

Question

我想知道是否存在以下算法的标准方法。我想对两个范围 x 和 y 进行排序和划分。 x 和 y 都应该使用从 x 和 y 中获取元素的二进制谓词进行分区。该函数的签名类似于:

template<typename ForwardIt1, typename ForwardIt2, typename Compare, typename BinaryPredicate>
std::pair<ForwardIt1, ForwardIt2> sort_and_partition(ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, Compare comp, BinaryPredicate p);

此处 comp 被转发给 std::sort。二元谓词 p 用于分区。然后，例如:

std::vector<T> x;
std::vector<T> y;

auto [xm, ym] = sort_and_partition(x.begin(), x.end(), y.begin(), y.end(), std::less<T>{}, std::equal_to<T>{});

这将产生四个范围:

• x1: [x.begin(), xm)
• x2: [xm, x.end())
• y1: [y.begin(), ym)
• y2: [ym, y.end())

其中 x1 和 y1 都已排序并包含等效元素(根据二进制谓词 p)。实际上，x1 和 y1 包含示例中 x 和 y 的排序交集。 x2 和 y2 也被排序，并且分别包含 x 和 y 唯一的所有元素。

我是否缺少通过组合 STL 中的现有算法来实现此类算法的明显方法？我现在正计划为此编写一个自定义实现，但想在开始实现之前先在这里检查一下。这个算法的好名字是什么？

更新，我已经实现了满足我要求的以下算法。该算法要求对输入范围进行排序。

/// Takes two sorted input ranges, and partitions both ranges such that all
/// elements that occur in both ranges precede those elements that only occur in
/// one of the two ranges.
template<typename ForwardIt1, typename ForwardIt2, typename Compare>
std::pair<ForwardIt1, ForwardIt2> frc::binary_partition(
    ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, Compare comp)
{
  auto equals = [&](const auto& x, const auto& y) { return !comp(x, y) && !comp(y, x); };

  // Invariant: first1 and last1 point to the first mismatch.
  std::tie(first1, first2) = std::mismatch(first1, last1, first2, last2, equals);

  while (first1 != last1 && first2 != last2)
  {
    // Iterators to the next matching elements.
    auto fm1{first1};
    auto fm2{first2};

    // Find next matching elements in both ranges.
    while (comp(*fm1, *fm2) || comp(*fm2, *fm1))
    {
      if (comp(*fm1, *fm2))
      {
        ++fm1;
      }
      else
      {
        ++fm2;
      }

      if (fm1 == last1 || fm2 == last2)
      {
        return std::pair(first1, first2);
      }
    }

    // Find the end of the matching subsequence.
    auto [lm1, lm2] = std::mismatch(fm1 + 1, last1, fm2 + 1, last2, equals);

    // In case matching elements are found, move the mismatching subrange behind
    // the matching subrange.
    first1 = std::rotate(first1, fm1, lm1);
    first2 = std::rotate(first2, fm2, lm2);
  }

  return std::pair(first1, first2);
}

Answer 1

不，我能想到两个原因:

1. 您实际上需要两种算法:std::sort和 std::stable_partition (或每个范围的两个分区的 std::partition 和 std::sort)。您可以自己编写。

2. 算法根据迭代器 实现它们的语义 - 这就是应该实现使其适用于两个范围的额外部分的地方。换句话说，如果一种算法的语义可以用一个输入范围来定义，那么就不会出现多个输入范围的重载。

   您必须使用自定义迭代器，它将在内部操作两个不同范围(容器)的迭代器。我想 boost::zip_iterator 正是您要找的。