stack using vectors

[funprogrammer]

Is it wrong to use vectors to build stack? I looked online and looks like most solutions have used list or user defined list structure. Is there any issue with vectors I am missing here?

[Yanson]

why not use a stack?
http://www.cplusplus.com/reference/stack/stack/?kw=stack

[funprogrammer]

Yes, I will definitely use library functions all the time. In this particular case, the problem was to create a stack using basic data structures.

[JLBorges]

> Is it wrong to use vectors to build stack?

No. It is typically the best option when the items in the stack are either moveable or inexpensively-copyable. The default that the standard provides is std::deque<T>; so I tend to do something like this:

namespace stx
{
    template < typename T, typename A = std::allocator<T>, template <typename,typename> class CNTR = std::vector >
    using stack = std::stack< T, CNTR<T,A> > ;
}

> most solutions have used list or user defined list structure.

Those are truly terrible implementations.

There is a quality of implementation issue; so some measurements are warranted:

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <string>
#include <ctime>
#include <iomanip>

namespace stx
{
    template < typename T, typename A = std::allocator<T>, template <typename,typename> class CNTR = std::vector >
    using stack = std::stack< T, CNTR<T,A> > ;
    
    template < typename T, typename A = std::allocator<T> >
    using terrible_stack = std::stack< T, std::list<T,A> > ;
}

template < typename INT_STACK > long long time_it()
{
    constexpr std::size_t N = 8'000'000 ;

    const auto start = std::clock() ;
    {
        INT_STACK stack ;
        int i = 0 ;
        while( stack.size() < N ) stack.push(++i) ;
        while( stack.size() > N/8 ) stack.pop() ;
        while( stack.size() < N ) stack.push(++i) ;
        while( stack.size() > N/4 ) stack.pop() ;
        while( stack.size() < N ) stack.push(++i) ;
        while( stack.size() > N/2 ) stack.pop() ;
        while( stack.size() < N ) stack.push(++i) ;
    }
    const auto end = std::clock() ;

    return (end-start) * 1000.0 / CLOCKS_PER_SEC ;
}

template < typename INT_STACK > long long time_it_monotonic()
{
    constexpr std::size_t N = 16'000'000 ;

    const auto start = std::clock() ;
    {
        INT_STACK stack ;
        int i = 0 ;
        while( stack.size() < N ) stack.push(++i) ;
        while( !stack.empty() ) stack.pop() ;
    }
    const auto end = std::clock() ;

    return (end-start) * 1000.0 / CLOCKS_PER_SEC ;
}

int main()
{
    std::cout << "typical usage:\n-----------------------\n" ;
    std::cout << std::setw(15) << "stack(deque)" << std::setw(5) << time_it< std::stack<int> >() << " millisecs\n" ;
    std::cout << std::setw(15) << "stack(vector)" << std::setw(5) << time_it< stx::stack<int> >() << " millisecs\n" ;
    std::cout << std::setw(15) << "stack(list)" << std::setw(5) << time_it< stx::terrible_stack<int> >() << " millisecs\n" ;
    
    std::cout << "\nmonotonic usage:\n-----------------------\n" ;
    std::cout << std::setw(15) << "stack(deque)" << std::setw(5) << time_it_monotonic< std::stack<int> >() << " millisecs\n" ;
    std::cout << std::setw(15) << "stack(vector)" << std::setw(5) << time_it_monotonic< stx::stack<int> >() << " millisecs\n" ;
    std::cout << std::setw(15) << "stack(list)" << std::setw(5) << time_it_monotonic< stx::terrible_stack<int> >() << " millisecs\n" ;
}

coliru, LLVM and GNU:

clang++ -std=c++14 -stdlib=libc++ -Wall -Wextra -pedantic-errors -O3 main.cpp && ./a.out
echo ============================================
g++ -std=c++14 -Wall -Wextra -pedantic-errors -O3 main.cpp && ./a.out
typical usage:
-----------------------
stack(deque) 420 millisecs
stack(vector) 220 millisecs
stack(list) 1800 millisecs

monotonic usage:
-----------------------
stack(deque) 380 millisecs
stack(vector) 320 millisecs
stack(list) 1840 millisecs
============================================
typical usage:
-----------------------
stack(deque) 370 millisecs
stack(vector) 240 millisecs
stack(list) 1960 millisecs

monotonic usage:
-----------------------
stack(deque) 500 millisecs
stack(vector) 320 millisecs
stack(list) 1930 millisecs

http://coliru.stacked-crooked.com/a/9b923b6f2de913bb

rextester, microsoft (this machine is really slow; smaller numbers than coliru are used):

typical usage:
-----------------------
stack(deque) 904 millisecs
stack(vector) 421 millisecs
stack(list) 3822 millisecs

monotonic usage:
-----------------------
stack(deque) 531 millisecs
stack(vector) 327 millisecs
stack(list) 2247 millisecs

http://rextester.com/WYSFS9904