stl_stack.h

Go to the documentation of this file.

// Stack implementation -*- C++ -*-
 
// Copyright (C) 2001-2025 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.
 
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.
 
/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1996,1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */
 
/** @file bits/stl_stack.h
 *  This is an internal header file, included by other library headers.
 *  Do not attempt to use it directly. @headername{stack}
 */
 
#ifndef _STL_STACK_H
#define _STL_STACK_H 1
 
#include <bits/concept_check.h>
#include <debug/debug.h>
#if __cplusplus >= 201103L
# include <bits/uses_allocator.h>
#endif
#if __glibcxx_containers_ranges // C++ >= 23
# include <ranges> // ranges::to
# include <bits/ranges_algobase.h> // ranges::copy
#endif
 
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
 
#if __glibcxx_format_ranges
  template<typename, typename> class formatter;
#endif
 
  /**
   *  @brief  A standard container giving FILO behavior.
   *
   *  @ingroup sequences
   *
   *  @tparam _Tp  Type of element.
   *  @tparam _Sequence  Type of underlying sequence, defaults to deque<_Tp>.
   *
   *  Meets many of the requirements of a
   *  <a href="tables.html#65">container</a>,
   *  but does not define anything to do with iterators.  Very few of the
   *  other standard container interfaces are defined.
   *
   *  This is not a true container, but an @e adaptor.  It holds
   *  another container, and provides a wrapper interface to that
   *  container.  The wrapper is what enforces strict
   *  first-in-last-out %stack behavior.
   *
   *  The second template parameter defines the type of the underlying
   *  sequence/container.  It defaults to std::deque, but it can be
   *  any type that supports @c back, @c push_back, and @c pop_back,
   *  such as std::list, std::vector, or an appropriate user-defined
   *  type.
   *
   *  Members not found in @a normal containers are @c container_type,
   *  which is a typedef for the second Sequence parameter, and @c
   *  push, @c pop, and @c top, which are standard %stack/FILO
   *  operations.
  */
  template<typename _Tp, typename _Sequence = deque<_Tp> >
    class stack
    {
#ifdef _GLIBCXX_CONCEPT_CHECKS
      // concept requirements
      typedef typename _Sequence::value_type _Sequence_value_type;
# if __cplusplus < 201103L
      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
      __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
# endif
      __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
#endif
 
      template<typename _Tp1, typename _Seq1>
        friend bool
        operator==(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);
 
      template<typename _Tp1, typename _Seq1>
        friend bool
        operator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);
 
#if __cpp_lib_three_way_comparison
      template<typename _Tp1, three_way_comparable _Seq1>
        friend compare_three_way_result_t<_Seq1>
        operator<=>(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);
#endif
 
#if __cplusplus >= 201103L
      template<typename _Alloc>
        using _Uses = typename
          enable_if<uses_allocator<_Sequence, _Alloc>::value>::type;
 
#if __cplusplus >= 201703L
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 2566. Requirements on the first template parameter of container
      // adaptors
      static_assert(is_same<_Tp, typename _Sequence::value_type>::value,
          "value_type must be the same as the underlying container");
#endif // C++17
#endif // C++11
 
    public:
      typedef typename _Sequence::value_type            value_type;
      typedef typename _Sequence::reference             reference;
      typedef typename _Sequence::const_reference       const_reference;
      typedef typename _Sequence::size_type             size_type;
      typedef          _Sequence                        container_type;
 
    protected:
      //  See queue::c for notes on this name.
      _Sequence c;
 
    public:
      // XXX removed old def ctor, added def arg to this one to match 14882
      /**
       *  @brief  Default constructor creates no elements.
       */
#if __cplusplus < 201103L
      explicit
      stack(const _Sequence& __c = _Sequence())
      : c(__c) { }
#else
      template<typename _Seq = _Sequence, typename _Requires = typename
               enable_if<is_default_constructible<_Seq>::value>::type>
        stack()
        : c() { }
 
      explicit
      stack(const _Sequence& __c)
      : c(__c) { }
 
      explicit
      stack(_Sequence&& __c)
      : c(std::move(__c)) { }
 
#ifdef __glibcxx_adaptor_iterator_pair_constructor // C++ >= 23 && HOSTED
      template<typename _InputIterator,
               typename = _RequireInputIter<_InputIterator>>
        stack(_InputIterator __first, _InputIterator __last)
        : c(__first, __last) { }
#endif
 
#if __glibcxx_containers_ranges // C++ >= 23
      /**
       * @brief Construct a stack from a range.
       * @since C++23
       */
      template<__detail::__container_compatible_range<_Tp> _Rg>
        stack(from_range_t, _Rg&& __rg)
        : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg)))
        { }
 
      /**
       * @brief Construct a stack from a range.
       * @since C++23
       */
      template<__detail::__container_compatible_range<_Tp> _Rg,
               typename _Alloc>
        stack(from_range_t, _Rg&& __rg, const _Alloc& __a)
        : c(ranges::to<_Sequence>(std::forward<_Rg>(__rg), __a))
        { }
#endif
 
      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
        explicit
        stack(const _Alloc& __a)
        : c(__a) { }
 
      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
        stack(const _Sequence& __c, const _Alloc& __a)
        : c(__c, __a) { }
 
      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
        stack(_Sequence&& __c, const _Alloc& __a)
        : c(std::move(__c), __a) { }
 
      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
        stack(const stack& __q, const _Alloc& __a)
        : c(__q.c, __a) { }
 
      template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
        stack(stack&& __q, const _Alloc& __a)
        : c(std::move(__q.c), __a) { }
 
#if __cplusplus > 202002L
      template<typename _InputIterator, typename _Alloc,
               typename = _RequireInputIter<_InputIterator>,
               typename = _Uses<_Alloc>>
        stack(_InputIterator __first, _InputIterator __last, const _Alloc& __a)
        : c(__first, __last, __a) { }
#endif
#endif
 
      /**
       *  Returns true if the %stack is empty.
       */
      _GLIBCXX_NODISCARD bool
      empty() const
      { return c.empty(); }
 
      /**  Returns the number of elements in the %stack.  */
      _GLIBCXX_NODISCARD
      size_type
      size() const
      { return c.size(); }
 
      /**
       *  Returns a read/write reference to the data at the first
       *  element of the %stack.
       */
      _GLIBCXX_NODISCARD
      reference
      top()
      {
        __glibcxx_requires_nonempty();
        return c.back();
      }
 
      /**
       *  Returns a read-only (constant) reference to the data at the first
       *  element of the %stack.
       */
      _GLIBCXX_NODISCARD
      const_reference
      top() const
      {
        __glibcxx_requires_nonempty();
        return c.back();
      }
 
      /**
       *  @brief  Add data to the top of the %stack.
       *  @param  __x  Data to be added.
       *
       *  This is a typical %stack operation.  The function creates an
       *  element at the top of the %stack and assigns the given data
       *  to it.  The time complexity of the operation depends on the
       *  underlying sequence.
       */
      void
      push(const value_type& __x)
      { c.push_back(__x); }
 
#if __cplusplus >= 201103L
      void
      push(value_type&& __x)
      { c.push_back(std::move(__x)); }
 
#if __cplusplus > 201402L
      template<typename... _Args>
        decltype(auto)
        emplace(_Args&&... __args)
        { return c.emplace_back(std::forward<_Args>(__args)...); }
#else
      template<typename... _Args>
        void
        emplace(_Args&&... __args)
        { c.emplace_back(std::forward<_Args>(__args)...); }
#endif
#endif
 
#if __glibcxx_containers_ranges // C++ >= 23
      template<__detail::__container_compatible_range<_Tp> _Rg>
        void
        push_range(_Rg&& __rg)
        {
          if constexpr (requires { c.append_range(std::forward<_Rg>(__rg)); })
            c.append_range(std::forward<_Rg>(__rg));
          else
            ranges::copy(__rg, std::back_inserter(c));
        }
#endif
 
      /**
       *  @brief  Removes first element.
       *
       *  This is a typical %stack operation.  It shrinks the %stack
       *  by one.  The time complexity of the operation depends on the
       *  underlying sequence.
       *
       *  Note that no data is returned, and if the first element's
       *  data is needed, it should be retrieved before pop() is
       *  called.
       */
      void
      pop()
      {
        __glibcxx_requires_nonempty();
        c.pop_back();
      }
 
#if __cplusplus >= 201103L
      void
      swap(stack& __s)
#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
      noexcept(__is_nothrow_swappable<_Sequence>::value)
#else
      noexcept(__is_nothrow_swappable<_Tp>::value)
#endif
      {
        using std::swap;
        swap(c, __s.c);
      }
#endif // __cplusplus >= 201103L
 
#if __glibcxx_format_ranges
      friend class formatter<stack<_Tp, _Sequence>, char>;
      friend class formatter<stack<_Tp, _Sequence>, wchar_t>;
#endif
    };
 
#if __cpp_deduction_guides >= 201606
  template<typename _Container,
           typename = _RequireNotAllocator<_Container>>
    stack(_Container) -> stack<typename _Container::value_type, _Container>;
 
  template<typename _Container, typename _Allocator,
           typename = _RequireNotAllocator<_Container>>
    stack(_Container, _Allocator)
    -> stack<typename _Container::value_type, _Container>;
 
#ifdef __glibcxx_adaptor_iterator_pair_constructor
  template<typename _InputIterator,
           typename _ValT
             = typename iterator_traits<_InputIterator>::value_type,
           typename = _RequireInputIter<_InputIterator>>
    stack(_InputIterator, _InputIterator) -> stack<_ValT>;
 
  template<typename _InputIterator, typename _Allocator,
           typename _ValT
             = typename iterator_traits<_InputIterator>::value_type,
           typename = _RequireInputIter<_InputIterator>,
           typename = _RequireAllocator<_Allocator>>
    stack(_InputIterator, _InputIterator, _Allocator)
    -> stack<_ValT, deque<_ValT, _Allocator>>;
#endif
 
#if __glibcxx_containers_ranges // C++ >= 23
  template<ranges::input_range _Rg>
    stack(from_range_t, _Rg&&) -> stack<ranges::range_value_t<_Rg>>;
 
  template<ranges::input_range _Rg, __allocator_like _Alloc>
    stack(from_range_t, _Rg&&, _Alloc)
    -> stack<ranges::range_value_t<_Rg>,
             deque<ranges::range_value_t<_Rg>, _Alloc>>;
#endif
#endif
 
  /**
   *  @brief  Stack equality comparison.
   *  @param  __x  A %stack.
   *  @param  __y  A %stack of the same type as @a __x.
   *  @return  True iff the size and elements of the stacks are equal.
   *
   *  This is an equivalence relation.  Complexity and semantics
   *  depend on the underlying sequence type, but the expected rules
   *  are: this relation is linear in the size of the sequences, and
   *  stacks are considered equivalent if their sequences compare
   *  equal.
  */
  template<typename _Tp, typename _Seq>
    _GLIBCXX_NODISCARD
    inline bool
    operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
    { return __x.c == __y.c; }
 
  /**
   *  @brief  Stack ordering relation.
   *  @param  __x  A %stack.
   *  @param  __y  A %stack of the same type as @a x.
   *  @return  True iff @a x is lexicographically less than @a __y.
   *
   *  This is an total ordering relation.  Complexity and semantics
   *  depend on the underlying sequence type, but the expected rules
   *  are: this relation is linear in the size of the sequences, the
   *  elements must be comparable with @c <, and
   *  std::lexicographical_compare() is usually used to make the
   *  determination.
  */
  template<typename _Tp, typename _Seq>
    _GLIBCXX_NODISCARD
    inline bool
    operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
    { return __x.c < __y.c; }
 
  /// Based on operator==
  template<typename _Tp, typename _Seq>
    _GLIBCXX_NODISCARD
    inline bool
    operator!=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
    { return !(__x == __y); }
 
  /// Based on operator<
  template<typename _Tp, typename _Seq>
    _GLIBCXX_NODISCARD
    inline bool
    operator>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
    { return __y < __x; }
 
  /// Based on operator<
  template<typename _Tp, typename _Seq>
    _GLIBCXX_NODISCARD
    inline bool
    operator<=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
    { return !(__y < __x); }
 
  /// Based on operator<
  template<typename _Tp, typename _Seq>
    _GLIBCXX_NODISCARD
    inline bool
    operator>=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
    { return !(__x < __y); }
 
#if __cpp_lib_three_way_comparison
  template<typename _Tp, three_way_comparable _Seq>
    [[nodiscard]]
    inline compare_three_way_result_t<_Seq>
    operator<=>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
    { return __x.c <=> __y.c; }
#endif
 
#if __cplusplus >= 201103L
  template<typename _Tp, typename _Seq>
    inline
#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11
    // Constrained free swap overload, see p0185r1
    typename enable_if<__is_swappable<_Seq>::value>::type
#else
    void
#endif
    swap(stack<_Tp, _Seq>& __x, stack<_Tp, _Seq>& __y)
    noexcept(noexcept(__x.swap(__y)))
    { __x.swap(__y); }
 
  template<typename _Tp, typename _Seq, typename _Alloc>
    struct uses_allocator<stack<_Tp, _Seq>, _Alloc>
    : public uses_allocator<_Seq, _Alloc>::type { };
#endif // __cplusplus >= 201103L
 
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace
 
#endif /* _STL_STACK_H */