4 ms·

Data structures with circular references are so incredibly rare in practice. I've occasionally needed to use a graph (sometimes even a cyclic one), and petgraph

Data structures with circular references are so incredibly rare in practice. I've occasionally needed to use a graph (sometimes even a cyclic one), and petgraph with integer indexes works fine for that. Other than that, I've been writing Rust full-time for over 7 years and really not needed them. The benefit is that for almost all code you get mutability xor aliasing, which I think is incredibly important to achieving correctness at scale.

dmitrygr 3y ago
> Data structures with circular references are so incredibly rare in practice A doubly-linked list enters the chat...
- sunshowers 3y ago
  Doubly-linked lists are incredibly rare, few people should ever use one and even fewer people should ever write one. In almost all cases vectors are better [1]. Rust's stdlib comes with one: https://doc.rust-lang.org/std/collections/struct.LinkedList.html https://doc.rust-lang.org/std/collections/struct.LinkedList.... [1] There are some cases where they're useful, e.g. when amortized O(1) append is not enough and you want actual O(1) append. But this matters to almost no one.
  - dmitrygr 3y ago
    > Doubly-linked lists are incredibly rare, few people should ever use one Umm... how do you propose implementing a queue or a stack cpu-efficiently and memory-efficiently using vectors?
    - sunshowers 3y ago
      In almost all cases, it is better to use a vector for both those data structures. Cache locality is king, memcpy is blazing fast, and pointer chasing is generally pretty bad for performance. For a stack, just use a regular vector. Pushes are amortized O(1), and pops are O(1). For a queue, a ring buffer backed by a vector. (This is how VecDeque in Rust's stdlib works.) Again, enqueue is amortized O(1) and dequeue is O(1). Even if you do need to use a linked list, it's generally better to depend on someone else's implementation than write your own.
      - dmitrygr 3y ago
        > it's generally better to depend on someone else I am the someone else who writes that, often enough… All y'all forget that behind your cute libraries and abstractions stands someone who wrote them in C or assembly…
        sunshowers 3y ago
        In that case, you'll find that Rust is an excellent language for writing doubly-linked lists. A lot of the point of Rust is to make a few people do the hard work of writing some complex data structure in unsafe code, and let everyone else reap the benefits.
        keybored 3y ago
        Where do I send the thank you card?
- keybored 3y ago
  > incredibly rare > doubly-linked lists Synonyms for application developers.

dmitrygr 3y ago

> Data structures with circular references are so incredibly rare in practice A doubly-linked list enters the chat...

sunshowers 3y ago
Doubly-linked lists are incredibly rare, few people should ever use one and even fewer people should ever write one. In almost all cases vectors are better [1]. Rust's stdlib comes with one: https://doc.rust-lang.org/std/collections/struct.LinkedList.html https://doc.rust-lang.org/std/collections/struct.LinkedList.... [1] There are some cases where they're useful, e.g. when amortized O(1) append is not enough and you want actual O(1) append. But this matters to almost no one.
- dmitrygr 3y ago
  > Doubly-linked lists are incredibly rare, few people should ever use one Umm... how do you propose implementing a queue or a stack cpu-efficiently and memory-efficiently using vectors?
  - sunshowers 3y ago
    In almost all cases, it is better to use a vector for both those data structures. Cache locality is king, memcpy is blazing fast, and pointer chasing is generally pretty bad for performance. For a stack, just use a regular vector. Pushes are amortized O(1), and pops are O(1). For a queue, a ring buffer backed by a vector. (This is how VecDeque in Rust's stdlib works.) Again, enqueue is amortized O(1) and dequeue is O(1). Even if you do need to use a linked list, it's generally better to depend on someone else's implementation than write your own.
    - dmitrygr 3y ago
      > it's generally better to depend on someone else I am the someone else who writes that, often enough… All y'all forget that behind your cute libraries and abstractions stands someone who wrote them in C or assembly…
      - sunshowers 3y ago
        In that case, you'll find that Rust is an excellent language for writing doubly-linked lists. A lot of the point of Rust is to make a few people do the hard work of writing some complex data structure in unsafe code, and let everyone else reap the benefits.
      - keybored 3y ago
        Where do I send the thank you card?
keybored 3y ago
> incredibly rare > doubly-linked lists Synonyms for application developers.