如何用C++实现常数时间与常数空间的Range类以支持范围for循环

要满足常数时间和空间复杂度，核心思路是不预存所有范围内的元素，而是通过自定义迭代器在遍历过程中动态生成当前值。范围for循环的本质是依赖对象的begin()和end()方法返回迭代器，以及迭代器的operator*、operator++、operator!=操作，所以我们只需要给Range类实现这些必要组件即可。

完整实现代码 #

#include <iostream>

class Range {
private:
    int start_;
    int end_;

public:
    // 构造函数：初始化左闭右开的范围（对应示例中0到10的遍历需求）
    Range(int start, int end) : start_(start), end_(end) {}

    // 自定义迭代器，满足输入迭代器的最低要求即可
    class Iterator {
    private:
        int current_;
    public:
        explicit Iterator(int current) : current_(current) {}

        // 返回当前值的引用，支持auto& x的写法
        int& operator*() {
            return current_;
        }

        // 前缀自增，移动到下一个元素
        Iterator& operator++() {
            ++current_;
            return *this;
        }

        // 判断迭代器是否到达遍历终点
        bool operator!=(const Iterator& other) const {
            return current_ != other.current_;
        }
    };

    // 返回起始位置的迭代器
    Iterator begin() {
        return Iterator(start_);
    }

    // 返回结束位置的迭代器
    Iterator end() {
        return Iterator(end_);
    }
};

// 测试示例代码
int main() {
    for (auto &x : Range{0, 10}) {
        std::cout << x << " ";
    }
    // 输出结果：0 1 2 3 4 5 6 7 8 9 
    return 0;
}

关键细节说明 #

• 空间复杂度：Range对象仅存储两个整数（start_和end_），迭代器仅存储当前遍历的整数，无论范围多大，占用内存都是固定的，完全符合常数空间要求。
• 时间复杂度：每个迭代操作（取值、自增、判断结束）都是O(1)的常数时间，遍历全程无额外耗时操作。
• 左闭右开规则：示例中Range{0,10}会遍历0到9，和C++标准库容器的范围for行为保持一致。如果需要左闭右闭的范围，只需在构造函数中将end_设为end+1，或者修改end()的返回值即可。

扩展支持多类型 #

如果需要支持long、unsigned int等其他数值类型，可以将Range改为模板类：

template<typename T>
class Range {
private:
    T start_;
    T end_;
public:
    Range(T start, T end) : start_(start), end_(end) {}

    class Iterator {
    private:
        T current_;
    public:
        explicit Iterator(T current) : current_(current) {}

        T& operator*() { return current_; }
        Iterator& operator++() { ++current_; return *this; }
        bool operator!=(const Iterator& other) const { return current_ != other.current_; }
    };

    Iterator begin() { return Iterator(start_); }
    Iterator end() { return Iterator(end_); }
};

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