How come Java's TreeSet has no get() method?

Question

What if I want to retrieve and update objects that stored in a TreeSet?

The reason I'm asking, is that I want to be able to maintain some data stracture that will store Students. I want it to be sorted (by grades - which is an instance variable of Student), and - it needs to be kept sorted even after I update one (or more) grade(s) as well.

So, after briefly looking over Java's collections, I decided to go with TreeSet and set a comparator that compares two students by their grades. problem is, I just found out that TreeSet has no get() method!

Any help and suggestions would be greatly appreciated.

Solution 1

What would you expect a get() method on a Set to do?

• Sets are not indexed, so a get(int index) makes no sense. (Use a List if you want to get elements by index).
• get(Object obj) would also not make sense, because you'd have the object that you're trying to get already.
• There is already a contains() method to check if a Set contains an object.
• You can iterate over a Set if you want to do something with all elements in the set.

Solution 2

You can retrieve the elements from the treeset by using an Iterator. You can try something like this:

Iterator<Integer> it = treeSet.iterator();

Integer current = 0;
while(it.hasNext() ) {
current = it.next();

}

Hope this helps.

Solution 3

I do have a case where I use a two TreeSets (because they are faster in searches). One of these trees is huge, and the objects in the trees are different, so I create a mock object (of Type 2, second tree) that has the fields used to sort, using data from an object from the small tree and check if there is a counterpart on the second. Now I need to check a value from the object found in the second tree to add value on a report.

Using an iterator, instead of a binary search to retrieve the object I need, defeats the purpose of using a binary tree. The second tree is 5GB plus, finding matchings with data in the first tree (200MB). I need a search strategy that makes sense for this huge amount of data, therefore I chose a Binary Search tree. Entries are unique.

Solution 4

Usually, you will not want to retrieve an element in a set when you already have it. You might to remove your element from a set, or know if it belongs to a set, thats all. Know want you want to do is to index your students by grade, so the index is the grade, not the object itself. Map is the solution.

If I were you, I would use the following structure which retrieves all students with the same grade quickly (they are sorted by grades too) :

private SortedMap<Integer,Set<Student>> _studentsByGrade = new TreeMap<Integer,Set<Student>>();

public void updateStudent(Student student, int oldGrade, int newGrade)
{
  getOrCreateContainer(oldGrade).remove(student);
  getOrCreateContainer(newGrade).add(student);
  student.setGrade(newGrade);
}

public Set<Student> getOrCreateContainer(int grade)
{
  Set<Student> set = _studentsByGrade.get(grade);
  if(set==null)
  {
    set = new HashSet<Student>();
    _studentsByGrade.put(grade, set);
  }
  return set;
}

Don't forget to overload the equals and hashcode in your Student class to make it work correctly.

You might also want to check the cqengine library if you want to perform java indexations easily and fast, but the solution presented above is just ok for your usage.

Solution 5

The TreeSet is sorted upon insertion. If you order by students' grades and modify them after being added, the items are no longer sorted (same order as before).

The TreeSet also does not use equals() to determine if an element is already added, but uses the comparator instead (same order = same item). So if two students have the same grades, only one of them is added. From Javadoc:

TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal.

Instead of using TreeSet, you can use a HashSet and sort the students by grade whenever you need them (create a new List containing the students, sort it and iterate over it).

View more solutions

Comments

[piet.t]

Just what I wanted to write: +1. Except for the indexed case: instead of "makes no sense" I would write "use a List"

[Rohit Jain]

Or use a Map to store the objects based on some key.

[so.very.tired]

Thanks for the help. So what options do I have here?

[Jesper]

@so.very.tired That depends on what you want to do. What do you want to do, that you think you'd need a get() method for?

[Jesper]

@piet.t Thanks for the suggestion, added.

[so.very.tired]

@Jesper I want to update Students average so that the collection will remain sorted after the update.

[Jesper]

@so.very.tired If you're updating one of the fields that the comparator uses (the grade field of your Student object), then you'll have to (1) remove the Student from the Set, (2) update the variable and (3) put the Student back in the Set. Modifying the value that Set depends on to determine the order while it is in the Set will cause trouble.

[so.very.tired]

So basically there's no actual way to do it dynamically.

[Peter Walser]

At least not using the standard collections. As long as the ordering can be arbitrary (any Comparator or Comparable implementation), the collection would need a way to observe the contained objects for changes. This would require two interfaces, one for the observables (to be implemented by the objects) and one for the observer (listener interface with callback method, for the observer, which is the collection).

[cloud]

I don't agree with the second. get(Object obj) is useful if the obj's compare method just compare the content, not the reference. So what if I want to get the reference of an element in Set?

[bryant1410]

I agree that a get() makes sense in a SortedSet

[Juh_]

personal situation: I want a a sorted list with TreeSet.floor (and similar) methods defined on it. But still, many algorithms using it need index-get accessor. That's a good usage example of a TreeSet with get(index), no?

[timxor]

Your answer implies items in TreeSet are not nested. If I have TreeSet<TreeMap<String, Integer>> marketStocks = new TreeSet<>(); then it makes perfect sense. In this scenario we wish to avoid duplicate key mappings and use a set.

[Z.better]

but what if I have a treeset, it is sorted, but it does not have get() either.....

[Yuri]

So, if a get(i) doesn't make sense on a SortedSet, why are first() and last() provided?

[Jesper]

@Yuri I didn't say get(index) doesn't make sense on a SortedSet. (It doesn't on a Set because a set is not an ordered collection). Since a SortedSet is an ordered collection, first() and last() do make sense. Why the designers of java.util.SortedSet didn't provide a get(index) method is a mistery.

[Yuri]

I see, but because the question explicitly mentions a TreeSet, which implements a SortedSet, I thought that part seems to be a bit "overlooked" in the answer. Hence the explicit question. Thanks for the quick reply.

[mjs]

Not true. It does make sense, since the comparable might be resolving to return an object given another object. you might want to get the object in the set to update a value such as a date, rather now, you might have to remove and then add, which is a more costly operation, not to mention that all other fields in the new instance also now has to be set, albeit you could update the removed instance and then put it back in. The used to get object might not in some cases have to be the same as the one in the set.

[Coder]

what if you have a treeset of nodes? then youd want to do this. maybe answer the question instead...