Swift: Array and ArraySlice (Xcode 7.3, Swift 2.2; updated Xcode 8 beta 6, Swift 3)


** Jump to Swift 3 code **

Before we begin

A great debt in writing this post is owed to a presentation by AirspeedVelocity at a Swift London event held in the Facebook offices in 2015. There he went into the depths of how arrays and other types are stored and copied in memory. Here I'm looking at a far more basic level aimed at the practical implications of Array and ArraySlice when coding.

Array

Let's consider a humble array of type Array<Int>:
var array = [1,2,3,4,5,6,7,8,9,10]
If we want to retrieve the first item in the array we can do the following:
let firstItem = array.first
Or we can subscript the array like so:
let firstItem = array[0]
In both instances we retrieve an Int value.

Slicing

Now let's suppose we take a range from the original array to create a new one:
let slice = array[1...7] // [2, 3, 4, 5, 6, 7, 8]
for i  in slice {
    i
}
slice.first // 2
As you'll see we can do pretty much all the things that are available to us with an array with this subarray. But now let's try using subscripting:
let firstItem = slice[0] // error!
And we get an error. Why? Because as it turns out there is no index 0, the start index of the ArraySlice is 1, as we can see when we write:
let startIndex = slice.startIndex // 1
An ArraySlice is a part of an Array and its indices remain the same as they were inside the original array. We cannot rely on the assumption that [0] will be the first item in a subarray or ArraySlice and neither can we rely on count-1 being the final value:
let lastItem = slice[slice.count-1] // 7
Note: It instead returns the penultimate value in this instance not the final one as we would expect from array[array.count-1].

Losing the connection

While indices are shared between Array and ArraySlice and even memory addresses, this doesn't mean that an ArraySlice behaves like a pointer to a class. This non-pointer like behaviour is demonstrated here:
var arr1 = [1,2,3,4,5,6,7]
var slice1 = arr1[1...4]
arr1[1] = 10
slice1[1] // 2

arr1.dropFirst()
slice1.first // 2
The slice does not mutate along with the original array. As we would expect when working with class-based types, e.g.
let arrNS:NSMutableArray = [1,2,3,4,5,6,7]
let arrNS2 = arrNS
arrNS2[1] // 2
arrNS[1] = 10
arrNS2[1] // 10
As with arrays themselves the behaviour of the ArraySlice type is on the surface (no matter what happens in memory) one of copying not pointing:
var arr1 = [1,2,3,4,5,6,7]
var arr2 = arr1
arr1[1] = 10
arr2[1] // 2
And this is how it should always be treated when coding. The only difference being that when the copy is made in the case of ArraySlice, it is made along with the original indices.

Instantiating an Array with an ArraySlice

Now lets try replacing the original array with this subarray.
array = slice // error!
Again, error! While Array and ArraySlice share common methods and adopt the same protocols they are different types. Swift being strongly typed will not for that reason allow one to be exchanged for another. Unless we first instantiate an Array using the ArraySlice:
array = Array(slice) // OK!
Now we have the array that we were perhaps expecting first of all:
array.startIndex // 0
let firstValue = array[0] // 2
But let's rewind a bit because the fact that Array and ArraySlice are not instantly swappable doesn't mean they are entirely incompatible. We can as we have seen instantiate an Array using an ArraySlice, but we can also append a slice to an array and make comparisons.
array.appendContentsOf(slice)
array.elementsEqual(slice)
While the elements might be equal the Array and the ArraySlice cannot be compared for equality
array == slice // error!
unless we write our own function of what we consider to be equatable:
func ==(lhs:Array, rhs:ArraySlice) -> Bool {
    return lhs == Array(rhs)
}
Here we ignore the difference of an Array and an ArraySlice seeing both as equal. It matters not whether we transform the ArraySlice into an Array or the Array into an ArraySlice to make the comparison, since the equality of an ArraySlice does not depend on its indices being the same as another, only its values and their order.
func ==(lhs:Array, rhs:ArraySlice) -> Bool {
    return ArraySlice(lhs) == rhs
}
And now the rules of equality are the same as for a regular comparison between Arrays or ArraySlices as between the two. (It is you who must decide whether code like this is desirable for your own implementation.)

Conclusion

Accessing the first and last items in an Array, or ArraySlice, is simple:
array.first
slice.last
But use of startIndex and endIndex can feel cumbersome and it can be off-putting, until we see the possible consequences when an ArraySlice is passed where perhaps we were thinking we were working with an Array. Now the utilising of the startIndex and endIndex don't seem like such a bad idea:
slice[slice.startIndex.advancedBy(2)...slice.startIndex.advancedBy(4)] // 4, 5, 6 
Remember also the protection you are afforded by being able to set a limit to the advancedBy: method:
slice[slice.startIndex.advancedBy(2, limit:slice.endIndex.predecessor())...slice.startIndex.advancedBy(10, limit:slice.endIndex.predecessor())] // 4, 5, 6, 7, 8
The benefits of all this are, as AirspeedVelocity pointed out in his presentation mentioned at the beginning of this post, that subarrays are only copied when necessary. If it's not necessary to make a copy and all work can be done within the boundaries of an ArraySlice, then this is typically how Swift does it. By referencing the same memory address as the original array. So while your default might be to transform every ArraySlice to a new Array for simplicity, it might be worth thinking first of all whether this is necessary.

Further reading

'Slicing for Speed: Understanding the Slice type in Swift' (Nate Cook)
'Status of Slice in Swift' (Marcin Krzyzanowski)

Further thoughts: Choosing between Array and ArraySlice as a return type

While the following method takes elements from an array it doesn't maintain the original indices (see closing note below), and therefore it makes no sense to utilise ArraySlice as the return type, since an ArraySlice needs to not only be a part of an Array but also needs to maintain the original indices for each element. This retaining of original indices does not occur because there is no such thing as a non-contiguous range type in Swift that would provide us with a way to create an ArraySlice that contained non-contiguous indices.
extension Array {
    func step(from from: Index, to:Index, interval: Int) -> Array<Element> {
        let stride = from.stride(to: to, by: interval)
        var arr = Array<Element>()
        for i in stride {
           arr.append(self[i])         
        }
        return arr
    }
}
let steps = array.step(from: array.startIndex, to:array.endIndex, by: 2)

Swift 3 (Xcode 8, beta 6) version

extension Array {
    func step(from: Index, to:Index, interval: Int) -> Array<Element> {
        let strde = stride(from: from, to: to, by: interval)
        var arr = Array<Element>()
        for i in strde {
            arr.append(self[i])
        }
        return arr
    }
}
let array = [1,2,3,4,5,6]
let steps = array.step(from: array.startIndex, to:array.endIndex, interval: 2)

Array Slice with Non-Contiguous Indices (Xcode 7.3, Swift 2.2)

To achieve an array slice that has non-contiguous indices we'd need to build our own, so here's a start:
struct NonContiguousArraySlice<T> {
    private var array:Array<ArraySlice<T>>
    
    init(array arr:Array<ArraySlice<T>>) {
        array = arr
    }
    var startIndex:Int {
        if let first = array.first {
            return first.startIndex
        }
        else {
            return 0
        }
    }
    var endIndex:Int {
        if let last = array.last {
            return last.endIndex
        }
        else {
            return 0
        }
    }
    
    var count:Int {
        return array.count
    }
    subscript(a:Int) -> T? {
        for i in array {
            if a > self.endIndex || a < self.startIndex {
                return nil
            }
            if i.startIndex == a {
                return i.first
            }
        }
        return nil
    }
    
}
protocol SubscriptingTypes {
    
}
extension Array.Index: SubscriptingTypes {
}
extension Range: SubscriptingTypes {
}
extension Array {
    
    init(noncontiguous a:NonContiguousArraySlice<Element>) {
        self = Array(a.array.flatten())
    }
    
    // TODO: Random selection from range method
    func randomSelection(length:Int) -> NonContiguousArraySlice<Element> {
        var arr = Array<ArraySlice<Element>>()
        var picker:Set<Int> = []
        srandomdev()
        repeat {
           picker.insert(random()%(arr1.count - 1))
        }
        while picker.count < length
        for i in picker {
            arr.append(self[i...i])
        }
        arr = removeDuplicatesAndSortSlices(arr)
        return NonContiguousArraySlice(array: arr)
    }
    
    subscript(a:SubscriptingTypes, b:SubscriptingTypes, c:SubscriptingTypes...) -> NonContiguousArraySlice<Element> {
        var arr = Array<ArraySlice<Element>>()
        if let aa = a as? Index {
        arr.append(self[aa...aa])
        }

        else if let aa = a as? Range<Index> {
            for i in aa {
                arr.append(self[i...i])
            }
        }
        if let bb = b as? Index {
            arr.append(self[bb...bb])
        }
        else if let bb = b as? Range<Index> {
            for i in bb {
                arr.append(self[i...i])
            }
        }
        for i in c {
            if let ii = i as? Index {
                arr.append(self[ii...ii])
            }
            else if let ii = i as? Range<Index> {
                for i in ii {
                    arr.append(self[i...i])
                }
            }
        }
        arr = removeDuplicatesAndSortSlices(arr)
        return NonContiguousArraySlice(array: arr)
    }

    
    func removeDuplicatesAndSortSlices(arr:Array<ArraySlice<Element>>) -> Array<ArraySlice<Element>> {
        var inds:[Index] = []
        let reducedArr = arr.reduce(Array<ArraySlice<Element>>(), combine: {(arr,t) in
            if !inds.contains(t.startIndex) {
                inds.append(t.startIndex)
                return arr + [t]
            }
            else {
                return arr
            }
            
        })
        return reducedArr.sort({$0.startIndex < $1.startIndex})
        
    }
}

let arr1 = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
let noncontigSlice = arr1[1,4,5]
noncontigSlice[4] // 5
noncontigSlice[5] // 6
noncontigSlice[2] // nil
noncontigSlice[15] // nil

let arrayFromRanges = arr1[2..<3, 1..<7, 1..<7] // doesn't matter that ranges cross over
arrayFromRanges[0] // nil
arrayFromRanges.count // 6

let mixedSliced = arr1[2..<3,5,7,9..<14]
mixedSliced.endIndex // 14
mixedSliced.endIndex
mixedSliced.count
Array(noncontiguous:arrayFromRanges) // [2, 3, 4, 5, 6, 7]
Array(noncontiguous:mixedSliced) // [3, 6, 8, 10, 11, 12, 13, 14]

// the numeral 6 number of items required in noncontiguous slice
let randSelection = arr1.randomSelection(6)
randSelection.startIndex // 0
randSelection.endIndex // 13
randSelection.count // 6

Array(noncontiguous: randSelection) // [1, 2, 4, 8, 10, 13] 
each slice maintaining its original indices.

Swift 3 (Xcode 8, beta 6) version

struct NonContiguousArraySlice<T> {
    internal var array:Array<ArraySlice<T>>
    
    init(array arr:Array<ArraySlice<T>>) {
        array = arr
    }
    var startIndex:Int {
        if let first = array.first {
            return first.startIndex
        }
        else {
            return 0
        }
    }
    var endIndex:Int {
        if let last = array.last {
            return last.endIndex
        }
        else {
            return 0
        }
    }
    
    var count:Int {
        return array.count
    }
    subscript(a:Int) -> T? {
        for i in array {
            if a > self.endIndex || a < self.startIndex {
                return nil
            }
            if i.startIndex == a {
                return i.first
            }
        }
        return nil
    }
    
}
protocol SubscriptingTypes {
    
}
extension Array.Index: SubscriptingTypes {
}
extension Range: SubscriptingTypes {
}
extension Array {
    
    init(noncontiguous a:NonContiguousArraySlice<Element>) {
        self = Array(a.array.joined())
    }
    
    // TODO: Random selection from range method
    func randomSelection(length:Int) -> NonContiguousArraySlice<Element> {
        var arr = Array<ArraySlice<Element>>()
        var picker:Set<Int> = []
        srandomdev()
        repeat {
            picker.insert(Int(arc4random_uniform(UInt32(arr1.count - 1))))
        }
            while picker.count < length
        for i in picker {
            arr.append(self[i...i])
        }
        arr = removeDuplicatesAndSortSlices(arr: arr)
        return NonContiguousArraySlice(array: arr)
    }
    
    subscript(a:SubscriptingTypes, b:SubscriptingTypes, c:SubscriptingTypes...) -> NonContiguousArraySlice<Element> {
        var arr = Array<ArraySlice<Element>>()
        if let aa = a as? Index {
            arr.append(self[aa...aa])
        }
            
        else if let aa = a as? Range<Index> {
            for i in aa.lowerBound..<aa.upperBound {
                arr.append(self[i...i])
            }
        }
        if let bb = b as? Index {
            arr.append(self[bb...bb])
        }
        else if let bb = b as? Range<Index> {
            for i in bb.lowerBound..<bb.upperBound {
                arr.append(self[i...i])
            }
        }
        for i in c {
            if let ii = i as? Index {
                arr.append(self[ii...ii])
            }
            else if let ii = i as? Range<Index> {
                for i in ii.lowerBound..<ii.upperBound {
                    arr.append(self[i...i])
                }
            }
        }
        arr = removeDuplicatesAndSortSlices(arr: arr)
        return NonContiguousArraySlice(array: arr)
    }
    
    
    func removeDuplicatesAndSortSlices(arr:Array<ArraySlice<Element>>) -> Array<ArraySlice<Element>> {
        var inds:[Index] = []
        let reducedArr = arr.reduce(Array<ArraySlice<Element>>(), {(arr,t) in
            if !inds.contains(t.startIndex) {
                inds.append(t.startIndex)
                return arr + [t]
            }
            else {
                return arr
            }
            
        })
        return reducedArr.sorted(){$0.startIndex < $1.startIndex}
        
    }
}

let arr1 = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
let noncontigSlice = arr1[1,4,5]
noncontigSlice[4] // 5
noncontigSlice[5] // 6
noncontigSlice[2] // nil
noncontigSlice[15] // nil

let arrayFromRanges = arr1[2..<3, 1..<7, 1..<7] // doesn't matter that ranges cross over
arrayFromRanges[0] // nil
arrayFromRanges.count // 6

let mixedSliced = arr1[2..<3,5,7,9..<14]
mixedSliced.endIndex // 14
mixedSliced.endIndex
mixedSliced.count
Array(noncontiguous:arrayFromRanges) // [2, 3, 4, 5, 6, 7]
Array(noncontiguous:mixedSliced) // [3, 6, 8, 10, 11, 12, 13, 14]

// the numeral 6 number of items required in noncontiguous slice
let randSelection = arr1.randomSelection(length: 6)
randSelection.startIndex // 0
randSelection.endIndex // 13
randSelection.count // 6

Array(noncontiguous: randSelection) // [1, 2, 4, 8, 10, 13]


Closing note

Along with ArraySlice there is also a Slice type and a MutableSlice type. The latter conforming to a MutableSliceable protocol. (Note: originally there was a Sliceable protocol, which all these types adhered to as well, but this was renamed collection type.) In the header file we see these detailed notes above Slice and find other similar notes for the other related types:
/// A view into a sub-sequence of elements of another collection.
///
/// A `Slice` instance stores the base collection, the start and end indices of
/// the view.  It does not copy the elements from the collection into separate
/// storage. Thus, creating a slice has `O(1)` complexity.
///
/// A `Slice` instance inherits the value or reference semantics of the base
/// collection.  That is, if a `Slice` instance is wrapped around a mutable
/// colection that has value semantics (for example, `Array`), mutating the
/// original collection would not affect the copy stored inside of the slice.
///
/// An element of a slice is located under the same index in the slice and in
/// the base collection, as long as neither the collection or the slice were
/// mutated.  Thus, indices of a slice can be used interchangibly with indices
/// of the base collection.
///
/// - Warning: Long-term storage of `Slice` instances is discouraged.
///
///   Because a `Slice` presents a *view* onto the storage of some larger
///   collection even after the original collection goes out of scope, storing
///   the slice may prolong the lifetime of elements that are no longer
///   accessible, which can manifest as apparent memory and object leakage.  To
///   prevent this effect, use slices only for transient computation.
We can use this Slice type in the following way:
let array = [1,2,3,4,5]
let slice = Slice(base: array, bounds: 1..<3)

A word of warning

Apple is clear to point out in its documentation that you should "use ArraySlice only for transient computation" because retaining an ArraySlice may extend the life of the original array beyond what is intended, which can lead to problems.

Comments