基于std::ranges实现排序数组最长重复序列保留及N扩展方案问询

给定已排序数组，需要仅保留其中重复值的最长连续序列；同时希望将功能参数化，支持保留长度排名前N的重复序列。目前已有一段实现代码，询问是否可以通过std::ranges/views/projections实现更简洁的方案。

现有实现代码 #

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

auto keep_longest_sequences(auto first, auto last)
{
    auto dest_init = first;
    auto dest = first;

    decltype(std::distance(first, last)) max_range_size = 0;

    while (first != last) {
        auto it_next_val = std::upper_bound(first, last, *first);
        auto size = std::distance(first, it_next_val);

        if (size > max_range_size) {
            max_range_size = size;
            dest = dest_init;
            std::copy(first, it_next_val, dest);
            dest += size;
        }
        else if (size == max_range_size) {
            std::copy(first, it_next_val, dest);
            dest += size;
        }
        first = it_next_val;
    }

    return dest;
}

int main() {
    std::vector<int> v = { 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6, 7, 7, 7, 7 };
    
    v.erase(keep_longest_sequences(v.begin(), v.end()), v.end());

    for (auto vi : v) {
            std::cout << vi << " ";
    }
}

预期结果 #

仅保留最长序列时输出：

2 2 2 2 7 7 7 7

支持保留前2长的序列时输出：

1 1 1 2 2 2 2 6 6 6 7 7 7 7

基于std::ranges的简洁实现 #

1. 仅保留最长连续重复序列的版本 #

利用C++20的std::ranges组件，通过分组、筛选、展平的声明式写法实现，代码更简洁直观：

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

int main() {
    std::vector<int> v = {1,1,1,2,2,2,2,3,3,4,4,5,6,6,6,7,7,7,7};

    // 1. 将连续重复元素分组
    auto grouped = v | std::views::chunk_by([](int a, int b){ return a == b; });

    // 2. 计算所有分组的长度，找出最大值
    auto lengths = grouped | std::views::transform([](auto&& r){ return std::ranges::distance(r); });
    const auto max_len = *std::ranges::max_element(lengths);

    // 3. 筛选长度等于最大值的分组，再展平为一维序列
    auto result = grouped | std::views::filter([max_len](auto&& r){ return std::ranges::distance(r) == max_len; })
                          | std::views::join;

    // 输出结果
    for (int num : result) {
        std::cout << num << " ";
    }

    // 若要修改原容器：
    // std::ranges::copy(result, v.begin());
    // v.erase(std::ranges::next(v.begin(), std::ranges::distance(result)), v.end());
}

2. 参数化支持保留前N长序列的版本 #

通过收集分组信息、排序长度阈值、筛选符合条件的分组，实现可配置的前N长序列保留功能：

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

template <std::ranges::forward_range R>
auto keep_top_n_longest_sequences(R&& r, size_t top_n) {
    // 1. 分组并存储每组的长度与对应子序列
    std::vector<std::pair<size_t, std::ranges::subrange<std::ranges::iterator_t<R>>>> groups;
    for (auto&& chunk : r | std::views::chunk_by([](auto a, auto b){ return a == b; })) {
        groups.emplace_back(std::ranges::distance(chunk), chunk);
    }

    if (groups.empty()) return std::views::empty<typename R::value_type>();

    // 2. 提取所有分组长度并降序排序，获取第top_n长的阈值（兼容并列情况）
    std::vector<size_t> lengths;
    std::ranges::transform(groups, std::back_inserter(lengths), [](auto& p){ return p.first; });
    std::ranges::sort(lengths, std::greater<>());

    top_n = std::min(top_n, lengths.size());
    const auto threshold = lengths[top_n - 1];

    // 3. 筛选长度不小于阈值的分组，展平为结果序列
    auto filtered_groups = groups | std::views::filter([threshold](auto& p){ return p.first >= threshold; })
                                  | std::views::transform([](auto& p){ return p.second; });

    return filtered_groups | std::views::join;
}

int main() {
    std::vector<int> v = {1,1,1,2,2,2,2,3,3,4,4,5,6,6,6,7,7,7,7};

    // 保留前2长的连续重复序列
    auto result = keep_top_n_longest_sequences(v, 2);

    for (int num : result) {
        std::cout << num << " ";
    }
}

实现说明 #

• std::views::chunk_by：专门用于已排序序列的连续重复元素分组，是核心工具。
• std::views::transform/filter：实现分组信息转换与筛选逻辑，代码可读性更强。
• std::views::join：将筛选后的多组序列展平为一维，直接输出或写入容器。
• 参数化版本通过长度排序获取阈值，自动兼容并列情况（比如多个序列长度同为第N长时，全部保留）。

内容的提问来源于stack exchange，提问作者Damir Tenishev