list literal gotcha and suggestion

Neal Gafter neal at
Wed Oct 7 10:02:08 PDT 2009

On Wed, Oct 7, 2009 at 9:15 AM, Reinier Zwitserloot <reinier at
> wrote:

> Will you stop beating around the bush? What is it then?
> What will this code print, and will the call to test() take O(1) or O(n)
> time?
> public class Test {
>     public void test(Collection<?> t) {
>         System.out.println(t.size());
>         System.out.println(t.contains("Hello"));
>     }
>     public static void main(String[] args) {
>         test({"a", "b", "c", "a", "b", "c", /* 99,993 more strings */,
> "Hello"});
>     }
> }
> Will it take O(N) time and print '100000\ntrue\n', or will it take O(1)
> time and print '99997\ntrue\n'?

In practice, this will fail to compile because the size of the bytecode
required to express the body of the main method doesn't fit within the JVM's

Ignoring that for a moment, I would expect it to take O(N) time to construct
the collection, because it would be done as a sequence of operations to add
one element at a time.  That's the only way to reasonably extend this to
non-constants (note that a collection literal itself cannot be a
"compile-time constant").  It is a separate decision what kind of collection
you get in this case.  I suggest that it's result be some type that
implements Collection but not List or Set, is immutable, and whose
construction (via a factory) doesn't remove duplicates; I'd expect it to
print 100000.

In other words, it is the compile-time conversion from "collection
literal..." to "set" that causes the duplicates to be removed, and this
program doesn't trigger that conversion.  I would still expect the compiler
to produce warnings when it detects that a literal that is converted to a
set contains duplicate values.

> is this legal:
> int x = 0;
> {"a", "b"}.get(x)?

No, because the collection literal isn't subjected to a conversion to some
appropriate type.  Similarly, the following isn't legal:


because the "3" isn't subjected to a boxing conversion.


More information about the coin-dev mailing list