2

我正在尝试通过移植Sedgewick 和 Wayne的Algorithms, 4th Edition中的主要示例来提高我的 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;

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

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

4

6 回答 6

6

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

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

现场示例

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

于 2017-02-14T08:52:35.700 回答
1

在此处查看 TemplateRex 的出色回答。我能够在没有包装类的情况下解决问题,所以我会尝试回答我自己的问题。

这是我在http://en.cppreference.com上找到的关于实现迭代器的最有用的示例,您可以在与问题相同的 GitHub链接中找到我更新的 ResizingArrayStack 代码。

template<typename T> class ResizingArrayStack {
public:

    //----- Begin reversed iteration section -----//
    // Please see the example here, (http://en.cppreference.com/w/cpp/iterator/iterator).
    // Member typedefs inherit from std::iterator.
    class stackIterator: public std::iterator<
                        std::input_iterator_tag,   // iterator_category
                        T,                         // value_type
                        T,                         // difference_type
                        const T*,                  // pointer
                        T                          // reference
                        >{
        int index = 0;
        T* it_ptr = nullptr;
    public:
        // Prefix ++, equal, unequal, and dereference operators are the minimum required for range based for-loops.
        stackIterator(int _index = 0, T* _it_ptr = nullptr) { index = _index; it_ptr = _it_ptr; }
        // Here is where we reverse the sequence.
        stackIterator& operator++() { --index; return *this; }
        bool operator==(stackIterator other) { return index == other.index; }
        bool operator!=(stackIterator other) { return !( *this == other ); }
        T operator*() { return it_ptr[index-1]; }
    };

    stackIterator begin() { return stackIterator(N, array_ptr); }
    stackIterator end() {
        N = 0;  // 'Empty' the array.
        max_size = 1;  // Don't waste time calling resize() now. 
        return stackIterator(0, array_ptr);
    }
    //----- End reversed iteration section -----//

private:
    // Allocate space for a traditional array on the heap.
    T* array_ptr = new T[1];
    // Keep track of the space allocated for the array, max_size * sizeof(T).
    int max_size = 1;
    // Keep track of the current number of items on the stack.
    int N = 0;

默认情况下,调用基于范围的 for 循环以相反(或 LIFO)顺序迭代的代码。

// It's nice performance-wise to iterate in reverse without calling pop() or triggering a resize.
for ( auto i : lifo_stack) {
    cout << "Current loop iteration has i = " << i << endl;
}
于 2017-02-14T23:10:38.963 回答
1

这里是你的问题的划痕。不要将其视为工作代码。使用它来了解如何实现反向迭代器(仅一种可能的方式)。

template<typename T> class ResizingArrayStack {
public: 
    class reverse_iterator
    {       
        ResizingArrayStack & _storage;
        int _pointer;

    public:
        inline reverse_iterator(ResizingArrayStack & storage,
                                int pointer)
            : _storage(storage)
            , _pointer(pointer)
        {}

        inline reverse_iterator & operator++() // prefix
        {
            --_pointer;
            return *this;
        }

        inline reverse_iterator operator++() // postfix
        {
            reverse_iterator tmp(*this);
            --_pointer;
            return tmp;
        }

        inline T & operator*()
        {
            return _storage.getByIndex(_pointer);
        }

        // TODO: == != etc
    };      

    reverse_iterator rbegin() { return reverse_iterator(*this, N - 1); }
    reverse_iterator rend() { return reverse_iterator(*this, -1); }
    // ...  //
};
于 2017-02-14T08:28:22.587 回答
1

此解决方案不会引入不必要的副本,也不会像某些评论所建议的那样显示不正确的转发。说明如下。

您可以使用一些具有实际返回反向迭代器的开始和结束函数的包装器。

template<class T>
struct revert_wrapper
{
    T o;
    revert_wrapper(T&& i) : o(std::forward<T>(i)) {}
};

template<class T>
auto begin(revert_wrapper<T>& r)
{
    using std::end;
    return std::make_reverse_iterator(end(r.o));
}

template<class T>
auto end(revert_wrapper<T>& r)
{
    using std::begin;
    return std::make_reverse_iterator(begin(r.o));
}

template<class T>
auto begin(revert_wrapper<T> const& r) 
{ 
    using std::end;
    return std::make_reverse_iterator(end(r.o));
}

template<class T>
auto end(revert_wrapper<T> const& r)
{
    using std::begin;
    return std::make_reverse_iterator(begin(r.o));
}

template<class T>
auto reverse(T&& ob)
{
    return revert_wrapper<T>{ std::forward<T>(ob) };
}

像这样使用:

std::vector<int> v{1, 2, 3, 4};
for (auto i : reverse(v))
{
    std::cout << i << "\n";
}

或者在你的情况下

for ( auto& i : reverse(lifo_stack) ) {
    cout << "Current loop iteration has i = " << i << endl;
    cout << "Popped an item from the stack: " << lifo_stack.pop() << endl;
}

由于转发不是一个简单的话题,并且存在误解,我将进一步解释一些细节。我将使用std::vector<int>“待反转”类型作为示例T

1.功能模板reverse

1.1 传递左值std::vector<int>

std::vector<int> v{1, 2, 3, 4};
auto&& x = reverse(v);

在这种情况下,编译器创建的实例reverse如下所示:

template<>
auto reverse<std::vector<int>&>(std::vector<int>& ob)
{
    return revert_wrapper<std::vector<int>&>{ std::forward<std::vector<int>&>(ob) };
}

我们在这里看到两件事:

  • Tof revert_wrapperwill be ,因此std::vector<int>&不涉及副本。
  • 我们将左值作为左值转发给revert_wrapper

1.2 传递右值std::vector<int>

std::vector<int> foo();
auto&& x = reverse(foo());

我们再看一下函数模板的实例化:

template<>
auto reverse<std::vector<int>>(std::vector<int>&& ob)
{
    return revert_wrapper<std::vector<int>>{ std::forward<std::vector<int>>(ob) };
}

并且可以再次注意两件事:

  • Trevert_wrapperstd::vector<int>,因此复制向量,防止右值在任何基于范围的循环可以运行之前超出范围
  • 一个右值std::vector<int>&&将被转发到的构造函数revert_wrapper

 

2.类模板revert_wrapper及其构造函数

2.1在左值的情况下revert_wrapper创建者reversestd::vector<int>&

template<>
struct revert_wrapper<std::vector<int>&>
{
    std::vector<int>& o;
    revert_wrapper(std::vector<int>& i) : 
        o(std::forward<std::vector<int>&>(i)) {}
};

如上所述:当我们存储参考时,不涉及副本。也似乎很熟悉,实际上它与上面的forward相同reverse:我们转发一个左值作为左值引用。

2.2在右值的情况下revert_wrapper创建者reversestd::vector<int>&&

template<>
struct revert_wrapper<std::vector<int>>
{
    std::vector<int> o;
    revert_wrapper(std::vector<int>&& i) : 
        o(std::forward<std::vector<int>>(i)) {}
};

这次我们将对象按值存储以防止悬空引用。转发也很好:我们将右值引用转发reverserevert_wrapper构造函数,然后我们将它转​​发给std::vector构造函数。我们可以static_cast<T&&>(i)以相同的方式使用,但我们不是(std::)mov(e)从左值 ing,我们正在转发:

  • 左值作为左值和
  • 右值作为右值。

我们还可以在这里看到另一件事:revert_wrapper按值存储的实例的唯一可用构造函数采用右值。因此,我们不能(轻易地)欺骗这个类来制作不必要的副本。

请注意,在构造函数的初始化程序中std::forward替换为实际上是错误的。std::moveorevert_wrapper

于 2017-02-14T08:34:14.990 回答
1

一旦你有了正常运行的(常规)迭代器,就可以使用标准库帮助类模板实现反向迭代器std::reverse_iterator

#include <iterator>

class XX { 

    // your code

    typedef std::reverse_iterator<iterator> reverse_iterator;

    reverse_iterator rbegin() { return reverse_iterator{end()}; }
    reverse_iterator rend() { return reverse_iterator{begin()}; }
于 2017-02-14T08:35:43.050 回答
1

查看您的完整代码lifo_stack.pop()会使您的迭代器无效,因此它不能在ranged for中使用。你有未定义的行为

此外,将范围用于堆栈没有多大意义。如果您可以迭代其元素,那么它现在就不是堆栈了,不是吗?堆栈具有只能访问最近插入的元素的属性。


根据您的评论:

考虑一下您缓慢而单独地添加项目,但希望尽快将它们从堆栈中转储的情况。我不希望在那时触发 pop() 的复制和调整数组大小的开销。

我仍然认为 ranged-for 对堆栈没有意义。

以下是我认为您的问题已解决的方法:

lifo_stack.disable_resizing(); // prevents resizing 
while (!lifo_stack.is_empty()
{
    lifo_stack.pop(); // maybe use the poped element
}
lifo_stack.enable_resizing(); // re-enables resizing and triggers a resize

如果您不需要弹出的元素而只想清空堆栈,则有一种更快的方法(基于您的类实现):

// empties the stack
void clear()
{
   delete[] array_ptr;
   array_ptr = new T[1];;
   max_size = 1;
   N = 0;
}

最后一个决赛虽然如果你想使用现代 C++ 然后使用unique_ptr而不是手动newdelete. 它更容易,但最重要的是更安全。并阅读 0/3/5 规则。

于 2017-02-14T08:37:22.543 回答