如何在C++ ranges视图上使用range::find实现唯一字符序列查找

问题描述 #

我想把一段检测首个全唯一字符序列的代码改成C++ Ranges风格。原有代码通过循环遍历子串、检查元素唯一性来定位起始标记；我已经实现了一个基于ranges::views::sliding的版本，但只是略有优化。我觉得这应该可以用简单的find操作实现，但在视图上使用range::find始终不成功，也没找到相关示例——请问能不能在Ranges视图上使用find？

原有代码 #

bool hasOnlyUniqueElements( auto& data ) {
    std::unordered_set<char> set;

    for( auto& value : data )
        set.emplace( value );

    return set.size() == data.size();
}

int64_t getStartPacketMarker( const std::string& data, int64_t markerSize ) {
    for( int64_t i = 0; i < data.size() - markerSize; i++ )
    {
        std::string_view packet( data.begin() + i, data.begin() + i + markerSize );
        if( hasOnlyUniqueElements( packet ) )
            return i + markerSize;
    }
    return -1;
}

已实现的Ranges版本 #

int64_t getStartPacketMarker( const std::string& data, int64_t markerSize ) {
    int64_t idx = 0;
    for( auto packet :  data | ranges::views::sliding( markerSize ) ) {
        if( hasOnlyUniqueElements( packet ) )
            return idx + markerSize;
        idx++;
    }

    return -1;
}

解答 #

当然可以在Ranges视图上使用查找操作，但你需要用ranges::find_if而非ranges::find——因为find是用来匹配特定值的，而我们需要查找满足「所有元素唯一」这个自定义条件的滑动窗口。

优化后的Ranges风格实现

首先可以先把hasOnlyUniqueElements适配为支持任意Range的版本：

bool hasOnlyUniqueElements(const auto& range) {
    std::unordered_set<char> char_set;
    // 用all_of结合insert的返回值，提前终止不必要的遍历
    return ranges::all_of(range, [&char_set](char c) {
        return char_set.insert(c).second;
    });
}

然后用ranges::find_if实现声明式的查找逻辑，不需要手动维护索引：

#include <ranges>
#include <algorithm>

int64_t getStartPacketMarker(const std::string& data, int64_t markerSize) {
    // 生成所有长度为markerSize的滑动窗口视图
    auto sliding_windows = data | ranges::views::sliding(markerSize);
    
    // 找到第一个满足元素全唯一的窗口
    auto match_iter = ranges::find_if(sliding_windows, hasOnlyUniqueElements);
    
    if (match_iter != sliding_windows.end()) {
        // 计算窗口起始位置：窗口首元素与原字符串起始的偏移量
        auto start_offset = ranges::distance(data.begin(), match_iter->begin());
        return start_offset + markerSize;
    }
    
    return -1;
}

或者用views::enumerate直接绑定窗口与索引，更直观：

int64_t getStartPacketMarker(const std::string& data, int64_t markerSize) {
    auto indexed_windows = data | ranges::views::sliding(markerSize)
                               | ranges::views::enumerate();
    
    auto match_iter = ranges::find_if(indexed_windows, [](const auto& idx_window) {
        return hasOnlyUniqueElements(idx_window.second);
    });
    
    if (match_iter != indexed_windows.end()) {
        return match_iter->first + markerSize;
    }
    
    return -1;
}

关键说明

• Ranges视图完全兼容标准库的range算法（包括find_if），只要视图满足输入范围的要求（sliding视图属于输入范围）。
• 用find_if替代手动循环，代码更符合Ranges的声明式编程风格，也避免了手动维护索引可能带来的错误。

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