如何最好地控制迭代方向？

Question

我有一个包含大量昂贵的对象的容器，复制起来很费劲。我有时需要按照正常顺序遍历整个容器，有时需要反向遍历。一旦确定了遍历方向，就不需要在中途更改，即不需要随机访问。

我希望实现这样的模式：

#include <iostream>
#include <vector>
using namespace std;
int main( int argc, char** )
{
    // pretend this is a vector of expensive objects
    vector<int> foo = {1,2,3,4,5};

    // calculate forward or backward iteration direction
    bool backwards = (argc > 1);

    if( backwards )
        // prepare backward iteration, but don't copy objects
    else
        // prepare forward iteration, but don't copy objects

    for( auto& i : /* either forward or backward */ )
    {
        // my loop body
        cout << i;
    }

    return 0;
}

这是一个C++11程序，但我不认为这真的能在这里帮助我。我只是没有看到最好的方法来做这件事。谢谢你的帮助。

- srking

Answer 1

C++标准容器有一种称为“反向迭代器”的东西。使用std::vector::rbegin()和std::vector::rend()可以获得一个迭代器，它可以逆向遍历向量。在C++03中，这很容易实现：

#include <iostream> 
#include <vector>  

// Use const reference to pass expensive-to-copy types
void loop_body(const int& i)
{
    std::cout << i;
}

int main( int argc, char** ) 
{ 
    // pretend this is a vector of expensive objects 
    std::vector<int> foo = {1,2,3,4,5}; 

    // calculate forward or backward iteration direction 
    bool backwards = (argc > 1); 

    if( backwards ) { 
        std::for_each(foo.rbegin(), foo.rend(), &loop_body);
    } else { 
        std::for_each(foo.begin(), foo.end(), &loop_body);
    } 
    return 0; 
} 

你可以使用C++11中的lambda表达式来实现这一点：

#include <iostream> 
#include <vector> 

int main( int argc, char** ) 
{ 
    // pretend this is a vector of expensive objects 
    std::vector<int> foo = {1,2,3,4,5}; 

    // calculate forward or backward iteration direction 
    bool backwards = (argc > 1); 

    // Use const reference to pass expensive-to-copy types
    auto loop_body = [](const int& i)
    {
        std::cout << i;
    };

    if( backwards ) { 
        std::for_each(foo.rbegin(), foo.rend(), loop_body);
    } else { 
        std::for_each(foo.begin(), foo.end(), loop_body);
    } 
    return 0; 
}

- In silico

---

谢谢。从所有这些高质量的回答中选择答案非常困难。我选择了你的答案，因为它与我的示例代码非常接近，并且还包含了将循环体分解的关键建议。 - srking

Answer 2

为什么不将您的算法放入模板函数中？这样使用begin/end或rbegin/rend进行调用就变得非常简单。

template <class Iterator>
void do_stuff(Iterator first, Iterator last)
{
    // Your loop code here.
}

或者您可以使用lambda表达式（因为它是C++11中的特性）以及std::for_each函数，方法如下：

auto loop_body = [&](int &i) { std::cout << i << std::endl; } ;

if (backward)
  std::for_each(v.rbegin(), v.rend(), loop_body);
else
  std::for_each(v.begin(), v.end(), loop_body);

- Mark B

---

不是最好的，因为很可能您可以使用标准库算法。然后，您的函数只需要描述对单个元素执行的操作，而不是整个序列。 - jalf

@jalf：或者do_stuff可以基于标准库算法来实现。我觉得这是个抉择。 - ildjarn

@Mark：我编辑了答案，加入了lambda解决方案。希望你没意见。 - Nawaz

@jalf：我的意思是，这个想法是最好的。正如你所看到的，我已经编辑了答案，添加了 lambda 和 std::for_each。 - Nawaz

我曾经认为循环需要某种状态，这种状态不容易在单个函数对象中表示，但是lambda解决方案也很好。 - Mark B

好的，非常棒的解决方案。 :) - jalf

Answer 3

标准库容器具有正常和反向迭代器，这解决了问题的一大部分。

不幸的是，它们是不同的类型，因此您无法创建一个可以容纳正常或反向迭代器的单个变量。

所以我会将您的循环包装在一个单独的函数中，并将其模板化以适用于两者：

template <typename It>
void myloop(It first, It last) {
    for(It cur = first; cur != last; ++cur)
    {
        // my loop body
        cout << *cur;
    }
}

然后像这样调用它：

if( backwards )
    myloop(foo.rbegin(), foo.rend());
else
    myloop(foo.begin(), foo.end());

当然，你可以使用标准库算法之一来代替循环：

if( backwards )
    std::for_each(foo.rbegin(), foo.rend(), [](int item){  cout << item;});
else
    std::for_each(foo.begin(), foo.end(), [](int item){  cout << item;});

（注意，我在这里使用for_each只是为了简单起见。很可能，std::transform或std::copy更适合描述您想要做的事情。

我还使用了lambda表达式而不是myloop函数。你可以选择任何一种方式，但是lambda更短，而且在我看来更容易阅读。

）

- jalf

Answer 4

std::vector<int>::iterator begin = foo.begin();
std::vector<int>::iterator last = foo.end();
if (last != begin)
{
    --last;
    int direction = 1;
    if( backwards )
    {
        std::swap(begin, last);
        direction = -1;
    }
    for( auto& i = begin;  ; i += direction)
    {
        // do stuff
        if (i == last)
            break;
    }
}

- Mark Ransom

---

谢谢Mark。这个答案紧密遵循示例代码的精神，并指出了使用单个for循环实例所需的旋转。 - srking

Answer 5

即使这是一个老问题，我最近也遇到了同样的问题，并用以下方法解决：

将以下内容放在某个地方：

namespace mani {

    // an extension to std::for_each where you can choose the direction:
    template <class InputIterator, class Function> Function for_each_reverse(bool reverse, const InputIterator& first, const InputIterator& last, Function fn)
    {
        if (reverse) {
            return std::for_each(std::reverse_iterator<InputIterator>(last), std::reverse_iterator<InputIterator>(first), fn);
        }
        return std::for_each(first, last, fn);
    }

}

"...然后你可以像这样简单地使用它：

"

auto start = ...
auto end = ...
bool reverse = ...
mani::for_each_reverse(reverse, start, end, [&](const MyItem& item) {
    ...
});

如果reverse为假，它将按正常顺序遍历项目。如果reverse为真，则会反向迭代项目。

- Mani

Answer 6

你需要做的是创建自己的迭代器包装器。我可以想到三种方法：

• 一种像两个迭代器类型的union一样的迭代器，它有两个不同类型的迭代器成员和一个选择哪个活动的标志。

• 包含单个双向迭代器和一个指示正向或反向操作的标志。

• 某种具有虚函数的通用迭代器（效率低下，但编写可能很简单）。

- user1084944

---

话虽如此，“编写将操作迭代器范围的代码作为单独函数”的方法可能比你尝试采取的方法更好。 - user1084944