是否存在具有用户定义的冲突处理程序的std :: unique-style库算法？

Question

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

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

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

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

Answer 1

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

虽然实施并不太难......

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

返回值将是压缩矢量的新“结束” - 你可以像erase那样remove_if。

你可以看到它运行here。