>我有一个对数组,例如:
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';
}
这段代码可以更简洁吗?(不更改基础容器的类型(
我希望通过替换为标准库中的算法来尝试消除原始循环,但我没有看到一个完全合适的算法。
我想要一些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
等非常熟悉,不想使用它。
嗯,一种不使用其他容器的方法,没有原始循环(或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::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 << '}';
}
(注意:OP 在我的回答之后编辑了问题,以指定他们不想使用map
或其变体,然后再次指定它需要就地(
哈希表将为您完成合并工作:
std::unordered_map<char, int> coalesced;
for(const auto key_val : X)
coalesced[key_val.first] += key_val.second;
现在我们有一个哈希表,其内容为
A : 4
B : 2
C : 5
如果你想把它放到另一个std::vector
,那很好:
vector< pair<char, int> > Y(coalesced.begin(), coalesced.end());
或者你可以保持原样。
unordered_map
是未排序的w.r.t键(因此称为"无序"(。如果您希望对它们进行排序,那么您可以以完全相同的方式使用std::map
(但它是作为二叉搜索树而不是哈希表实现的(