lilyball / swift-deque

A double-ended queue collection for Swift
Apache License 2.0
8 stars 1 forks source link

Consder adding Deque.makeContiguous() #4

Open lilyball opened 3 years ago

lilyball commented 3 years ago

Deque can have either contiguous or noncontiguous storage depending on mutation patterns. It supports providing a pointer to its backing storage if and only if it's contiguous. It also makes certain guarantees about indices after mutation as long as it doesn't transition between contiguous and noncontiguous storage.

Right now, if I need to force a Deque to be contiguous, the only practical way to do this is to force a copy into a new Deque using something like Deque(AnySequence(deque)). Not only is this awkward, it also forces a copy even if the source was already contiguous.

To that end, we may want to add a deque.makeContiguous() method that ensures the storage is contiguous. We may also want to add optional parameters for asserting sufficient capacity before/after the contiguous storage, to allow for guarantees about indices and contiguous storage availability after appending/prepending elements.

lilyball commented 3 years ago

Question: With the parameters to assertion sufficient pre/post capacity, would we want this to behave like reserveCapacity in that it can shrink the capacity if it has to reallocate? I'm inclined to say yes.