2

假设我得到两个无符号整数：

size_t A, B;

它们加载了一些随机数，A 可能大于、等于或小于 B。我想从 A 循环到 B。但是，比较和增量都取决于哪个更大。

for (size_t i = A; i <= B; ++i) //A <= B
for (size_t i = A; i >= B; --i) //A >= B

显而易见的蛮力解决方案是将这些嵌入到 if 语句中：

if (A <= B)
{
 for (size_t i = A; i <= B; ++i) ...
}
else
{
 for (size_t i = A; i >= B; --i) ...
}

请注意，我必须从A循环到B，因此我不能有两个中间整数并将 A 和 B 扔到正确的插槽中，然后进行相同的比较和增量。在“A 更大”的情况下，我必须递减，反之必须递增。

我可能会有许多需要相同设置的嵌套循环，这意味着每个 if/else 都会有一个函数调用，我必须通过它传递大量变量，或者另一个 if/else 与另一个 if/else 等。

在不牺牲太多速度的情况下，是否有任何棘手的捷径可以避免这种情况？函数指针和紧密的、经常重复的循环中的东西对我来说听起来非常痛苦。有一些疯狂的模板解决方案吗？

4

4 回答 4

7

我的错误，最初误解了这个问题。

要从 to 创建一个包容性循环A，B您遇到了一个棘手的情况。你需要循环一个过去的B。所以你在循环之前计算出那个值。我在for循环中使用了逗号运算符，但为了清楚起见，您始终可以将其放在外面。

int direction = (A < B) ? 1 : -1;
for( size_t i = A, iEnd = B+direction; i != iEnd; i += direction ) {
    ...
}

如果您不介意修改Aand B，您可以这样做（A用作循环变量）：

for( B+=direction, A != B; A += direction ) {

}

我玩了一会……不知道函数指针的内联规则是什么，或者这是否更快，但无论如何这是一个练习。=)

inline const size_t up( size_t& val ) { return val++; }
inline const size_t down( size_t& val ) { return val--; }

typedef const size_t (*FnIncDec)( size_t& );

inline FnIncDec up_or_down( size_t A, size_t B )
{
    return (A <= B) ? up : down;
}

int main( void )
{
    size_t A = 4, B = 1;
    FnIncDec next = up_or_down( A, B );

    for( next(B); A != B; next(A) ) {
        std::cout << A << endl;
    }

    return 0;
}

对此作出回应：

这不适用于 A = 0, B = UINT_MAX 的情况（反之亦然）

那是对的。问题是由于溢出，初始值i和变得相同。iEnd为了解决这个问题，您将改为使用do->while循环。这删除了初始测试，这是多余的，因为您将始终至少执行一次循环体......通过删除第一个测试，您第一次遍历终止条件。

size_t i = A;
size_t iEnd = B+direction;

do {
    // ...
    i += direction;
} while( i != iEnd );
于 2012-12-13T21:40:24.557 回答
5 
size_t const delta = size_t(A < B? 1 : -1);
size_t i = A;
for( ;; )
{
    // blah

    if( i == B ) { break; }
    i += delta;
}
于 2012-12-13T22:10:25.920 回答
2

你打算如何处理迭代值？

如果这将是数组中的某个索引，您应该使用相关iterator或reverse_iterator类，并围绕这些实现您的算法。您的代码将更加健壮，并且更易于维护或发展。此外，标准库中的很多工具都是使用这些接口构建的。

实际上，即使你不这样做，你也可以实现一个返回自己索引的迭代器类。

您还可以使用一点元编程魔法来定义您的迭代器将如何根据Aand的顺序运行B。

在继续之前，请考虑这仅适用于和的常数值。AB

template <int A,int B>
struct ordered {
    static const bool value = A > B ? false: true;
};

template <bool B>
int pre_incr(int &v){
    return ++v;
}

template <>
int pre_incr<false>(int &v){
    return --v;
}

template <int A, int B>
class const_int_iterator : public iterator<input_iterator_tag, const int>
{
    int p;
  public:
    typedef const_int_iterator<A,B> self_type;
    const_int_iterator() : p(A) {}
    const_int_iterator(int s) : p(s) {}
    const_int_iterator(const self_type& mit) : p(mit.p) {}
    self_type& operator++() {pre_incr< ordered<A,B>::value >(p);return *this;}
    self_type operator++(int) {self_type tmp(*this); operator++(); return tmp;}
    bool operator==(const self_type& rhs) {return p==rhs.p;}
    bool operator!=(const self_type& rhs) {return p!=rhs.p;}
    const int& operator*() {return p;}
};


template <int A, int B> 
class iterator_factory {    
  public:
    typedef const_int_iterator<A,B> iterator_type;
    static iterator_type begin(){
        return iterator_type();
    }
    static iterator_type end(){
        return iterator_type(B);
    }
};

在上面的代码中，我定义了一个iterator从 A 到 B 的值的准系统类。有一个简单的元编程测试来确定 A 和 B 是否按升序排列，并选择正确的运算符 ( ++or --) 来遍历这些值。

最后，我还定义了一个简单的工厂类来保存begin和end迭代方法，使用这个类可以让你的依赖类型值 A 和 B 只有一个声明点（我的意思是你只需要使用 A 和 B 一次这个容器，以及从那里生成的迭代器将取决于这些相同的 A 和 B，从而在一定程度上简化了代码）。

这里我提供一个简单的测试程序，输出值从 20 到 11。

#define A 20
#define B 10

typedef iterator_factory<A,B> factory;

int main(){

   auto it = factory::begin();

   for (;it != factory::end();it++)
      cout << "iterator is : " << *it << endl;

}

不过，使用标准库可能会有更好的方法来做到这一点。

使用Oand UINT_MAXfor Aand的问题B被提出来了。我认为应该可以通过使用这些特定值重载模板来处理这些情况（留给读者作为练习）。

于 2012-12-13T23:44:29.053 回答
0 
size_t A, B;

if (A > B) swap(A,B);  // Assuming A <= B, if not, make B to be A

for (size_t i = A; A <= B; ++A) ...
于 2012-12-13T22:09:41.517 回答