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

Question

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

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

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

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

Answer 1

我想不出一个标准算法。 std::unique 几乎满足要求，但不幸的是，您提供的用于比较元素的 BinaryPredicate 不允许修改它们 ("binary_pred shall not apply any non-constant function through the dereferenced iterators." - [algorithms.requirements] C++17 标准中的第 7 段）- 让实现更自由地优化的要求（例如，向量的不同部分的并行处理）。

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

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;
}

return 值将是压缩向量的新 "end" - 您可以从中 erase 就像 remove_if.

可以看到运行here.

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

Is there a std::unique-style library algorithm that has user-defined collision handler?

c++

algorithm

reduce

unique