c++ - 是否有具有用户定义的碰撞处理程序的 std::unique 风格的库算法？

Question

我有一个基本的 std::vector 键/值对。它是按键排序的。我想在压缩 vector 时使用用户定义的二元运算符减少所有相邻的重复键条目。

这基本上是一个 std::unique 应用程序，用户可以在其中决定如何处理碰撞，而不仅仅是保留第一个条目。

有没有满足这个要求的库算法？我可以自己写，但我更愿意依赖专家写的东西。

map-as-sorted-vector 是算法其他部分的核心，无法更改。我仅限于 C++14。

Answer 1

我想不出一个标准的算法。 std::unique 几乎满足要求，但不幸的是，您提供的用于比较元素的 BinaryPredicate 不允许修改它们(“binary_pred 不得通过取消引用的迭代器应用任何非常量函数。” - [algorithms.requirements] C++17 标准中的第 7 段)- 让实现更自由地优化的要求(例如， vector 的不同部分的并行处理)。

虽然实现起来并不难......

template <typename Iterator, typename BinaryPredicate, typename Compaction>
Iterator compact(Iterator begin, Iterator end, BinaryPredicate equals, Compaction compaction)
{
    if (begin == end) return begin;
    Iterator compact_to = begin;
    while (++begin != end)
        if (equals(*begin, *compact_to))
            compaction(*compact_to, *begin);
        else
            *++compact_to = *begin;
    return ++compact_to;
}

返回值将是压缩 vector 的新“结束” - 您可以从中删除，就像您对 remove_if 所做的那样。

你可以看到它正在运行 here 。