vector和list的区别

1. vector底层实现是数组；list是双向链表
2. vector是顺序内存,支持随机访问，list不行
3. vector在中间节点进行插入删除会导致内存拷贝，list不会
4. vector一次性分配好内存，不够时才进行翻倍扩容；list每次插入新节点都会进行内存申请
5. vector随机访问性能好，插入删除性能差；list随机访问性能差，插入删除性能好

deque（双端数组）

支持快速随机访问，由于deque需要处理内部跳转，因此速度上没有vector快。

1、deque概述：

deque是一个双端开口的连续线性空间，其内部为分段连续的空间组成，随时可以增加一段新的空间并链接

注意:

由于deque的迭代器比vector要复杂，这影响了各个运算层面，所以除非必要尽量使用vector；为了提高效率，在对deque进行排序操作的时候，我们可以先把deque复制到vector中再进行排序最后在复制回deque

2、deque中控器：

deque是由一段一段的定量连续空间构成。一旦有必要在其头端或者尾端增加新的空间，便配置一段定量连续空间，串接在整个deque的头端或者尾端

好处：

避免“vector的重新配置，复制，释放”的轮回，维护连整体连续的假象，并提供随机访问的接口；

坏处：

其迭代器变得很复杂

deque采用一块map作为主控，其中的每个元素都是指针，指向另一片连续线性空间，称之为缓存区，这个区才是用来储存数据的。

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内可容纳多少指针

}

//map其实是一个T**

deque迭代器:

template<class T, class Ref, class Ptr, size_t BufSiz>

struct _deque_iterator { typedef _deque_iterator<T, T &, T *, BufSiz> iterator;

typedef _deque_iterator<T, cosnt T &, const T *, BufSiz> const_iterator;

static size_t buffer_size() { return _deque_buf_size(BufSiz, sizeof(T)); };

typedef randem_access_iterator_tag iterator_category;

typedef T value_type;

typedef Ptr pointer;

typedef Ref reference;

typedef size_t size_type;

typedef ptrdiff_t difference_type;

typedef T **map_pointer;

typedef _deque_iterator self;

T *cur;

T *first;

T *last;

inline size_t _deque_buf_size(size_t n, size_t sz) { return n != 0 ? n :

(sz < 512 ? size_t(512 / sz) : size_t(1));

} }

deque拥有两个数据成员

start与finish迭代器，分别由deque:begin()与deque:end()传回

//迭代器的关键行为，其中要注意的是一旦遇到缓冲区边缘，可能需要跳一个缓存区

void set_node(map_pointer new_node) { node = new_node;

first = *new_node;

last = first + difference_type(buffer_size());

}

//接下来重载运算子是_deque_iterator<>成功运作的关键 reference operator*() const { return *cur; }

pointer operator->() const { return &(operator*()); }

difference_type operator— (const self &x) const { return difference_type (buffer_szie()) * (node-x.node-1)+(cur-first)+(x.last-

x.cur);

}

self &operator++() { ++cur;

if (cur == last) { set_node(node + 1);

cur = first;

} return *this;

}

self operator++(int) { self temp = *this;

++*this;

return temp;

}

self &operator--() { if (cur == first) {

set_node(node - 1);

return *this;

}

self operator-(int) { self temp = *this;

--*this;

return temp;

}

//以下实现随机存取，迭代器可以直接跳跃n个距离 self &operator+=(difference_type n) {

difference_type offest = n + (cur - first);

if (offest > 0 && offest < difference_type(buffer_size()))

cur += n;

else { offest > 0 ? offest / fifference_type(buffer_size()) : -difference_type((-

offest - 1) / buffer_size()) - 1;

set_node(node + node_offest);

cur = first + (offest - node_offest * difference_type(buffer_size()));

} return *this;

}

self operator+(differnece_type n) { self tmp = *this;

return tmp += n;

}

self operator-=() { return *this += -n; }

self operator-(difference_type n) { self temp = *this;

return *this -= n;

}

rference operator[](difference_type n) { return *(*this + n);

}

bool operator==(const self &x) const { return cur == x.cur; } bool operator!=(const self &x) const { return !(*this == x); }

bool operatoe<(const self &x) const { return (node == x.node) ? (cur < x.cur) : (node - x.node);

}

deque数据结构:

deque的构造与管理

//deque首先自行定义了两个空间配置器 typedef simple_alloc <value_type, Alloc> data_allocator;

typedef simple_alloc <pointer, Alloc> map_allocator;

deque中有一个构造函数用于构造deque结构并赋初值

deque(int n, const value_type &value) : start(), finish(), map(0), map_size(0) { fill_initialize(n, value);//这个函数就是用来构建deque结构，并设立初值

}

template<class T, class Alloc, size_t BufSize)

void deque<T, Alloc, BufSize>::fill_initialize(size_type n, const value_type &value) { creat_map_and_node(n);//安排结构

map_pointer cur;

_STL_TRY { //为每个缓存区赋值

for (cur=start.node;cur<finish.node;++cur)

uninitalized_ fill(*cur, *cur+buffer_size(), value);

//设置最后一个节点有一点不同 uninitalized_fill(finish.first, finish.cur, value);

}

catch() { // ...

} }

template<class T, class Alloc, size_t Bufsize> void deque<T, alloc, Bufsize>::creat_map_and_node(size_type num_elements) {

//需要节点数=元素个数/每个缓存区的可容纳元素个数+1 size_type num_nodes = num_elements / Buf_size() + 1;

map_size = max(initial_map_size(), num_nodes + 2);//前后预留2个供扩充

//创建一个大小为map_size的map map = map_allocator::allocate(map_size);

//创建两个指针指向map所拥有的全部节点的最中间区段 map_pointer nstart = map + (map_size() - num_nodes) / 2;

map_poniter nfinish = nstart + num_nodes - 1;

map_pointer cur;

_STL_TRY {

catch() { // ...

}

//最后为deque内的start和finish设定内容 start.set_node(nstart);

finish.set_node(nfinish);

start.cur = start.first;

finish.cur = finish.first + num_elements % buffer_szie();

}

接下来就是插入操作的实现，第一，首先判断是否有扩充map的需求，若有就扩，然后就是在插入函数中，首先判断是否在结尾或者开头从而判断是否跳跃节点。

void push_back(const value_type &t) { if (finish.cur != finish.last - 1) {

construct(finish.cur, t);

++finish.cur;

} else push_back_aux(t);

}

// 由于尾端只剩一个可用元素空间（finish.cur=finish.last-1）， // 所以我们必须重新配置一个缓存区，在设置新元素的内容，然后更改迭代器的状态

tempalate<class T, class Alloc, size_t BufSize> void deque<T, alloc, BufSize>::push_back_aux(const value_type &t) {

value_type t_copy = t;

reserve_map_at_back();

*(finish.node + 1) = allocate_node();

_STL_TRY { construct(finish.cur, t_copy);

finish.set_node(finish.node+1);

finish.cur=finish.first;

}

• STL_UNWIND {

deallocate_node(*(finish.node + 1));

} }

//push_front也是一样的逻辑