c++ - 将 std::unique 与减少步骤相结合的算法？

Question

有人能想出一个干净(和快速)的解决方案来解决以下问题:

我有一个条目序列，这些条目基本上包含一个键和一个值，比如

struct Value {
    int index = 0;
    int cost = 0;
}

我现在想合并条目，这样每个键只包含一次，但值应该组合 - 即每个 index 应该只包含在序列中一次，并且每个重复索引的 cost 应该累加。

我提出的基本解决方案对序列进行排序，当在传递给 BinaryPredicate 的 std::sort 中检测到相等的条目时， cost 将被汇总到 lhs 中。然后 rhs 的成本将被设置为 0。然后是一个 remove_if，它删除了 0-cost 值。请参见此处的示例:

#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iostream>

struct Value
{
    int index = 0;
    int cost = 0;
};

// generate a bunch of random values in a vector
// values will have indices in range [0..10]
std::vector<Value> generator()
{
    std::vector<Value> v(20);
    std::generate(v.begin(), v.end(), []() { return Value{std::rand() % 10, std::rand() % 10}; });
    return v;
}

void print(const std::vector<Value> &values)
{
    for (auto v : values)
        std::cout << "{i=" << v.index << ", c=" << v.cost << "}, ";
    std::cout << "\n";
}

// 
void merge(std::vector<Value> &values)
{
    // sort values and merge costs
    std::sort(values.begin(), values.end(), [](auto &lhs , auto &rhs) {
        if (lhs.index == rhs.index) {
            lhs.cost += rhs.cost;
            rhs.cost = 0;
        }
        return lhs.index < rhs.index;
    });
    // remove entries with empty cost
    auto it = std::remove_if(values.begin(), values.end(), [](const auto &v) { return v.cost == 0; });
    values.erase(it, values.end());
}

int main()
{
    auto v = generator();
    std::cout << "generated values: ";
    print(v);

    merge(v);
    std::cout << "merged values: ";
    print(v);

}

Live on Compiler Explorer
事情是:虽然上面的例子产生了正确的结果，但我认为它不符合 C++ 标准。 BinaryPredicate “不应通过解引用的迭代器应用任何非常量函数” http://eel.is/c++draft/algorithms.requirements#8.sentence-4 。比较是一个二元谓词。 http://eel.is/c++draft/alg.sorting#general-2.sentence-1 )
这是否意味着我唯一的选择是推出自定义的 inplace_unique_reduce 或类似的东西，或者是否有另一种优雅的方法来解决这个问题？我宁愿不必为此编写自己的非平凡算法。
谢谢

Answer 1

假设您可以接受额外的分配，我会使用 std::map (或 std::unordered_map ):

auto merge_entries(std::vector<Value>& original_values) {
    auto values = std::map<int, int>();

    for (const auto [index, cost] : original_values) {
        values[index] += cost;
    }

    const auto end_of_merged_values = std::transform(
            values.cbegin(), values.cend(), original_values.begin(),
            [](const auto entry) {
                return Value{entry.first, entry.second};
            }
    );

    original_values.erase(end_of_merged_values, original_values.end());
}

除了一个 for() 循环(可以用 std::for_each 替换，虽然这种更改会引入不必要的样板文件，导致代码更难阅读，在我看来)，此解决方案仅使用 STL。
我们首先使用 map 合并所有条目，然后我们覆盖一些元素，以便我们的原始 std::vector 保存合并的条目。非常方便的是 std::transform 返回一个指向插入范围末尾的迭代器。为什么对我们有益？因为除了不发生合并的不太可能的场景之外，与最初传入的元素相比，我们的元素更少。使用该迭代器，我们可以对 vector 的其余部分(未覆盖的元素)进行 erase，使其保持干净，类似 STL 的风格。

假设您是 而不是 可以进行额外的分配，但是您 是 可以加强您的迭代器要求(双向)，我将使用 std::partial_sum 和 std::unique :

template <class BiDirIt, class BinaryPredicateCompare, class BinaryOpReduce>
auto inplace_unique_reduce(
        BiDirIt first, BiDirIt last,
        BinaryPredicateCompare cmp,
        BinaryOpReduce reduce
) {
    std::partial_sum(
            std::make_reverse_iterator(last), std::make_reverse_iterator(first),
            std::make_reverse_iterator(last),
            [cmp, reduce](auto acc, const auto& elem) {
                if (cmp(acc, elem)) {
                    return reduce(acc, elem);
                } else {
                    acc = elem;
                }
                return acc;
            }
    );

    return std::unique(first, last, cmp);
}

像这样使用:

auto values = std::vector<Value>{
        {1, 1}, {2, 2}, {2, 7}, {0, 5},
        {3, 3}, {1, 2}, {3, 10}
};
auto comparator = [](const auto& lhs, const auto& rhs) {
    return lhs.index == rhs.index;
};
auto reducer = [](const auto& lhs, const auto& rhs) {
    return Value{lhs.index, lhs.cost + rhs.cost};
};

auto to_remove = inplace_unique_reduce(
        values.begin(), values.end(),
        comparator,
        reducer
);

values.erase(to_remove, values.end());

for (const auto[index, cost] : values) {
    std::cout << index << ' ' << cost << '\n';
}

就像您的原始答案一样，这不会合并不相邻的元素，但是要做到这一点，您必须按照 index 对它们进行排序，或者使用我的答案的第一部分中的类似 map 的内容。 std::make_reverse_iterator 调用是必要的，因为 std::partial_sum 在给定的一组连续等效元素的最右侧累积合并元素。另一方面， std::unique 仅保留此类组中的第一个元素。因此，您希望以与 std::unique -ing 的顺序相反的顺序合并元素。

您对复制或移动成本高昂的情况提出了一些担忧 - 在这种情况下，您要么保留考虑到您的独特约束的自定义解决方案，要么减轻您的约束。在这里，我们移动分配合并的条目，但这就是潜在的瓶颈。如果您的移动分配运算符很昂贵，我担心没有标准的解决方案适合您，您 必须 自己动手，就像在您的答案中一样。