（Boolan） STL与泛型编程第三周笔记
c++stack(堆栈）是一个容器的改编，它实现了一个先进后出的数据结构（FILO）
使用该容器时需要包含#include头文件；
定义stack对象的示例代码如下：
stacks1;
stacks2;
stack的基本操作有：
1.入栈：如s.push(x);
2.出栈:如 s.pop().注意：出栈操作只是删除栈顶的元素，并不返回该元素。
3.访问栈顶：如s.top();
4.判断栈空：如s.empty().当栈空时返回true。
5.访问栈中的元素个数，如s.size（）;
下面举一个简单的例子：
#include
#include
using namespace std;
int main(void)
{
stacks;//定义一个栈
for(int i=0;i<10;i++)
s.push(i);
while(!s.empty())
{
printf("%lf\n",s.top());
s.pop();
}
cout<<"栈内的元素的个数为："<
return 0;
}
1.容器deque
deque是一种分段连续的容器，特点是双向开口，可以认为它是一段连续的内存空间，不仅可以向前方增加内存空间，也可以向后方增加内存空间。
在实际内存中实现双向扩充是比较复杂的事情，那么deque中是如何实现的呢？ deque通过一个控制器来串联一系列的缓冲器（buffer），从而达到逻辑上的连续效果。
deque的内存管理示意图，如下图所示：
deque是通过一个vector在维护自身的控制器，在控制器中存储的是指向buffer的指针，因此我们需要用一个指向指针的指针来指向这个vector的地址。
deque能在逻辑上实现内存连续，最关键的是iterator在起作用。 迭代器运行到边界的时候，都需要检测是否到边界，然后通过回到控制buffer的那个vector来管理边界的buffer了。 在iterator中，cur、first、last和node分别指向了用户使用时的当前的数据，first指向了buffer的第一块空间，last指向了buffer之后那个不在buffer中的空间， 而node指向了控制buffer的指针序列中的实际位置
deque的源代码如下所示（参考课程PPT）：
deque iterator的源代码如下所示：
deuqe的插入问题：
元素插入的时候因为是按顺序排列，如果插入元素不在两头在中间，会改变其他元素的位置，如果插入点距离前段比较近，那么移动前段比较合适，效率较高；
如果插入点距离后端比较近，那么将插入点之后的元素向后移动比较快。
deque insert函数的源代码如下：
iterator insert(iterator postion, const value_type& x){
if(postion.cur == start.cur) //如果安插点是deque的最前端
{
push_front(x); //直接使用push_front
return start;
}
else if(postion.cur == finish.cur) //如果安插点是deque的最末位
{
push_back(x); //直接交给push_back
iterator tmp = finish;
--tmp;
return tmp;
}
else
{
return insert_aux(postion, x);
}
}
template
typename deque::iterator_deque:: itert_aux(iterator pos, const value_type& x){
difference_type index = pos - start; //安插点之前的元素个数
value_type x_copy = x;
if(index < size() / 2){ //如果安插点之前的元素较少
push_front(front()); //在最前端加入第一个元素同值的元素
.......
copy(front2, pos1, front1); //元素搬移
}
else { //安插点之后的元素较少
push_back(back());//在尾端加入最末元素同值的元素
......
copy_backward(pos, back2, back1);//元素搬移
}
*pos = x_copy;//在安插点上设定新值
return pos;
}
deque如何模拟连续空间，全是的确iterators的功劳
具体代码如下：
reference operator[](size_type n)
{
return start[difference_type(n)];
}
reference front()
{
return *start;
}
reference back()
{
iterator tmp = finish;
--tmp;
return *tmp;
}
size_type size() const
{
return finish - start;
}
bool empty() const
{
return finish == start;
}
reference operator* () const
{
return *cur;
}
pointer operator->() const
{
return &(operator*());
}
//两个iterator之间的距离相当于
//（1）两个iterator之间的buffer的总长度+
//（2）itr至buffer末尾的长度+
//（3）x至buffer开头的长度
difference_type
operator- (const self& x) const
{
return difference_type(buffer_size()) * (node - x.node - 1) + (cur - first) + (x.last - x.cur);
//buffer size * 首尾buffer之间的buffer之间的数量 + 末尾（当前）buffer的元素量 + 起始buffer的元素量
}
self& operator++()
{
++cur; //切换至下一个元素
if(cur == last){ //如果抵达缓冲区的末尾
set_node(node + 1); //就跳至下一个节点（缓冲区）的起点
cur = first;
}
return *this;
}
self operator++(int)
{
self tmp = *this;
++*this;
return tmp;
}
self& operator--()
{
if(cur == first){ //如果目前在缓冲区开头，
set_node(node - 1); //就跳至前一节点（缓冲区）的最末端。
cur = last;
}
--cur; //往前移动一个元素（最末元素）
return *this;
}
self operator--(int)
{
self tmp = *this;
--*this;
return tmp;
}
void set_node(map_pointer new_node)
{
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size));
}
self& operator+=(difference_type n ){
difference_type offset = n + (cur - first);
if(offset >= 0 && offset < difference_type(buffer_size())
//目标位置在同一级缓存区
cur += n;
else{
//目标位置不在同一级缓存区内
difference_type node_offset = offset > 0? offset / difference_type(buffer_size()): -difference_type((-offset - 1) / buffer_size;
//切换至正确的的缓存区
set_node(node + node_offset);
cur = first + (offset - node_offset * difference_type(buffser_size());
}
return *this;
}
operator+(difference_type n) const
{
self tmp = *this;
return tmp += n;
}
self& operator-=(difference_type n)
{
return *this += - n;
}
self operator-(difference_type n)
{
self tmp = *this;
return tmp -= n;
}
reference operator[] (difference_type n)const
{
return *(*this + n);
}
GNU 4.9版本中实现的dequeUML图，如下图所示：
2.容器 queue
容器queue是以deque为底层结构实现的，具体代码如下：
template >
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:
bool empty() const{return c.empty();}
size_type size() const{return c.size();}
reference front() const {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(); }
void pop(){c.pop.front();}
}
3.容器 stack
容器stack也是以deque为底层结构实现的，需要注意的是queue和stack都不允许遍历，也不提供iterator，具体代码如下：
template >
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:
bool empty() const{return c.empty();}
size_type size() const{return c.size();}
reference top() const {return c.back();}
const_reference top() const{ return c.back();}
void push (const value_type& x){ c.push_back(); }
void pop(){c.pop.back();}
}
4.容器 rb_tree
Red-Black tree（红黑树）是平衡二元搜寻树（balanced Binary search tree）中常被使用的一种。
平衡二院搜寻树的特征：排列规律，有利于search和insert，并保持适度平衡，无任何节点过深。
红黑树的实现代码：
5.容器 set，multiset
容器set的实现代码：
template , class Alloc = alloc>
class set{
public:
//typedefs:
typedef Key key_type;
typedef Key value_type;
typedef Compare key_compare;
typedef Compare value_compare;
private:
typedef rb_tree rep_type;
rep_type t;
public:
typedef typename rep_type::const_iterator iterator;
...
//set的所有操作，都调用底层rb_tree的函数，从这点看来，set实际应该为container adapter
}
容器multiset的实现代码如下：
6.容器 map和multimap
map的实现代码如下：
multimap实现代码如下：
容器map独特的operator[]
