Why is `Dictionary[position:]` not settable?

the Dictionary type exposes a non-nil subscript [position:] which takes a Dictionary.Index. i always wondered why this subscript is get-only, since i often find myself wanting to check if a key-value pair is present in the dictionary, and then mutate the value only if it exists.

if let index:Dictionary<Foo, Bar>.Index = dictionary.index(forKey: key)
{
    dictionary[index].someMutatingMethod()
}

can we add a setter to this subscript, so that the above code will work?

Without commenting on the position subscript, if you have a key and want to mutate the value at that key if it’s in the dictionary, you can use optional chaining:

dictionary[key]?.someMutatingMethod()

It even works with mutating assignments:

dictionary[key]? += 4
2 Likes

that’s a possible workaround, but in general, the goal of storing dictionary indices is to avoid repeated key lookups. what if you want to call more than one mutating method? or if you want to store an index, and come back to it later?

1 Like

You can't really meaningfully store index for later mutations. Things might have already shifted by then. Even writing to the same index might move the slots depending whether you write nil to it.

the elements do not shift if you do not insert or remove values. in this case, i am simply mutating values that already exist in the dictionary.

That design would require the dictiinary[index] to return non-optional. :thinking: I can't figure out how it would work even if I have access dictionary internals. Feels like something pretty hard to guardrail.

Maybe a new Dictionary.OccupiedIndex :thinking::thinking:.

Dictionary[position:] already is non-optional.

1 Like

Hmm, right. I guess dictionary[valueAt: index] would be theoretically possible :thinking:.

The value referenced by the subscript is not the mutable value, but the pair of the immutable key and mutable value.

With that in mind, do you have ideas on how such a setter would work - perhaps check the equatable/hashable of the set key against the key at the current index and and fatalError() if modified?

1 Like

right. probably it would be better to provide a new subscript like the Dictionary[valueAt:] subscript @Lantua proposed

1 Like

Because Swift.Dictionary conforms to Collection, not to MutableCollection (hence the get-only subscript via index) and it cannot conform to MutableCollection cause it wouldn't be possible to have the subscript's setter via Dictionary.Index perform in O(1): modifying a Dictionary.Element means you'd also have the possibility to modify the key value. That would be an operation which requires first eliminating the old key from the underlaying hash table (eventually moving any colliding key in the underlaying hash table to new positions), after that calculating the position in the hash table for the new element key and setting it… which could be a key already present in the hash table… All of this work is not guaranteed to be done with an O(1) complexity, which is a requirement for Collection and MutableCollection subscript.
Not to mention also that changing that element key means also you'd might be potentially changing the value of another element with the new key already present in the dictionary and which obviously resides at a different index than the one currently accessed.
Thus Dictionary —which has unique keys— needs the additional subscription via key as setter/modifier and cannot use a subscription via its indices as a mutator.

More in general though, the lack of an intermediate official protocol for data structures which would be ideally placed between Sequence and Collection is an old problem for who wants to implement data structures in Swift.
There are data structures which are sequences with non destructive iteration (as per Collection) and whose subscript via index can have a complexity of O(n) or O(log n), as well as obtaining startIndex and endIndex in that same complexity magnitude rather than O(1).
They could adhere to an official protocol called a Pile, QueueProtocol, or whatever fancier, and it would also be an opportunity for official implementations of OrderedSet, OrderedDictionary, SortedSet, SortedDictionary, PriorityQueue, RandomQueue, Bag, etc.

That would be possible, but it wouldn't make so much sense having given the key subscripts works perfectly well for mutating values.
Plus you could do that via subscripting the values property of the dictionary which shares the same indices of the dictionary and has a mutating subscript. For example assuming you have a dictionary of type [String:Int], you can already do:

    dictionary.values[dictionary.startIndex] += 1
    dictionary.values[dictionary.startIndex..<dictionary.endIndex] *= 10
    …

etc.

1 Like

Dictionary's index-based subscript returns a key-value pair, so making it mutable would mean that someone could change the key at a particular index. That would be bad news, since the index is derived from the key's hash value (plus a bit of extra work). You'd up in a situation where either mutating the key-value pair at a particular index moves that pair to a different index (which breaks the MutableCollection requirements) or the dictionary is no longer maintaining the correct invariants about where keys live and all the rest of your interaction with the dictionary falls apart.

Happily, the collection of values via the .values property is mutable and shares its index type with its parent dictionary, so you can mutate using the index:

var letters = ["a": 1, "b": 2]
if let i = letters.index(forKey: "b") { 
    letters.values[i] += 10 
} 
// letters == ["a": 1, "b": 12]
23 Likes

Doesn't MutableCollection require that the subscript's setter can't invalidate indices? That would also be violated if subscript(position:) had a setter.

It is not explicitly stated in the definition of MutableCollection, but the part where it states that:

a[i] = x
let y = a[i]

// Must be equivalent to:
a[i] = x
let y = x

Could be seen as not invalidating indices stored priorly the operation took effect.
The MutableCollection definition though talks about “same position” not “same index”, which could be ambiguous.
Indeed it should explicitly state that previously stored indices must not be invalidated when the subscript mutator is used.

Exactly as you said it.

That is to resolve any possible ambiguity leading to potential MutableCollection implementations where “distance” might be seen as the offset of the index from startIndex, making perfectly fine doing this:

let clone = a
let i = a.index(a.startIndex, offsetBy: 3)
a[i] = newValue
// a copies its storage, clone 
// retains old storage

let j = a.index(a.startIndex, offsetBy: 3)
let y = a[j] 
// y == newValue
let x = a[i]
// runtime error cause i is no longer valid
// or worse x == oldValue cause i points to
// the old storage kept alive by clone. 

That interpretation of MutableCollection might also lead to implementations were it would not be possible to fast-iterate indices and using its mutator subscript inside the loop.

Anyway for sure in the case of Dictionary the index based subscript mutator might end up removing a key-value pair and modifying another element already present in the Dictionary at a different “position” than the one specified in the subscript.

Thus ending up affecting the count of elements of the dictionary —which is an operation prohibited by MutableCollection— and also breaking the other rule about the “position” of the element mutated.

1 Like
Terms of Service

Privacy Policy

Cookie Policy