how can i implement my own stack iterator in c++

Question

i've been trying to implement an iterator to my stack like this :

#include <iostream>
#include <stack>
#include <deque>

template <typename T, class container=std::deque<T>>
class MutantStack : public std::stack
{
    public:
        MutantStack(){}
        ~MutantStack(){}
        MutantStack(const MutantStack &stack)
        {
            *this = stack;
        }

        typedef typename std::deque::iterator iterator;
};

but i couldn't make a begin and end iterator, how i can do it ? and another question what the c.begin() in deque iterator means, i found this exemple :

iterator begin()
{
return this->c.begin();
}

What is the actual problem you need to solve by creating your own stack? What will this `MutantStack` solve that plain `std::stack` doesn't? Right now this feels very much like an [XY problem](https://xyproblem.info/) to me. — Some programmer dude, Aug 22 '22 at 06:08
Does this answer your question? [How to correctly implement custom iterators and const\_iterators?](https://stackoverflow.com/questions/3582608/how-to-correctly-implement-custom-iterators-and-const-iterators) — starball, Aug 22 '22 at 06:08
And perhaps you might need a little more time with [a `std::stack` reference](https://en.cppreference.com/w/cpp/container/stack). — Some programmer dude, Aug 22 '22 at 06:09

score 0 · Answer 1 · answered Aug 22 '22 at 06:41

I am not sure, if you selected the correct approach.

Because, you can use a std::deque in the first place. It offers all functionality that a stack offers. And more.

So maybe better use a std::deque or a std::vector.

Additionally, deriving from standard containers is not the best idea. You may read about that here on SO.

But if you want to do that for exceptional purposes, then simply take the address of the top(). This will be the last element in the underlying container. And if you subtract the size() of the stack (corrected by 1), then you have a pointer to the beginning of the underlying container.

And then you can use the artificial iterator and subscript operator [] as expected.

Please see the following example:

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

using Number = int;
using UnderlyingContainer = std::vector<Number>;
using Stack = std::stack< Number, UnderlyingContainer>;

using StackIterator = Number *const;

int main()
{
    // Put the test data onto the stack
    Stack myStack{ UnderlyingContainer {1,2,3,4,5} };

    if (not myStack.empty()) {

        // Get "iterators"
        StackIterator end = &myStack.top() + 1;
        StackIterator begin = end - myStack.size();

        Number *const & stk = begin;

        for (size_t i{}; i < myStack.size(); ++i)
            stk[i] = stk[i] + 10;

        for (size_t i{}; i < myStack.size(); ++i)
            std::cout << stk[i] << '\n';

        std::transform(begin, end, begin, [](const Number n) {return n - 10; });
        std::copy(begin, end, std::ostream_iterator<Number>(std::cout, "\n"));
    }
}

So, it looks like we found what you want to have, but in reality, we simply work on the underlying container.

score 0 · Answer 2 · edited Jan 27 '23 at 19:24

After some research I found this solution:

template <typename T, class container=std::deque<T>>
class MutantStack : public std::stack<T>
{
    public:
        MutantStack(){}
        ~MutantStack(){}
        MutantStack(const MutantStack &stack)
        {
            *this = stack;
        }
        typedef typename container::iterator iterator;
        iterator begin()
        {
            return this->c.begin();
        }
        iterator end()
        {
            return this->c.end();
        }
};

The stack object inherits from the deque type like this :

template <class Type, class Container = deque<Type> > class stack;

but it exposes only a few methods such as: pop push empty swap and emplace. Therefore it has also the deque iterator. So I used it as above. The c in c.begin() and c.end() is a container_type defined in the stack class:

public:
    typedef _Container                               container_type;
protected:
    container_type c;

This means the c is the container and when typing c.begin() we get the first value in Mutantstack; it's like saying value[0] on an array. Now my MutantStack class inherit from the std::stack class that's itself inherits from the std::deque class:

     `MutantStack -> std::stack -> std::deque`

how can i implement my own stack iterator in c++

2 Answers2