STL源码剖析--读书笔记

天下大事，必作于细——引自STL源码剖析

希望可以从中汲取到很多智慧

STL概论与版本简介

STL六大组件功能与运用

1. 容器：各种数据结构，用在存放数据。
2. 算法：各种常用算法。
3. 迭代器：扮演容器与算法之间的胶合剂。
4. 仿函数：行为类似函数，可作为算法的某种策略。从实现的角度来看，仿函数是一种重载了operator()的class或class template。
5. 配接器：一种用来修饰容器，仿函数，迭代器接口的东西。
6. 配置器：负责空间配置与管理。

STL六大组件的交互关系：容器通过配置器获得数据存储的空间；算法通过迭代器存取容器中的内容；仿函数可以协助算法完成不同策略的变化，配接器可以修饰或套接容器，仿函数，迭代器接口。

临时对象的产生运用

刻意制造临时对象的方法是，在型别名称之后加上一对小括号，并可以指定初值。

静态常量整数成员在class内部直接初始化

如果class内含const static int data member，我们可以在class之内直接给予初值。

Function call操作符(operator())

在过去c语言时代，欲将函数当作参数传递，唯有通过函数指针才能达成。

但是函数指针优缺点，最重要的是他无法持有自己的状态，也无法达到组件技术的可适配性，也就是无法再将某些修饰条件加诸于其上而改变其状态。

STL算法的特殊版本所接受的所谓“条件”或“策略”或“一整组操作”，都以仿函数形式呈现。

空间的配置与释放

SGI标准对此的设计哲学如下：

• 向system heap要求空间
• 考虑多线程状态
• 考虑内存不足时的应对措施
• 考虑过多“小型区块”可能造成的内存碎片问题

按照我自己的积累想到的思路就是，对不同大小的内存用不同的链表进行管理，并调整合并的策略，这也是linux中free函数的做法。

C++的内存配置基本操作是::operator new()，基本的释放操作是::delete()，这两个全局函数相当于c的malloc()和free()，SGI也确实以malloc()和free()实现的。——嘿嘿，这不是想到一块去了么～

SGI设计了双层配置器，如果配置区块大小超过128bytes，则使用第一层配置器，也就是直接使用malloc()和free()；否则使用第二级配置器，为了降低负担，使用复杂的memory pool整理方式。维护16个自由链表，负责16中小型区块的配置能力。

第一级配置器 __malloc_alloc_template

总体就是在使用malloc()，realloc()，如果内存不足，会调用oom_malloc()，oom_realloc()，同时也可以调用set_new_handler()从而让发生oom时，调用自己自己制定的分配策略。

tips:The point to note is that realloc() should only be used for dynamically allocated memory.

第二级配置器 __default_alloc_template

这里的知识点要是具体想了解，可以搜索一下ctf wiki的linux pwn部分，其实有更完备的解释，当时学ctf的时候接触过，就暂时不展开了。free-lists的节点结构如下，free-lists就是实际管理内存快分配释放的组建，不同类型的内存快在不同的list上：

union obj {
  union obj * free_list_link;
  char client_data[1];
}

这是属于一物二用，可以节省空间。

内存池

当free list中没有可用的区块时，就需要去内存池memory pool上分割一些空间来做堆块，并放到free list上，一般性是20块，如果不够20块，但是也满足需求时，也返回不足的区块；如果连一个区块空间都无法供应，显然需要再调用malloc()从heap中配置内存，为内存池注入活水，这里的水量时判断内存池空闲空间大小的依据，其实就是end_free - start_free。

万一，system heap空间都不够了，malloc()调用失败，就会四处找“尚有未用区块，且区块足够够大”的free lists，找到了就用。

内存处理基本工具

STL定义有五个全局函数，作用于为初始化的空间上，注意，是为初始化，不是为开辟。五函数如下：

• construct()
• destroy()
• uninitialized_copy(). 应用于高层次函数copy()
• uninitialized_fill(). 应用于高层函数fill()
• uninitialized_fill_n(). 应用于高层函数fill_n()

// [first,last)范围内的每一个迭代器都指向为初始化的区域，范围内的每一个对象都调用construct
// 该函数会调用construct(&*(result+(i-first)),*i)
template<class InputIterator, class ForwardIterator>
ForwardIterator unintialized_copy(InputIterator first, InputIterator last, ForwardIterator result);

// 每个迭代器调用construct(&*i,x)
template<class ForwardIterator, class T>
void unintialized_fill(ForwardIterator first, ForwardIterator last, const T& x);

// 有了size大小，自然不需要last了
template<class ForwardIterator, class Size, class T>
ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n, const T& x);

迭代器概念与traits编程技法

之前空间配置器中我们提到，c++本身并不直接支持对“指针所指之物”的类型判断，也不支持对“对象析构函数是否为trivial“的判断，因此上述的value_type()和__type_traits<>如何实现需要我们思考。不过首先先了解一下迭代器。

Design Patterns一书中提供的23个设计模式中包含一种iterator模式，定义如下：提供一种方法，使之能够依序巡防某个聚合物所含的各个元素，而又无需暴露该聚合物的内部表达式。

迭代器是一种smart pointer

迭代器是一种行为类似指针的对象，因此迭代器最重要的编程工作就是对operator*和operator->进行重载。关于这一点，可以参考auto_ptr。

现在来为list链表设计一个迭代器，假设list及其节点的结构如下：

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

template<typename T>
class ListItem {
public:
  T value() const {retur _value;}
  ListItem* next() const {return _next;}
  ...
private:
  T _value;
  ListItem* _next;
};

再介绍一个find()算法，代码如下：

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

接下来为了让List结构能够使用find()算法，我们需要为他设计一个行为类似指针的外衣，也就是一个迭代器。设计一个专门为链表服务的迭代器。

template<class Item>
struct ListIter {
  Item* ptr;	// 保持与容器之间的一个联系
  ListIter(Item* p = 0) : ptr(p) {}
  // 不实现copy,operator=，因为编译器提供的缺省行为已经足够
  Item& operator*() const { return *ptr; }
  Item* operator->() const { return ptr; }
  bool operator==(const ListIter& i) const { return ptr == i.ptr; }
  bool operator!=(const ListIter& i) const { return ptr != i.ptr; }
  ListIter& operator++() { ptr = ptr->next(); return *this; }
  ListIter operator++(int) { ListIter tmp = *this; ++*this; return tmp; }
}

然而有一个句法上的问题，重载函数间的区别决定于它们的参数类型上的差异，但是不论是increment或decrement的前缀还是后缀都只有一个参数。为了解决这个语言问题，C++规定后缀形式有一个int类型参数，当函数被调用时，编译器传递一个0做为int参数的值给该函数。

• ++i; // 调用 i.operator++();
• i++; // 调用 i.operator++(0);
• –i; // 调用 i.operator–();
• i–; // 调用 i.operator–(0);

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

List<int> myList;
ListIter<ListItem<int>> begin(myList.front());
ListIter<ListItem<int>> end;
ListIter<ListItem<int>> iter;
iter = find(begin,end,3);	//当然这里需要重载一下ListItem<int>和int的operator!=

可以看到不可避免的会暴露LIstItem的一些细节，这本不该暴露，所以干脆把迭代器的开发工作交给List的设计者，他们足够了解。

迭代器相应型别

其实就是类型类别，毕竟c++只支持sizeof()，不支持typeof()，即使使用typeid()，获得的也只是名称，不能作为变量声明之用。

解决办法是利用function template的参数推导机制。

template <class I, class T>
void func_impl(I iter, T t) {
  T tmp;
}

template <class I>
inline void func(I iter) {
  func_impl(iter, *iter);
}

int main() {
  int i;
  func(&i);
}

以func()为对外接口，把实际操作全部置于func_impl()之中。

tips:template参数推导机制只能推导出参数的类型，无法推导出函数的返回值类型。

为了与C保持兼容，返回值并非是调用函数时的必要条件，因此函数模版类型推导和函数重载都不能且不应依赖返回值

Traits编程技法——STL源代码门钥

迭代器所指对象的型别，成为该迭代器的value type，万一value type需要用于函数的传回值该如何处理呢？声明内嵌型别似乎是个好主意。

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

// func()的返回类型必须加上关键字typename
template<class I>
typename I::value_type func(I ite) { return *ite; }

// ...
MyIter<int> ite(new int(8));
cout << func(ite);

但并不是所有迭代器都是class type，原生指针就不是，如果不是class tyoe，就无法为其定义内嵌型别，这是可以采用template partial specialization。

Partial Specialization偏特化的意义

如果class template拥有一个以上的template参数，可以针对其中某个或数个单飞全部的template参数进行特化工作。可以在泛化设计中提供一个特化版本。

之前的解决方法如下，就是特化一个指针版本:

template<class I>
struct iterator_traits {
  typedef typename I::value_type value_type;
};

template<class I>
struct iterator_traits<T*> {
  typedef T value_type;
};

template<class I>
struct iterator_traits<const T*> {
  typedef T value_type;	// 萃取出来时是T，而非const T
};

template<class I>
typename I::value_type func(I ite) { return *ite; }

这样不论是面对迭代器MyIter，还是int*，const int *，都可以通过tratis取出正确的value type。

最常用到迭代器的相应型别有五种：value type，difference type，pointer，reference，iterator category。

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
  • 指迭代器所指对象的型别
• difference type
  • 用来表示两个迭代器之间的距离，因此也可以用来表示一个容器的最大容量，头尾之间的距离就是容量
• reference
  • 与迭代器所指之物的内容是否可以改变相关，之前的Item&就是
• pointer
  • 指向迭代器所指之物，之前的Item*就是
• iterator category
  • 比较繁杂，展开一下

Iterator_category

根据移动性与施行操作，迭代器被分为五类：

• Input Iterator：只读
• Output Iterator：唯写，write only
• Forward Iterator：在迭代器所形成的区间上操作，比如replace()
• Bidirectional Iterator：可以双向移动
• Random Access Iterator：随机读写

这些迭代器的分类与从属关系如下。tips:直线与箭头代表的并非继承关系，而是所谓的concept与refinement的关系。

Input Iterator	Output Iterator
      |           |
      |           |
      |           |
      +	          +
Forward Iterator
      |
      |
      +
Bidirectional Iterator
      |
      |
      +
Random Access Iterator

举个例子：advanced()

Syntax，以下函数介绍来自GeeksforGeeks

template 
    void advance (InputIterator& it, Distance n);

it : Iterator to be advanced
n : Number of element positions to advance.
This shall only be negative for random-access and bidirectional iterators.

Return type :
None.

以下是针对Input Iterator，Bidirectional Iterator，Random Access Iterator三个迭代器的设计版本。

template <class InputIterator, class Distance>
void advance_II(InputIterator& i, Distance n) {
  for (; n > 0; --n, ++i);
}

template <class BidirectionalIterator, class Distance>
void advance_BI(BidirectionalIterator& i, Distance n) {
  if (n >= 0)
    for (; n > 0; --n, ++i);
  else
    for (; n < 0; ++n, --i);
}

template <class RandomAccessIterator, class Distance>
void advance_RAI(RandomAccessIterator& i, Distance n) {
  i += n;
}

没有针对ForwardIterator设计的版本，因为用InputIterator的版本即可。

调用时，可以简单的if-else逻辑即可，如下所示。

template <class InputIterator, class Distance>
void advance(InputIterator& i, Distance n) {
  if (is_random_access_iterator(i))
    advance_RAI(i,n);
  else if (is_bidirectional_iterator(i))
    advance_BI(i,n);
  else
    advance_II(i,n);
}

具体细节可以先不考虑，但大概就是这么个意思，但是像这样在执行期间才决定使用哪一个版本，会影响效率，最好能在编译期就选择正确的版本。

如果tratis有能力萃取出迭代器的种类，把它当作advance函数的第三个参数，不就可以进行重载了么？当然这个参数必须是class type。

修改后如下：

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidrectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidrectional_iterator_tag {};

// 这里的最后一个参数都只声明了型别，并未指定参数名称，因为用不上，纯粹为了激活重载
template <class InputIterator, class Distance>
inline void __advance(InputIterator& i, Distance n, input_iterator_tag) {
  for (; n > 0; --n, ++i);
}

template <class ForwardIterator, class Distance>
inline void __advance(ForwardIterator& i, Distance n, forward_iterator_tag) {
  __advance(i, n, input_iterator_tag());
}

template <class BidirectionalIterator, class Distance>
inline void __advance(BidirectionalIterator& i, Distance n, bidrectional_iterator_tag) {
  if (n >= 0)
    for (; n > 0; --n, ++i);
  else
    for (; n < 0; ++n, --i);
}

template <class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag) {
  i += n;
}

// 需要一个上层用来调用的接口
template <class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n) {
  __advance(i,n,iterator_traits<InputIterator>::iterator_category());
}

std::iterator的保证

为了符合规范，任何迭代器都应该提供五个内嵌相应型别，以利于tratis萃取。STL提供了一个iterator class，如果每个设计的迭代器都继承自他，就可以保证符合STL所需之规范。iterator class不含任何成员，纯粹就是型别定义。

template <class Category,
					class T,
					class Distance = ptrdiff_t,
					class Pointer = T*,
					class Reference = T&>
struct iterator {
  typedef Category iterator_category;
  typedef T value_type;
  typedef Distance difference_type;
  typedef Pointer pointer;
  typedef Reference reference;
}

当然书上之后还介绍了SGI STL中的__type_traits，暂时没有阅读下去，先了解一下基础。

序列式容器

容器，置物之所也。任何特定的数据结构都是为了实现某种特定的算法。根据数据在容器中的排列特性，和谐数据结构分为序列式和关联式两种。

所谓的序列式容器，其中的元素都可序，但未必有序。

vector

vector的数据安排以及操作方式与array非常相似，两者唯一的差别在于空间运用的灵活性。array是静态空间，一旦配置了就不可变，扩展的话需要人为开辟一个新的空间，然后把数据搬迁过去。但是vector不一样，有自动扩容机制，虽然本质还是开辟一个新的空间，但是这一行为对用户是不可见的。

由此也可以得知，vector的实现，关键在于两点：

• 对大小的控制
• 对重新配置时数据移动的效率

vector定义

书自带了一定的源代码，感兴趣的可以去搞一份，我自己不打算贴在这里，后文涉及到了会提一下。

vector的迭代器

vector维护的是一个线性空间，可提供Random Access Iterators。

template <class T, class Alloc = alloc>  // 預設使用 alloc 為配置器
class vector {
public:
  // 以下標示 (1),(2),(3),(4),(5)，代表 iterator_traits<I> 所服務的5個型別。
  typedef T value_type;				// (1)
  typedef value_type* pointer; 			// (2)
  typedef const value_type* const_pointer;
  typedef const value_type* const_iterator;
  typedef value_type& reference; 		// (3)
  typedef const value_type& const_reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type; 	// (4)
  // 以下，由於vector 所維護的是一個連續線性空間，所以不論其元素型別為何，
  // 原生指標都可以做為其迭代器而滿足所有需求。
  typedef value_type* iterator;
  // ....
};

/* 根據上述寫法，如果客端寫出這樣的碼：
      vector<Shape>::iterator is;
      is 的型別其實就是Shape*
      而STL 內部運用 iterator_traits<is>::reference 時，獲得 Shape&
                 運用iterator_traits<is>::iterator_category 時，獲得 
                      random_access_iterator_tag		(5)
      （此乃iterator_traits 針對原生指標的特化結果）
  */

vector数据结构

protected:
  // 專屬之空間配置器，每次配置一個元素大小
  typedef simple_alloc<value_type, Alloc> data_allocator;

  // vector採用簡單的線性連續空間。以兩個迭代器start和end分別指向頭尾，
  // 並以迭代器end_of_storage指向容量尾端。容量可能比(尾-頭)還大，
  // 多餘即備用空間。
  iterator start;
  iterator finish;
  iterator end_of_storage;
	// ...

以上是class vector中protected的一部分，代码本身注释还是很清晰的，start指向目前使用空间的头，finish指向目前使用空间的尾，end_of_storage指向目前可用空间的尾。

vector的构造与内存管理

其实就是研究一下constructor和push_back。

一个小测试

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void showVector(const vector<int>& p) {
    cout << "size = " << p.size() << endl;
    cout << "capacity = " << p.capacity() << endl;
}

void testCap() {
    vector<int> iv = vector<int>(2,9);
    showVector(iv); //  size = 2    cap = 2
    
    iv.push_back(1);
    showVector(iv); //  size = 3    cap = 4
    
    iv.push_back(2);
    showVector(iv); //  size = 4    cap = 4
    
    iv.push_back(3);
    showVector(iv); //  size = 5    cap = 8
    
    iv.pop_back();
    iv.pop_back();
    iv.pop_back();
    iv.pop_back();
    showVector(iv); //  size = 1    cap = 8
    iv.pop_back();
    
    showVector(iv); //  size = 0    cap = 8
}

int main(int argc, const char * argv[]) {
    // insert code here...
    // std::cout << "Hello, World!\n";
    testCap();
    return 0;
}

做了个简单的例子，规律还是很直接的，满了以后扩充，cap翻倍。

push_back

// 增加一個元素，做為最後元素
void push_back(const T& x) {
  if (finish != end_of_storage) {  // 還有備用空間
    construct(finish, x);   		// 直接在備用空間中建構元素。
    ++finish;                          	// 調整水位高度
  }
  else                                  // 已無備用空間
    insert_aux(end(), x);			
}
	
// insert_aux函数
template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
  if (finish != end_of_storage) {  // 還有備用空間
    // 在備用空間起始處建構一個元素，並以vector 最後一個元素值為其初值。    
    construct(finish, *(finish - 1));
    // 調整水位。
    ++finish;
    // 以下做啥用？
    T x_copy = x;	// 建一个临时变量
    copy_backward(position, finish - 2, finish - 1);	// 倒着拷贝，最后一个元素，最先拷贝，迷？last比first小？
    *position = x_copy;	// end()处的内容改为需要插入的对象x
  }
  else {		// 已無備用空間
    const size_type old_size = size();	// new size
    const size_type len = old_size != 0 ? 2 * old_size : 1;	// new cap
    // 以上配置原則：如果原大小為0，則配置 1（個元素大小）；
    // 如果原大小不為0，則配置原大小的兩倍，
    // 前半段用來放置原資料，後半段準備用來放置新資料。
    iterator new_start = data_allocator::allocate(len); // 實際配置
    iterator new_finish = new_start;	//	空间开辟后，finish == start，还没有元素
    __STL_TRY {
      // 將原vector 的內容拷貝到新 vector。
      // 第三个参数是the beginning of the destination range
      // return value：Iterator to the element past the last element copied.
      new_finish = uninitialized_copy(start, position, new_start);
      // 為新元素設定初值x
      construct(new_finish, x);	// 插入新元素
      // 調整水位。
      ++new_finish;
      // 將原vector 的備用空間中的內容也忠實拷貝過來（啥用途？）
      new_finish = uninitialized_copy(position, finish, new_finish);
    }

#       ifdef  __STL_USE_EXCEPTIONS 
    catch(...) {
      // "commit or rollback" 語意：若非全部成功，就一個不留。
      destroy(new_start, new_finish); 
      data_allocator::deallocate(new_start, len);
      throw;
    }
#       endif /* __STL_USE_EXCEPTIONS */
    // 解構並釋放原 vector
    destroy(begin(), end());
    deallocate();

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

可以看到新的cap确实是两倍，一旦引起空间重新分配，指向原vector的所有迭代器就失效了，这里可能会引起bug。

别的其实也都差不多，毕竟还是一个线性的结构。

List

链式结构的迭代器，插入删除的复杂度低，不浪费空间，删了就是删了，链式结构和线性结构的区别可以数据结构的基础里查阅一下就ok了。选择什么迭代器，也按照数据结构的特性自行选择就好，在大多数情况下，这么选择是没错的。

链表中的每个节点基本结构如下

template <class T>
struct __list_node {
  typedef void* void_pointer;
  void_pointer next;  // 型別為 void*。其實可設為 __list_node<T>*
  void_pointer prev;
  T data;
};

有next，prev两个指针，那肯定是双向链表啦。

链表肯定不能提供随机存取，但是可以双向移动，所以list提供的是Bidrectional Iterators。

list有一个重要性质：插入操作(insert)和接合(splice)操作都不会造成原有的list迭代器失效，毕竟只需要加一个节点就可以了，原先对象存放的节点不需要进行修改(插入相邻处，处理一下指针就好)，这和vector还是有区别的，毕竟vector本质上还是需要开辟新的空间，销毁旧的空间，只不过对用户而言，这些操作是透明的。

SGI list 不仅是双向链表，还是一个环状链表，这个我在源码山粗略得看了一下，没看出来，尴尬，但这样就可以考一个节点不断遍历所有节点了，其实本来就是双向的，一直可以遍历所有的。

别的操作，虽然书上讲的操作挺细致的，但其实就是数据结构里链表的操作。

deque

概述

• deque是一种双向开口的连续线性空间，虽然vector也可以也可以在头尾都插入元素，但是在头部插入元素的效率比较低。
• deque没有capcaity，因为他是动态地以分段连续的空间组合而成，随时可以增加一段新的空间并连接起来。
• 除非必要，尽可能地选择vector，因为deque需要有对应的组件来调度各个空间，操作起来更复杂。

这里有两个点可以展开，首先是什么叫作连续的空间拼接，这里不是物理意义上的拼接，而是逻辑意义上的。

再计算机系统里，常用的管理空间并扩容的手法就是：让一块空间专门用来存放实际存储数据的空间的地址，这样能管理的空间首先成指数倍增长；同时，还可以通过一个专门存放地址的数据块来管理全部的数据块。在deque中，这样的中央控制元件叫map，当然只是名字叫map而已，实际结构不是常规意义上的map。

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
public:                         // Basic types
  typedef T value_type;
  typedef value_type* pointer;
  //...
protected:                      // Internal typedefs
  // 元素的指標的指標（pointer of pointer of T）
  typedef pointer* map_pointer;	
  map_pointer map;	// 指向map，map是塊連續空間，
                    // 其內的每個元素都是一個指標（稱為節點），指向一塊緩衝區。
  size_type map_size;	// map內可容納多少指標。
  // ...
}

map其实是一个T**，也就是指向指针的指针，这和上文所说的是一样的。

deque的迭代器

struct __deque_iterator {
  // 保持與容器的聯結
  T* cur;	// 此迭代器所指之緩衝區中的現行（current）元素
  T* first;	// 此迭代器所指之緩衝區的頭
  T* last;	// 此迭代器所指之緩衝區的尾（含備用空間）
  map_pointer node;
  // ...
}

值得注意的是，这里的cur，first，last，都代表着当前元素所在的缓冲区的头，尾，当前，不是所有缓冲区的，只能定位某一块缓冲区而已，但是这里的node指向了中央控制器map中缓冲区所对应的指针。

deque里begin()，end()，返回的都是迭代器，这两个迭代器的结构就是如上文代码展示的__deque_iterator一样，有各自的cur，first，last，node。

其余的一些操作，需要模仿的时候再看远吗即可，主要就是operator重载后的操作，可以模仿一下中央控制器的调度，总体而言，就是一个传统的master-slave结构的调度方式。

deque的数据结构

deque如果是上述的逻辑，那么肯定会遇到两个问题：

• 如果map没有足够的空间存储指针该如何
  • 老三步：1）开辟一个新空间；2）搬过去；3）销毁旧的空间
• 如何快速获得整个deque的首尾元素
  • 那就需要提前准备两个指针，一个指向第一个缓冲区的第一个元素，另一个指向最后一个缓冲区的最后一个元素，所以deque才一直维护着start，finish两个迭代器，就是用来完成这个功能。
• 如果给缓冲区添加新元素
  • deque的每个缓冲区是有容量的上限的，如果存满了，会开辟新的缓冲区，并作迁移。

deque的元素操作的原理，暂时不展开，主要设计难点就是上文说的，因为单个元素的操作，对于整体的matser-slave的调度压力不大，涉及的也不多。

stack

概述

是一种first in last out的数据结构。

由于stack所有元素都必须符合first in last out的规则，只有stack顶端的元素，才能被外界直接操作到，所以stack不需要提供迭代器，也不提供走访功能。

底层的容器是deque和vector的版本都见过了，所以所用的版本具体是怎么实现的，如果涉及到调试，需要自己去源码看一下。

其余暂时没什么可以补充的。

queue

是一种first in first out的数据结构。

底层的容器是deque，由于queue和stack一样，由他的底部容器完成其所有工作，**而具有这种“修改某物接口，形成另一种风貌”之性质者，称为adapter(配接器)**，因此STL queue往往不被归类为container(容器)，而被归类为container adapter。

同理，和stack一样，queue也不提供遍历功能，也不提供迭代器。

heap

heap并不属于STL容器组件，扮演priority queue的助手，这东西java里也用来做heap的算法题，用法也差不多：自己设置优先级，然后存数据，然后排序。

同理，也没有迭代器，具体算法参考相关的数据结构书，如果自己实现的话：标准情况下，可以建造一个树形的结构，但是实际做题中，如果面试官要求你不要用priority queue相关的api，如果不熟练，不要用树结构，可以考虑利用数组来实现完全二叉树，用数组下标来表示二叉树中各个节点的位置。

priority_queue

只允许在底端加入元素，并从顶端取出元素。其内的元素并非依照被推入的次序排列，而是自动依照元素的权值排列。

缺省情况下priority_queue是利用一个max-heap完成，后者是一个以vector表现的complete binary tree，当然，缺省情况下自然是以vector为底部容器。结合取数的原则，自然也就不提供遍历功能，不提供迭代器。

slist

SGL STL提供了一个单向链表slist(single linked list)，底部迭代器是forward iterator，和list一样，insert，erase，splice等操作不会造成原油迭代器的实效。

list插入的新元素会插入在指定位置之前，对于slist这样的单链表而言，无法直接查看上一个元素，只能从头开始找，所以除了slist的起点附近区域，都不推荐执行insert和erase；同样slist也不提供push_back()，只提供了push_front()。

本文作者： xiaoyuyu
本文链接： http://woaixiaoyuyu.github.io/2022/02/15/STL%E6%BA%90%E7%A0%81%E5%89%96%E6%9E%90/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！

赏

谢谢你请我吃糖果