Avoiding wrapper objects in collections

Question

I'm getting a little annoyed of having to wrap primitive types in wrapper objects to store them in collection data structures (sets, maps, lists, etc.) in languages like Java and Objective C. I'd really like to have, say, a Map data structure that works the same way whether I'm mapping NSNumbers to Strings or integers to doubles or integers to MyBigCustomObject*.

My understanding is that the reason collection data structures in these languages require wrapping in an object is so it can just always assume that the number given is a pointer - I actually can make a NSDictionary with [NSDictionary dictionaryWithObject: MyCustomObject forKey: 1], but it will treat the 1 as a pointer instead of an integer, try to access memory address 1 and segfault. But I don't see any reason why you couldn't make a collection data structure that keeps track of the type of keys and values that wouldn't have this problem. Even a relatively inflexible data structure like a Map of specifically-ints to specifically-pointers-to-objects would be a decently common use case (I certainly could use one, I'm doing a lot of work recently that involves indexing objects by an integer ID). Is there a reason why this isn't a common paradigm in languages that have an Object/primitive type distinction?

Answer 1

It is, of course, possible. However, it would require duplicating all the code (which can be quite much for an optimized implementation) for each non-reference type, or a way to automatically specialize the implementation for each type.

I assume that nobody considered the first option worthwhile.

The second way adds some complexity to the language and its implementation. Also, in the case of Java, there are generics (which could in principle be used to implemented the second option) but early design decisions (some would say errors) prevent the second option, as generics are compiled to non-generic code that simply uses objects everywhere and casts as necessary.

Note that there is one language, C++, which has a mechanism for the second option (templates). It doesn't treat objects as pointers (reference types) though.

Edit: As FredOverflow points out in the comments, this does exist. Scala exposes the second option to the programmer with a @specialized annotation.

Answer 2

This is basically what happens in C++- the language always knows whether something is a pointer or not. Quite simply, there is no fundamental reason that this is required at all- Java and other languages just do it because they enjoy restricting programmer freedom.

Answer 3

But I don't see any reason why you couldn't make a collection data structure that keeps track of the type of keys and values that wouldn't have this problem.

this is exactly the issue in those languages. Due to the way that Generics are implemented in Java and Objective-C, this information is not available anymore at runtime.

It is conceivable though to implement a data structure whose constructor takes instances of Type in its constructor and using that information to store the data. It sounds like a lot of work though, and the API gets messy. Question to the community: does an implementation of such a data structure already exist?

Answer 4

in Java, this seem to be a common paradigm indeed. One can find plenty 3-rd party libraries for collections like you refer to. Some of these were discussed at SO: What is the most efficient Java Collections library? Searching web for java library high performance collections shows even more, like eg HPPC

• The reason why such libraries didn't make it into standard Java API (yet?) is most likely that these did not gain popularity sufficient to justify such an inclusion (yet?). Another possible reason is that there seem to be no common agreement (yet?) on how to design standard API for these collections. As Joshua Bloch said, Public APIs, like diamonds, are forever. You have one chance to get it right so give it your best.