std::views::transform在std::views::chunk后失效及后续问题求助

需求说明 #

从std::multimap<uint32_t, uint32_t>中提取所有键恰好出现两次的条目，将对应的值相乘后求和。

最初尝试的代码 #

// std::multimap<uint32_t, uint32_t> gears
auto gearRatios = gears
    | std::views::filter([&gears](const auto& pair) { return gears.count(pair.first) == 2; })
    | std::views::transform([&gears](const auto& pair) { return pair.second; })
    | std::views::chunk(2)
    | std::views::transform([](const auto& elements) { return std::accumulate(elements.begin(), elements.end(), 1, [](const auto& acc, const auto& value) { return acc * value; }); });
uint32_t sumOfGearRatios = std::accumulate(gearRatios.begin(), gearRatios.end(), 0);

编译错误信息 #

[build] C:/Users/morit/Git/aoc2023/03/02_EngineSchematics.cpp:135:82: note:   deduced conflicting types for parameter '_InputIterator' ('std::counted_iterator<std::ranges::transform_view<std::ranges::filter_view<std::ranges::ref_view<std::multimap<unsigned int, unsigned int> >, main()::<lambda(const auto:62&)> >, main()::<lambda(const auto:63&)> >::_Iterator<false> >' and 'std::ranges::take_view<std::ranges::subrange<std::ranges::transform_view<std::ranges::filter_view<std::ranges::ref_view<std::multimap<unsigned int, unsigned int> >, main()::<lambda(const auto:62&)> >, main()::<lambda(const auto:63&)> >::_Iterator<false>, std::ranges::transform_view<std::ranges::filter_view<std::ranges::ref_view<std::multimap<unsigned int, unsigned int> >, main()::<lambda(const auto:62&)> >, main()::<lambda(const auto:63&)> >::_Iterator<false>, std::ranges::subrange_kind::unsized> >::_Sentinel<true>')
[build]   135 |         | std::views::transform([](const auto& elements) { return std::accumulate(elements.begin(), elements.end(), 1, [](const auto& acc, const auto& value) { return acc * value; }); });
[build]       |                                                                   ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
[build] C:/Users/morit/Git/aoc2023/03/02_EngineSchematics.cpp: In function 'int main()':
[build] C:/Users/morit/Git/aoc2023/03/02_EngineSchematics.cpp:135:9: error: no match for 'operator|' (operand types are 'std::ranges::chunk_view<std::ranges::transform_view<std::ranges::filter_view<std::ranges::ref_view<std::multimap<unsigned int, unsigned int> >, main()::<lambda(const auto:62&)> >, main()::<lambda(const auto:63&)> > >' and 'std::ranges::views::__adaptor::_Partial<std::ranges::views::_Transform, main()::<lambda(const auto:64&)> >')
[build]   131 |     auto gearRatios = gears
[build]       |                       ~~~~~
[build]   132 |         | std::views::filter([&gears](const auto& pair) { return gears.count(pair.first) == 2; })
[build]       |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
[build]   133 |         | std::views::transform([&gears](const auto& pair) { return pair.second; })
[build]       |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
[build]   134 |         | std::views::chunk(2)
[build]       |         ~~~~~~~~~~~~~~~~~~~~~~
[build]       |         |
[build]       |         std::ranges::chunk_view<std::ranges::transform_view<std::ranges::filter_view<std::ranges::ref_view<std::multimap<unsigned int, unsigned int> >, main()::<lambda(const auto:62&)> >, main()::<lambda(const auto:63&)> > >
[build]   135 |         | std::views::transform([](const auto& elements) { return std::accumulate(elements.begin(), elements.end(), 1, [](const auto& acc, const auto& value) { return acc * value; }); });
[build]       |         ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
[build]       |                                |
[build]       |                                std::ranges::views::__adaptor::_Partial<std::ranges::views::_Transform, main()::<lambda(const auto:64&)> >

开发环境 #

• Windows 10
• GCC 13.1.0 x64（通过MSYS64安装）
• CMake 3.26.4
• Ninja 1.11.1

修改后的代码（仍编译失败） #

尝试改用chunk_by分组，但filter中无法直接调用chunk.size()：

// std::multimap<uint32_t, uint32_t> gears
auto gearRatios = gears
    | std::views::chunk_by([](const auto& pairOne, const auto& pairTwo) { return pairOne.first == pairTwo.first; })
    | std::views::filter([](const auto& chunk) { return chunk.size() == 2; })
    | std::views::transform([](const auto& elements) { return std::ranges::fold_left(elements, 1, [](const auto& acc, const auto& value) { return acc * value; }); });
uint32_t sumOfGearRatios = std::ranges::fold_left(gearRatios, 0, [](const auto& acc, const auto& value) { return acc + value; });

示例输入与预期输出 #

示例输入：

std::multimap<uint32_t, uint32_t> gears{
    {5, 20},
    {5, 30},
    {6, 50},
    {15, 10},
    {15, 5},
    {15, 2}
}

预期输出：仅统计键出现两次的条目乘积，最终求和结果为600（即20*30）

解决方案 #

问题核心是chunk_by生成的chunk是无范围大小信息的视图，无法直接调用size()。以下是几种优雅的解决方式：

方案1：用std::ranges::distance获取元素数量 #

auto gearRatios = gears
    | std::views::chunk_by([](const auto& a, const auto& b) { return a.first == b.first; })
    | std::views::filter([](const auto& chunk) { return std::ranges::distance(chunk) == 2; })
    | std::views::transform([](const auto& chunk) {
        auto it = std::ranges::begin(chunk);
        auto first_val = it->second;
        ++it;
        auto second_val = it->second;
        return first_val * second_val;
      })
    | std::views::sum;

方案2：利用multimap有序特性，用equal_range高效分组 #

std::multimap按键有序排列，直接用equal_range定位同键元素范围，效率更高：

uint32_t sumOfGearRatios = 0;
auto it = gears.begin();
while (it != gears.end()) {
    auto [range_begin, range_end] = gears.equal_range(it->first);
    const auto count = std::distance(range_begin, range_end);
    if (count == 2) {
        uint32_t product = 1;
        for (auto r_it = range_begin; r_it != range_end; ++r_it) {
            product *= r_it->second;
        }
        sumOfGearRatios += product;
    }
    it = range_end;
}

方案3：用std::ranges::fold_left统计元素数量 #

auto gearRatios = gears
    | std::views::chunk_by([](const auto& a, const auto& b) { return a.first == b.first; })
    | std::views::filter([](const auto& chunk) {
        return std::ranges::fold_left(chunk, 0u, [](auto cnt, const auto&) { return cnt + 1; }) == 2;
      })
    | std::views::transform([](const auto& chunk) {
        return std::ranges::fold_left(chunk, 1u, [](auto prod, const auto& p) { return prod * p.second; });
      })
    | std::views::sum;

内容的提问来源于stack exchange，提问作者Moritz Geier