Reuse BitField Allocations

[Stebalien]

When taking the union, difference, and intersection between two bitfields by-value (or at least one by-value), we should be able to reuse the allocations.

Difference/Intersection

These can be done as in-place filtermaps of one of the ranges.

• In the intersection case, this works if we can take either of the ranges by-value.
• In the difference case, this works if we have the left range by-value.

Union

Union is a bit trickier, but we can still avoid too many allocations.

1. Perform an in-place "filter" between the two ranges such that they both end up containing in-order non-overlapping elements. Starting with two fingers at the first elements of both range vectors.
   1. If the left range comes strictly before the right, advance the left finger.
   2. If the ranges overlap, extend the left range to cover both, advance the right finger.
   3. If the right range comes strictly before the left, advance the right finger and increment an extend counter.
2. Grow the left vector by the extend counter.
3. Starting at the ends of the vectors, walk backwards performing a sorted merge into the end of the left vector. If two ranges overlap, take the range from the left vector and ignore the range in the right vector (we previously extended the left range to include the right range).

While this requires two passes, it requires at most one allocation (if the left vector doesn't have enough capacity). The current iterative approach will keep allocating in power of two sizes.

This only requires one of the bitfields to be by-value.