产品销售网站模块如何设计,黄页是什么应用,微山建设局网站,软件工程专业就业前景1 std::deque 的主要应用场景
std::deque#xff08;双端队列#xff09;在C编程中有许多应用场景#xff0c;尤其是当需要在序列的两端进行高效的插入和删除操作时。以下是std::deque的一些典型应用场景#xff1a;
#xff08;1#xff09;排队系统#xff1a; std:…1 std::deque 的主要应用场景
std::deque双端队列在C编程中有许多应用场景尤其是当需要在序列的两端进行高效的插入和删除操作时。以下是std::deque的一些典型应用场景
1排队系统 std::deque 非常适合实现排队系统如电影院售票或银行排队系统。可以使用 push_back() 在队列的末尾添加新客户使用 pop_front() 从队列的头部移除已服务的客户。由于 std::deque 在两端操作具有高效的性能这种实现方式比使用 std::vector 或 std::list 更加高效。
2缓冲区处理 在处理数据流或需要维护一个固定大小的缓冲区时std::deque 也非常有用。可以使用 push_back()添加新数据并使用 pop_front() 移除旧数据以保持缓冲区的大小恒定。
3撤销与重做功能 在实现如文本编辑器或图形设计工具的撤销与重做功能时std::deque 可以存储用户的操作历史。使用push_back()添加新操作使用 pop_front() 撤销最近的操作。由于 std::deque 在头部和尾部的操作都很高效这可以提供快速且流畅的撤销与重做体验。
4历史记录管理 在需要维护一个操作历史记录的系统中如网页浏览器或游戏应用std::deque 可以用于存储最近的访问历史或得分记录。
5任务调度 在任务调度系统中std::deque 可以用于存储待处理的任务。新的任务可以添加到队列的末尾而处理完成的任务可以从队列的头部移除。
1.1 std::deque 应用于排队系统
在应用于排队系统的开发中std::deque双端队列的优势主要体现在以下几个方面
1高效的插入和删除操作 std::deque 允许在队列的头部和尾部进行高效的插入和删除操作这对于排队系统来说非常有用因为客户通常是在队列的尾部加入而在头部被处理。
2空间优化 std::deque 通常不是以连续内存存储的而是通过一系列小的、单独的内存块来实现。这意味着它可以在内存分配方面更加灵活尤其是在处理大量数据时可以更有效地利用内存。
3无需重新分配内存 当在std::deque的尾部添加元素时通常不需要重新分配内存或移动现有的元素因为std::deque预先分配了一些内存块。这可以减少内存分配和拷贝的开销。
注意虽然上述优点 std::list 也具备但是 std::deque 还支持元素的随机访问另外与 std::list 对比std::deque 所占据的内存空间也小一些其效率低于 std::vector但是比 std::list 要好很多所以如果在排队系统中还需要随机访问元素时std::deque 就更合适一些。
如下为样例代码
第一步定义 Customer 类 首先需要定义一个 Customer 类来表示排队系统中的客户。这个类应该包含一个成员变量来存储客户的 ID并且应该有一个方法来打印客户的信息。
#include iostream
#include deque
#include memory // 定义一个表示客户的简单类
class Customer {
public:Customer(int id) : m_id(id) {}// 打印客户的信息 void print() const {std::cout Customer ID: m_id std::endl;}private:int m_id;
};第二步定义QueueSystem类 接下来定义 QueueSystem 类这个类将使用 std::deque 来存储 Customer 对象。QueueSystem 类将包含 enqueue入队、dequeue出队和size获取队列大小等方法。
// 排队系统类
class QueueSystem {
public:// 添加客户到队列 void enqueue(int customerId) {m_customers.emplace_back(new Customer(customerId));}// 处理队列中的下一个客户 void dequeue() {if (m_customers.empty()) {std::cout Queue is empty. std::endl;return;}// 获取并移除队列头部的客户 auto customer std::move(m_customers.front());m_customers.pop_front();// 处理客户在这里只是打印信息 customer-print();// 客户处理完毕后智能指针会自动释放内存 }// 显示队列中的客户数量 size_t size() const {return m_customers.size();}// 队列中的客户数量是否为空 bool empty() {return m_customers.empty();}private:std::dequestd::unique_ptrCustomer m_customers; // 使用智能指针的deque
};第三步实现 main 函数 最后需要在 main 函数中实例化 QueueSystem 对象并使用它的方法来模拟排队系统。
int main()
{QueueSystem system;// 添加客户到队列 system.enqueue(1);system.enqueue(2);system.enqueue(3);// 显示队列中的客户数量 std::cout Number of customers in queue: system.size() std::endl;// 处理队列中的客户 while (!system.empty()) {system.dequeue();}return 0;
}上面的代码的输出为
Number of customers in queue: 3
Customer ID: 1
Customer ID: 2
Customer ID: 3在这个示例中QueueSystem 类使用 std::dequestd::unique_ptr来存储等待处理的客户。客户通过 enqueue 方法添加到队列的尾部而 dequeue 方法则从队列的头部移除并返回一个客户。由于 std::deque 在尾部插入和头部删除操作上的高效性这个排队系统可以快速地处理大量的客户。
1.2 std::deque 应用于撤销与重做功能
在使用 std::deque 来实现撤销与重做功能时其优势在于能够高效地在队列两端添加和删除元素。对于撤销操作可以将操作存储在一个 std::deque 中并允许用户撤销最近的操作。对于重做操作可以简单地从队列的另一端取出操作并执行。由于 std::deque 支持两端操作它非常适合这种撤销/重做场景。
以下是一个使用 std::deque 实现撤销与重做功能的示例
第一步定义 SimpleAction 类 首先需要定义一个 SimpleAction 类该类负责具体的执行、撤销与重做职责。
#include iostream
#include deque
#include memory
#include string // 定义一个操作类包含执行、撤销与重做的方法
class SimpleAction
{
public:SimpleAction(const std::string description): m_description(description) {}void execute() {std::cout Executing: m_description std::endl;// 执行操作的代码 }void undo() {std::cout Undoing: m_description std::endl;// 执行撤销操作的代码 }void redo() {std::cout Redoing: m_description std::endl;// 执行重做操作的代码 }private:std::string m_description;
};第二步定义 UndoRedoManager 类 UndoRedoManager 类负责维护历史记录以及重做队列并且通过创建一个包含“执行”和“撤销”操作对的方法实现了具体的撤销与重做功能。
class UndoRedoManager
{
public:void execute(std::unique_ptrSimpleAction action) {// 执行操作 action-execute();// 将操作添加到历史记录中 m_actions.emplace_back(std::move(action));// 清空重做队列 m_redoActions.clear();}void undo() {if (m_actions.empty()) {std::cout No more actions to undo. std::endl;return;}// 获取并执行最后一个操作的撤销过程 auto lastAction std::move(m_actions.back());m_actions.pop_back();lastAction-undo();// 将操作添加到重做队列中 m_redoActions.emplace_front(std::move(lastAction));}void redo() {if (m_redoActions.empty()) {std::cout No more actions to redo. std::endl;return;}// 获取并执行最后一个操作的重做过程 auto lastAction std::move(m_redoActions.front());m_redoActions.pop_front();lastAction-redo();// 将操作添加到历史记录中 m_actions.emplace_front(std::move(lastAction));}private:std::dequestd::unique_ptrSimpleAction m_actions;std::dequestd::unique_ptrSimpleAction m_redoActions;
};第三步实现 main 函数 最后需要在 main 函数中测试 UndoRedoManager 的功能。
int main()
{UndoRedoManager manager;// 创建并执行一些操作 manager.execute(std::make_uniqueSimpleAction(Action 1));manager.execute(std::make_uniqueSimpleAction(Action 2));manager.execute(std::make_uniqueSimpleAction(Action 3));// 撤销操作 manager.undo();manager.undo();// 重做操作 manager.redo();return 0;
}上面的代码的输出为
Executing: Action 1
Executing: Action 2
Executing: Action 3
Undoing: Action 3
Undoing: Action 2
Redoing: Action 2注意如果操作非常多频繁的进行撤销与重做还可以考虑使用 std::deque 的 shrink_to_fit 方法来减少内存使用。
2 std::deque 与 std::vector 的对比
下面是 std::deque 和 std::vector 在几个关键方面的对比
内存布局和性能特性
std::vector通常std::vector 在内存中是一块连续存储的数组。这使得它在随机访问通过索引元素时非常高效因为可以直接通过偏移量计算得到元素地址。然而std::vector 在序列开始或中间插入或删除元素时可能需要重新分配和复制内存这会导致较高的开销。std::dequestd::deque 通常是以一系列固定大小的块chunks来实现的这些块可以在内存中独立分配和释放。因此std::deque 在序列的两端插入和删除元素时非常高效因为这些操作通常只需要改变一些指针或句柄而不需要移动大量元素。然而std::deque 的随机访问性能通常比 std::vector 差因为需要额外的间接引用。
空间效率
std::vector由于 std::vector 在内存中连续存储因此它在空间效率方面通常优于std::deque尤其是在存储大量数据时。std::deque由于 std::deque 使用多个独立的内存块它可能会引入一些额外的内存开销尤其是当存储的元素较小时。
迭代器失效
std::vector当 std::vector 进行插入或删除操作时可能会导致迭代器、引用和指针失效。特别是当在 std::vector 的开始或中间位置插入或删除元素时。std::deque相比之下std::deque 在两端插入或删除元素时不会使已存在的迭代器、引用和指针失效。
扩展和收缩
std::vector当 std::vector 的大小增长时它可能需要重新分配更大的内存块并将现有元素复制到新位置。这可能会导致额外的性能开销。同样当 std::vector 的大小减小时它可能会释放内存。std::dequestd::deque 的扩展和收缩通常是通过添加或删除内存块来实现的这些操作通常比 std::vector 的重新分配和复制要快。
初始化和填充
std::vector由于 std::vector 是连续存储的因此可以使用 std::vector::assign、std::vector::resize 等成员函数进行高效的初始化和填充。std::deque虽然 std::deque 的填充操作也可以很高效但它通常不如 std::vector 在连续内存上的操作那么快速。
总结来说选择std::deque还是std::vector取决于具体的使用场景
如果需要频繁在序列两端插入和删除元素并且不关心随机访问性能那么 std::deque 可能是更好的选择。如果需要高效的随机访问并且不经常在序列中间进行插入和删除操作那么 std::vector 可能更合适。
3 std::deque 与 std::list 的对比
下面是 std::deque 和 std::list 在几个关键方面的对比
内存布局和性能特性
std::dequestd::deque 通常是以一系列固定大小的块chunks来实现的这些块可以在内存中独立分配和释放。这使得 std::deque 在序列的两端插入和删除元素时非常高效因为这些操作通常只需要改变一些指针或句柄而不需要移动大量元素。然而由于需要额外的间接引用std::deque 的随机访问性能可能不如连续存储的容器。std::liststd::list 是一个双向链表每个元素都包含指向前一个和下一个元素的指针。这使得 std::list 在序列的任意位置进行插入和删除操作都非常高效因为只需要更新少数几个指针。与 std::deque 相比std::list 的随机访问性能较差因为需要遍历链表来访问特定位置的元素。
空间效率
std::deque由于 std::deque 使用多个独立的内存块它可能会引入一些额外的内存开销尤其是当存储的元素较小时。然而与 std::list 相比std::deque 通常更加空间高效因为 std::list 中的每个元素都需要存储额外的指针。std::list由于 std::list 的每个元素都包含指向前一个和下一个元素的指针因此它通常比 std::deque 更占用内存。
迭代器失效
std::deque在 std::deque 的两端插入或删除元素时不会使已存在的迭代器、引用和指针失效。然而在 std::deque 的中间进行插入或删除操作可能会使迭代器、引用和指针失效。std::list在 std::list 的任意位置进行插入或删除操作都不会使已存在的迭代器、引用和指针失效。这是因为 std::list 的插入和删除操作只涉及更新指针而不涉及移动元素。
扩展和收缩
std::dequestd::deque 的扩展和收缩通常是通过添加或删除内存块来实现的这些操作通常比连续存储的容器要快。然而当 std::deque 的大小增长时可能需要重新分配更大的内存块。std::liststd::list 的扩展和收缩是通过在链表中添加或删除节点来实现的这些操作通常很快因为它们只涉及更新指针。
初始化和填充
std::dequestd::deque 可以使用 std::deque::assign、std::deque::resize 等成员函数进行高效的初始化和填充。然而与 std::vector 相比std::deque 的填充操作可能不如连续存储的容器那么快速。std::liststd::list 的初始化和填充操作通常涉及在链表中添加节点这些操作相对较快但可能不如连续存储的容器那么高效。
总结来说选择std::deque还是std::list取决于具体的使用场景
如果需要频繁在序列两端插入和删除元素并且关心空间效率那么std::deque可能是更好的选择。如果需要在序列的任意位置进行高效的插入和删除操作并且不关心随机访问性能那么std::list可能更合适。
4 实现一个简单的 std::deque 容器
如下是一个简化的 std::deque 容器的实现主要体现 std::deque 的分段存储特性
#include iostream
#include memory
#include vector template typename T
class Deque {
private:struct Node {std::vectorT buffer;std::shared_ptrNode prev;std::shared_ptrNode next;Node() default;Node(const Node) delete;Node operator(const Node) delete;Node(Node other) noexcept : buffer(std::move(other.buffer)), prev(std::move(other.prev)), next(std::move(other.next)) {}~Node() {// 当Node被销毁时其管理的内存也会被自动释放 }};public:// 构造函数和析构函数 Deque(){auto newNode std::make_sharedNode();m_front newNode;m_back newNode;}~Deque() {clear();}// 禁用拷贝构造函数和赋值运算符 Deque(const Deque) delete;Deque operator(const Deque) delete;// 移动构造函数和移动赋值运算符 Deque(Deque other) noexcept : m_front(std::move(other.m_front)), m_back(std::move(other.m_back)), m_size(other.m_size) {other.m_size 0;}Deque operator(Deque other) noexcept {if (this ! other) {clear();m_front std::move(other.m_front);m_back std::move(other.m_back);m_size other.m_size;other.m_size 0;}return *this;}// 在队首插入元素 void push_front(const T value) {if (m_front m_front-buffer.size() NODE_CAPACITY) {push_front_node(value);}else {m_front-buffer.insert(m_front-buffer.begin(),value);m_size;if (m_front-buffer.size() 1) {m_back m_front;}}}// 在队尾插入元素 void push_back(const T value) {if (m_back m_back-buffer.size() NODE_CAPACITY) {push_back_node(value);}else {m_back-buffer.push_back(value);m_size;if (m_back-buffer.size() 1) {m_front m_back;}}}// 从队首移除元素 void pop_front() {if (m_front !m_front-buffer.empty()) {m_front-buffer.erase(m_front-buffer.begin());--m_size;if (m_front-buffer.empty()) {if (m_front m_back) {m_front.reset();m_back.reset();}else {auto nextNode m_front-next;nextNode-prev.reset();m_front nextNode;}}}}// 从队尾移除元素 void pop_back() {if (m_back !m_back-buffer.empty()) {m_back-buffer.pop_back();--m_size;if (m_back-buffer.empty()) {if (m_front m_back) {m_front.reset();m_back.reset();}else {auto prevNode m_back-prev;prevNode-next.reset();m_back prevNode;}}}}// 获取队首元素 T front() {if (empty()) {throw std::out_of_range(Deque is empty);}return m_front-buffer.front();}// 获取队尾元素 T back() {if (empty()) {throw std::out_of_range(Deque is empty);}return m_back-buffer.back();}// 检查deque是否为空 bool empty() const {return m_size 0;}// 获取deque的大小 size_t size() const {return m_size;}// 清除deque中的所有元素 void clear() {while (m_front) {pop_front();}}private:// 私有辅助函数用于在deque前端创建新节点 void push_front_node(const T value) {auto newNode std::make_sharedNode();newNode-buffer.push_back(value);newNode-next m_front;if (m_front) {m_front-prev newNode;}else {m_back newNode;}m_front newNode;m_size;}// 私有辅助函数用于在deque后端创建新节点 void push_back_node(const T value) {auto newNode std::make_sharedNode();newNode-buffer.push_back(value);newNode-prev m_back;if (m_back) {m_back-next newNode;}else {m_front newNode;}m_back newNode;m_size;}private:std::shared_ptrNode m_front;std::shared_ptrNode m_back;size_t m_size 0;static constexpr size_t NODE_CAPACITY 4; // 每个Node的缓冲区大小 };int main()
{Dequeint myDeque;// 在队首和队尾插入元素 myDeque.push_back(1);myDeque.push_back(2);myDeque.push_front(3);myDeque.push_front(4);// 输出Deque的元素 std::cout Front: myDeque.front() std::endl;std::cout Back: myDeque.back() std::endl;std::cout Size: myDeque.size() std::endl;// 从队首和队尾移除元素 myDeque.pop_front();myDeque.pop_back();// 再次输出Deque的元素 std::cout Front: myDeque.front() std::endl;std::cout Back: myDeque.back() std::endl;std::cout Size: myDeque.size() std::endl;return 0;
}上面代码的输出为
Front: 4
Back: 2
Size: 4
Front: 3
Back: 1
Size: 2在上面的代码中实现了一个简单的 std::deque 容器它使用了分段连续存储技术。每个 Node 包含一个 std::vectorT 作为缓冲区以及指向前后 Node 的 std::unique_ptr。当在 deque 的前端或后端添加元素时如果当前 Node 的缓冲区已满就会创建一个新的 Node并将元素添加到新 Node 的缓冲区中。同样地当从 deque 的前端或后端移除元素时如果导致某个 Node 变为空就会释放该 Node。
这个实现展示了 std::deque 的基本特性包括在队首和队尾高效地插入和移除元素以及访问队首和队尾元素。然而这个实现并不完整例如它没有提供迭代器支持、异常安全性保证也没有优化内存分配等。此外它也没有处理可能的内存分配失败情况。在实际应用中std::deque 的实现会更加复杂和健壮。
