3 ms·

https://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_ wa

https://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 ago
Oh, 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]
- Manishearth 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? You learn to structure your code in a certain way. Design patterns from C++ will not necessarily carry over. It certainly is painful to program in Rust if you design your code as if it were C++. In practice, the stuff you talk of doesn't end up being a problem; Rust still lets you do all that just that it's different.
  - mehrdadn 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? > You learn to structure your code in a certain way. Design patterns from C++ will not necessarily carry over. Er... data structures with parent pointers and sibling pointers are "design patterns from C++" to you?
    - Manishearth 9y ago
      Using move constructors to keep them updated is a design pattern. Most such datastructures either get implemented with Rc/Weak (which has a performance cost but often not a problem), or with "unsafe", which lets you write Rust as if it were more like C++ (you still have types, but you now also have certain dangerous abilities that you use carefully). Rust provides you the tools to properly abstract this unsafe such that it stays within the implementation and doesn't leak. This is true for Vec and BTreeMap, for example. You're talking about arguing with the compiler but unsafe Rust is not much worse than regular C++ in this aspect (there are some differences), so you always have the ability to drop down to this place where the compiler won't fight you to do stuff like this. Generally you can abstract away low level datastructures as unsafe code that's safe to use from the outside (this is usually something you can manageably audit) and everything else stays safe. Most such datastructures exist as libraries or in the stdlib already.

mehrdadn 9y ago

Oh, 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]
Manishearth 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? You learn to structure your code in a certain way. Design patterns from C++ will not necessarily carry over. It certainly is painful to program in Rust if you design your code as if it were C++. In practice, the stuff you talk of doesn't end up being a problem; Rust still lets you do all that just that it's different.
- mehrdadn 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? > You learn to structure your code in a certain way. Design patterns from C++ will not necessarily carry over. Er... data structures with parent pointers and sibling pointers are "design patterns from C++" to you?
  - Manishearth 9y ago
    Using move constructors to keep them updated is a design pattern. Most such datastructures either get implemented with Rc/Weak (which has a performance cost but often not a problem), or with "unsafe", which lets you write Rust as if it were more like C++ (you still have types, but you now also have certain dangerous abilities that you use carefully). Rust provides you the tools to properly abstract this unsafe such that it stays within the implementation and doesn't leak. This is true for Vec and BTreeMap, for example. You're talking about arguing with the compiler but unsafe Rust is not much worse than regular C++ in this aspect (there are some differences), so you always have the ability to drop down to this place where the compiler won't fight you to do stuff like this. Generally you can abstract away low level datastructures as unsafe code that's safe to use from the outside (this is usually something you can manageably audit) and everything else stays safe. Most such datastructures exist as libraries or in the stdlib already.