首页 > 代码库 > 《STL源码剖析》---stl_stack.h阅读笔记

《STL源码剖析》---stl_stack.h阅读笔记

2024-07-17 12:43:14   226人阅读

Stack栈是常用的一个FILO数据结构，FILO是指first in last out，先进后出。因为栈只有一个口，即在这个口进也在这个口出。只能在栈顶操作，不能访问栈中的其他元素，所以栈没有迭代器。
Stack的实现是依赖其他容器的，用deque做底层数据结构。这样的实现，在STL中往往不称做container容器，往往被归类为container adapter容器适配器。deque是双向开口的数据结构，功能远强大于栈，只需简单分装即可做成栈。

用其他容器做底层数据结构也可是实现栈，vector、list也支持empty、size、back、push_back、pop_back操作。我想用deque是一种折中吧！如果用vector在重新分配空间时需要拷贝原来空间的元素，释放原来空间。如果使用list的话，每一次push_back、pop_back都涉及空间的分配和释放。

G++ 2.91.57，cygnus\cygwin-b20\include\g++\stl_stack.h 完整列表
/*
 *
 * 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.
 */

/* NOTE: This is an internal header file, included by other STL headers.
 *   You should not attempt to use it directly.
 */

#ifndef __SGI_STL_INTERNAL_STACK_H
#define __SGI_STL_INTERNAL_STACK_H

__STL_BEGIN_NAMESPACE

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class T, class Sequence = deque<T> >
#else
template <class T, class Sequence>
#endif
class stack {
	//友元函数，后面会展开的
  friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);
  friend bool operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);
public:
  typedef typename Sequence::value_type value_type;
  typedef typename Sequence::size_type size_type;
  typedef typename Sequence::reference reference;
  typedef typename Sequence::const_reference const_reference;
protected:
  Sequence c;	// 底层容器deque
public:
  // 以下完全利用 Sequence c 的操作，完成 stack 的操作。
  bool empty() const { return c.empty(); }
  size_type size() const { return c.size(); }
  reference top() { return c.back(); }
  const_reference top() const { return c.back(); }
  
  void push(const value_type& x) { c.push_back(x); }
  void pop() { c.pop_back(); }
};

template <class T, class Sequence>
bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
  return x.c == y.c;
}

template <class T, class Sequence>
bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
  return x.c < y.c;
}

__STL_END_NAMESPACE

#endif /* __SGI_STL_INTERNAL_STACK_H */

// Local Variables:
// mode:C++
// End:



联系
我们