4 ms·

> If so, why the implementation of LinkedList<T> doesn’t? Because the stdlib doesn't want to expose too many unsafe APIs on its datastructures, giving it freed

> If so, why the implementation of LinkedList<T> doesn’t? Because the stdlib doesn't want to expose too many unsafe APIs on its datastructures, giving it freedom to evolve the internals. And LinkedLists are considered a niche type anyway, not for general use. As kibwen mentioned, you are free to create your own linkedlist implementation that exposes this API. Rust has a heap, and you can free things directly if you need.

Const-me 10y ago
Let’s summarize. I want to implement efficient LRU cache data structure. In C++, I don’t need to spend time implementing and debugging my own linked lists, because standard library implementation already good enough for the task. I only need to encapsulate two standard containers together, and write a pair of methods to add/remove stuff. In Rust, I need to roll out my own lists, because stdlib doesn't want to expose too many unsafe APIs on its data structures. You agree with all of the above? If yes, hope now you see how Rust isn’t good enough for creating complex specialized data structures.
- Manishearth 10y ago
  That's a non sequitur. The choice made by thee stdlib to not support many linked list operations (there probably are crates in the ecosystem for this anyway) does not imply Rust is unsuitable for complex specialized datastructures. It implies that Rust has opinions about what should and shouldn't be in the stdlib. In fact, you said it yourself, "specialized". Since linkedlists are generally used in specific cases with different required ergonomics, you do not want to expose a catch-all.
  - Const-me 10y ago
    > That's a non sequitur. Why not? An LRU cache is moderately complex specialized data structure. As you see, for some reasons, it’s much simpler to implement in C++ then in Rust. > The choice made by thee stdlib to not support many linked list operations does not imply Rust is unsuitable for complex specialized data structures I never said it’s unsuitable. Technically, all modern programming languages are Turing complete, so in some sense they’re equivalent. I only said Rust isn’t good enough for that. Meaning, in many other languages doing that is much simpler than in Rust. Linked lists are special case of trees, which in turn special case of graphs. Both trees and graphs are used a lot: DOM trees, syntax trees, KD/PK trees, quad edge graphs, and so on. Rust’s memory management model is neither manual nor garbage collected. This feature makes it hard to implement those pointer-based data structures, where items are in shared ownership of the container, where you want to split/merge those containers, and move items across containers. Not impossible, just hard and/or inefficient (like those ref.counted implementation that increment/decrement those counters each time I traverse the graph, even if I only reading stuff).
    - Manishearth 10y ago
      > it’s much simpler to implement in C++ then in Rust. Because of the standard library. This is not a language issue, this is a library issue. This has nothing to do with Rust's memory model. It has to do with Rust's choices of having a smaller, maintainable stdlib and relying on the crates ecosystem for most libraries (which can then evolve independently of the language, which is nice). Someone has to write a linkedlist implementation of the type you describe and put it in a crate, and that's it; everyone can use that. It should be trivial to make a pull request to https://github.com/contain-rs/linked-list https://github.com/contain-rs/linked-list to add the method you describe, for example. -------- Edit: Rust does make it harder to implement the bottom level of low level abstractions (doubly linked lists, LRU caches, etc), since these deal with memory the most and can easily become unsafe. You implement them once with a safe API, and use them as much as you want. The reason std doesn't expose too many unsafe APIs on its datastructures is because if you need that level of control, it is better to have your own implementation. Safety is hard; and the more unsafe APIs you expose, the more you run the risk of external unsafe code depending on the internals of the implementation in the stdlib. Due to this, it would be preferred if you write the LRU cache with a linkedlist implementation embedded in it (which could be a separate crate for reusability), with the invariants well documented. This is a choice made by the stdlib, but has nothing to do with the language itself and is a choice that external crates are free to not follow.
      - Const-me 10y ago
        > Rust does make it harder to implement the bottom level of low level abstractions Yeah, prohibitively harder. If you really need an efficient linked list, or tree, or graph, Rust makes it nearly impossible to accomplish. > The reason std doesn't expose too many unsafe APIs on its datastructures is because if you need that level of control, it is better to have your own implementation This might be true for Rust, but the argument is language-specific. In C++ I often need “that level of control” and yet I’m happy with many stock implementations. Moreover, I can combine different data structures to produce whatever I need. Can’t in Rust, because the library designers (not just std, the rest of them as well) think I better have my own implementation if I need that level of control. > Safety is hard Not necessarily. C# is very safe, and yet it’s much friendlier to developers: I never used unsafe C# code to overcome language limitations, only to interop with unmanaged code.

Const-me 10y ago

Let’s summarize. I want to implement efficient LRU cache data structure. In C++, I don’t need to spend time implementing and debugging my own linked lists, because standard library implementation already good enough for the task. I only need to encapsulate two standard containers together, and write a pair of methods to add/remove stuff. In Rust, I need to roll out my own lists, because stdlib doesn't want to expose too many unsafe APIs on its data structures. You agree with all of the above? If yes, hope now you see how Rust isn’t good enough for creating complex specialized data structures.

Manishearth 10y ago
That's a non sequitur. The choice made by thee stdlib to not support many linked list operations (there probably are crates in the ecosystem for this anyway) does not imply Rust is unsuitable for complex specialized datastructures. It implies that Rust has opinions about what should and shouldn't be in the stdlib. In fact, you said it yourself, "specialized". Since linkedlists are generally used in specific cases with different required ergonomics, you do not want to expose a catch-all.
- Const-me 10y ago
  > That's a non sequitur. Why not? An LRU cache is moderately complex specialized data structure. As you see, for some reasons, it’s much simpler to implement in C++ then in Rust. > The choice made by thee stdlib to not support many linked list operations does not imply Rust is unsuitable for complex specialized data structures I never said it’s unsuitable. Technically, all modern programming languages are Turing complete, so in some sense they’re equivalent. I only said Rust isn’t good enough for that. Meaning, in many other languages doing that is much simpler than in Rust. Linked lists are special case of trees, which in turn special case of graphs. Both trees and graphs are used a lot: DOM trees, syntax trees, KD/PK trees, quad edge graphs, and so on. Rust’s memory management model is neither manual nor garbage collected. This feature makes it hard to implement those pointer-based data structures, where items are in shared ownership of the container, where you want to split/merge those containers, and move items across containers. Not impossible, just hard and/or inefficient (like those ref.counted implementation that increment/decrement those counters each time I traverse the graph, even if I only reading stuff).
  - Manishearth 10y ago
    > it’s much simpler to implement in C++ then in Rust. Because of the standard library. This is not a language issue, this is a library issue. This has nothing to do with Rust's memory model. It has to do with Rust's choices of having a smaller, maintainable stdlib and relying on the crates ecosystem for most libraries (which can then evolve independently of the language, which is nice). Someone has to write a linkedlist implementation of the type you describe and put it in a crate, and that's it; everyone can use that. It should be trivial to make a pull request to https://github.com/contain-rs/linked-list https://github.com/contain-rs/linked-list to add the method you describe, for example. -------- Edit: Rust does make it harder to implement the bottom level of low level abstractions (doubly linked lists, LRU caches, etc), since these deal with memory the most and can easily become unsafe. You implement them once with a safe API, and use them as much as you want. The reason std doesn't expose too many unsafe APIs on its datastructures is because if you need that level of control, it is better to have your own implementation. Safety is hard; and the more unsafe APIs you expose, the more you run the risk of external unsafe code depending on the internals of the implementation in the stdlib. Due to this, it would be preferred if you write the LRU cache with a linkedlist implementation embedded in it (which could be a separate crate for reusability), with the invariants well documented. This is a choice made by the stdlib, but has nothing to do with the language itself and is a choice that external crates are free to not follow.
    - Const-me 10y ago
      > Rust does make it harder to implement the bottom level of low level abstractions Yeah, prohibitively harder. If you really need an efficient linked list, or tree, or graph, Rust makes it nearly impossible to accomplish. > The reason std doesn't expose too many unsafe APIs on its datastructures is because if you need that level of control, it is better to have your own implementation This might be true for Rust, but the argument is language-specific. In C++ I often need “that level of control” and yet I’m happy with many stock implementations. Moreover, I can combine different data structures to produce whatever I need. Can’t in Rust, because the library designers (not just std, the rest of them as well) think I better have my own implementation if I need that level of control. > Safety is hard Not necessarily. C# is very safe, and yet it’s much friendlier to developers: I never used unsafe C# code to overcome language limitations, only to interop with unmanaged code.