I'm curious as to why Kotlin Set
s have indices. You can access elements by using mySet.elementAt(index)
. No other language I know has this feature. Is the feature any useful if sets aren't supposed to be ordered and yet they have indices? Also, doesn't this feature make Set
s in Kotlin slower than other Set
s in other languages?
CodePudding user response:
Set
has the elementAt
method, not because it is based on indices (so it is not "slower than other languages" just because it has this method), but because it implements Iterable<T>
. elementAt
is an extension function on Iterable<T>
:
fun <T> Iterable<T>.elementAt(index: Int): T
What a Set
is based on depends on which concrete implementation of Set
you use (Set
is just an interface). HashSet
is based on a hash table, for example.
So Set
gets this elementAt
method "for free" just because it implements Iterable<T>
. The only way for it to not have elementAt
is to not implement Iterable<T>
, but that would mean you can't iterate over a Set
. That's not very useful, is it? Also, as I'll talk about later, elementAt
does have its uses.
Since elementAt
is an extension function on Iterable<T>
, all it can do really, is to ask to the iterator to give it n elements, and return the last element. This is how it is implemented.
public fun <T> Iterable<T>.elementAt(index: Int): T {
if (this is List)
return get(index)
return elementAtOrElse(index) { throw IndexOutOfBoundsException("Collection doesn't contain element at index $index.") }
}
...
public fun <T> Iterable<T>.elementAtOrElse(index: Int, defaultValue: (Int) -> T): T {
if (this is List)
return this.getOrElse(index, defaultValue)
if (index < 0)
return defaultValue(index)
val iterator = iterator()
var count = 0
while (iterator.hasNext()) {
val element = iterator.next()
if (index == count )
return element
}
return defaultValue(index)
}
If your Set
does not have a particular order (e.g. HashSet
), then its iterator will return elements in no particular order either, so using elementAt(x)
is not very meaningful. On the other hand, if you are using an ordered set, like a LinkedHashSet
(this is what setOf
and mutableSetOf
creates), then using elementAt
does make sense.
Also note that elementAt
does have O(n) time, but that doesn't mean that accessing the set using the set's methods (e.g. contains
) also has O(n) time. That also depends on which concrete implementation of Set
you use. Both LinkedHashSet.contains
and HashSet.contains
are O(1) time.