<p dir="auto">As part of the stabilization process, we'd like our standard collection implementations to be <em>good</em>. Maybe even <em>great</em>. Wouldn't that be nice? The overall quality of each implementation is pretty varied, partially just because the language has dramatically shifted out from underneath them. Vec and HashMap are in a good place because they're The Big Dogs of data structuring, and have gotten substantial attention as a result. Other less-used collections are in worse shape, and need some serious attention.</p>
<p dir="auto">If you're interested in working on a Rust project, or collections in particular, here's a big list of things to do experiment with on libcollections.</p>
<ul class="contains-task-list">
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> DList's internal "safe" API is totally busted. It's not safe at all. Possibly simply because RawLink is Copyable. This allows a reference to a RawLink to be converted into a value, allowing mutation of an immutable DList.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> Investigate implementing a proper bidirectional cursor on DList that can insert/remove values. It's borderline useless without this.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> Full code review of BitV and BitVSet. They've had a lot of bugs because the code base has seen a lot of churn. Some legacy references to the bad-old-day of BitV being an enum still exist (such as a benchmark that just tests how fast bitshifting a uint is).</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="41020369" data-permission-text="Title is private" data-url="https://github.com/rust-lang/rust/issues/16736" data-hovercard-type="issue" data-hovercard-url="/rust-lang/rust/issues/16736/hovercard" href="https://github.com/rust-lang/rust/issues/16736">#16736</a> BitV's internal representation is a Vec of uints. It should almost certainly be a Vec of u32's, or some other non-machine-sized type.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> RingBuf <em>should not be</em> a Vec of Options.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> Investigate whether accepting total unsafety in TreeMap and using RawPtrs everywhere is worth it. May be necessary in a future full of scoped allocators.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> Replace the bulky triple of Vecs used in BTreeMap's Node struct with a single manually allocated<br>
buffer, in the same vein as HashMap's RawTable.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> Investigate a richer default B-selection algorithm for BTreeMap's default constructor than "6"</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox"> Investigate alternative node-search schemes over trivial linear search for BTreeMap. Binary search? skip-k-at-a-time linear search? Dynamic (or static!) selection of these algorithms based on B/K/V?</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> Seriously optimize BTreeMap <em>at all</em>. <em>At all</em>.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> Investigate the possibility of replacing the heap-allocated <code class="notranslate">Vec&lt;*mut Node&lt;T&gt;&gt;</code>-based search-stacks of BTreeMap, TreeMap, and TrieMap with a stack-allocated <code class="notranslate">[*mut Node&lt;T&gt;, ..uint::BITS]</code> (TreeMap might need more, it's an AA-tree, dunno how tall they can get). Note that a preliminary experiment on BTree gave very poor results, though it has the least to gain from such a design from it's current design (tracks depth, can use <code class="notranslate">with_capacity</code>.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> Investigate the possibility of reusing the SearchStack concept used in BTreeMap to more safely wrap the rawptr-based search stacks of TreeMap and TrieMap.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> Investigate the possibility of making the iterators for TreeMap and TrieMap DoubleEnded, rather than having separate forward/backward iterators.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> At very least, get rid of the old-style internal backwards iterator on TrieMap.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> Investigate the possibility of cutting out a lot of the macro-madness from TreeMap and TrieMap (BTreeMap has no macros and little-to-no code duplication, just hardcore generics). Possibly using the Deref/DerefMut trick in HashMap.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> Investigate completely replacing the unsafe rawptr search-stacks in the iterators of TreeMap and TrieMap with safe stacks of iterators over the nodes themselves, like BTreeMap does.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> Investigate arbitrary sub-range iterators for sorted sets/maps.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> Investigate functionality augmentations to a lot of collections iterators. For instance DList's iterator provides <code class="notranslate">peek_next</code> and <code class="notranslate">remove_next</code> methods for soundly removing elements from the list during iteration. At <em>least</em> Vec, RingBuf, and HashMap could all support this soundly, I believe. Vec, RingBuf, and DList could also support <code class="notranslate">insert_next</code>. Special iterator-like objects dedicated to these tasks might be better ideas, though (cursors, zippers, etc).</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="42940833" data-permission-text="Title is private" data-url="https://github.com/rust-lang/rust/issues/17320" data-hovercard-type="issue" data-hovercard-url="/rust-lang/rust/issues/17320/hovercard" href="https://github.com/rust-lang/rust/issues/17320">#17320</a> Implement the new Entry API on TreeMap and TrieMap.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox"> Investigate different hashing architectures and mechanisms for hash algorithm selection than the current one. For instance, our current stream-based architecture is poorly designed for small keys (e.g. u64's) which can and should be hashed in a single step.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox"> <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="38641004" data-permission-text="Title is private" data-url="https://github.com/rust-lang/rust/issues/15947" data-hovercard-type="issue" data-hovercard-url="/rust-lang/rust/issues/15947/hovercard" href="https://github.com/rust-lang/rust/issues/15947">#15947</a> Investigate making ordering-based collections <em>comparator</em> based rather than directly <em>Ord</em>-based using unboxed closures. Ord types should be supported through some kind of "natural comparator" that is reversible (for supporting reverse orderings). PriorityQueue in particular would like this to simplify min-vs-max-heap.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox"> Investigate optimizing PriorityQueue.extend with a modified heapify operation.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox"> Consider more slice utility methods. slice.rotate_left/right? slice.shift_and_replace_left/right?</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> Consider providing <code class="notranslate">split(&amp;mut self, at: Index) -&gt; Self</code> on some collections.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox"> Investigate tricks used in other languages to optimize for common/special access patterns.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox"> Tests! Code coverage!</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox"> Docs! Examples!</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox"> Detailed discussions of what individual collections are good/bad for.</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox"> Performance comparison tables (probably just assymptoticss</li>
<li class="task-list-item"><input type="checkbox" id="" disabled="" class="task-list-item-checkbox" checked=""> There was only one other checked box and it looked lonely so I made it a friend. :D</li>
</ul>
<p dir="auto">Tracking issue for the <code class="notranslate">fmt_flags_align</code> feature, which is <a href="https://doc.rust-lang.org/nightly/std/fmt/struct.Formatter.html#method.align" rel="nofollow"><code class="notranslate">fmt::Formatter::align</code></a> and the associated enum.</p>