Efficiently aggregating an array of non-optionals without a default value

Question

I need to efficiently aggregate an array of non-optional values, knowing its size, having a way to get its values, but not having a default value.

Following is a rather synthetic example, resembling what I need. It won't compile, but it will give you the idea:

public func array<A>( count: Int, getValue: () -> A ) -> Array<A> {
  var array = [A](count: count, repeatedValue: nil as! A)
  var i = 0
  while (i < count) {
    array[i] = getValue()
    i++
  }
  return array
}

Please note that the result of type Array<A?> won't do, I need non-optionals. Also note that the solution must be efficient, it must not do any extra traversals.

Answer 1

You can make a working function from your example code by using the append() method to add array elements:

public func array<A>(count: Int, @noescape getValue: () -> A) -> [A] {
    var array = [A]()
    array.reserveCapacity(count)
    for _ in 0 ..< count {
        array.append(getValue())
    }
    return array
}

The @noescape attribute tells the compiler that the passed closure does not outlive the function call, this allows some performance optimizations, compare @noescape attribute in Swift 1.2.

But it is easier to use the map() method of CollectionType:

/// Return an `Array` containing the results of mapping `transform`
/// over `self`.
///
/// - Complexity: O(N).
@warn_unused_result
public func map<T>(@noescape transform: (Self.Generator.Element) throws -> T) rethrows -> [T]

In your case:

public func array<A>(count: Int, @noescape getValue: () -> A) -> [A] {
    let array = (0 ..< count).map { _ in getValue() }
    return array
}

Here map() transforms each integer in the range 0 ... count-1 to an array element. The underscore in the closure indicates that its argument (the current index) is not used.

I leave it to you to check which method is faster.

Example usage:

let a = array(10) { arc4random_uniform(10) }
print(a) // [3, 7, 9, 4, 2, 3, 1, 5, 9, 7] (Your output may be different :-)