c++ - 带有 std::unique_ptr 的 BST:在参数中使用右值引用有什么区别?
问题描述
为了练习,我正在使用二叉搜索树和带有智能指针的红黑树。
节点如下:
template <typename T>
struct BSTNode {
T key;
std::unique_ptr<BSTNode<T>> left;
std::unique_ptr<BSTNode<T>> right;
BSTNode<T>* succ;
BSTNode(const T& key) : key {key}, succ {nullptr} {}
};
在这里,succ
表示有序继任者,因为我正在解决 CLRS 12.3-5,它说要在没有与父级链接的情况下进行锻炼。
无论如何,这段代码运行愉快:
void Transplant(BSTNode<T>* u, std::unique_ptr<BSTNode<T>>&& v) {
auto p = Parent(u);
if (!p) {
root = std::move(v);
} else if (u == p->left.get()) {
p->left = std::move(v);
} else {
p->right = std::move(v);
}
}
void Delete(BSTNode<T>* z) {
if (!z) {
return;
}
BSTNode<T>* pred = nullptr;
if (z->left) {
pred = Maximum(z->left.get());
} else {
auto y = Parent(z);
auto x = z;
while (y && x == y->left.get()) {
x = y;
y = Parent(y);
}
pred = y;
}
pred->succ = z->succ;
if (!z->left) {
Transplant(z, std::move(z->right));
} else if (!z->right) {
Transplant(z, std::move(z->left));
} else {
auto y1 = z->right.get();
std::unique_ptr<BSTNode<T>> y;
if (!y1->left) {
y = std::move(z->right);
} else {
while (y1->left) {
y1 = y1->left.get();
}
y = std::move(Parent(y1)->left);
}
if (Parent(y.get()) != z) {
Transplant(y.get(), std::move(y->right));
y->right = std::move(z->right);
}
y->left = std::move(z->left);
Transplant(z, std::move(y));
}
}
相反,当我在子例程“移植”中删除右值引用时,它给出了段错误:
void Transplant(BSTNode<T>* u, std::unique_ptr<BSTNode<T>> v) { // crashes
auto p = Parent(u);
if (!p) {
root = std::move(v);
} else if (u == p->left.get()) {
p->left = std::move(v);
} else {
p->right = std::move(v);
}
}
Delete
崩溃发生在,的第 18 行Transplant(z, std::move(z->right));
。
这里有什么区别?有人告诉我std::unique_ptr
s 通常是按值传递的。
此外,Transplant
没有右值引用的代码已经在节点与其父节点有链接的 BST 代码中工作。我不明白为什么。
解决方案
当您通过unique_ptr
值传递时,您会丢失原始指针:
void use_ptr(std::unique_ptr<int>) {}
std::unique_ptr<int> ptr = std::make_unique<int>(999);
use_ptr(std::move(ptr));
// here ptr no longer contains a pointer to 999
assert(!ptr);
std::cout << *ptr; // this is UB
当您通过右值引用传递它时,原始指针在函数调用后保持非空:
void use_ptr(std::unique_ptr<int>&&) {}
std::unique_ptr<int> ptr = std::make_unique<int>(999);
use_ptr(std::move(ptr));
// ptr still manages a pointer to `999`
assert(ptr);
std::cout << *ptr; // this is not UB
std::move
它本身不会移动任何东西,它只是使某些东西成为 xvalue 的演员表。当您std::unique_ptr<int>
从该 xvalue 构造参数时,实际的移动就会发生 - 一旦您构造了一个 new std::unique_ptr<int>
,您就失去了原来的那个。当你经过时,&&
你不构造任何东西,你只是传递一个引用。
考虑这个调用:
Transplant(z, std::move(z->right));
和
void Transplant(BSTNode<T>*, std::unique_ptr<BSTNode<T>>)
inside Transplant
,z->right
是一个unique_ptr
不拥有任何东西的 , z->right.get() == nullptr
,因为您刚刚从它移到了第二个Transplant
参数。
推荐阅读
- sdn - 如何使带有 RYU SDN 的 mininet 在 iperf 流量下正常工作?
- android - 通过 Instagram 相机在 Spark AR 中的 Android 上水平居中 2d 元素的问题
- c# - 如何从 C# 中列出使用/未使用的本机库?
- asp.net-core - Asp.Net Core 3.1 Web 应用程序,找不到 Api 页面问题
- ios - 如何使用适用于 iOS 的 Admob (google) 设置 MoPub 中介?
- node.js - 电子构建器在詹金斯上失败:ENOENT:没有这样的文件或目录,copyfile elevate.exe
- php - Mailchimp addListMember 在已经存在时返回客户端错误 400 错误请求
- swagger - Azure Functions 和 Swagger UI - 如何在 Swagger UI 中显示查询字符串参数?
- openlayers-6 - OpenLayers 基础层(OSM)不如 osm.org 流畅
- c# - C#如何绘制一个像素宽度的线