3 ms·
> 99% of the move constructors in C++ are focused on making this work correctly. It's not necessary in Rust. There are the 1% that do stuff like the small strin
by mehrdadn 9y ago
> 99% of the move constructors in C++ are focused on making this work correctly. It's not necessary in Rust. There are the 1% that do stuff like the small string optimization. Yes, you can't do this as neatly in Rust.
Hm, so let's say had this binary tree in C++:
template<class T>
class Node {
Node(Node const &) = delete; // don't worry about copying for now
Node &operator =(Node const &) = delete;
unique_ptr<Node> a, b;
Node *parent;
T value;
public:
Node(Node &&other) : a(move(other.a)), b(move(other.b)), parent(move(other.parent)), value(move(other.value)) {
if (parent) {
if (parent->a == &other) { parent->a = this; }
if (parent->b == &other) { parent->b = this; }
}
other.parent = NULL;
}
}
You're saying I... can't have my binary tree in Rust?
- Manishearth 9y agohttps://doc.rust-lang.org/std/collections/struct.BTreeMap.html https://doc.rust-lang.org/std/collections/struct.BTreeMap.ht... you can't implement it _this_ way, but you can still implement a binary search tree (Btreemap is a b-tree, which is a generalization of a binary tree). Normally in Rust for a tree like structure with parent pointers you'd either use unsafe code or use Rc/Weak, depending on what you need. As far as binary search trees are concerned IIRC you can implement them without parent pointers, you'd move your relocation method to something called on the parent node.
- mehrdadn 9y agoOh, the parent pointer (or even the BST nature) wasn't really the point. The parent pointer was just an example that was easy to understand. For BSTs specifically, in C++, IIRC they use threading (= sibling pointers) to allow iterators O(1)-time access to the siblings in constant space, and those would have the same problems. And I didn't even mean to limit this to the BST case (I edited my comment while you were probably typing yours so you probably saw the version where I mentioned BSTs). In other non-BST binary trees you may well need a parent pointer for good time/space complexity, not merely find it convenient. Note that this isn't just limited to trees. Even doubly-linked lists would have this issue, as would other more-complex data structures. I guess my larger point is, it seems like the repercussions aren't just limited to missing low-level optimizations like small-string optimization like you claim, but they extend to your entire global object model as well as to what operations & time complexities you can support without the compiler yelling at you. That seems quite painful to me. Who wants to constantly argue with the compiler as to whether or not he should be allowed to have parent/sibling/other pointers?
- viraptor 9y ago> Who wants to constantly argue with the compiler as to whether or not he should be allowed to have parent/sibling/other pointers? People who value "I'm sure this can't explode", over "I'm pretty sure it won't explode, but at least it's a fast template that can stack-allocate" ;-) But seriously - you can still do a lot of that if you really need to for some reason. Either use an external library in C++ or write some unsafe code which won't restrict your pointers.
- mehrdadn 9y ago> But seriously - you can still do a lot of that if you really need to for some reason. Either use an external library in C++ or write some unsafe code which won't restrict your pointers. How would unsafe code help here? The problem we were talking about was the lack of move constructors, and I just gave an example of their usefulness with parent pointers. How would unsafe code help? Unsafe code doesn't suddenly give you move constructors does it? (As for writing external C++ code and linking to it... I mean yeah, but if the entire object model you have to interact with has to be in C++, then you might as well write the whole code in C++ at that point...)
- Manishearth 9y ago> How would unsafe code help? Unsafe code doesn't suddenly give you move constructors does it? Unsafe code lets you store parent pointers as raw pointers and update them manually when you move things. You don't actually _want_ a move constructor here; your btree values are on the heap anyway; what you want is a .move() method that chains correctly, and you can write this in Rust. In C++ the move constructor is a convenient way of doing this but not the only way. Move constructors are how you organize the code in C++. Rust will not support the same code organization. This does not mean it's not doable in Rust, just that you have to design it differently. Rust is not C++; this is ok.
- deleted 9y ago[deleted]