C#和.Net框架

deque结构

• deque是双向开口的连续性空间，它通过buffer和map进行组织。它是一种分段连续的结构，其中buffer是申请的一块连续的空间，map是利用vector来进行组织的。

deque的数据成员

iterator start; //迭代器begin()
iterator finish; //迭代器end()
map_pointer map; //表示“中控中心”map的指针,指向vector
size_type map_size;//也是按照2倍进行库容

deque的迭代器数据成员

T* cur; //当前的buffer位置
T* first;//当前buffer的起始点
T* last;//当前buffer的end()
map_pointer node;//指向“中控中心”

每个buffer的容量个数的设置

• deque定义 : template<class T,class Alloc = alloc, size_t BufSiz = 0>
• 对于BufSiz就是定义buffer的大小，分配规则如下

inline size_t _deque_buf_size(size_t n,size_t sz)
{
    //如果指定缓冲区大小，则按这个来
    return  n != 0 ? n :
    //如果未指定缓冲区大小，那么按元素的大小，如果小于512，则范围512/sz，否则返回1
                (sz < 512 ? size_t(512/sz) : size_t(1))
}

push_back和push_front()

• 首先会检查当前缓冲区是否够用
• 如果不够用，检查map的是否有可用空间。
• 如果不够用，就会进行扩容，与vector类似(扩容的是浅拷贝，值拷贝map中的buffer指针)
• 对于deque的begin和end,初始化的时候会尽可能的让它在中间。

insert()

• insert的时候会考虑是靠前还是靠后，然后使用向前插入还是向后插入