在C++中实现Python的range
目录代码在最后，可以先看代码再看说明
在实现过程中几个应该注意的问题
整型溢出
for (auto i : irange(1e9, -2e9, -2e9))
std::cout << i << "\n";
std::cout << '\n';
// 如果不注意溢出，会发生如下输出
1000000000
-1000000000
1294967296
-705032704
1589934592
-410065408
1884901888
-115098112
使用<limits>中的整型范围可解，同时std::numeric_limits可以得出泛型的范围
std::numeric_limits<value_type>::max(); // 最大值
std::numeric_limits<value_type>::min(); // 最小值
std::numeric_limits<value_type>::lowest(); // 最小值
对于整型来说，min(), lowest()是相同的
对于浮点数，min()代表正区间的下溢值，lowest()代表最小值（在负区间）
如下，可以使i不溢出
if (i <= std::numeric_limits<value_type>::max() - step)
i += step;
else
i = std::numeric_limits<value_type>::max();
迭代器选择
众所周知，C++中for (<type> <name> : <iterable>) {}是通过begin(), end()等函数获得的迭代器运作的。C++提供了多种迭代器类型，如ForwardIterator，RandomAccessIterator等，需要选择合适的range的迭代器
我选择InputIterator作为迭代器类型，提供了只读、只递增的限制
template <typename T, typename Diff>
class RangeIterator
{
public:
typedef std::input_iterator_tag iterator_category;
typedef T value_type;
typedef const T *pointer;
typedef const T &reference;
typedef Diff difference_type;
}
注意iterator_category, value_type, pointer, reference, difference_type都要有，否则无法被识别为InputIterator!
理论上，begin()应该是变动的，但end()不应该是变动的，可以在返回值加上限制（const）
iterator begin() const { return iterator(start_, step_); }
const iterator end() const { return iterator(stop_, step_); }
终止条件
Python中的range是左开右闭区间，[start, stop, step)，我们的实现也要相同
在C++中，依靠的是operator==(), operator!=()来判断迭代器终止的
bool operator!=(const self &other) const
{
return other.step == step &&
(step > 0 && i < other.i || step < 0 && i > other.i);
}
bool operator==(const self &other) const { return !operator!=(other); }
类型选择
为了尽善尽美，我希望range类可以满足各种类型的需要（包括浮点型），那么就不得不使用泛型了
-
有符号整型
最容易解决，没什么好说的
-
无符号整形
因为step有可能是负数，所以step需要是有符号的
-
浮点数
同样容易，就是注意
std::numeric_limits使用lowest()来调整溢出范围
为此，写了一个获取step类型的萃取器，可以获取整型的有符号版
template <typename T, bool>
struct get_diff_
{ typedef T difference_type; };
template <typename T>
struct get_diff_<T, true>
{ typedef std::make_signed_t<T> difference_type; };
template <typename T>
struct get_diff : get_diff_<T, std::is_integral_v<T>>
{};
template <typename T>
using get_diff_t = typename get_diff<T>::difference_type;
vector转换
我还希望range和vector能够互相转换，这比较简单，因为之间的条件都已经准备好了（迭代器和vector的转换）
在Range中添加
template <typename U>
operator std::vector<U>() const { return std::vector<U>(begin(), end()); }
最终代码
#include <vector>
#include <limits>
namespace range_space
{
template <typename T, bool>
struct get_diff_
{ typedef T difference_type; };
template <typename T>
struct get_diff_<T, true>
{ typedef std::make_signed_t<T> difference_type; };
template <typename T>
struct get_diff : get_diff_<T, std::is_integral_v<T>>
{ };
template <typename T>
using get_diff_t = typename get_diff<T>::difference_type;
template <typename T, typename Diff = get_diff_t<T>>
class Range
{
public:
class RangeIterator
{
friend class Range;
public:
typedef std::input_iterator_tag iterator_category;
typedef RangeIterator self;
typedef T value_type;
typedef const T *pointer;
typedef const T &reference;
typedef Diff difference_type;
RangeIterator(value_type x, value_type s) : i(x), step(s) {}
bool operator!=(const self &other) const
{
return other.step == step &&
(step > 0 && i < other.i || step < 0 && i > other.i);
}
bool operator==(const self &other) const { return !operator!=(other); }
reference operator*() const { return i; }
pointer operator->() const { return &i; }
self &operator++()
{
if (step > 0)
{
if (i <= std::numeric_limits<value_type>::max() - step)
i += step;
else
i = std::numeric_limits<value_type>::max();
}
else
{
if (i >= std::numeric_limits<value_type>::lowest() - step)
i += step;
else
i = std::numeric_limits<value_type>::lowest();
}
return *this;
}
self operator++(int)
{
self temp = *this;
i += step;
return temp;
}
private:
value_type i;
difference_type step;
};
typedef RangeIterator iterator;
public:
typedef T value_type;
typedef Diff difference_type;
// step != 0 and (stop - start) * step > 0
Range(value_type start, value_type stop, difference_type step)
: start_(start), stop_(stop), step_(step) {}
Range(value_type start, value_type stop) : Range(start, stop, 1) {}
explicit Range(value_type stop) : Range(0, stop, 1) {}
template <typename U>
operator std::vector<U>() const { return std::vector<U>(begin(), end()); }
iterator begin() const { return iterator(start_, step_); }
const iterator end() const { return iterator(stop_, step_); }
private:
value_type start_, stop_, step_;
};
} // namespace range_space
如果嫌命名空间麻烦的话，可以再加上
inline namespace range_instance
{
using irange = range_space::Range<int>;
using lrange = range_space::Range<long>;
using xrange = range_space::Range<long long>;
using drange = range_space::Range<double>;
using frange = range_space::Range<float>;
template <typename T>
using range = range_space::Range<T>;
} // inline namespace range_instance
如果想直接取消无符号整形的泛型，可以在Range中加入
template <typename T, typename Diff = ...>
class Range
{
static_assert(T() - 1 < 0, "need signed value type");
...
};
如果能够实现BigInteger, BigDecimal或是其他数字类型的话，可以实现
std::numeric_limits, std::is_integeral, std::make_signed的特化，就可以加入Range中了
和Python对比
- Python的
int是BigInteger不会溢出，范围很大；C++有特定的整型类型等，范围较小 - Python没有内置的浮点数的
range（numpy有） - Python的泛型比较高级（在typing模块中），因为Python本身是动态的；C++是静态的