c++ - 使用默认移动赋值运算符的 C++ 队列实现
问题描述
我和我的小组尝试根据以下堆栈代码示例在 C++ 中实现队列。
template<typename T>
class Stack {
private:
struct Node {
T data;
Node* next;
Node(T data, Node* next): data(data), next(next) {}
// No destructor here; it is a private inner class and would be slow
// to delete a chain of nodes this way!
};
private:
Node* head;
public:
Stack(): head(nullptr) {}
~Stack() {
while (head != nullptr) {
Node* old_head = head;
head = head->next; // update
delete old_head;
}
}
// Prohibit copy construction and copy assignment
Stack(Stack&) = delete;
Stack& operator=(Stack&) = delete;
// Wait wait I want to be able to move
Stack(Stack&&) = default;
Stack& operator=(Stack&&) = default;
public:
int getSize() {
int count = 0;
for (Node* n = head; n != nullptr; n = n->next) count++;
return count;
}
bool isEmpty() {
return head == nullptr;
}
void push(T x) {
head = new Node(x, head);
}
T pop() {
if (isEmpty()) {
throw underflow_error("Cannot pop from empty stack");
}
Node* nodeToDelete = head;
T poppedValue = head->data;
head = head->next;
delete nodeToDelete;
return poppedValue;
}
T peek() {
if (isEmpty()) {
throw underflow_error("Cannot peek into empty stack");
}
return head->data;
}
};
就像堆栈示例一样,我们尝试使用相同的想法为队列实现移动,包括默认的移动赋值运算符。这样做,我们在运行代码时遇到了诸如无效操作数错误、折叠堆栈帧等问题。
template < typename T >
class Queue {
private:
struct Node {
T data;
Node * next;
Node(T data, Node * next): data(data), next(next) {}
};
private: Node * head;
private: Node * tail;
public:
Queue(): head(nullptr), tail(nullptr) {}~Queue() {
while (head != nullptr) {
Node * old = head;
head = head -> next;
delete old;
}
}
Queue(Queue & ) = delete;
Queue & operator = (Queue & ) = delete;
Queue(Queue && ) = default;
Queue & operator = (Queue && ) = default;
public:
int get_size() {
int count = 0;
for (Node * n = head; n != nullptr; n = n -> next)
count++;
return count;
}
bool isEmpty() {
return head == nullptr;
}
void enqueue(T x) {
Node * temp = new Node {x, nullptr};
if (head == nullptr) {
head = temp;
tail = temp;
} else {
tail -> next = temp;
tail = temp;
}
}
T dequeue() {
if (isEmpty()) {
throw underflow_error("Cannot dequeue from empty queue");
}
Node * nodeToDelete = head;
T poppedValue = head -> data;
head = head -> next;
delete nodeToDelete;
return poppedValue;
}
};
我们最终制作了自己的移动赋值运算符,队列按预期工作。以下代码是我们最终得到的。
Template <typename T>
class Queue {
private:
struct Node {
T data;
Node *next;
Node(T data, Node *next) : data(data), next(next) {}
};
private:
Node *head;
private:
Node *tail;
public:
Queue() : head(nullptr), tail(nullptr) {}
~Queue() {
while (head != nullptr) {
Node *old = head;
head = head->next;
delete old;
}
}
Queue(Queue &) = delete;
Queue &operator=(Queue &) = delete;
Queue(Queue &&) = default;
Queue &operator=(Queue &&other) {
if (&other == this) {
return *this;
}
delete head;
head = other.head;
tail = other.tail;
other.head = nullptr;
other.tail = nullptr;
return *this;
}
public:
int get_size() {
int count = 0;
for (Node *n = head; n != nullptr; n = n->next) {
count++;
}
return count;
}
bool is_empty() {
return head == nullptr;
}
void enqueue(T x) {
Node *temp = new Node{x, nullptr};
if (head == nullptr) {
head = temp;
tail = temp;
} else {
tail->next = temp;
tail = temp;
}
}
T dequeue() {
if (is_empty()) {
throw underflow_error("Cannot dequeue from empty queue");
}
Node *nodeToDelete = head;
T poppedValue = head->data;
head = head->next;
delete nodeToDelete;
return poppedValue;
}
尽管我们最终选择了后一种实现,但我们真的很好奇为什么默认的移动赋值运算符适用于堆栈而不是队列。我们想知道是不是因为我们为类创建了自己的析构函数并禁用了复制运算符,但我们不确定。也许我们正在执行错误?任何帮助/反馈将不胜感激!
解决方案
通常,在动态内存分配方面,您应该始终考虑实现自己的移动赋值运算符和移动构造函数。
你的堆栈一似乎工作,但实际上它是不正确的。
尝试将这些添加到您的堆栈中,您将看到问题:
Stack <int> func() {
Stack <int> s;
s.push(3);
return s;
}
int main()
{
Stack <int> b;
b = func(); // assignment move
return 0;
}
func()
正在返回一个具有非空head
成员变量的堆栈(这很关键)- 离开时
func()
,局部变量s
被破坏 - 离开时
main()
,局部变量b
被破坏(这里有问题)
这就是为什么此代码会在您的堆栈中导致双重释放问题的原因。
(顺便说一句,您的队列分配移动运算符可能会导致内存泄漏,因为delete head;
可能不是您想要做的。)
推荐阅读
- eclipse - 在 tomcat 项目中构建 WAR 文件
- laravel - Laravel 计划任务无法访问模型的属性
- c# - 如何控制 grpc 中的写入缓冲区大小(或:如何处理 grpc 中的慢流读取器)?
- c# - 组合超过 3 个旋转(四元数)
- javascript - javascript:将相同和不同的键映射到不同的值
- python - 基于每行中至少一个元素的正则表达式匹配的新数据框列
- mysql - 从 mysql 查询返回一个连接的字符串
- javascript - 用户登录时不会显示表单和 div
- php - wordpress 如何实现 php 短代码
- r - h2o 交叉验证预测摘要中 AUC NaN 值的解释