Better alternative to the “reverse-and-popLast” pattern?

i’m finding myself writing a lot of array-related code that looks like:

        var elements:[Element]  = self.elements
        self.elements           = []
        elements.reverse()
        while var element:Element = elements.popLast()
        {
            ...
        }

this is obviously very awkward and its only real purpose is to prevent copy-on-write from getting triggered when element is mutated. has anyone found a better approach compared to this pattern?

Doesn't a Deque fit well here? You get cheap prefix removals, and can just mutate your self.elements in-place

for me at least, this kind of thing is showing up in those sorts of RandomAccessCollection-conforming “container” types that use an Array<T> as their backing storage. these types do not themselves support Deque-like operations, and changing them all to use a Deque as their backing storage instead seems excessive, especially since Deque is not part of the standard library…

the most recent time i ran into this was when i was writing a simple array “merge” function that combines two sorted arrays (or more precisely, an Array and a Sequence, which may or may not conform to BidirectionalCollection) into a single sorted array. this does not strike me as something that ought to require a Deque.

ArraySlice.popFirst() is O(1). Also iterators might be an option.

2 Likes

this is not true. ArraySlice holds a reference to the underlying Array instance, which in turn holds a reference to all of the elements in the Array, including elements not included in the ArraySlice itself. this means that ArraySlice.popFirst() cannot transfer exclusive ownership to bound variable. if Element is, say, a nested Array, the entire sub-array will be copied. in a use-case such as updating a single scalar element in each sub-array, this could turn an O(n) algorithm into an O(n^2) algorithm.

1 Like

I'm not sure if I've understood what you're saying here correctly, but ArraySlice.popFirst() should itself be O(1), without needing to mutate anything about the underlying Array. Its popFirst implementation is inherited from Collection:

extension Collection where SubSequence == Self {
  /// Removes and returns the first element of the collection.
  ///
  /// - Returns: The first element of the collection if the collection is
  ///   not empty; otherwise, `nil`.
  ///
  /// - Complexity: O(1)
  @inlinable
  public mutating func popFirst() -> Element? {
    // TODO: swift-3-indexing-model - review the following
    guard !isEmpty else { return nil }
    let element = first!
    self = self[index(after: startIndex)..<endIndex]
    return element
  }
}

The slice itself is reformed with a new range, without needing to copy since it just refers to the same underlying buffer. If you're talking about mutating the slice and having to write back through to the original array, that does get a bit trickier — but that didn't seem indicated from your original post.

if the original parent array is of type, say [[Int]], then the popFirst() call itself will indeed be O(1), but any operations performed on the return value will be O(n) due to copy-on-write. however i was able to solve my problem after realizing i could use the original array as ‘scratch space’ by iterating over indices (which can be used to subscript into a _modify accessor) and performing the mutation in-place within the original array, and then transfer the updated value to its destination as needed without recursive copying.

4 Likes

Came to suggest this, glad you already found it.

1 Like

Got it, agreed. I realize I had meant to elaborate a little bit further in my comment about multiple indirection as that was what I had understood you to mean, but this covers it more clearly.

Glad this ended up with a clean and performant solution!

1 Like
Terms of Service

Privacy Policy

Cookie Policy