How can a stack be a range?

user_17890874 0
Viewed 111

Here is another question. But my question is not same as it. I want a stack can be handled like a one pass range, not to handle it like its' underlying container. The stack in my question only support pop and push , and once you read one element from the stack, it will be removed.

I have a stack that only support pop and push, here is an example. I can handle the elements in the stack one by one, just like a range. So I want it to be a range (support std::ranges::range). How can I do it elegantly?

#include <memory>
#include <iostream>
#include <stack>

template <typename T>
struct my_stack : private std::stack<T> {
    using base = std::stack<T>;
    using base::push;

    auto pop() {
        auto ret = std::move(base::top());
        base::pop();
        return std::move(ret);
    }

    bool empty() {
        return base::size() == 0;
    }
};

int main() {
    my_stack<int> s;
    s.push(1);
    s.push(3);
    s.push(5);
    s.push(7);

    while(!s.empty()) {
        std::cout << s.pop() << std::endl;
    }
}

Here is a try, it works but I don't like it much.

#include <memory>
#include <iostream>
#include <stack>
#include <optional>

template <typename T>
struct my_stack : private std::stack<T> {
    using base = std::stack<T>;
    using base::push;

    auto pop() {
        auto ret = std::move(base::top());
        base::pop();
        return std::move(ret);
    }

    bool empty() {
        return base::size() == 0;
    }

    std::optional<T> optional_pop() {
        if(empty()) return {};
        return std::move(pop());
    }

    struct iterator {
        std::optional<T> _op_val;
        my_stack *_p_stack;

        T operator*() {
            return std::move(_op_val.value());
        }

        iterator& operator++() {
            _op_val = _p_stack->optional_pop();
            return *this;
        }

        auto operator<=>(const iterator&) const = default;
    };

    iterator end() {
        return iterator{{}, this};
    }

    iterator begin() {
        return iterator{optional_pop(), this};
    }
};

int main() {
    my_stack<int> s;
    
    for(auto val : s) {
        std::cout << val << std::endl;
    }
    s.push(1);
    s.push(3);
    s.push(5);
    s.push(7);

    for(auto val : s) {
        std::cout << val << std::endl;
    }
}
c++
2 Answers

Implement your own stack_iterator (based on basic_istream_view​::​iterator), e.g.

#include <iterator>

template<class Stack>
class stack_iterator {
  Stack* s_;
public:
  using iterator_concept = std::input_iterator_tag;
  using value_type       = typename Stack::value_type;
  using difference_type  = ptrdiff_t;

  explicit stack_iterator(Stack& s) : s_(std::addressof(s)) { }
  stack_iterator(stack_iterator&&) = default;
  stack_iterator& operator=(stack_iterator&&) = default;
  stack_iterator(const stack_iterator&) = delete;
  stack_iterator& operator=(const stack_iterator&) = delete;

  decltype(auto) operator*() const { return s_->top(); }
  stack_iterator& operator++() { s_->pop(); return *this; }
  void operator++(int) { ++*this; }
  bool operator==(std::default_sentinel_t) const {
    return s_->empty();
  }
};

Then you can use it like

std::stack<int> s;
std::ranges::copy(
  std::ranges::subrange(stack_iterator(s), std::default_sentinel),
  std::ostream_iterator<int>(std::cout , " "));

Demo

user_116387180

Yes, you can. You will have to implement an input iterator for your type:

#include <stack>
#include <iterator>
#include <vector>
#include <algorithm>

template<class T> struct InputIterator;

template<class T> struct Stack : std::stack<T, std::vector<T>> {
  [[nodiscard]] InputIterator<T> begin() noexcept;
  [[nodiscard]] auto end() const noexcept { return nullptr; }
};

template<class T> struct InputIterator {
private:
  Stack<T> *data_;

public:
  explicit InputIterator(Stack<T> *stack) : data_{stack} {}

  InputIterator &operator++() noexcept {
    data_->pop();
    return *this;
  }

  [[nodiscard]] auto operator++(int) noexcept {
    struct Proxy {
      T i;
      [[nodiscard]] auto& operator*() const noexcept {
        return i;
      }
    };

    Proxy res{std::move(**this)};
    ++*this;
    return res;
  }

  [[nodiscard]] T &operator*() const noexcept { return data_->top(); }
  [[nodiscard]] Stack<T> const *operator->() const noexcept { return data_; }

  [[nodiscard]] bool operator==(InputIterator const &other) const noexcept {
    return data_ == other.data_;
  }

  [[nodiscard]] bool operator==(std::nullptr_t) const noexcept {
    return data_->empty();
  }
};

template<class T> InputIterator<T> Stack<T>::begin() noexcept {
  return InputIterator{this};
}

namespace std {
template<class T> struct iterator_traits<InputIterator < T>> {
  using difference_type = ptrdiff_t;
  using value_type = T;
  using pointer = T *;
  using reference = T &;
  using iterator_category = std::input_iterator_tag;
};
}

template<class T> auto begin(std::stack<T> &s) {
  return InputIterator<T>{&s};
}

int main() {
  Stack<int> s;
  s.push(1);
  s.push(2);
  s.push(3);

  std::vector<int> vec;
  std::ranges::copy(s, std::back_inserter(vec));
  // v -> 3, 2, 1
}
user_101473990
Related