> On Dec 5, 2017, at 2:48 PM, Jordan Rose via swift-dev <swift-dev@swift.org>
> wrote:
>
>
>
>> On Dec 4, 2017, at 18:48, Brent Royal-Gordon via swift-dev
>> <swift-dev@swift.org> wrote:
>>
>>> On Dec 2, 2017, at 12:31 PM, Cao, Jiannan via swift-dev
>>> <swift-dev@swift.org> wrote:
>>>
>>> I'd like to discuss the relation between RangeReplaceableCollection and
>>> MutableCollection
>>>
>>> MutableCollection is a Collection type that can { set } any element with
>>> subscript(position: Index). (and also { set } for subscript(range:
>>> Range<Index>))
>>>
>>> RangeReplaceableCollection requires a function replaceRange(_:with:)
>>>
>>> If a type conforms to RangeReplaceableCollection, it means any of its range
>>> can be replaced, that includes the situation to replace only one element.
>>> So if some type conforms to RangeReplaceableCollection, it is sufficient to
>>> be a MutableCollection.
>>> So I think the RangeReplaceableCollection should conforms to
>>> MutableCollection should inherits from MutableCollection.
>>
>>
>> I thought this too a couple years ago, but it's not really true.
>> `MutableCollection` requires not only that you be able to set elements, but
>> also that when you do so, it doesn't change any of the indices in the
>> collection. Some collections can't guarantee that. For example, `String`
>> can't conform to `MutableCollection` because if you set some character in
>> the middle of the string to a character that's a different size, it might
>> move characters later in the string to different indices. So Swift lets you
>> say `myString.replaceSubrange(myRange, with: newCharacters)`, but it doesn't
>> let you say `myString[myRange] = newCharacters`.
>>
>> `MutableCollection` and `RangeReplaceableCollection` are very similar in
>> that they both involve changing a collection. But they are different *kinds*
>> of changes to a collection, so it makes sense for a collection to support
>> either one of them without supporting the other.
>
> MutableCollection's subscript setter is also expected to take constant time
> (well, proportional to the size of a single element). That may not be the
> case for a range replacement implementation, even if it turns out the other
> elements in the collection don't have to move.
>
The most common example a
not-constant-time-element-updatable-but-still-range-replaceable-collection
being String, since graphemes can vary in width in the underlying buffer.
For an example of why this is important, see this optimization for removing
elements from a RangeReplaceableCollection:
https://github.com/apple/swift/pull/11576/files#diff-6290705036ea8e99c92cd1a8afc9494bR1095
When the collection is both range-replaceable and mutable, it can save time by
not re-allocating the whole buffer, and just shuffling elements down in-place.
But it needs to know that swapping two elements takes constant time for this to
be an improvement and not an accidentally-quadratic disaster.
> Jordan
> _______________________________________________
> swift-dev mailing list
> swift-dev@swift.org
> https://lists.swift.org/mailman/listinfo/swift-dev
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev
