4、stack
stack是一种先进先出的数据结构。只能在栈顶操作。它以底层容器完成所有的操作，因此是一个adapter（配接器）。
template <class T, class Sequence = deque<T> >
class stack
{
//下面的__STL_NULL_TMPL_ARGS可以展开成为<>,这样写是为了让class template的
//某个具体实现与friend function template 的某个具体实现一对一关联（VC不支持？未验证）
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 cosnt_reference;
protected:
Sequence c;
public:
//利用底层容器c进行操作
};
stack还有一个特性就是没有迭代器：因为只能在栈顶进行操作，所以不必要定义迭代器，也不能遍历。
5、queue
和stack基本一致。
6、Heap
Heap在STL中不是实际组件，只是priority的助手。
binary heap：一种完全二叉树。可以用数组表示。如果数组的第一个元素保留（设为无穷大或者无穷西欧啊），从第二个元素开始储存，则有：对于i处的节点，其子节点必定位于2i和2i+1处，其父节点位于i/2处。（SGI STL中没有用到这个方法，因此取值方法有所改变）
heap操作：
push_heap：在heap中插入一个新值的时候，先把它插入到最后面（树中最下面一排的最后一个）。然后将它和父节点进行比较，如果其键值大于父节点的，就交换位置，如此一直上溯。
pop_heap：在heap中删除最大值的时候(其实是将最大值元素交换到heap的尾部，然后--size)。先进行交换，然后对交换后的数组进行从上往下的调整：如果子节点中最大的键值大于父节点的键值，就将他们两个交换，然后继续往下进行。
ajust_heap：上述调整方法。
（SGI STL使用的方法：先不进行交换，而是将父节点设为空洞，然后将空洞下层到符合的底层，再将前堆尾元素在空洞位置进行一次push_heap）
sort_heap：进行N次pop_heap，就完成了一次堆排序。
make_heap：因为所有的叶子节点都不需要调整，所以从N/2处往上进行调整。
7、priority_queue
priority_queue是一个带有权值观念的队列，因此取出元素的时候只能取出权值最大的元素。
priority_queue完全以底层容器为根据（缺省为vector），加上heap处理规则实现。
8、slist
slist是一个单向链表。（SGI中有实现，但是并不在STL容器中）
因为slist是单向的，因此对于获得slist的链表尾端需要进行一次完整的遍历，因而push_back操作十分费时，没有提供。
slist特点：节点和迭代器设计运用了继承关系，比list要复杂。
struct __slist_node_base
{
__slist_node_base *next;
};
template<typename T>
struct __slist_node: public __slist_node_btose
{
T data;
};
struct __slist_iterator_base
{
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef forward_iterator_tag iterator_category; //单向
__slist_node_base *node; //指向节点基本结构
};
template <typename T, typename Ref, typename Ptr>
struct __slist_iterator: public __slist_iterator_base
{
typedef __slist_iterator<T, T&, T*> iterator;
typedef __slist_iterator<T, const T&, const T*> const_iterator;
typedef __slist_iterator<T, Ref, Ptr> self;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef __slist_node<T> list_node;
};
（为什么要用继承？）
posted on 2010-05-30 03:32
dead_horse 阅读(372)
评论(0) 编辑 收藏 引用 所属分类:
STL读书笔记