Containers - meta-issue to talk about quality of containers, what should be replaced, etc #3863
Comments
|
This is an important issue. My general plan is to remove the existing Right now we don't offer any functional-style persistent data structures other than |
|
An interesting thought: one could implement persistent/functional data structures based on ARCs, as well. |
|
I think making all container types sendable and freezable is a good default. I think the libs should shy away from managed types unless they're mandated by the data structure (eg. a circular list or a list / tree that supports tail-sharing). While there are some advantages to chaining over open addressing, I don't feel they're substantial enough in a language with automatic memory management (esp. one with owning pointers, engineered around swapping). I think if someone wants a "small" hashmap entry they can just make the value type ~V rather than V. We can make this space/speed tradeoff clear in the docs. Given our very pleasant randomized / strong hash function, I think a double-hashed open address table should be default there. The second (...Nth) hash function can be derived from the key values in the table: just use k+n. The default TreeMap should be an LLRB tree, yes. Imperative, to match the Map interface. I don't think the functional interface matters much for sendable types. We should have a different interface for managed (@), substructure-sharing maps: Tries and functional LLRBs at least satisfy this. Various HAMTs and Heaps do too. FunMap? ManagedMap? PersistMap? I'm not sure how to name that. Given that core is merging with rt and we want to implement as much of rt as possible in rust itself, I think it reasonable to move a few primary container types into core. Not every possible container ever, but the Normal Bunch Every Program Uses: the Map trait, HashMap and TreeMap, a small variety of Lists (sendable, managed, circular), Sets (Tree and Hash), Queue (unsafe, double-ended, circular) and Heap (vector-based). |
|
By the way, I started doing some of the work towards refactoring the map trait (you see the |
|
I think Persistent* is a good naming scheme. Other languages (like Clojure) use this naming as well to differentiate between those and the imperative versions. |
|
I think it would be best to close this issue and coordinate on this wiki page instead. Issues can be opened for individual bugs, features and wanted containers. I've worked on a lot on related issues since this was opened/discussed, so the issues discussed here are mostly dealt with. Summary of changes since this was opened:
|
rustfmt fails to format this match expression, because it has several long string literals over the maximum line width. This seems to exhibit rustfmt issues rust-lang#3863 (Gives up on chains if any line is too long) and rust-lang#3156 (Fail to format match arm when other arm has long line).
rustfmt fails to format this match expression, because it has several long string literals over the maximum line width. This seems to exhibit rustfmt issues rust-lang#3863 (Gives up on chains if any line is too long) and rust-lang#3156 (Fail to format match arm when other arm has long line). Format it with a large line width (e.g., by setting `max_width = 200` in rustfmt.toml) and, in case the rustfmt bugs are later fixed, mark it with `#[rustfmt::skip]`, as it is more legible with each case on one line.
rustfmt fails to format this match expression, because it has several long string literals over the maximum line width. This seems to exhibit rustfmt issues rust-lang#3863 (Gives up on chains if any line is too long) and rust-lang#3156 (Fail to format match arm when other arm has long line). Format it with a large line width (e.g., by setting `max_width = 200` in rustfmt.toml) and, in case the rustfmt bugs are later fixed, mark it with `#[rustfmt::skip]`, as it is more legible with each case on one line.
rustfmt fails to format this match expression, because it has several long string literals over the maximum line width. This seems to exhibit rustfmt issues rust-lang#3863 (Gives up on chains if any line is too long) and rust-lang#3156 (Fail to format match arm when other arm has long line).
…braheemdev Fix long lines which rustfmt fails to format rustfmt fails to format this match expression, because it has several long string literals over the maximum line width. This seems to exhibit rustfmt issues [rust-lang#3863](rust-lang/rustfmt#3863) (Gives up on chains if any line is too long) and [rust-lang#3156](rust-lang/rustfmt#3156) (Fail to format match arm when other arm has long line). Format it with a large line width (e.g., by setting `max_width = 200` in rustfmt.toml) and, in case the rustfmt bugs are later fixed, mark it with `#[rustfmt::skip]`, as it is more legible with each case on one line.
…braheemdev Fix long lines which rustfmt fails to format rustfmt fails to format this match expression, because it has several long string literals over the maximum line width. This seems to exhibit rustfmt issues [rust-lang#3863](rust-lang/rustfmt#3863) (Gives up on chains if any line is too long) and [rust-lang#3156](rust-lang/rustfmt#3156) (Fail to format match arm when other arm has long line). Format it with a large line width (e.g., by setting `max_width = 200` in rustfmt.toml) and, in case the rustfmt bugs are later fixed, mark it with `#[rustfmt::skip]`, as it is more legible with each case on one line.
Rollup merge of rust-lang#136606 - thaliaarchi:format-long-lines, r=ibraheemdev Fix long lines which rustfmt fails to format rustfmt fails to format this match expression, because it has several long string literals over the maximum line width. This seems to exhibit rustfmt issues [rust-lang#3863](rust-lang/rustfmt#3863) (Gives up on chains if any line is too long) and [rust-lang#3156](rust-lang/rustfmt#3156) (Fail to format match arm when other arm has long line). Format it with a large line width (e.g., by setting `max_width = 200` in rustfmt.toml) and, in case the rustfmt bugs are later fixed, mark it with `#[rustfmt::skip]`, as it is more legible with each case on one line.
One of the main things people often look at standard libraries for are good containers.
Right now, as far as I can tell, there are the following containers:
HashMap - in std/map.rs - a chained hash-table, with the usual performance characteristics (expected constant time access, insert, removal, no order, no comparing)
LinearMap - in core/send_map.rs - open addressing hash table, sendable (same general behavior as above, but sendable)
TreeMap - in std/treemap.rs - unbalanced binary search tree, very bad pathological inputs, is ordered, can be compared
FunTreeMap - in std/fun_treemap.rs - looks to be the same as above, but without mutation.
SmallIntMap - in std/smallintmap.rs - wee! constant time everything, ordered, comparable! oh yeah, space order the maximum key :)
So here are some questions I have:
Any thoughts people have about containers? Time permitting, I might work on a red-black tree implementation to replace the TreeMap.
Related issues (that I found): #3385, #2009
The text was updated successfully, but these errors were encountered: