像 std::vector 中的元素一样就地合并

Question

我有一个数组对，例如：

X = {{A, 1}, {B, 2}, {C, 1}, {A, 3}, {C, 4}}

我想生成一个数组：

Y = (x, n) such that n = sum i for (x, i) in X

所以在上面的例子中，我们有：

Y = {{A, 4}, {B, 2}, {C, 5}}

我目前的代码是：

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

using namespace std;

int main() {

    char A = 'A';
    char B = 'B';
    char C = 'C'; 

    vector< pair<char, int> > X = {{A, 1}, {B, 2}, {C, 1}, {A, 3}, {C, 4}};

    // Sort by first element of the pair
    sort(begin(X), end(X), [](auto a, auto b) { return a.first < b.first; });

    // Could this be better? Is there an existing STL algorithm that will
    // do this in-place?
    vector< pair<char, int> > Y;
    for(auto p : X) {
        if(Y.empty() || Y.back().first != p.first) {
            Y.push_back(p);
        } else {
            Y.back().second += p.second;
        }
    }

    cout << "Y:";
    for (auto p : Y) {
       cout << '{' << p.first << ' ' << p.second << '}';
    }
    cout << '\n';

}

这段代码可以更简洁吗？（不改变底层容器的类型）

我想尝试通过替换为标准库中的一种算法来消除 raw loop，但我没有看到非常适合的算法。

我想要一些 std::unique 的变体，它不仅需要判断两个元素是否等价的谓词，还需要一个定义如何组合它们的函数。它可能看起来像：

coalesce(begin(X), end(X), [](auto a, auto b){ return a.first == b.first; }, [](auto a, auto b) { return {a.first, a.second+b.second} });

FWIW，这是 coalesce 的一个实现，它似乎有效：

template<class ForwardIt, class BinaryPredicate, class BinaryFunction>
ForwardIt coalesce(ForwardIt first, ForwardIt last, BinaryPredicate p, BinaryFunction f)
{
    if (first == last)
        return last;

    ForwardIt result = first;
    while (++first != last) {
        if(p(*result, *first)) {
            *result = f(*result, *first);
        } else {
            ++result;
            *result = *first;
        }
    }
    return ++result;
}

代码变为：

    vector< pair<char, int> > X = {{A, 1}, {B, 2}, {C, 1}, {A, 3}, {C, 4}};

    // Sort by first element of the pair
    sort(begin(X), end(X), [](auto a, auto b) { return a.first < b.first; });

    // Easier to understand the intent!
    auto e = coalesce(begin(X), end(X),
                      [](auto a, auto b) { return a.first == b.first; },
                      [](auto a, auto b) { return pair<char, int>{a.first, a.second+b.second}; });

    for_each(begin(X), e, [](auto p) {
        cout << '{' << p.first << ' ' << p.second << '}';
    });
    cout << '\n';

注意：我对 map 等非常熟悉，不想使用它。

Answer 1

（注意：OP 在我回答后编辑了问题，指定他们不想使用 map 或其变体，然后再次指定它需要 in-place）

哈希 table 将为您完成合并工作：

std::unordered_map<char, int> coalesced;
for(const auto key_val : X)
    coalesced[key_val.first] += key_val.second;

现在我们有一个散列table，其内容为

A : 4
B : 2
C : 5

如果您想将其放入另一个 std::vector，没问题：

vector< pair<char, int> > Y(coalesced.begin(), coalesced.end());

或者你可以离开 as-is。

unordered_map 是未排序的 w.r.t 键（因此得名“无序”）。如果你想让它们排序，那么你可以使用完全相同的方式 std::map （但它是作为二叉搜索树而不是哈希实现的 table）

Demo

Answer 2

我很想用 Compare 来定义它，而不是等于。你会 std::upper_bound 得到组和每个组中的 std::accumulate。

template<class ForwardIt, class OutputIt, class Compare = std::less<>, class BinaryOperation = std::plus<>>
OutputIt coalesce(ForwardIt first, ForwardIt last, OutputIt d_first, Compare comp = {}, BinaryOperation op = {})
{
    while (first != last) {
        ForwardIt group = std::upper_bound(first, last, *first, comp);
        *d_first++ = std::accumulate(std::next(first), group, *first, op);
        first = group;
    }
    return d_first;
}

可以这样使用

vector< pair<char, int> > X = {{'A', 1}, {'B', 2}, {'C', 1}, {'A', 3}, {'C', 4}};
less<> comp;
auto add = [](auto a, auto b) { return pair<char, int>{a.first, a.second+b.second}; };

sort(begin(X), end(X)/*, comp*/);

auto e = coalesce(begin(X), end(X), begin(X), comp, add);
X.erase(e, end(X));

for (auto [k, v] : X) {
    cout << '{' << k << ' ' << v << '}';
}

Answer 3

嗯，一种不使用其他容器、没有原始循环（或 std::for_each）的方法可能会将 std::sort 与 std::partial_sum

结合起来

std::partial_sum 用于计算前缀和，或者更确切地说是一种组合相邻元素的通用方法。在我们的初始排序之后，我们可以使用 std::partial_sum 来组合具有相同键的元素：

std::vector< std::pair<char, int> > Y;
std::vector< std::pair<char, int> > Y(X.size());
std::partial_sum(X.begin(), X.end(),  Y.rbegin(), [](const auto& lhs, const auto& rhs)
{
    if (lhs.first != rhs.first)
        return rhs;
    return std::make_pair(lhs.first, lhs.second + rhs.second);
});

请注意，我们在 Y 中向后迭代。这是为下一步设计的，我稍后会详细说明。

这让我们走到了那里。现在我们有一个 Y 看起来像这样：

Y:{C 5}{C 1}{B 2}{A 4}{A 1}

现在我们的任务是删除重复项，我们可以用 std::unique:

Y.erase(std::unique(Y.begin(), Y.end(), 
   [](const auto& lhs, const auto& rhs){
      return lhs.first == rhs.first;}), Y.end());

我们需要在反向范围内使用 partial_sum，因为 std::unique“从每组连续的等效元素中消除除第一个元素以外的所有元素”，我们需要最后的 partial_sum 最先出现。

考虑到排序，整个算法是 O(N log N)。内存使用量为 O(N)。

像 std::vector 中的元素一样就地合并

in-place coalescing like elements in a std::vector

c++

algorithm

c++-standard-library

Demo

Demo