Match std::collections API

[tapeinosyne]

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 by std.

The missing methods that can be immediately implemented with no internal changes are:

• clear
• is_empty
• contains_key
• Keys iterator
• Values, ValuesMut iterators

Some that would require some work or discussion, but are clearly useful:

• 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 to remove_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.)

[sdleffler]

I'll note that BTreeMap doesn't have reserve/with_capacity, so there is precedent for leaving it out.

[sdleffler]

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.

[sdleffler]

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.

[erikbrinkman]

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.