Results 1 to 6 of 6
  1. #1
    kreyszig is offline Member
    Join Date
    Oct 2010
    Posts
    35
    Rep Power
    0

    Question "Array Map" with Binary Search...

    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!

  2. #2
    pbrockway2 is online now Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,571
    Rep Power
    12

    Default

    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.

  3. #3
    kreyszig is offline Member
    Join Date
    Oct 2010
    Posts
    35
    Rep Power
    0

    Default

    Quote Originally Posted by pbrockway2 View Post
    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...

  4. #4
    pbrockway2 is online now Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,571
    Rep Power
    12

    Default

    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.

  5. #5
    pbrockway2 is online now Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,571
    Rep Power
    12

    Default

    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.

  6. #6
    kreyszig is offline Member
    Join Date
    Oct 2010
    Posts
    35
    Rep Power
    0

    Default

    Quote Originally Posted by pbrockway2 View Post
    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

Similar Threads

  1. Decimal to Binary "Using Array"
    By pinkdreammsss in forum Java Applets
    Replies: 10
    Last Post: 04-23-2010, 07:21 PM
  2. Replies: 2
    Last Post: 03-18-2009, 09:36 PM
  3. Replies: 2
    Last Post: 01-24-2009, 07:56 PM
  4. Eclispe: "Launch failed. Binary not found"
    By qwertyuiop23 in forum Eclipse
    Replies: 1
    Last Post: 11-16-2008, 07:06 AM
  5. Replies: 1
    Last Post: 10-20-2008, 08:35 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •