方便的结构用于遍历值范围。

• 下载 steps_loop_tests.zip

与上一版本的更改

自本文上一版本以来，已进行了以下更改：

• 添加了一个部分，其中包含对提议的循环构造的更正式定义；
• 实现更关注边界情况（步长为零时，循环遍历相应整数类型的整个范围时）；
• 基准测试包含 Windows 和 Linux 编译器下的结果。
• 添加了“正确性测试”部分。

引言

在本文中，提议了以下循环：

for  (auto&& x : step(start, count, step-width)) { ... }

for (auto  x : step(count)) {...}

for (auto  x : step_backward(count)) {...}

for (auto  x : step_to(start, finish, step-width)) {...}

for (auto  x : step_until(start, finish, step-width)) {...}

它们基于 C++11 的 for-range 循环。为了编写这样的循环，需要实现相应的函数step、step_backward、step_to 和 step_until。本文展示了它们的实现，讨论了此类循环的优点，并包含了基准测试结果。

背景

在某些情况下，我们需要顺序生成值，例如，以固定步长。如果我们想使用迭代器（这很自然），我们就必须将值存储在容器中。如果序列包含数百万个元素，这可能会成为一个问题。如果将其存储在容器中，将占用大量空间；我们将不得不提供移动构造函数和移动赋值运算符，并且通常要注意如何在函数之间传递容器。

使用标准的 for 循环可能不方便：使用无符号整数编写从 0 开始的递减序列并不直接。以下代码将不起作用：

for (std::size_t  j =  N-1;  j >= 0; --j) // infinite loop

{

. . .

}

我们必须编写以下循环，这对初学者来说并不明显：

for (std::size_t  j =  N;  j-- != 0;)

{

      . . .

}

浮点数循环，它们遍历浮点类型的值，也存在一些问题。以下循环：

for (double x = 0.5; x < 1.0; x += 0.1)

{

    std::cout << std::setprecision(17) << x << std::endl;

}

（在大多数计算机上）会打印出类似这样的内容：

0.5

0.59999999999999998

0.69999999999999996

0.79999999999999993

0.89999999999999991

0.99999999999999989

我们得到了六个值，而不是“预期”的五个。为了达到所需的效果，我们可以有两种选择。一种是使用整数步长并编写以下代码：

double x = 0.5;

for (int i = 0; i < 5; ++i)

{  

     std::cout << std::setprecision(17) << x << std::endl;

     x += 0.1;

}

另一种选择是从上界减去一个小的 epsilon：

double epsilon = 0.05;

double right_bound = 1.0 – epsilon;

for (double x = 0.5; x < right_bound; x += 0.1)

{

    std::cout << std::setprecision(17) << x << std::endl;

}

在其他编程语言（如 Python[1]、Pascal 等）中，可以使用带步长的范围。

本文提出的实现已在 VC++ CTP 2014、GNU C++ 4.9、GNU C++ 4.9.2 和 Clang 3.6 中进行了测试。

 C++ 中的现有实现和其他语言中的构造

在 Boost [2] 中，有一个名为 irange 的类模板，其定义如下：

template<class Integer>

iterator_range< range_detail::integer_iterator<Integer> >

irange(Integer first, Integer  last);


template<class Integer, class StepSize>

iterator_range< range_detail::integer_iterator_with_step<Integer, StepSize> >

irange(Integer first, Integer last, StepSize step_size);

 

它可以用于以固定步长遍历范围 [first, last)。

    std::size_t m = 5;

    for (auto x : boost::irange(0U, m)) // OK in the 32-bit code

    {

        std::cout << x << " ";

    }

std::cout << std::endl;

 

此循环将输出：

0 1 2 3 4

最后一个参数始终不包含在范围内。允许负步长。

std::vector<int> v = { 1, 2, 3, 4 };

for (auto i : boost::irange(static_cast<int>(v.size()) - 1, -1, -1))

{

        std::cout << v[i] << std::endl;

}

irange 模板允许为整数范围编写循环。它类似于 Python [1] 中的 range 函数。

这里存在一些问题。首先，循环的第一个和最后一个边界应为同一类型。以下表达式将无法编译：

boost::irange(0, m), // the first parameter is not unsigned

boost::irange(v.size() - 1, -1, -1) // v.size() is unsigned

在大多数编译器上，即使是 boost::irange(0U, m) 在 64 位代码中也会失败。应写成如下形式：

boost::irange(0ULL, m)

或者更好：

boost::irange(static_cast<std::size_t>(0), m) // will work in any code, including 32-bit and 64-bit

第二个问题是我们倾向于使用 std::size_t 的索引，并且使用无符号值进行递减范围的循环时使用 irange 不方便。如果递减范围排除第一个边界并包含最后一个边界，那就更好了。

对于浮点数，有一个 linspace 函数，定义在 Python 的 Nympy 库 [3] 中，它允许如下编写循环：

for x in np.linspace(2.0, 3.0, num=5, endpoint=True):

print(x)

此循环将输出以下值：

2.0

2.25

2.5

2.75

3.0

 

另一方面，如果 endpoint 定义为 False，则输出将是：

2.0

2.25

2.5

2.75

 

在 MATLAB [4] 中，也有一个名为 linspace 的函数，但它总是包含最后一个边界。

提议的循环构造

提议以下四种类型的循环构造。

1. step 循环

1.1. 三参数 step 循环

以下循环：

for(auto&& control_variable : step(start_value, step_count, step_width)) statement

等同于以下语句：

{
    auto control_variable = start_value;   
    auto __counter = step_count;
    auto __stepw = step_width;
    while (__counter-- != 0)
    {
        statement;
        control_variable += __stepw;
    }   
}

其中 __counter 和 __stepw 仅为说明目的而定义（这意味着它们不是显式可用的，并且实际实现可能使用不同的变量来实现相同效果）。step_count 的类型必须是整数。

示例 1

这里有一个 step 循环的示例：

for (auto&& i : step(10, 5, -2))
{
    std::cout << i << std::endl;
}

它将输出以下值：

10
8
6
4
2

示例 2

以下循环将不输出任何内容，因为 step_width 为零，循环体不会执行。

for (auto&& i : step(10, 10, 0))
{
    std::cout << i << std::endl;
}

示例 3

steps 循环不仅可以用于生成算术值：

for (auto c : step(std::string("!"), 6, std::string("*")))
{
    std::cout << c << std::endl;
}

此代码将打印：

!
!*
!**
!***
!****
!*****

这意味着 steps loop也可以用于迭代各种用户定义的 Big Numbers。

1.2. 两参数 step 循环

如果 step 的最后一个参数缺失，则假定其类型为 int，值为 1。因此，以下内容：
loop

for(auto&& control_variable : step(start_value, step_count)) statement

等同于

for(auto&& control_variable : step(start_value, step_count, 1)) statement

示例

这里有一个两参数 step 循环的示例：

for (auto&& i : step(3, 5)) 
{
    std::cout << i << std::endl;   
}

它将输出此内容：

3
4
5
6
7

1.3. 单参数 step 循环

以下循环：

for(auto control_variable : step(step_count)) statement

等同于此语句：

for(auto&& control-variable : step(0,step-count, 1)) statement

示例

这是一个单参数 step 循环的示例：

for (auto i : step(5))
{
    std::cout << i << std::endl;
}

它将输出以下值：

0
1
2
3
4

2. step_backward 循环

此循环：

for(auto control_variable : step_backward(step_count) statement

等同于以下语句：

{
     auto __counter = step_count;
     for(auto&& control_variable = step(__counter-1, __counter, -1)  statement
}

其中 __counter 仅为说明目的而定义。

示例

这是一个单参数 step 循环的示例：

for (auto i : step_backward(5))
{
    std::cout << i << std::endl;
}

它将输出以下值：

4
3
2
1
0

3. step_to 循环

3.1. 三参数 step_to 循环

此循环：

for (auto control_variable : step_to(start_value, target_value, step_width) statement

等同于以下语句：

{
    typename template CommonType<decltype(start_value),decltype(target_value)>::type __common_type;
    __common_type control_variable = start_value;
    __common_type __target = target_value;
    auto __stepw = step_width;
    if (__stepw > 0)
    {
        if (control_variable <= __target)
        {
            while (true)
            {
                statement;
                if (control_variable > __target - __stepw)
                    break;
                control_variable += __stepw;
            }
        }
    }
    else if (__stepw < 0)
    {
        if (control_variable >= __target)
        {
            while (true)
            {
                statement;
                if (control_variable < __target - __stepw)
                    break;
                control_variable += __stepw;
            }
        }
    }
}

其中 __common_type、__target 和 __stepw 仅为说明目的而定义。

CommonType<T,U>::type 类型定义如下：

• 如果 T 和 U 代表相同的类型，则使用该类型；
• 否则，使用 decltype(T()+U())。

start_value、target_value 和 step_width 的所有表达式的类型都必须是整数。target_value 的值可能不是 control_variable 的最终值。如果 __common_type 是 int 或与 int 相同或更高等级的类型（unsigned、long、unsigned long、long long、unsigned long long 等），则循环遍历该类型所有值范围的效果是依赖于实现的，这意味着你不应依赖结果并避免编写此类循环。

示例 1

这里有一个 step_to 循环的示例：

for (auto i : step_to(10, 2, -2))
{
    std::cout << i << std::endl;
}

它将输出以下值：

10
8
6
4
2

示例 2

以下循环的效果是依赖于实现的：

unsigned long long counter = 0;

for (auto i : step_to(std::numeric_limits<int>::max(), std::numeric_limits<int>::min(), -1))
{
    counter++;
}

std::cout << counter << std::endl; // implementation-dependent output

示例 3

此循环的效果已正确定义（循环计数器 i 的类型为 long long）：

unsigned long long counter = 0;
long long max1 = std::numeric_limits<int>::max();
long long min1 = std::numeric_limits<int>::min();

for (auto i : step_to(max1, min1, -1))
{
    counter++;
}

std::cout << counter << std::endl;

结果将是 (a-b+1)，在大多数实现中：

4294967296

3.2. 两参数 step_to 循环

在 step_to 中，最后一个参数可以省略。在这种情况下，假定其类型为 int，值为 1。
此循环：

for (auto control_variable : step_to(start_value, target_value) statement

产生与以下语句相同的结果：

for (auto control_variable : step_to(start_value, target_value, 1) statement

4. step_until 循环

4.1. 三参数 step_until 循环

以下循环：

for (auto control_variable : step_until(start_value, target_value, step_width) statement

等同于以下语句：

{
    typename template CommonType<decltype(start_value),decltype(target_value)>::type __common_type;
    __common_type control_variable = start_value;
    __common_type __target = target_value;
    auto __stepw = step_width;
    if (__stepw > 0)
    {
        if (control_variable < __target)
        {
            while (true)
            {
                statement;
                if (control_variable >= __target - __stepw)
                    break;
                control_variable += __stepw;
            }
        }
    }
    else if (__stepw < 0)
    {
        if (control_variable > __target)
        {
            while (true)
            {
                statement;
                if (control_variable <= __target - __stepw)
                    break;
                control_variable += __stepw;
            }
        }
    }
}

其中 __common_type、__target 和 __stepw 仅为说明目的而定义。start_value、target_value 和 step_width 的所有表达式的类型都必须是整数。target-value 的值永远不会赋值给 control_variable。

示例 1

这里有一个 step_until 循环的示例：

for (auto i : step_until(10, 2, -2))
{
    std::cout << i << std::endl;
}

它将输出以下值：

10
8
6
4

示例 2

这是另一个 step_until 循环：

unsigned long long counter = 0;

for (auto i : step_to(std::numeric_limits<int>::max(), std::numeric_limits<int>::min(), -1))
{
    counter++;
}

std::cout << counter << std::endl;

此代码将输出表达式的值：

static_cast<long long>(std::numeric_limits<int>::max())-static_cast<long long>(std::numeric_limits<int>::min())

在大多数 32 位和 64 位系统上，输出将是：

4294967295

4.2. 两参数 step_until 循环

在 step_until 中，最后一个参数可以省略。在这种情况下，假定其类型为 int，值为 1。
此循环：

for (auto control_variable : step_until(start_value, target_value) statement

产生与以下语句相同的结果：

for (auto control_variable : step_until(start_value, target_value, 1) statement

 

实现

创建用于 for-range 循环的类

在 C++11 中，有一个 for-range 循环，允许迭代容器的元素。这里有一个例子：

std::vector<unsigned> a{ 5, 6, 7, 8 };
for (auto x : a)
{
   std::cout << x << std::endl;
}

此循环等同于以下循环：

for (auto it = a.begin(), itStop = a.end(); it != itStop; ++it)
{
    auto x = *it;
   
    std::cout << x << std::endl;   
}

在 for-range 循环中，类 a 不必是容器。它可以是一个不存储值的类：它可以通过提供的迭代器生成值。

我们需要一个起始值、步数和一个步长。这些值的确切类型取决于我们想要编写的循环。在这种情况下，我们必须创建一个模板。这是一个模板的通用结构：

template<class T, class N, class S>
class steps_class
{
public:

  // types

    typedef to-be-defined iterator;

// constructor

    steps_class(T start, N step_count, S step);

// iterators

    iterator begin() const;

    iterator end() const;

// property functions

    T first_value() const;
    N size() const;
    S step_length() const;
};

我们可以这样使用这个类：

std::string str = "apples";
for (auto i : steps_class<std::size_t, std::size_t,int>(str.size()-1, str.size(), -1))
{
   std::cout << str[i] << std::endl;
}

这将打印：

s
e
l
p
p
a

引言中讨论的浮点值循环可以重写如下：

for (auto x : steps_class<double, unsigned, double>(0.5, 5, 0.1))
{
    std::cout << x << std::endl;
}

这是 steps_class 的完整定义：

template<class T, class N, class S>
class steps_class
{
public:

    class steps_iterator : public std::iterator<std::forward_iterator_tag, T>
    {
        N m_step_counter;
        T m_counter;
        S m_step;

    public:
        steps_iterator() : m_step_counter(N()) {}
        steps_iterator(N steps_count, T start, S step) :m_step_counter(steps_count), m_counter(start), m_step(step)
        {
        }

        steps_iterator& operator++()
        {
            --m_step_counter;
            m_counter += m_step;
            return *this;
        }

        steps_iterator operator++(int)
        {
            steps_iterator  it = *this;
            --m_step_counter;
            m_counter += m_step;
            return it;
        }

        const T& operator*() const
        {
            return m_counter;
        }

        const T* operator->() const
        {
            return &m_counter;
        }

        bool operator== (const steps_iterator& r) const
        {
            return m_step_counter == r.m_step_counter;
        }

        bool operator!= (const steps_iterator& r) const
        {
            return !(m_step_counter == r.m_step_counter);
        }
    };

    typedef steps_iterator iterator;

private:
    iterator m_end_iterator;
    iterator m_start_iterator;

public:
    steps_class(T start, N step_count, S step) : m_start_iterator(step_count, start, step)
    {
    }

    iterator begin() const
    {
        return m_start_iterator;
    }

    iterator end() const { return m_end_iterator; }
};

 

循环构造的实现

1. step 循环的实现

使用 steps_class 并不真正方便：它需要显式指定所有参数的类型。提供方便的函数来编写各种循环要容易得多。三参数和两参数 step 循环可以实现如下：

template<class T, class N, class S = int>
inline auto step(T a, N n, S s = 1)->steps_class<decltype(a + s), N, S>
{
    static_assert(std::is_integral<N>::value, "step: the second parameter should be of integral type");
    return steps_class<decltype(a + s), N, S>(a, n, s);
}

单参数 step 循环的实现可以如下：

template<class N>
inline steps_class<N, N, int> step(N n)
{
    static_assert(std::is_integral<N>::value, "step: parameter should be of integral type");
    return steps_class<N, N, int>(N(0), n, 1);
}

2. step_backward 循环的实现

step_backward 循环可以实现如下：

template<class N>
inline steps_class<N, N, int> step_backward(N n)
{
    static_assert(std::is_integral<N>::value, "step_backward: parameter should be of integral type");
    return steps_class<N, N, int>(n + int(-1), n, int(-1));
}

3. step_to 和 step_until 循环的实现

首先，我们必须定义 CommonType 模板定义。这里是这个模板的一个简单定义：

template<class T, class U>
class CommonType
{
    typedef typename std::remove_reference<T>::type T1;
    typedef typename std::remove_reference<U>::type U1;
 
public: 
    typedef decltype(T1() + U1()) type;
};

template<class T>
class CommonType<T,T>
{
    typedef typename std::remove_reference<T>::type T1;

public: 
    typedef T1 type;
};   

由于我们可能将变量作为参数传递给 step_to 和 step_until 循环，因此 T 和 U 的类型可能是，例如， int&、char& 而不是简单的 int 和 char。这就是为什么我们必须使用 remove_reference。

在此实现中，我们将使用 steps_class 来计算迭代次数。使用 std::size_t 和计数器类型很方便，除非其等级低于前两个参数（start_value 和 target_value）的公共类型。在这种情况下，我们可以如下开始 step_to 的定义：

template<class T, class U, class S = int,
         class StartType = typename CommonType<T, U>::type,
         class CounterType = typename CommonType<std::size_t, StartType>::type>
inline steps_class<StartType, CounterType, S> step_to(T a, U b, S s = 1)

模板参数中添加了两个额外的类型：StartType 和 CounterType。前者将是循环中生成的值的类型，后者将用于计算步数。

这些循环的完整定义将如下所示：

template<class T, class U, class S = int,
            class StartType = typename CommonType<T, U>::type,
            class CounterType = typename CommonType<std::size_t, StartType>::type>
inline steps_class<StartType, CounterType, S> step_to(T a, U b, S s = 1)
{                
    static_assert(std::is_integral<StartType>::value, "step_to requires integral parameters");       
    CounterType  n = 0;

    if (s == 0 || b != a && (b < a) != (s < 0))
    {
        n = 0;           
    }
    else
    {
        S abs_s = s > 0 ? s : -s;
        CounterType diff = b > a ? (long long)b - (long long)a : (long long)a - (long long)b;

        if (abs_s == 1)
            n = diff;
        else
            n = diff / abs_s;

        n++;           
    }
    return steps_class<StartType, CounterType, S>(a, n, s);
}

template<class T, class U, class S = int,
            class StartType = typename CommonType<T, U>::type,
            class CounterType = typename CommonType<std::size_t, StartType>::type>
inline steps_class<StartType, CounterType, S> step_until(T a, U b, S s = 1)
{       
    static_assert(std::is_integral<StartType>::value, "step_until requires integral parameters");       
    CounterType  n;

    if (b == a || s == 0 || (b < a) != (s < 0))
    {
        n = 0;
    }
    else
    {
        S abs_s = s > 0 ? s : -s;           
        CounterType diff = b > a ? (long long)b - (long long)a : (long long)a - (long long)b;

        if (abs_s == 1)
            n = diff;
        else
            n = diff / abs_s;

        CounterType finish = a + n*s;
        if (finish != b)
        {
            n++;
        }
    }
    return steps_class<StartType, CounterType, S>(a, n, s);
}

其他示例

steps 函数不仅可以用于生成算术值：

for (auto c : step(std::string("!"), 6, std::string("*")))
{
    std::cout << c << std::endl;
}

此代码将打印：

!
!*
!**
!***
!****
!*****

这意味着 steps 函数也可用于各种用户定义的 Big Numbers。

基准测试

以下循环已用于基准测试：

• T1 - 具有单参数步长的两级循环；
• T2 - 两级循环，以步长 2 遍历向量索引；
• T3 - 两级循环，以步长 5 遍历向量索引；
• T4 - 使用 7 点开放牛顿-科茨规则进行积分计算。

我在 Windows 8.1 和 Linux Mint 17 Qiana 下运行了测试。计算机不同：

• Windows 在一台拥有 8GB 内存和四核 i7-4790、3.6 GHz 处理器的计算机上运行；
• Linux 在一台拥有 6GB 内存和双核 i5-2410M、2.3 GHz 处理器的计算机上运行。

使用的编译器如下：

• VC++ 2014；
• GCC C++ 4.9.0；
• GCC C++ 4.9.2；
• Clang 3.6

对于 VC++，设置了以下优化：

对于其他编译器，使用了 -O3 选项。

在各种编译器中，结果略有不同，并且 32 位和 64 位模型之间存在一些差异。Windows 的结果如图 1 所示。

图 1. Windows 下的基准测试结果。

时间以毫秒为单位；百分比计算如下：

100*(timing_steps - timing_standard)/timing_standard

负百分比表示 steps 构造性能更好。我还用黄色标出了结果接近（相差在 1% 以内）的情况，用绿色标出了 steps 代码性能好 1% 以上的情况，用红色标出了 steps 性能差 1% 以上的情况。

Linux 的结果如图 2 所示。

图 2. Linux 下的基准测试结果

总的来说，steps 构造的结果表现出非常好的性能。

正确性测试

测试包含各种不同范围的循环。还包括了 stop_to 循环的依赖于实现的特性。总的来说，在不同的实现中观察到以下问题（这些是众所周知的问题）：

• 在 VC++ 的 32 位和 64 位代码中，常量 -2147483648 的类型为 unsigned，值为 2147483648，这与 std::numeric_limits<int>::min()（具有正确值）不同；同时 -2147483648LL 是正确的；
• 在 GCC 和 Clang 中，常量 -2147483648 在内存中占用 8 字节。

这两个问题都导致 step_to 循环在不同编译器中的行为不同。这就是我提到一些依赖于实现的问题的原因。在提供的测试中，依赖于实现的问题被归类为“可接受的错误”：它们不会产生我们想要的结果，但可以接受。我们不应该依赖依赖于实现的代码，并避免此类循环。

其他问题包括浮点计算。所提供的测试是“一对一”的比较，使用标准循环和 step 循环产生了完全相同的结果。但可以通过稍微修改这些测试，使其在激进的优化下可能产生不同的结果，尽管使用的计算看起来相同。这有几个原因。我将举出两个主要原因：

• 计算顺序可能发生变化（例如，由于舍入，浮点数的求和可能产生不同的结果）；
• Intel 浮点算术传统上使用 80 位浮点数，但在 xmm 寄存器上的计算（通常会生成更快的代码）使用 64 位数字（精度差异明显）。

参考文献

[1]. Python 3.2 内置函数.: https://docs.pythonlang.cn/3.2/library/functions.html

[2].  Boost irange: https://boost.ac.cn/doc/libs/1_55_0/libs/range/doc/html/range/reference/ranges/irange.html

[3].  NumPy linspace: https://docs.scipy.org.cn/doc/numpy/reference/generated/numpy.linspace.html

[4]. MATLAB linspace: http://www.mathworks.co.uk/help/matlab/ref/linspace.html