实现范围适配器
面试考点
范围适配器(Range Adapter)是 C++20 Ranges 库的核心组件。面试官考察你是否理解惰性求值、视图(view)的设计原则、迭代器适配、管道运算符(|)的重载,以及如何实现可组合的自定义视图。
核心概念
范围适配器是一种惰性包装器:它不复制数据,只在迭代时按需计算。view_interface 提供了基于 begin()/end() 的默认实现。管道运算符 | 让多个适配器可以像 Unix 管道一样串联。核心设计是:适配器对象存储参数但不执行操作,迭代器在 ++ 和 * 时才真正计算。
基本示例
#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 | h | h(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) 构造的设计原理。