Is it safe to assume that collection transformatio...

# announcements

[David Glasser]

Is it safe to assume that collection transformation functions like map return Lists whose get method is O(1)? If so, is that documented?

[Shawn]

well, map is defined as an extension method to a number of collection types

[Shawn]

the map you’re referring to is likely inline fun <T, R> Iterable<T>.map()

[David Glasser]

Right, that one.

[Casey Brooks]

I believe the default implementation is to map the results to an ArrayList, which gets mapped to the underlying platform-specific equivalent. I don’t think it’s specifically documented, but it’s easy enough to see by looking at the source

[Shawn]

which does return a List, but neither the Iterable nor List interfaces make any guarantee as to underlying access complexities

[David Glasser]

I can read the source and I know what it does. A colleague is wondering if it's ok to rely on this if you need the return value to be O(1)

[Shawn]

it really depends on what counts as “good enough” as a guarantee in your situation

[Shawn]

it’s my understanding that the language makes no guarantees as to what kind of List will be returned by that map function, but pragmatically speaking on the JVM it’s going to be ArrayList more likely than not

[Casey Brooks]

For a strict guarantee, you should probably use mapTo(ArrayList()) instead.

[David Glasser]

Hmm I guess you can add an extension function like if (this is Random Access) this else ArrayList(this)

[David Glasser]

There's nothing like that in the stdlib right? Your suggestion is nice though it misses the capacity calculation from the stdlib version

[David Glasser]

(I'm kind of of the opinion that in the Java/Kotlin world, if a function returns a LinkedList of non constant size you really need to document that fact, but technically it's legal)

[Shawn]

I’m not sure how your extension function would work in a general case - there is no Random Access interface or abstract type to match upon, but (edit: apparently there is) sure, you could do something like that, and there isn’t a semantically-comparable function available in the stdlib to my knowledge

[David Glasser]

There is such an interface... Unless it's internal to the stdlib?

[Casey Brooks]

Generally, I wouldn’t rely upon constant-time access for anything in a List, regardless of the type. Usually, you’d use a Map for guarantees of random-access time-complexity.

[Casey Brooks]

Lists are for iterating, Maps are for random access

[Shawn]

Would you care to enlighten me @David Glasser? I’m not familiar with the interface in question

[David Glasser]

https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-random-access.html

[Shawn]

oh wow, today I learned

[David Glasser]

Sure, but arrays are for random access by index if your data is usefully ordered!

[Shawn]

cool 👍

[David Glasser]

Me too!

[David Glasser]

The empty list class (which I don't think is public but is eg returned by listOf() implements it too

[Shawn]

I suppose new IndexOutOfBoundsException() is a O(1) operation 🤔