Table of Contents
Overview
The Set interface has no definition of first or last elements. To say differently, there is no order in a Set. SortedSet solves that problem by offering an order of elements and letting you access elements by their indexes.
Let’s take a look at the part of the Set interface where we have the SortedSet:
As you can see, SortedSet has no direct concrete implementation. We have TreeSet and ConcurrentSkipListSet implement SortedSet through NavigableSet interface.
Here are the methods of SortedSet
| Method name | Function |
comparator() | Returns the comparator that used to order elements in the set |
first() | Get the first element |
headSet(E e) | Get a SortedSet of elements that are less than e |
last() | Get the last element |
tailSet(E from) | Get a SortedSet of elements that are greater than or equal to e (inclusive) |
| subSet(E from, E to) | Get a subset of elements that are greater than from and less than to |
spliterator() | Creates a Spliterator over the elements in the set |
Since elements in SortedSet are ordered, the elements’ class must implement Comparable or when creating the SortedSet, you must pass in a Comparator that accepts the element’s type.
You may recall another data structure that has similar requirements, which is PriorityQueue.
SortedSet in action
Let’s try the operations of a SortedSet by using a TreeSet. As you can see from the diagram, TreeSet implements NavigableSet that in turn extends SortedSet.
Consider the following block:
private static void sortedSetBasicOperations() {
SortedSet<String> mySet = new TreeSet<>();
mySet.add("Karen");
mySet.add("Zed");
mySet.add("Abby");
mySet.add("Quentin");
mySet.add("Randall");
//print the full set
System.out.println("The full set is: " + mySet);
//Getting first and last elements
System.out.println("First element: " + mySet.first());
System.out.println("Last element: " + mySet.last());
//Getting all elements from Karen
System.out.println("From Karen: " + mySet.tailSet("Karen"));
//Getting all elements before Quentin
System.out.println("To Quentin: " + mySet.headSet("Quentin"));
//Getting all elements from Karen to before Quentin
System.out.println("From Karen To Quentin: " + mySet.subSet("Karen", "Quentin"));
}This is the output of the above code when executed:
Using SortedSet in multi-threaded code
From the diagram, you can see, that there is one implementation of the SortedSet in the java.util.concurrent package. That’s ConcurrentSkipListSet.
Let’s first consider an example where we use non-safe SortedSet first then we’ll use ConcurrentSkipListSet to address the issue.
private static void nonSafeTreeSetOperation() throws InterruptedException {
var numberSet = new TreeSet<Integer>();
ExecutorService service = Executors.newFixedThreadPool(10);
for (int i = 0; i < 20; i++) {
int finalI = i;
service.submit(() -> numberSet.add(finalI) );
}
service.shutdown();
service.awaitTermination(10, TimeUnit.SECONDS);
System.out.println("The set size: " + numberSet.size());
System.out.println("The set: " + numberSet);
}When executing this code, you might see different results between executions:
Here are some possible outcomes:
Now, if we change TreeSet to ConcurrentSkipListSet, the problem is solved:
private static void safeTreeSetOperation() throws InterruptedException {
var numberSet = new ConcurrentSkipListSet<Integer>();
ExecutorService service = Executors.newFixedThreadPool(10);
for (int i = 0; i < 20; i++) {
int finalI = i;
service.submit(() -> numberSet.add(finalI) );
}
service.shutdown();
service.awaitTermination(10, TimeUnit.SECONDS);
System.out.println("The set size: " + numberSet.size());
System.out.println("The set: " + numberSet);
}The output is consistent. There are always 20 elements in the list:
Conclusion
As you can see, the SortedSet data structure adds more power to the Set interface. There is no order in a set. However, with SortedSet, you can have the items ordered in their natural order or you can specify a comparator to offer the order mechanism yourself.
You can find the code of this article here on Github.
I build softwares that solve problems. I also love writing/documenting things I learn/want to learn.