STL

STL源码剖析学习笔记

• 针对SGI-STL

STL六大组件

STL提供六大组件，彼此可以组合套用：

1. 容器（containers）：各种数据结构，如vector、list、deque、set、map，用以存放数据。
2. 算法（algorithms）：各种常用算法，如sort、search、copy、erase等。
3. 迭代器（iterators）：扮演容器与算法之间的胶合剂，是所谓的“泛型指针”，所有STL容器都附带有自己专属的迭代器。
4. 仿函数（functors）：行为类似函数，可作为算法的某种策略。
5. 配接器（adapters）：用来修饰容器或仿函数或迭代器接口的东西。
6. 配置器（allocators）：负责空间配置与管理，从实现角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的class template。

前闭后开表示法

任何一个STL算法，都需要获得由一对迭代器（泛型指针）所标示的区间，用以表示操作范围，这一对迭代器所标示的是前闭后开区间，以[first, last)表示。

空间配置器

整个STL的操作对象（所有的数值）都存放在容器之内，而容器一定需要配置空间以置放资料，故空间配置器allocator极其重要！

内存分配器（allocator）通常需要提供基本的内存分配、释放、构造和销毁等功能。

SGI空间配置器

SGI标准的空间配置器：std::allocator

SGI自己从未用过它，也不建议我们使用，主要原因是效率不佳，它只是把C++的::operator new和::operator delete做一层薄薄的封装而已。

SGI特殊的空间配置器：std::alloc

一般而言，我们所习惯的C++内存配置操作和释放操作如下：

class Foo { ... };
Foo* pf = new Foo; // 配置内存，然后构造对象
delete pf; // 将对象析构，然后释放内存

• new算式内含两阶段操作：（1）调用::operator new配置内存；（2）调用Foo::Foo()构造对象内容。
• delete算式也内含两阶段操作：（1）调用Foo::~Foo()将对象析构；（2）调用::operator delete释放内存。

为了精密分工，STL allocator决定将这两阶段操作区分开来，内存配置操作由alloc::allocate()负责，内存释放操作由alloc::deallocate()负责；对象构造操作由::construct()负责，对象析构操作由::destroy()负责。

SGI构造和析构的基本工具

// stl_construct.h的部分代码
#include <new.h>

template <class T1, class T2>
inline void construct(T1* p, const T2& value)
{
    new (p) T1(value); // placement new；调用T1::T1(value)
}

// destroy()第一版本，接受一个指针
template <class T>
inline void destroy(T* pointer)
{
    pointer->~T(); // 调用dtor ~T()
}

// destroy()第二版本，接受两个迭代器。此函数设法找出元素的数值型别
template <class ForwardIterator>
inline void destroy(ForwardIterator first, _ForwardIterator last) 
{
  __destroy(first, last, value_type(first));
}

// 判断元素的数值型别value_type是否有trivial destructor
template <class ForwardIterator, class T>
inline void __destroy(ForwardIterator first, ForwardIterator last, T*)
{
    typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;
    __destroy_aux(first, last, trivial_destructor());
}

// 如果元素的数值型别有non-trivial destructor（析构函数复杂），逐个销毁对象
template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator first, ForwardIterator last, __false_type)
{
    for(; first < last; ++first)
        destroy(&*first);
}

// 如果元素的数值型别有trivial destructor（析构函数简单，编译器自动处理）
template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator first, ForwardIterator last, __true_type) {}

// destroy()第二版本针对迭代器为char*和wchar_t*的特化版
inline void destroy(char*, char*) {}
inline void destroy(wchar_t*, wchar_t*) {}

• construct()接受一个指针p和一个初值value，用途就是将初值指定到所指的空间上。
• destroy()有两个版本，第一个版本接受一个指针，准备将该指针所指之物析构掉。第二个版本接受first和last两个迭代器，准备将[first, last)范围内的所有对象析构掉。（我们不知道[first, last)范围有多大，万一很大，一次次调用析构函数对效率是一种伤害，因此，首先利用value_type()判断该型别的析构函数是否无关痛痒，若是，则什么也不做就结束，若否（false_type），才以循环的方式遍历整个范围，并对每个对象调用第一个版本的destroy()。）

空间的配置与释放 std::alloc

• SGI STL以malloc()和free()完成内存的配置与释放。
• 考虑到小型区块所可能造成的内存破碎问题，SGI设计了双层级配置器，第一级配置器直接使用malloc()和free()，第二级配置器则视情况采用不同的策略：当配置区块超过128bytes时，视之为“足够大”，便调用第一级配置器；当配置区块小于128bytes时，视之为“过小”，为了降低额外负担，便采用复杂的memory pool的整理方式，而不再求助于第一级配置器。

第一级配置器剖析

template <int inst>
class __malloc_alloc_template
{
private:
// 以下都是函数指针，所代表的函数用以处理内存不足的情况
// oom : out of memory
    static void* oom_malloc(size_t);
    static void* oom_realloc(void *, size_t);
    static void (* __malloc_alloc_oom_handler) ();
public:
    static void * allocate(size_t n)
    {
        void *result = malloc(n); // 第一级配置器直接使用malloc()
        // 以下无法满足需求时，改用oom_malloc()
        if (0 == result)
            result = oom_malloc(n);
        return result;
    }

    static void deallocate(void *p, size_t /* n */)
    {
        free(p); // 第一级配置器直接使用free()
    }

    static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
    {
        void * result = realloc(p, new_sz); // 第一级配置器直接使用realloc()
        if (0 == result)
            result = oom_realloc(p, new_sz);
        return result;
    }

    // 以下仿真C++的set_new_handler() -> 可以通过它指定自己的out-of-memory handler
    static void (* set_malloc_handler(void (*f)()))()
    {
        void (* old) () = __malloc_alloc_oom_handler;
        __malloc_alloc_oom_handler = f;
        return (old);
    }
};

// 初值为0，有待客端设定
template <int inst>
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;

template <int inst>
void *__malloc_alloc_template<inst>::oom_malloc(size_t n)
{
    void (* my_malloc_handler)();
    void *result;

    // 不断尝试释放、配置、再释放、再配置
    for (;;)
    {
        my_malloc_handler = __malloc_alloc_oom_handler;
        if (0 == my_malloc_handler)
            __THROW_BAD_ALLOC;
        (*my_alloc_handler)(); // 调用处理例程，企图释放内存
        result = malloc(n); // 再次尝试配置内存
        if (result)
            return (result);
    }
}

template <int inst>
void *__malloc_alloc_template<inst>::oom_realloc(void * p, size_t n)
{
    void (* my_malloc_handler)();
    void *result;

    // 不断尝试释放、配置、再释放、再配置
    for (;;)
    {
        my_malloc_handler = __malloc_alloc_oom_handler;
        if (0 == my_malloc_handler)
            __THROW_BAD_ALLOC;
        (*my_alloc_handler)(); // 调用处理例程，企图释放内存
        result = realloc(p, n); // 再次尝试配置内存
        if (result)
            return (result);
    }
}

// 直接将参数inst指定为0
typedef __malloc_alloc_template<0> malloc_alloc;

• SGI第一级配置器的allocate()和realloc()都是在调用malloc()和realloc()不成功后，改调用oom_malloc()和oom_realloc()。后两者都有内循环，不断调用“内存不足处理例程”，期望在某次调用之后，获得足够的内存而圆满完成任务。但如果“内存不足处理例程”并未被客端设定，oom_malloc()和oom_realloc()便直接调用__THROW_BAD_ALLOC，丢出bad_alloc异常信息，或利用exit(1)中止程序。
• 设计、设定“内存不足处理例程”是客端的责任。

第二级配置器剖析

• __default_alloc_template

SGI第二级配置器的做法是：如果区块勾搭，超过128bytes时，就移交第一级配置器处理。当区块小于128bytes时，则以内存池（memory pool）管理，此法又称为次层配置：每次配置一大块内存，并维护对应之自由链表free-list。下次再有相同大小的内存需求，就直接从free-lists中取出。如果客端释还小额区块，就由配置器回收到free-lists中。

空间配置函数allocate()

• 身为一个配置器，__default_alloc_template拥有配置器的标准接口函数allocate()。

template <bool threads, int inst>
void *__default_alloc_template<threads, inst>::allocate(size_t)
{
    obj * volatile * my_free_list;
    obj * result;
    // 大于128 bytes就调用第一级配置器
    if (n > (size_t) __MAX_BYTES)
    {
        return (malloc_alloc::allocate(n));
    }
    // 寻找16个free lists中适当的一个
    my_free_list = free_list + FREELIST_INDEX(n);
    result = *my_free_list;
    if (result == 0)
    {
        // 未找到可用的free list，准备重新填充free list
        void *r = refill(ROUND_UP(n));
        return r;
    }
    // 调整free list
    *my_free_list = result->free_list_link;
    return (result);
}

空间释放函数deallocate()

• 身为一个配置器，__default_alloc_template拥有配置器的标准接口函数deallocate()。

template <bool threads, int inst>
void __default_alloc_template<threads, inst>::deallocate(void *p, size_t n)
{
    obj *q = (obj *)p;
    obj * volatile * my_free_list;

    // 大于128 bytes就调用第一级配置器
    if (n > (size_t) __MAX_BYTES)
    {
        malloc_alloc::deallocate(p, n);
        return;
    }

    // 寻找对应的free list
    my_free_list = free_list + FREELIST_INDEX(n);
    // 调整free list，回收区块
    q->free_list_link = *my_free_list;
    *my_free_list = q;
}

重新填充free lists

• 配置器__default_alloc_template的refill()接口。

template <bool threads, int inst>
void *__default_alloc_template<threads, inst>::refill(size_t n)
{
    int nobjs = 20;
    // 调用chunk_alloc() 尝试获取nobjs个区块作为free list的新节点
    char * chunk = chunk_alloc(n, nobjs);
    obj * volatile * my_free_list;
    obj * result;
    obj * current_obj, * next_obj;
    int i;

    // 如果只获得一个区块，这个区块就分配给调用者用，free list无新节点
    if (1 == nobjs)
        return (chunk);
    
    // 否则准备调整free list， 纳入新节点
    my_free_list = free_list + FREELIST_INDEX(n);

    // 以下在chunk空间内建立free list
    result = (obj *) chunk; // 这一块准备返回给客端
    // 引导free list指向新配置的空间（取自内存池）
    *my_free_list = next_obj = (obj *)(chunk + n);
    // 以下将free list的各节点串接起来
    for (i = 1; ; i++)
    {
        // 从1开始，因为第0各将返回给客端
        current_obj = next_obj;
        next_obj = (obj*)((char *)next_obj + n);
        if (nobjs - 1 == i)
        {
            current_obj -> free_list_link = 0;
            break;
        }
        else
        {
            current_obj -> free_list_link = next_obj;
        }
    }
    return (result);
}

内存池

• 从内存池中取空间给free list使用，是chunk_alloc()的工作。

迭代器 - iterator

迭代器（iterators）是一种抽象的设计概念，现实程序语言中没有直接对应于这个概念的实物。《Design Patterns》中iterator模式定义为：提供一种方法，使之能够依序巡访某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表述方式。

迭代器的设计思维

不论是泛型思维或STL的实际运用，迭代器（iterators）都十分重要。STL的中心思想在于：将数据容器和算法分开，彼此独立设计，最后再以一帖胶着剂将它们撮合在一起。

template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value)
{
    while (first != last && *first != value)
        ++first;
    return first;
}

迭代器是一种smart pointer

迭代器是一种行为类似指针的对象，而指针的各种行为中最常见的便是内容提领和成员访问，因此，迭代器最重要的编程工作就是对operator*和operator->进行重载。（可以参考C++标准程序库中的auto_ptr）

实践：给list（链表）设计一个迭代器

1. 其结构如下：

   // mylist.h
   #pragma once
   
   #include <iostream>
   
   template <typename T>
   class ListItem
   {
   public:
       T value() const { return _value; }
       ListItem* next() const { return _next; }
   private:
       T _value;
       ListItem* _next; // 单向链表
   };
   
   template <typename T>
   class List
   {
       void insert_front(T value);
       void insert_end(T value);
       void display(std::ostream &os = std::cout) const;
   private:
       ListItem<T>* _end;
       ListItem<T>* _front;
       long _size;
   };

2. List套用find()，需要设计一个迭代器，如下：

   // mylist-iter.h
   #include "mylist.h"
   
   template <class Item> // Item可以是单向链表节点或双向链表节点
   struct ListIter // 此处这个迭代器特定只为链表服务
   {
       Item* ptr; // 保持与容器之间的一个联系
   
       ListIter(Item* p = 0)
           : ptr(p) { }
   
       Item& operator*() const { return *ptr; }
       Item* operator->() const { return ptr; }
   
       // 以下两个operator++遵循标准做法
       ListIter& operator++()
       {
           ptr = ptr->next();
           return *this;
       }
       ListIter operator++(int)
       {
           ListIter tmp = *this;
           ++*this;
           return tmp;
       }
   
       bool operator==(const ListIter& i) const
       {
           return ptr == i.ptr;
       }
       bool operator!=(const ListIter& i) const
       {
           return ptr != i.ptr;
       }
   };

3. 现在可以将List和find()由ListIter粘合起来。

   #include "mylist.h"
   #include "mylist-iter.h"
   
   #include <iostream>
   #include "algorithm.h"
   
   using namespace std;
   
   // 本例value类型是int，需要重写全局operator!=重载函数
   template <typename T>
   bool operator!=(const ListItem<T>& item, T n)
   {
       return item.value() != n;
   }
   
   int main()
   {
       List<int> mylist;
   
       for (int i = 0; i < 5; i++)
       {
           mylist.insert_front(i);
           mylist.insert_end(i + 2);
       }
   
       mylist.display(); // 10 ( 4 3 2 1 0 2 3 4 5 6)
   
       ListIter<ListItem<int>> begin(mylist.front());
       ListIter<ListItem<int>> end; // default 0, null
       ListIter<ListItem<int>> iter; // default 0, null
   
       iter = find(begin, end, 3);
       if (iter == end)
           cout << "not found" << endl;
       else
           cout << "found." << iter->value() << endl;
       
       iter = find(begin, end, 7);
       if (iter == end)
           cout << "not found" << endl;
       else
           cout << "found." << iter->value() << endl;
   
   
       return 0;
   }

• 为了完成一个针对List而设计的迭代器，无可避免地暴露了太多List实现细节：在main()之中为了制作begin和end两个迭代器，暴露了ListItem；在ListIter class之中为了达成operator++的目的，暴露了ListItem的操作函数next()。要设计出ListIter，首先必须要对List的实现细节有非常丰富的了解。为了封装实现细节，STL容器都有专属迭代器！

迭代器相应型别

迭代器相应型别不只是“迭代器所指对象的型别”一种而已。根据经验，最常用的相应型别有五种。

Traits编程技法

迭代器所指对象的型别，称为该迭代器的value type。但函数的template参数推导机制推而导之的只是参数，无法推导函数的回返值型别。

// 声明内嵌型别方法
template <class T>
struct MyIter
{
    typedef T value_type; // 内嵌型别声明
    T* ptr;
    MyIter(T* p = 0) : ptr(p) { }
    T& operator*() const { return *ptr; }
};

traits：如果I有自己的value type，那么通过这个traits的作用，萃取出来的value_type就是I::value_type。

最常用到的迭代器相应型别有五种

template <class I>
struct iterator_traits
{
    typedef typename I::iterator_category iterator_category;
    typedef typename I::value_type value_type;
    typedef typename I::difference_type difference_type;
    typedef typename I::pointer pointer;
    typedef typename I::reference reference;
};

迭代器相应型别之一 value type

所谓value type，是指迭代器所指对象的型别。

迭代器相应型别之二 difference type

difference type用来表示两个迭代器之间的距离，因此它也可以用来表示一个容器的最大容量，因为对于连续空间的容器而言，头尾之间的距离就是其最大容量。

// STL的count()
template <class I, class T>
typename iterator_traits<I>::difference_type // 这一整行是函数回返型别
count (I first, I last, const T& value)
{
    typename iterator_traits<I>::difference_type n = 0;
    for (; first != last; ++first)
        if (*first == value)
            ++n;
    return n;
}

迭代器型别之三 reference type

在C++中，函数如果要传回左值，都是以by reference的方式进行，所以当p十个mutable iterator时，如果其value type是T，那么*p的型别不应该是T，应该是T&。如果p是一个constant iterators，其value type是T，那么*p的型别不应该是cosnt T，而应该是const T&。此处讨论的*p的型别，即所谓的reference type。

迭代器型别之四 pointer type

传回左值时，传回一个pointer，指向迭代器所指之物。

Item& operator*() const { return *ptr; } // Item& 是ListIter的reference type
Item* operator->() const { return ptr; } // Item* 是ListIter的pointer type

总结

设计适当的相应型别，是迭代器的责任。设计适当的迭代器，则是容器的责任。（只有容器本身，才知道该设计出怎样的迭代器来遍历自己。）

traits编程大量运用于STL实现品中，它利用“内嵌型别”的编程技巧与编译器的template参数推导功能，增强C++未能提供的关于型别认证方面的能力。

序列式容器

所谓序列式容器，其中的元素都可序，但未必有序。C++语言本身提供了一个序列式的容器array，STL另外提供vector、list、deque、stack、queue、priority-queue等序列式容器。(严格来说stack、queue等都是容器配接器！)

vector

• vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。

vector的迭代器

vector维护的是一个连续线性空间，所以不论其元素型别为何，普通指针都可以作为vector的迭代器而满足所有必要条件，因为vector迭代器需要的操作行为，如operator*、operator->等，普通指针天生就具备。vector支持随机存取。

template <class T, class Alloc = alloc>
class vector
{
// ...
public:
    typedef T value_type;
    typedef value_type* iterator; // vector的迭代器是普通指针
// ...
};

若客端代码如下，则ivite的型别其实就是int*，svite的型别其实就是Shape*。

vector<int>::iterator ivite;
vector<Shape>::iterator svite;

vector的数据结构

为了降低空间配置时的速度成本，vector实际配置的大小可能比客户端需求量大一些，以备将来可能的扩充。这便是容量（capacity），一个vector的容量永远大于或者等于其大小。

template <class T, class Alloc = alloc>
class vector
{
// ...
protected:
    iterator start; // 目前使用空间的头
    iterator finish; // 目前使用空间的尾
    iterator end_of_storage; // 目前可用空间的尾
// ...
};

运用start、finish、end_of_storage三个迭代器，便可轻易地提供首尾标示、大小等机能。

class vector
{
// ...
public:
    iterator begin() { return start; }
    iterator end() { return finish; }
    size_type size() const { return size_type(end() - begin()); }
    size_type capacity() const { return size_type(end_of_storage - begin()); }
    bool empty() const { return begin() == end(); }
    reference operator[] (size_type n) { return *(begin() + n); }
    reference front() { return *begin(); }
    reference back() { return *(end() - 1); }
// ...
};

vector的构造和内存管理

vector提供许多constructors，其中一个允许我们指定空间大小及初值。

// 构造函数，允许指定vector大小n和初值value
vector(size_type n, const T& value) { fill_initialize(n, value); }

// 填充并予以初始化
void fill_initialize(size_type n, const T& value)
{
    start = allocate_and_fill(n, value);
    finish = start + n;
    end_of_storage = finish;
}

// 配置而后填充
iterator allocate_and_fill(size_type n, const T& x)
{
    iterator result = data_allocator::allocate(n); // 配置n个元素空间
    uninitialized_fill_n(result, n, x);
    return result;
}

当push_back()将新元素插入于vector尾端时，该函数首先检查是否还有备用空间，如果有就直接在备用空间上构造元素，并调整迭代器finish，使vector变大；如果没有备用空间就扩充空间（2倍扩容）。

void push_back(const T& x)
{
    if (finish != end_of_storage)
    {
        // 有备用空间
        construct(finish, x);
        ++finish; // 调整水位高度
    }
    else
    {
        // 无备用空间，需要扩容
        insert_aux(end(), x);
    }
}

template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x)
{
    if (finish != end_of_storage)
    {
        // 有备用空间
        construct(finish, *(finish - 1));
        ++finish; // 调整水位
        T x_copy = x;
        copy_backward(position, finish - 2, finish - 1);
        *positioon = x_copy;
    }
    else
    {
        // 已无备用空间
        const size_type old_size = size();
        // 若原大小为0，则配置1个元素大小
        // 若原大小不为0，则二倍扩容
        const size_type len = old_size != 0 ? 2 * old_size : 1;

        iterator new_start = data_allocator::allocate(len); // 实际配置
        construct(new_finish, x); // 为新元素设定初值x
        ++new_finish;
        // 将原vector的备用空间中的内容也拷贝过来（？）
        new_finish = uninitialized_copy(position, finish, new_finish);
    }
    catch(...)
    {
        destroy(new_start, new_finish);
        data_allocator::deallocate(new_start, len);
        throw;
    }

    // 析构并释放原vector
    destroy(begin(), end());
    deallocate();

    // 调整迭代器，指向新vector
    start = new_start;
    finish = new_finish;
    end_of_storage = new_start + len;
}

• 所谓动态增加大小，并不是在原空间之后连续新空间（因为无法保证原空间之后尚有可配置的空间），而是以原大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。

list

• 相比于vector的连续线性空间，list就显得复杂许多。它的好处是每次插入或删除一个元素，就配置或释放一个元素空间。list对于空间的运用绝对精准，一点也不浪费。

list的节点（node）

// 实质是一个双向链表
template <class T>
struct __list_node
{
    typedef void* void_pointer;
    void_pointer prev; // 型别为void*
    void_pointer next;
    T data;
};

• list不能用普通指针作为迭代器，因为其节点不保证在存储空间中连续存在。

list的数据结构

SGI list不仅是一个双向链表，而且还是一个环状双向链表。（只需一个指针，便可以完整表现整个链表。）

template <class T, class Alloc = alloc>
class list
{
protected:
    typedef __list_node<T> list_node;
public:
    typedef list_node* link_type;
protected:
    link_type node; // 只要一个指针，便可表示整个环状双向链表
};

deque

• vector是单向开口的连续线性空间，deque则是双向开口的连续线性空间。
• deque允许常数时间内对头端进行元素的插入与移除操作。
• deque没有所谓容量（capacity）观念，它是动态地分段连续空间组合而成。
• 除非必要，应尽可能选用vector而非deque。

deque逻辑上是连续空间，实际是由一段一段的定量连续空间构成。一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。无需维护整体连续，但代价是复杂的迭代器架构。

deque的数据结构

deque的迭代器（较为复杂）必须能够指出分段连续空间（亦即缓冲区）在哪里；必须能够判断自己是否已经处于其所在缓冲区的边缘，如果是，一旦前进或后退时就必须跳跃至下一个或上一个缓冲区。

template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque
{
public:
    typedef T value_type;
    typedef value_type* pointer;
    typedef size_t size_type;

public:
    typedef __deque_iterator<T, T&, T*, BufSiz> iterator;

protected:
    typedef pointer* map_pointer;
protected:
    iterator start; // 第一个节点
    iterator finish; // 最后一个节点

    map_pointer map; // 指向map

    size_type map_size; // map内有多少指针
};

stack

• stack是一种“先进后出”（FILO）的数据结构。
• stack除了最顶端外，没有任何其它方法可以存取stack的其它元素。换言之，stack不允许所有遍历行为。
• stack不提供走访功能，也不提供迭代器。

stack的实现

stack以底部容器完成其所有工作，因此STL stack往往不被归类为container，而被归类为container adapter。

template <class T, class Sequence = deque<T>>
class 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; // 底层容器
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(); }
};

queue

• queue是一种“先进先出”（FIFO）的数据结构。
• queue除了最顶端可以取出、最低端可以加入外，没有任何其它方法可以存取queue的其它元素。换言之，queue不允许所有遍历行为。
• queue亦不提供迭代器。

queue的实现

queue以底部容器完成其所有工作，因此STL queue往往不被归类为container，而被归类为container adapter。

template <class T, class Sequence = deque<T>>
class queue
{
    // ...
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; // 底层容器
public:
    // 完全利用Sequence c的操作，完成queue的操作
    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

• 拥有权值观念的queue，其内的元素并非按照被推入的次序排列，而是自动依照元素的权值排列。
• priority_queue的所有元素，进出都有一定的规则，只有queue顶端的元素才有机会被外界取用。

priority_queue的实现

template <class T, class Sequence = vector<T>,
        class Compare = less<typename Sequence::value_type> >
class priority_queue
{
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; // 底层容器
    Compare comp; // 元素大小比较标准
public:
    priority_queue() : c() {}
    explicit priority_queue(const Compare& x) : c(), comp(x) {}

    template <class InputIterator>
    priority_queue(InputIterator first, InputIterator last, const Compare& x) : c(first, last), comp(x) { make_heap(c.begin(), c.end(), comp); }
    template <class InputIterator>
    priority_queue(InputIterator first, InputIterator last) : c(first, last) { make_heap(c.begin(), c.end(), comp); }

    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }
    const_reference top() const {return c.front(); }
    void push(const value_type& x)
    {
        // 将新元素推入末端
        c.push_back(x);
        // 重排heap
        push_heap(c.begin(), c.end(), comp);
    }
    void pop()
    {
        pop_heap(c.begin(), c.end(), comp);
        c.pop_back();
    }
};

关联式容器

所谓关联式容器，观念上类似关联式数据库：每笔数据（每个元素）都有一个键值和一个实值。一般而言，关联式容器的内部结构是一个平衡二叉树，以便获得良好的搜索效率。

红黑树 RB-tree

RB-tree不仅是一个二叉搜索树，而且必须满足以下规则：

1. 每个节点不是红色就是黑色。
2. 根节点为黑色。
3. 如果节点为红，其子节点必须为黑。
4. 任一节点至NULL（树尾端）的任何路径，所含之黑节点数必须相同。

算法

算法，问题之解法也。

质变算法

所有的STL算法都作用在由迭代器[first, last)所标出来的区间上，质变算法即指运算过程中会更改区间内（迭代器所指）的元素内容。诸如拷贝copy、互换swap、替换replace等。

• 这类算法运用于一个常数区间上会报错！

int ia[] = { 22, 30, 30, 17, 33, 40, 17, 23, 22, 12, 20 };
vector<int> iv(ia, ia + sizeof(ia)/sizeof(int));

vector<int>::const_iterator cite1 = iv.begin();
vector<int>::const_iterator cite2 = iv.end();

sort(cite1, cite2); // error

非质变算法

所有的STL算法都作用在由迭代器[first, last)所标出来的区间上，非质变算法即指运算过程中不会更改区间内（迭代器所指）的元素内容。诸如查找find、计数count、巡防for_each等。

• 这类算法应用一个会改变元素的仿函数，则元素当然会改变！

template <class T>
struct plus2
{
    void operator() (T& x) const
    { x += 2; }
};

int ia[] = { 22, 30, 30, 17, 33, 40, 17, 23, 22, 12, 20 };
vector<int> iv(ia, ia + sizeof(ia)/sizeof(int));

for_each(iv.begin(), iv.end(), plus2<int>());

算法示例

// 使用T所提供的greater-than操作符来判断大小
template <class T>
inline const T& max(const T& a, const T& b)
{
    return a < b ? b : a;
}

// 使用仿函数comp来判断大小
template <class T, class Compare>
inline const T& max(const T& a, const T& b, Compare comp)
{
    return comp(a, b) ? b : a;
}

仿函数 - functors

一种具有函数特质的对象，其实就是一个“行为类似函数”的对象，其类别定义中必须自定义function call运算子 - operator()。

// example
#include <functional>
#include <iostream>

using namespace std;

int main()
{
    greater<int> ig;
    cout << boolalpha << ig(4, 6); // false
    cout << greater<int>()(6, 4); // true - greater<int>()产生临时对象 (4, 6)指定两个参数
}

算术类仿函数

// 否定为一元运算，其它都是二元运算

// 加法、减法minus、乘法multiplies、除法divides、模取modulus类似
template <class T>
struct plus : public binary_function<T, T, T>
{
    T operator() (const T& x, const T& y) const
    {
        return x + y;
    }
};

template <class T>
struct modulus : public binary_function<T, T, T>
{
    T operator() (const T& x, const T& y) const
    {
        return x % y;
    }
};

template <class T>
struct negate : public unary_function<T, T>
{
    T operator(const T& x) const
    {
        return -x;
    }
};

配接器 - adapters

配接器在STL组件的灵活组合运用功能上，扮演着轴承、转换器的角色。(将一个class的接口转换为另一个class的接口，使原本不兼容而不能合作的classes，可以一起运作。)