STL deque

deque

deque (usually pronounced like "deck") is an irregular acronym of double-ended queue 双端数组，可以对头端和尾端进行插入删除操作。

1、deque与vector的头插速度

vector 对于头部的插入效率低，因为需要向后移动所有元素。deque 相对vector 要快。

2 、deque 内部中控器

deque 内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实的数据，中控器维护每个缓冲区的地址。

3、相关操作

3.1 构造函数

类似于vector.

default constructorfill constructor explicit deque (size_type n); deque (size_type n, const value_type& val, const allocator_type& alloc = allocator_type()) range constructor template <class InputIterator> deque (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type()); copy constructor (and copying with allocator) deque (const deque& x); deque (const deque& x, const allocator_type& alloc); move constructor (and moving with allocator) deque (deque&& x); deque (deque&& x, const allocator_type& alloc); initializer list constructor deque (initializer_list<value_type> il, const allocator_type& alloc = allocator_type());

测试：

void test_1() { std::deque<int> d1; // 默认构造函数 std::deque<int> d2 (4,100); //four ints with value 100 std::deque<int> d3 (d2.begin(),d2.end()); // iterating through second std::deque<int> d4 (d3); // a copy of third int myints[] = {16,2,77,29}; std::deque<int> d5 (myints, myints + sizeof(myints) / sizeof(int) ); std::cout << "The contents of d5 are:"; for (std::deque<int>::iterator it = d5.begin(); it!=d5.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; }

3.2 赋值操作

与vector一样

void printDeque(const deque<int> &d) { for(deque<int>::const_iterator it=d.begin();it!=d.end();it++) cout<<*it<<" "; cout<<endl; } void test_2() { deque<int> d1 = {1,2,3,4,5,6,7,8}; deque<int> d2; d2 = d1; printDeque(d1); printDeque(d2); deque<int> d3; d3.assign(++d2.begin(),--d2.end()); printDeque(d3); deque<int> d4; d4.assign(5,10); //5 个 10 printDeque(d4); }

3.3 容器大小，元素存取

empty() 判空 size() 元素个数 resize(int num) 重新指定容器大小 resize(int num,elem) 重新指定容器大小和填充的元素 at(int idx) operator[] front() 返回第一个 back 返回最后一个 测试

void test_3() { deque<int> d1; cout<<d1.empty()<<endl; d1.push_back(1); d1.push_back(3); d1.push_back(4); d1.push_back(5); d1.push_back(8); cout<<d1.empty()<<endl; cout<<"d1.size() is "<<d1.size()<<endl; d1.resize(10); printDeque(d1); d1.resize(15,1); printDeque(d1); cout<<"d1.at(0) = "<<d1.at(0)<<endl; cout<<"d1[0] = "<<d1[0]<<endl; cout<<"d1 front:"<<d1.front()<<endl; cout<<"d1 back:"<<d1.back()<<endl; }

3.4 插入删除

push_back(elem) push_front(elm) pop_back() pop_front() insert(pos,elem) 在位置pos ,插入elem insert(pos,n,elem) 在位置pos ,插入n 个 elem insert(pos,begin,end) 在位置pos ,插入n 个 elem erase(begin,end) erase(pos) clear() pos 均为迭代器指向的位置 测试

void test_4() { deque<int> d1; d1.push_back(1); printDeque(d1); d1.push_front(2); printDeque(d1); d1.push_back(3); d1.push_back(5); printDeque(d1); d1.pop_front(); d1.pop_back(); printDeque(d1); d1.insert(++d1.begin(),5,20); printDeque(d1); d1.erase(d1.end()); printDeque(d1); }