STL源码阅读(五)

STL源码阅读(五) (SGI STL v3.3)

stl_stack.h (<stack>)

// 容器适配器stack
template <class _Tp, class _Sequence = std::deque<_Tp>>
class stack { 
    _Sequence c;
 ...
    // 注意stack的函数接口的实现
    // 即_Sequence需要实现back, push_back, pop_back, empty, size接口
    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(); }
 ...
}

stl_queue.h (<queue>)

// 容器适配器queue
template <class _Tp, class _Sequence = std::deque<_Tp>>
class queue {
    _Sequence c;
 ...
    // 注意queue的函数接口实现
    // 即_Sequence需要实现back，front，push_back, pop_back, empty, size接口 
  bool empty() const { return c.empty(); }
  size_type size() const { return c.size(); }
  reference front() { return c.front(); }
  const_reference front() const { return c.front(); }
  reference back() { return c.back(); }
  const_reference back() const { return c.back(); }
  void push(const value_type& __x) { c.push_back(__x); }
  void pop() { c.pop_front(); }
 ...
}

// 容器适配器priority_queue
template <class _Tp, 
          class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(vector<_Tp>),
          class _Compare
          __STL_DEPENDENT_DEFAULT_TMPL(less<typename _Sequence::value_type>) > {
      _Sequence c;
      _Compare comp;
 ...
    // _Sequence需要实现front, push_back, pop_back, empty, size接口
    // 此外由其构造函数，可知priority_queue是以堆实现的，而make_heap需要随机迭代器，
    // 因此_Sequence的迭代器类型应该是random_access_iterator_tag
     priority_queue(const _Compare& __x, const _Sequence& __s) 
    : c(__s), comp(__x) 
    { make_heap(c.begin(), c.end(), comp); }
 ...
} 

参考资料

1. sgi STL
2. cppreference.com