网站建设中的安全问题,典型营销型网站有哪些,wordpress创业模式,项目可行性研究报告c STL_deque
1.deque的使用
deque(双端队列)#xff1a;是一种双开口的连续空间的数据结构#xff0c;双开口的含义是#xff1a;可以在头尾两端进行插入和 删除操作#xff0c;且时间复杂度为O(1)#xff0c;与vector比较#xff0c;头插效率高c STL_deque
1.deque的使用
deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和 删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高。 构造和析构
std::dequeT创建一个存储类型为 T 的元素的双端队列。std::deque(const std::dequeT other)复制构造函数用另一个双端队列初始化当前队列。~std::deque()析构函数释放内存。
示例
#include iostream
#include dequeint main() {// 创建一个存储整数的双端队列std::dequeint myDeque;// 在队尾插入元素myDeque.push_back(10);myDeque.push_back(20);myDeque.push_back(30);// 复制构造一个新的双端队列std::dequeint anotherDeque myDeque;// 输出原始队列的内容std::cout Original deque content:;for (const int value : myDeque) {std::cout value;}std::cout std::endl;// 输出复制构造的队列的内容std::cout Copied deque content:;for (const int value : anotherDeque) {std::cout value;}std::cout std::endl;// 注意析构函数会在作用域结束时自动调用释放内存return 0;
}容量相关
size()返回队列中元素的数量。empty()检查队列是否为空。
示例
#include deque
#include iostreamint main() {std::dequeint myDeque {10, 20, 30, 40};std::cout myDeque.size() std::endl; //4std::cout myDeque.empty() std::endl;//0return 0;
}resize(new_size)调整队列的大小。
void resize(size_type count);
void resize(size_type count, const value_type value);count新的队列大小。value在增加队列大小时用于填充新元素的默认值。
功能
如果 count 小于当前队列的大小resize 会移除尾部的元素使队列的大小变为 count。如果 count 大于当前队列的大小resize 会在尾部插入足够数量的默认值为 value 的元素使队列的大小变为 count。
示例
#include iostream
#include dequeint main() {std::dequeint myDeque {10, 20, 30};// 调整队列大小为 5填充默认值 0myDeque.resize(5);for (const int value : myDeque) {std::cout value; // 10 20 30 0 0}std::cout std::endl;// 调整队列大小为 3myDeque.resize(3);for (const int value : myDeque) {std::cout value; // 10 20 30}std::cout std::endl;return 0;
}元素访问
at(index)函数返回指定索引处的元素并在访问之前进行范围检查。如果索引超出了双端队列的有效范围将引发 std::out_of_range 异常。operator[](index)运算符返回指定索引处的元素但不进行范围检查。如果索引超出了有效范围行为将是未定义的。front()返回第一个元素的引用。back()返回最后一个元素的引用。
示例
#include deque
#include iostreamint main() {// 创建一个存储字符串的双端队列std::dequestd::string myDeque;// 在队尾插入元素myDeque.push_back(Alice);myDeque.push_back(Bob);myDeque.push_back(Charlie);// 使用 at(index) 进行范围安全的访问try {std::string value myDeque.at(1);// 索引1处的元素是 Bobstd::cout value std::endl; //Bob} catch (const std::out_of_range e) {std::cout Index is out of range. std::endl;}// 使用 operator[](index) 进行不安全的访问std::string unsafeValue myDeque[2];// 索引2处的元素是 Charliestd::cout 不安全: unsafeValue std::endl;// 使用 front() 访问第一个元素std::string firstElement myDeque.front();std::cout firstElement std::endl;// 使用 back() 访问最后一个元素std::string lastElement myDeque.back(); //Alicestd::cout lastElement std::endl; //Charliereturn 0;
}修改操作
push_back(value)在队尾插入一个元素。push_front(value)在队首插入一个元素。pop_back()移除队尾的元素。pop_front()移除队首的元素。insert(pos, value)在指定位置插入一个元素。erase(pos)移除指定位置的元素。clear()移除所有元素。
示例
#include deque
#include iostreamint main() {std::dequeint myDeque;// 在队尾插入元素myDeque.push_back(10);myDeque.push_back(20);// 在队首插入元素myDeque.push_front(5);// 输出队列内容for (const int value: myDeque) {std::cout value ;//5 10 20}std::cout std::endl;// 移除队尾的元素myDeque.pop_back();// 移除队首的元素myDeque.pop_front();// 输出队列内容for (const int value: myDeque) {std::cout value ;//10}std::cout std::endl;// 在指定位置插入元素std::dequeint::iterator it myDeque.insert(myDeque.begin() 1, 15);// 输出队列内容for (const int value: myDeque) {std::cout value ;//10 15}std::cout std::endl;// 移除指定位置的元素myDeque.erase(it);// 输出队列内容for (const int value: myDeque) {std::cout value ;//10}std::cout std::endl;// 清空队列myDeque.clear();if (myDeque.empty()) {std::cout Deque is empty.;} else {std::cout Deque is not empty.;}std::cout std::endl;return 0;
}迭代器
begin() 和 end()返回指向第一个元素和尾后元素的迭代器。
示例
#include iostream
#include dequeint main() {std::dequeint myDeque {10, 20, 30, 40};for (std::dequeint::iterator it myDeque.begin(); it ! myDeque.end(); it) {std::cout *it; //10 20 30 40}std::cout std::endl;return 0;
}rbegin() 和 rend()返回指向最后一个元素和首元素前一个位置的逆向迭代器。
示例
#include iostream
#include dequeint main() {std::dequeint myDeque {10, 20, 30, 40};for (std::dequeint::reverse_iterator rit myDeque.rbegin(); rit ! myDeque.rend(); rit) {std::cout *rit; //40 30 20 10}std::cout std::endl;return 0;
}2.deque的原理介绍
deque并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际deque类似于一个动态的二维数组其底层结构如下图所示 双端队列底层是一段假象的连续空间实际是分段连续的为了维护其“整体连续”以及随机访问的假象落在了deque的迭代器身上因此deque的迭代器设计就比较复杂如下图所示 那deque是如何借助其迭代器维护其假想连续的结构呢 3.deque的优缺点
与vector比较deque的优势是头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不需要搬移大量的元素因此其效率是比vector高的。 与list比较其底层是连续空间空间利用率比较高不需要存储额外字段。 但是deque有一个致命缺陷不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历因此在实际中需要线性结构 时大多数情况下优先考虑vector和listdeque的应用并不多而目前能看到的一个应用就是STL用其作为stack和queue的底层数据结构。
4.为什么选择deque作为stack和queue的底层默认容器
stack是一种后进先出的特殊线性数据结构因此只要具有push_back()和pop_back()操作的线性结构都可以作为stack的底层容器比如vector和list都可以queue是先进先出的特殊线性数据结构只要具有push_back和pop_front操作的线性结构都可以作为queue的底层容器比如list。但是STL中对stack和queue默认选择deque作为其底层容器主要是因为 stack和queue不需要遍历(因此stack和queue没有迭代器)只需要在固定的一端或者两端进行操作。在stack中元素增长时deque比vector的效率高(扩容时不需要搬移大量数据)queue中的元素增长时deque不仅效率高而且内存使用率高。 结合了deque的优点而完美的避开了其缺陷。
