实现范围适配器 ​

面试考点 ​

范围适配器(Range Adapter)是 C++20 Ranges 库的核心组件。面试官考察你是否理解惰性求值、视图(view)的设计原则、迭代器适配、管道运算符(|)的重载,以及如何实现可组合的自定义视图。

核心概念 ​

范围适配器是一种惰性包装器:它不复制数据,只在迭代时按需计算。view_interface 提供了基于 begin()/end() 的默认实现。管道运算符 | 让多个适配器可以像 Unix 管道一样串联。核心设计是:适配器对象存储参数但不执行操作,迭代器在 ++ 和 * 时才真正计算。

基本示例 ​

cpp
#include <iostream>
#include <vector>
#include <iterator>
#include <type_traits>
#include <functional>
#include <optional>

// ============================
// 示例1:Filter 视图
// ============================

// 过滤视图:只产出满足谓词的元素
template<typename Range, typename Pred>
class FilterView {
public:
    FilterView(Range range, Pred pred)
        : range_(std::move(range)), pred_(std::move(pred)) {}

    // 迭代器:跳过不满足条件的元素
    class iterator {
    public:
        using value_type = typename Range::value_type;
        using difference_type = std::ptrdiff_t;
        using pointer = const value_type*;
        using reference = const value_type&;
        using iterator_category = std::forward_iterator_tag;

        iterator() = default;

        iterator(typename Range::iterator current,
                 typename Range::iterator end,
                 const Pred* pred)
            : current_(current), end_(end), pred_(pred) {
            // 跳到第一个满足条件的元素
            advance_to_valid();
        }

        reference operator*() const { return *current_; }
        pointer operator->() const { return &(*current_); }

        iterator& operator++() {
            ++current_;
            advance_to_valid();
            return *this;
        }

        iterator operator++(int) {
            auto tmp = *this;
            ++(*this);
            return tmp;
        }

        bool operator==(const iterator& other) const {
            return current_ == other.current_;
        }

        bool operator!=(const iterator& other) const {
            return !(*this == other);
        }

    private:
        // 前进到下一个满足谓词的元素
        void advance_to_valid() {
            while (current_ != end_ && !(*pred_)(*current_)) {
                ++current_;
            }
        }

        typename Range::iterator current_;
        typename Range::iterator end_;
        const Pred* pred_;
    };

    iterator begin() {
        return iterator(range_.begin(), range_.end(), &pred_);
    }

    iterator end() {
        return iterator(range_.end(), range_.end(), &pred_);
    }

    // value_type 传递
    using value_type = typename Range::value_type;

private:
    Range range_;
    Pred pred_;
};

// ============================
// 示例2:Transform 视图
// ============================

// 映射视图:对每个元素应用变换函数
template<typename Range, typename Func>
class TransformView {
public:
    using output_type = std::invoke_result_t<Func, const typename Range::value_type&>;

    TransformView(Range range, Func func)
        : range_(std::move(range)), func_(std::move(func)) {}

    class iterator {
    public:
        using value_type = output_type;
        using difference_type = std::ptrdiff_t;
        using pointer = void;
        using reference = value_type;
        using iterator_category = std::forward_iterator_tag;

        iterator() = default;

        iterator(typename Range::iterator current, const Func* func)
            : current_(current), func_(func) {}

        // 解引用时才执行变换(惰性求值)
        value_type operator*() const { return (*func_)(*current_); }

        iterator& operator++() { ++current_; return *this; }

        iterator operator++(int) {
            auto tmp = *this;
            ++(*this);
            return tmp;
        }

        bool operator==(const iterator& other) const {
            return current_ == other.current_;
        }

        bool operator!=(const iterator& other) const {
            return !(*this == other);
        }

    private:
        typename Range::iterator current_;
        const Func* func_;
    };

    iterator begin() {
        return iterator(range_.begin(), &func_);
    }

    iterator end() {
        return iterator(range_.end(), &func_);
    }

    using value_type = output_type;

private:
    Range range_;
    Func func_;
};

// ============================
// 示例3:Take 视图
// ============================

// 取前 N 个元素
template<typename Range>
class TakeView {
public:
    TakeView(Range range, size_t count)
        : range_(std::move(range)), count_(count) {}

    class iterator {
    public:
        using value_type = typename Range::value_type;
        using difference_type = std::ptrdiff_t;
        using pointer = const value_type*;
        using reference = const value_type&;
        using iterator_category = std::forward_iterator_tag;

        iterator() = default;

        iterator(typename Range::iterator current,
                 typename Range::iterator end,
                 size_t remaining)
            : current_(current), end_(end), remaining_(remaining) {}

        reference operator*() const { return *current_; }

        iterator& operator++() {
            ++current_;
            if (remaining_ > 0) --remaining_;
            return *this;
        }

        bool operator==(const iterator& other) const {
            return current_ == other.current_ || remaining_ == other.remaining_;
        }

        bool operator!=(const iterator& other) const {
            return !(*this == other);
        }

    private:
        typename Range::iterator current_;
        typename Range::iterator end_;
        size_t remaining_ = 0;
    };

    iterator begin() {
        return iterator(range_.begin(), range_.end(), count_);
    }

    iterator end() {
        return iterator(range_.end(), range_.end(), 0);
    }

    using value_type = typename Range::value_type;

private:
    Range range_;
    size_t count_;
};

// ============================
// 管道运算符支持
// ============================

// 闭包对象:存储参数,等待范围输入
template<typename Func>
struct PipeClosure {
    Func func;

    PipeClosure(Func f) : func(std::move(f)) {}

    // 管道运算符:range | closure → closure(range)
    template<typename Range>
    friend auto operator|(Range&& range, const PipeClosure& closure) {
        return closure.func(std::forward<Range>(range));
    }
};

// 适配器工厂函数
namespace views {

// filter 适配器
inline auto filter = [](auto pred) {
    return PipeClosure([pred = std::move(pred)](auto range) {
        return FilterView(std::move(range), pred);
    });
};

// transform 适配器
inline auto transform = [](auto func) {
    return PipeClosure([func = std::move(func)](auto range) {
        return TransformView(std::move(range), func);
    });
};

// take 适配器
inline auto take = [](size_t n) {
    return PipeClosure([n](auto range) {
        return TakeView(std::move(range), n);
    });
};

} // namespace views

// ============================
// 辅助:让 vector 支持管道
// ============================

// 包装 vector 使其可以通过管道传递
template<typename T>
class VecRange {
public:
    VecRange(std::vector<T> v) : data_(std::move(v)) {}
    VecRange(std::initializer_list<T> il) : data_(il) {}

    using value_type = T;
    using iterator = typename std::vector<T>::iterator;
    using const_iterator = typename std::vector<T>::const_iterator;

    iterator begin() { return data_.begin(); }
    iterator end() { return data_.end(); }

private:
    std::vector<T> data_;
};

// ============================
// 测试
// ============================

void test_filter() {
    std::cout << "--- filter ---" << std::endl;

    VecRange<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // 过滤偶数
    auto evens = nums | views::filter([](int n) { return n % 2 == 0; });

    for (auto v : evens) {
        std::cout << v << " ";  // 2 4 6 8 10
    }
    std::cout << std::endl;
}

void test_transform() {
    std::cout << "\n--- transform ---" << std::endl;

    VecRange<int> nums = {1, 2, 3, 4, 5};

    // 每个元素乘以 10
    auto result = nums | views::transform([](int n) { return n * 10; });

    for (auto v : result) {
        std::cout << v << " ";  // 10 20 30 40 50
    }
    std::cout << std::endl;
}

void test_take() {
    std::cout << "\n--- take ---" << std::endl;

    VecRange<int> nums = {10, 20, 30, 40, 50, 60};

    // 取前 3 个
    auto first3 = nums | views::take(3);

    for (auto v : first3) {
        std::cout << v << " ";  // 10 20 30
    }
    std::cout << std::endl;
}

void test_pipeline() {
    std::cout << "\n--- 管道组合 ---" << std::endl;

    VecRange<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // 过滤偶数 → 乘以 10 → 取前 3 个
    auto result = nums
        | views::filter([](int n) { return n % 2 == 0; })
        | views::transform([](int n) { return n * 10; })
        | views::take(3);

    for (auto v : result) {
        std::cout << v << " ";  // 20 40 60
    }
    std::cout << std::endl;
}

int main() {
    test_filter();
    test_transform();
    test_take();
    test_pipeline();
    return 0;
}

范围适配器的设计原则 ​

原则说明
惰性求值不复制数据,迭代时才计算
O(1) 构造视图只存储引用/参数,不处理数据
可组合管道运算符串联多个适配器
不拥有数据视图引用底层范围,不拥有
迭代器适配包装底层迭代器,在 ++/* 中添加逻辑

管道运算符的工作原理 ​

表达式等价于
range | filter(pred)FilterView(range, pred)
range | transform(f)TransformView(range, f)
range | f | g | hh(g(f(range)))

常见问题 ​

视图为什么不拥有数据?

如果视图拷贝数据,每个管道步骤都会分配内存,O(N) 的空间开销。不拥有数据意味着所有视图共享底层范围,只在迭代时按需计算,空间复杂度 O(1)。代价是底层范围的生命周期必须长于视图。

管道运算符 | 是怎么实现的?

核心是闭包对象(Closure):views::filter(pred) 返回一个闭包,闭包重载了 operator|,接收左侧的范围并返回视图。这样 range | closure 就变成了 closure.func(range)。多层管道从左到右依次应用。

自定义视图需要满足什么要求?

C++20 的 view concept 要求:1) 满足 range(有 begin/end);2) 可移动构造和赋值;3) O(1) 的移动和析构。通常继承 std::ranges::view_interface 可以自动获得 empty()、operator bool()、front()、back() 等默认实现。

适用场景 ​

  • 数据处理管道(过滤、映射、分组)
  • 惰性求值避免中间集合分配
  • 函数式风格的数据变换
  • 大数据流的逐条处理

注意事项 ​

  • 视图不拥有数据,底层范围的生命周期必须足够长
  • 多次迭代视图会重复计算(没有缓存)
  • filter 视图的 begin() 不是 O(1)(需要找到第一个匹配元素)
  • 管道中的 lambda 捕获变量要注意生命周期
  • 自定义视图的迭代器需要正确定义五个类型别名

总结 ​

范围适配器的核心是惰性迭代器适配:视图只存储参数不执行计算,迭代器在 ++ 和 * 操作中才真正计算。管道运算符通过闭包对象实现,range | closure 调用 closure(range)。面试中要能实现 filter 和 transform 视图(包括迭代器类),实现管道运算符的重载,以及解释惰性求值和 O(1) 构造的设计原理。