Home > database >  Why do Kotlin Sets have indices?
Why do Kotlin Sets have indices?

Time:10-11

I'm curious as to why Kotlin Sets 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 Sets in Kotlin slower than other Sets 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.

  • Related