"Array Map" with Binary Search...

[kreyszig]

Hi,

I am looking for a Class that resembles TreeMap, but that uses an array instead of a Tree for faster random access using an element index (I will add and remove elements very rarely). I guess I will have to write my own, right?

Thanks!

[pbrockway2]

The problem is less one of faster random access than it is of having index based access at all! In the standard Java collection API a TreeMap is not a List. And this applies to maps generally: they are sorted by the natural order of their keys and not by index. They don't offer an indexOf() or get().

You might want to look at Google Collections.

[kreyszig]

The problem is less one of faster random access than it is of having index based access at all! In the standard Java collection API a TreeMap is not a List. And this applies to maps generally: they are sorted by the natural order of their keys and not by index. They don't offer an indexOf() or get().

You might want to look at Google Collections.

Well, I guess this comes a bit together right? The entrySet() function returns a Collection object rather than something like an ArrayList because TreeMap uses a Tree instead of an array internally...

[pbrockway2]

entrySet() actually returns a Set<Map.Entry<K,V>> (informally, a set of entries) rather than any old Collection. But, again, the lack of index based access isn't an implementation detail - it doesn't do this because a tree of some sort is involved in its implementation - rather it follows from the fact that a Map (any map) offers no index based access.

I should have mentioned that I posted the google link not because I know it has such a collection lurking there somewhere, but because it is more modern. If you can't what you want there (a map with index based access), it might be time to question whether such a thing is the way to go about whatever it is that you are going about.

[pbrockway2]

If you are adding and removing elements only very rarely why not have a class that contains *both* a Map (or SortedMap of some variety) and a List of keys (or entries). Use the map to provide map-like functionality and the list to provide index based access. The list would only have to be updated on the rare occasions that the collection's content changes.

[kreyszig]

If you are adding and removing elements only very rarely why not have a class that contains *both* a Map (or SortedMap of some variety) and a List of keys (or entries). Use the map to provide map-like functionality and the list to provide index based access. The list would only have to be updated on the rare occasions that the collection's content changes.

This would work, but it would duplicate the memory used by the lists and I can't afford this in the application I am developing. I decided to write my own map class finally. It uses also primitives instead of a generics when possible, so it will be a more memory efficient and optimal class for this particular application.

Thanks