我想知道是否存在以下算法的标准方法。我想对两个范围 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);
}
最佳答案
不,我能想到两个原因:
您实际上需要两种算法:
std::sort
和std::stable_partition
(或每个范围的两个分区的std::partition
和std::sort
)。您可以自己编写。算法根据迭代器 实现它们的语义 - 这就是应该实现使其适用于两个范围的额外部分的地方。换句话说,如果一种算法的语义可以用一个输入范围来定义,那么就不会出现多个输入范围的重载。
您必须使用自定义迭代器,它将在内部操作两个不同范围(容器)的迭代器。我想
boost::zip_iterator
正是您要找的。p>
关于c++ - 是否存在以下列方式对两个范围进行排序和划分的标准算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55688098/