https://kotlinlang.org logo
#announcements
Title
# announcements
d

David Glasser

09/16/2019, 5:14 PM
Is it safe to assume that collection transformation functions like
map
return Lists whose
get
method is O(1)? If so, is that documented?
s

Shawn

09/16/2019, 5:15 PM
well,
map
is defined as an extension method to a number of collection types
the
map
you’re referring to is likely
inline fun <T, R> Iterable<T>.map()
d

David Glasser

09/16/2019, 5:16 PM
Right, that one.
c

Casey Brooks

09/16/2019, 5:16 PM
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
s

Shawn

09/16/2019, 5:16 PM
which does return a
List
, but neither the Iterable nor List interfaces make any guarantee as to underlying access complexities
d

David Glasser

09/16/2019, 5:16 PM
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)
s

Shawn

09/16/2019, 5:17 PM
it really depends on what counts as “good enough” as a guarantee in your situation
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
c

Casey Brooks

09/16/2019, 5:18 PM
For a strict guarantee, you should probably use
mapTo(ArrayList())
instead.
👆 3
d

David Glasser

09/16/2019, 5:20 PM
Hmm I guess you can add an extension function like
if (this is Random Access) this else ArrayList(this)
There's nothing like that in the stdlib right? Your suggestion is nice though it misses the capacity calculation from the stdlib version
(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)
s

Shawn

09/16/2019, 5:24 PM
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
d

David Glasser

09/16/2019, 5:24 PM
There is such an interface... Unless it's internal to the stdlib?
c

Casey Brooks

09/16/2019, 5:24 PM
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.
Lists are for iterating, Maps are for random access
s

Shawn

09/16/2019, 5:25 PM
Would you care to enlighten me @David Glasser? I’m not familiar with the interface in question
s

Shawn

09/16/2019, 5:26 PM
oh wow, today I learned
d

David Glasser

09/16/2019, 5:26 PM
Sure, but arrays are for random access by index if your data is usefully ordered!
☝️ 1
s

Shawn

09/16/2019, 5:26 PM
cool 👍
d

David Glasser

09/16/2019, 5:26 PM
Me too!
The empty list class (which I don't think is public but is eg returned by listOf() implements it too
s

Shawn

09/16/2019, 5:30 PM
I suppose
new IndexOutOfBoundsException()
is a
O(1)
operation 🤔
5 Views