功能: 双端数组,可以对头端进行插入删除操作。
deque与vector区别:
deque容器
front():第一个元素,back():最后一个元素;
begin():起始迭代器,end():结束迭代器;
push_front():头部插入数据,pop_front():头部删除数据;
push_back():尾部插入数据,pop_back():尾部删除数据;
insert():插入数据,对外接口。
deque内部工作原理:
deque内部有个中控器,维护每段缓冲区中的节点(内容),缓冲区中存放真实数据;
中控器维护的是每个缓冲区的地址,使得使用deque时像一片连续的内存空间;
deque容器的迭代器也是支持随机访问的。
说明:
中控器中维护缓冲区的地址,缓冲区存放有效的数据。
在头部插入时,首地址是0x01,那么新数据首先在这个地址指向的缓冲区插入,当内存不够时,会再找新的缓冲区继续在头部插入数据,新缓冲的地址0x00也会在中控器中存入并维护;
同样地,在尾部插入时,首地址是0x03,新数据在这个地址指向的缓冲区插入,当内存不够时,会再找新的缓冲区继续在尾部插入数据,新缓冲的地址0x04也会在中控器中存入并维护。因此,deque可以实现快速的头部、尾部插入数据。
和vector数组相比,deque访问元素时没有vector快。比如访问第一个元素ele1,中继器要通过这个元素缓冲区的地址0x00访问,访问下一个元素时,要再通过地址0x01才能访问。也就是说,访问元素时,需要通过元素所在的缓冲区来访问。因此,deque头尾插入数据速度快,但是访问数据效率低,但也可以跳跃访问。
功能描述: deque容器构造
函数原型:
deque deqT;
——————默认构造形式deque(beg, end);
——————构造函数将[beg, end)区间中的元素拷贝给本身。deque(n, elem);
——————-构造函数将n个elem拷贝给本身。deque(const deque &deq);
——-拷贝构造函数代码示例:
void test1()
{int len = 50;//1、默认构造形式deque d1;for (int i = 1; i < 16; ++i){d1.push_back(i);//尾插}cout << "默认构造\td1:" << endl;printDeque(d1); cout << string(len, '-') << endl;//for (int i = 11; i < 16; ++i)//{// d1.push_front(i);//头插//}//cout << "头插 d1:" << endl;//printDeque(d1); cout << string(len, '-') << endl;//2、[beg, end)区间构造 左闭右开deque d2(d1.begin(), d1.end());cout << "区间构造\td2:" << endl;printDeque(d2); cout << string(len, '-') << endl;//3、n个elem拷贝构造deque d3(13, 15);cout << "n个elem拷贝构造\td3:" << endl;printDeque(d3); cout << string(len, '-') << endl;//4\拷贝构造deque d4(d3);cout << "拷贝构造\td4:" << endl;printDeque(d4); cout << string(len, '-') << endl;
}
说明:
以上的构造方法和vector中的一样,不赘述。要注意的是,如果想要容器是一个只读状态,容器可以加入const修饰,相应地,迭代器也要换成有const修饰的迭代器,如下所示。
//打印输出 加入const修饰迭代器 只读不写
void printDeque(const deque& d)
{for (deque::const_iterator it = d.begin(); it != d.end(); it++){//*it = 100;//const_iterator 容器数据不可以被修改cout << *it << " ";}cout << endl;
}
解释:
在打印函数中,有可能会对迭代器进行一个写操作,修改其中数据。如果想要这个打印函数只读不写,那么可以加入const修饰deque容器,即const deque
。如果迭代器还是原来deque
的定义方式,会提示“无法从const iterator…到iterator转换…”。因此,需要把起始迭代器也做修改,换成deque
,此时起始迭代器就不能被修改了,变成只读不写的状态。
总结: deque容器和vector容器的构造方式几乎一致,灵活使用即可
功能描述: 给deque容器进行赋值
函数原型:
deque& operator=(const deque &deq);
——————重载等号操作符assign(beg, end);
——————————————将[beg, end)区间中的数据拷贝赋值给本身。assign(n, elem);
——————————————-将n个elem拷贝赋值给本身。代码示例:
void printDeque(const deque& d)
{for (deque::const_iterator it = d.begin(); it != d.end(); it++){cout << *it << " ";}cout << endl;
}void test1()
{int len = 50;deque d1;for (int i = 1; i < 16; ++i){d1.push_back(i);//尾插}cout << "d1:" << endl;printDeque(d1); cout << string(len, '-') << endl;//1、operator=赋值deque d2;d2 = d1;cout << "operator=赋值\td2:" << endl;printDeque(d2); cout << string(len, '-') << endl;//2、assign区间赋值 [beg, end)deque d3;d3.assign(d2.begin(), d2.end());cout << "assign区间赋值\td3:" << endl;printDeque(d3); cout << string(len, '-') << endl;//3、assign n个elem拷贝赋值deque d4;d4.assign(13, 15);cout << "assign n个elem拷贝赋值\td4:" << endl;printDeque(d4); cout << string(len, '-') << endl;
}
总结: deque赋值操作也与vector相同,需熟练掌握
功能描述: 对deque容器的大小进行操作
函数原型:
deque.empty();
———————–判断容器是否为空
deque.size();
————————-返回容器中元素的个数
deque.resize(num);
——————重新指定容器的长度为num,若容器变长,则以默认值填充新位置。如果容器变短,则末尾超出容器长度的元素被删除。
deque.resize(num, elem);
————重新指定容器的长度为num,若容器变长,则以elem值填充新位置。如果容器变短,则末尾超出容器长度的元素被删除。
注意:
在vector容器中是有容量这个概念的,因为这是一个单端数组,左闭右开的范围,容量有限,并且vector有对外的接口capacity()。
但在deque容器中,是没有容量这个概念的,因为这是一个双端数组,可以无限动态扩展 deque容器,左开右开的范围,容量无限 ,所以没有capacity()这个对外接口,只有 大小 这个概念和接口 size()和resize()。
代码示例:
void printDeque(const deque& d)
{for (deque::const_iterator it = d.begin(); it != d.end(); it++){//*it = 100;//const_iterator 容器数据不可以被修改cout << *it << " ";}cout << endl;
}void test1()
{int len = 60;deque d1(13, 15);cout << "d1容器resize前\t" << endl << "d1: "; printDeque(d1);if (d1.empty()){cout << "容器为空!" << endl;}else{cout << "容器的大小:" << d1.size() << endl;}cout << string(len, '-') << endl;//重新指定大小 比原来小d1.resize(7);//删除超出新大小的数据cout << "d1容器resize后\t" << endl << "d1: ";printDeque(d1);if (d1.empty()){cout << "容器为空!" << endl;}else{cout << "容器的大小:" << d1.size() << endl;}cout << string(len, '-') << endl;//重新指定大小 比原来大d1.resize(13);//默认值0填充cout << "d1容器resize后\t" << endl << "d1: ";printDeque(d1);if (d1.empty()){cout << "容器为空!" << endl;}else{cout << "容器的大小:" << d1.size() << endl;}cout << string(len, '-') << endl;//重新指定大小 比原来大d1.resize(16, 15);//指定值填充cout << "d1容器resize后\t" << endl << "d1: ";printDeque(d1);if (d1.empty()){cout << "容器为空!" << endl;}else{cout << "容器的大小:" << d1.size() << endl;}cout << endl;
}
注意: resize时,比原来小,删除超出部分;比原来大,可以指定值填充,否则默认值0填充。
总结:
上一篇:数据结构入门6-1(图)
下一篇:dubbo源码解析-SPI机制