Data Structure Brushup (Java)

Question

This should be easy for many of you, but for me it's just another bit of rust needing to be chipped away as I get back into basic Java coding. Using bloody associative arrays for so long in other languages have turned me nice and spoiled. :P

My problem is simple: I'm storing a set of objects, each containing a string and a number, in a list. I would like each object inserted into this list to be sorted alphabetically by its string. I would also like to be able to retrieve objects from the list by their string as well. I would like to do this as formally and/or efficiently as possible.

Is there something already available in the Java standard libraries for this?

Answer 1

That sound like a SortedMap. With the String as the key and the Number as the value.

Answer 2

Apart from the SortedMap, you could have a

TreeSet<Pair<String, Number>>

where you supply the comparator to sort the pairs (or make your Pair class implement Comparable and do it there).

This keeps the objects separate from the data structure, and whilst for a trivial example like this it isn't a big deal, you can imagine that a TreeSet<MyObject> where MyObject implements Comparable is easier to grok in the long term.

Answer 3

there is a great writeup on java collections which covers most of your needs.

short advice concerning this: use a TreeMap(Comparator c) with a custom Comparator. key ist the string, value is the composite object with string and number

Answer 4

If you have duplicate string value among the objects in the list, you might want to look at Google Collections' TreeMultimap. With TreeMultimap, not only the keys are sorted but all values having the same key are also stored in a collection.

Multimap<String, Pair> mm = new TreeMultimap<String, Pair>(
      new Comparator<String>(){...}, 
      new PairComparator());
mm.put("A", new Pair("A", 1));
mm.put("B", new Pair("B", 2));
mm.put("B", new Pair("B", 3));
Collection values = mm.values(); 
   // values are [Pair("A", 1), Pair("B", 2), Pair("B", 3)]
Collection bValues = mm.get("B"); 
   // bValues are [Pair("B", 2), Pair("B", 3)]

Answer 5

I have done something similar to that, I used ArrayList to store them objects and write comparators for sorting the arraylist.