Open tapeinosyne opened 6 years ago
I'll note that BTreeMap
doesn't have reserve
/with_capacity
, so there is precedent for leaving it out.
append
wouldn't be hard to implement in the same vein as BTreeMap
, since a trie is inherently sorted. The same approach could be taken - create a "merged" iterator from the two tries and then construct a third trie from it.
drain
is an interesting one for a trie. The drain
method on Vec
allows for a range to be drained - the drain
method on HashMap
drains the entire HashMap
; BTreeMap
, on a cursory investigation, doesn't appear to have a drain
method. It would be easy to implement drain
like HashMap
- simply mem::replace
the trie itself with a new one, and then into_iter
the old. However, as a trie is an ordered mapping, it might make sense (and be fairly simple to) implement a drain
for all elements under a given prefix (implemented as a remove_prefix
and then .into_iter
.) It might also make sense to implement a drain
for all elements in a range... but that's a bit more difficult.
I think the reason drain doesn't exist on a BTreeMap is that the only reason to use drain vs move in a hasmap is that it preserves the allocated memory. That's not possible with a BTreeMap, so drain is no better than std::mem::take
.
For collections, it is generally desirable to match the standard library API where feasible. By and large,
qp_trie
already offers the methods one would expect from a trie, but there remain a few edges where the interface could be smoothed out to better fit the expectations created bystd
.The missing methods that can be immediately implemented with no internal changes are:
clear
is_empty
contains_key
Keys
iteratorValues
,ValuesMut
iteratorsSome that would require some work or discussion, but are clearly useful:
[x] O(1)
len
,(As already noted in the source.) While not strictly expected of a trie, constant-time length would make it easier to make iterators exactly sized, with benefits to allocation and serialization.
[ ]
drain
In
std
,Drain
iterators remove and yield a range of elements from a collection, without consuming the collection itself. (The specific behavior varies.) QP-tries could offer a draining prefix iterator, which would be roughly complementary toremove_prefix
.[ ]
retain
A convenience function to remove all elements that do not meet a given predicate.
At a glance, with the QP-tries being recursive, methods related to preallocation would require some significant restructuring to be effective, and the returns might be suspect:
[ ]
reserve
/with_capacity
[ ] specialized
append
(I jotted down a patch for the methods in the first section, and will follow up on the rest later on.)