How to iterate over Dictionary.Values plus one additional element?

say i have a dictionary and an extra value like:

let dictionary:[X: Y]
let extra:Y

is there any way to achieve

for y:Y in [extra] + dictionary.values
{
    ...
}

without actually copying the dictionary values into a temporary array, as + does?

This isn’t built into the language, but Swift Algorithm’s chain function concatenates two arrays without allocations or copying so it probably fits the bill.

6 Likes

Perhaps you may move the loop body out into a function / closure:

func doSomething(_ y: Y) {
    ...
}

doSomething(extra)
dictionary.values.forEach(doSomething)

Below would probably also achieve what you want, but looks like overkill:

struct ArrayListIterator<T>: IteratorProtocol {
    private var iterators: [Array<T>.Iterator]
    
    init(_ arrays: [[T]]) {
        iterators = arrays.map { $0.makeIterator() }
    }
    
    mutating func next() -> T? {
        while !iterators.isEmpty {
            if let element = iterators[0].next() {
                return element
            }
            iterators.removeFirst()
        }
        return nil
    }
}

struct ArrayList<T>: Sequence {
    let arrays: [[T]]
    
    func makeIterator() -> ArrayListIterator<T> {
        ArrayListIterator(arrays)
    }
}

for v in ArrayList(arrays: [["a", "b", "c"], ["d"], ["e", "f"]]) {
    print(v, terminator: "")
}
print() // abcdef

This and CollectionOfOne from the standard library for creating a collection for one element without allocating.

3 Likes
deleted Is my understanding correct that the key difference between `chain()` and `+` (in the context of this question) is that `chain()` is a function and can take advantage of Swift's built-in COW support so it doesn't actually copies the value?

But isn't + an operator method also? Why does it have no COW behavior?

EDIT: I just realized + doesn't apply to dictionary. So let's take array as an example. I think line 3 in the code below doesn't actually copies the value, does it?

let arr1: [String] = ["a", "b"]
let arr2: [String] = ["c"]
let combined = arr1 + arr2

EDIT2: My mistake. The OP was looking for something equivalent to +.

/// Prepend an element before a sequence.
@inlinable public func chain<Element>(
  _ element: Element,
  _ sequence: some Sequence<Element>
) -> some Sequence<Element> {
  chain(CollectionOfOne(element), sequence)
}
for y in chain(extra, dictionary.values)

this ended up being the route i took, as it did not require me to add another external dependency to my project.

i do wish the chain(_:_:) function was part of the standard library.

1 Like

Because for COW + would have to return a different type from Array, storing each part separately. That’s not ideal in a lot of situations, storage-wise.

Just to confirm, do you mean the compiler doesn't use COW in the following code because it prefers to maintain combined variable's storage in a single place?

let arr1: [String] = ["a", "b"]
let arr2: [String] = ["c"]
let combined = arr1 + arr2

Does it makes a difference if I remove the temporary variable?

let arr1: [String] = ["a", "b"]
let arr2: [String] = ["c"]
for i in arr1 + arr2 {
    // do something
}

I think the OP thought the above code copied values to a temporary array (please correct me if I'm wrong), but I can't see how it differs from the chain() call (see Jessy's above code for example).

chain is lazy and returns a whole new type, so it doesn’t allocate new storage, just references the two arrays. The + operator allocates new storage for the result.

2 Likes

Right, this has nothing to do with copy-on-write because you're not making a copy of arr1 or arr2, you're making a new Array with different contents.

A particularly clever implementation of + might be able to reuse the storage from arr1 IFF malloc gave us enough extra space due to bucket rounding AND it was uniquely referenced going into +, but that's a pretty obscure trick, not something I would count on.

2 Likes

I guess the question is "can the result of array "+" be lazy". I have these answers:

  • no it can't as "+" returns Array and array is not lazy.
  • yes it can, if it returns some new "lazy" ArraySum type, that can be further converted to "Array" when needed like so: Array(arraySum). In the quoted "for i in ...." example conversion from lazy to non lazy array is not needed.
  • yes it can, but the resulting (lazy) Array would have strange properties (e.g. worse than O(1) subscript, which is obviously bad).
1 Like

It should have O(1) subscript. You just check if the index is before or after the first arrays’s endIndex.

and you do so for half of the subarrays on average (the corresponding iterators) which gives you O(K) complexity (where K is the number of sub arrays). Yes, K can be as small as 2, but at the same time it could be as large as N (each sub array holding a single element).

i believe this discussion has drifted far from the original issue, which is that we don’t have a standard way of augmenting a Sequence with an additional (appended or prepended) element without having to import third-party frameworks.

I myself would consider Swift Algorithms a first-party dependency given its official sponsoring by Apple. Only external dependency in its entire graph is Swift Numerics (also developed by Apple), and neither even make use of Foundation so they’re about as close to being standard library as you can get without actually being in it.

i don’t think the involvement of Apple or any specific company is relevant to the “third-party” designation. for example, i do not understand why depending on swift-algorithms is better than depending on swift-benchmark, simply because swift-algorithms is developed by Apple and swift-benchmark is developed by Google.

for me, “third-party” vs “official” is a technical distinction based on whether or not SPM must clone an external repository to build a package. so_Concurrency, Dispatch, Foundation, etc. are first-party, but Algorithms would not be.