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

Question

我试图通过移植Sedgewick和Wayne的第四版算法中的主要示例来提高我的C++技能.我根据他们的Java 示例编写了一个通用的堆栈实现.

我的堆栈工作正常,但我想提高性能并试图编写反向迭代器.

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 << ',';    
    }
}

实例

请注意,这使用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 << ',';    
    }

实例(适用于gcc 5.1或clang 3.5)

或者,您可以使用Boost.Range库并简单地执行(将使用任何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 << ',';    
    }
}

实例

请注意,您必须小心将临时变量传递给此类适配器,我和Boost适配器在传递例如raw时不起作用,如std::vector<int>{3,2,1}评论中@Pixelchemist所指出的那样.