gnu / gcc / 19220ca6aa79921cc431e41f25986e16410c7a6a / . / libstdc++-v3 / include / bits / stl_stack.h

// Stack implementation -*- C++ -*- | |

// Copyright (C) 2001, 2002, 2004 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 2, 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. | |

// You should have received a copy of the GNU General Public License along | |

// with this library; see the file COPYING. If not, write to the Free | |

// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, | |

// USA. | |

// As a special exception, you may use this file as part of a free software | |

// library without restriction. Specifically, if other files instantiate | |

// templates or use macros or inline functions from this file, or you compile | |

// this file and link it with other files to produce an executable, this | |

// file does not by itself cause the resulting executable to be covered by | |

// the GNU General Public License. This exception does not however | |

// invalidate any other reasons why the executable file might be covered by | |

// the GNU General Public License. | |

/* | |

* | |

* 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 stl_stack.h | |

* This is an internal header file, included by other library headers. | |

* You should not attempt to use it directly. | |

*/ | |

#ifndef _STACK_H | |

#define _STACK_H 1 | |

#include <bits/concept_check.h> | |

#include <debug/debug.h> | |

namespace std | |

{ | |

// Forward declarations of operators == and <, needed for friend | |

// declaration. | |

template<typename _Tp, typename _Sequence = deque<_Tp> > | |

class stack; | |

template<typename _Tp, typename _Seq> | |

inline bool | |

operator==(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y); | |

template<typename _Tp, typename _Seq> | |

inline bool | |

operator<(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y); | |

/** | |

* @brief A standard container giving FILO behavior. | |

* | |

* @ingroup Containers | |

* @ingroup Sequences | |

* | |

* 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_front, | |

* such as std::list, std::vector, or an appropriate user-defined | |

* type. | |

* | |

* Members not found in "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> | |

class stack | |

{ | |

// concept requirements | |

typedef typename _Sequence::value_type _Sequence_value_type; | |

__glibcxx_class_requires(_Tp, _SGIAssignableConcept) | |

__glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept) | |

__glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) | |

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>&); | |

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. | |

*/ | |

explicit | |

stack(const _Sequence& __c = _Sequence()) | |

: c(__c) {} | |

/** | |

* Returns true if the %stack is empty. | |

*/ | |

bool | |

empty() const | |

{ return c.empty(); } | |

/** Returns the number of elements in the %stack. */ | |

size_type | |

size() const | |

{ return c.size(); } | |

/** | |

* Returns a read/write reference to the data at the first | |

* element of the %stack. | |

*/ | |

reference | |

top() | |

{ | |

__glibcxx_requires_nonempty(); | |

return c.back(); | |

} | |

/** | |

* Returns a read-only (constant) reference to the data at the first | |

* element of the %stack. | |

*/ | |

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); } | |

/** | |

* @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(); | |

} | |

}; | |

/** | |

* @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> | |

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> | |

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> | |

inline bool | |

operator!=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) | |

{ return !(__x == __y); } | |

/// Based on operator< | |

template<typename _Tp, typename _Seq> | |

inline bool | |

operator>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) | |

{ return __y < __x; } | |

/// Based on operator< | |

template<typename _Tp, typename _Seq> | |

inline bool | |

operator<=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) | |

{ return !(__y < __x); } | |

/// Based on operator< | |

template<typename _Tp, typename _Seq> | |

inline bool | |

operator>=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) | |

{ return !(__x < __y); } | |

} // namespace std | |

#endif /* _STACK_H */ |