c++ - 在自定义容器类上反转基于范围的 for 循环

Question

我试图通过移植 Sedgewick 和 Wayne 编写的 Algorithms, 4th Edition 中的主要示例来提高我的 C++ 技能。我写了一个基于他们的 Java 的通用堆栈实现 example .

我的堆栈工作正常，但我想提高性能，但在尝试编写反向迭代器时遇到了困难。

template<typename T> class ResizingArrayStack {
public:
    T* begin() { return &array_ptr[0]; }
    T* end() { return &array_ptr[N]; }

...

// Here we're iterating forward through the array, with an unused variable `i`.
// It would be nice performance-wise to iterate in reverse without calling pop(), and without triggering a resize.
for ( auto& i : lifo_stack ) {
    cout << "Current loop iteration has i = " << i << endl;
}
// // Alternatively, pop from the stack N times.
// cout << "Popped an item from the stack: " << lifo_stack.pop() << endl;

我尝试切换上面的begin和end成员函数，但发现扩展的for循环总是随着++__begin递增，即使 __end 位于较低的内存地址。我们怎样才能让 i 反向循环(相对于堆栈的 LIFO)？

如果有严重错误或看起来过时的方面，请随时对我的代码风格发表评论。我想与优秀的“现代”C++ 保持一致。

Answer 1

如果你想使用带有反向迭代器的 range-for 循环，你可以使用包装类 Reverse存储范围并返回 reverse_iterator s对应begin和 end

#include <iostream>
#include <iterator>
#include <vector>

template<class Rng>
class Reverse
{
    Rng const& rng;    
public:    
    Reverse(Rng const& r) noexcept
    : 
        rng(r)
    {}

    auto begin() const noexcept { using std::end; return std::make_reverse_iterator(end(rng)); }
    auto end()   const noexcept { using std::begin; return std::make_reverse_iterator(begin(rng)); }
};

int main()
{
    std::vector<int> my_stack;
    my_stack.push_back(1);
    my_stack.push_back(2);
    my_stack.push_back(3);

    // prints 3,2,1
    for (auto const& elem : Reverse(my_stack)) {
        std::cout << elem << ',';    
    }
}

Live Example

请注意，这使用 C++1z 模板推导，仅受 g++ 7.0 SVN 和 clang 5.0 SVN 支持。对于早期的编译器，您可以添加一个辅助函数

    template<class Rng>
    auto MakeReverse(Rng const& rng) { return Reverse<Rng>(rng); }

    for (auto const& elem : MakeReverse(my_stack)) {
        std::cout << elem << ',';    
    }

Live Example (适用于 gcc 5.1 或 clang 3.5)

或者，您可以使用 Boost.Range library并简单地做(将适用于任何 C++11 编译器)

#include <iostream>
#include <vector>
#include <boost/range/adaptor/reversed.hpp>

int main()
{
    std::vector<int> my_stack;
    my_stack.push_back(1);
    my_stack.push_back(2);
    my_stack.push_back(3);

    for (auto const& elem : boost::adaptors::reverse(my_stack)) {
        std::cout << elem << ',';    
    }
}

Live Example

请注意，在将临时变量传递给此类适配器时必须小心，我的适配器和 Boost 适配器在传递例如原始 std::vector<int>{3,2,1} ，正如@Pixelchemist 在评论中指出的那样。