☕ Java

SortedSet

SortedSet is an interface that extends Set and adds the contract that all elements are maintained in ascending order, determined either by their natural ordering (Comparable) or by a Comparator provided at construction. SortedSet defines six additional methods beyond Set: comparator(), first(), last(), headSet(), tailSet(), and subSet(). These methods enable range-based retrieval — extracting portions of the set based on element values rather than position. Understanding SortedSet as an interface separate from TreeSet is important for writing code that is generic over any sorted set implementation, and for understanding the semantics that all sorted set implementations must honour. This entry covers the SortedSet contract, its six methods, the ordering requirement, and how SortedSet fits into the NavigableSet extension.

The SortedSet Contract

SortedSet extends Set and adds a single fundamental guarantee: all elements are maintained in ascending sorted order. The ordering is defined by the set's comparator — either a Comparator provided at construction, or the elements' natural ordering via Comparable if no Comparator was provided. This ordering is used for all element comparisons, including equality testing. Two elements a and b are considered equal by a SortedSet if and only if comparator.compare(a, b) == 0 (or a.compareTo(b) == 0 for natural ordering), regardless of what a.equals(b) returns. This comparator-based equality is the most important distinction between SortedSet and regular Set. A regular Set uses equals() to determine duplicates. A SortedSet uses the comparator. If the comparator is consistent with equals — compare() returns 0 exactly when equals() returns true — then SortedSet behaves exactly like a regular Set. If the comparator is inconsistent with equals, the SortedSet may include or exclude elements in ways that surprise callers who expect Set-level equals() semantics. The Java documentation requires that the comparator used for a SortedSet be consistent with equals. This is described as a contract, not a hard enforcement — the JVM does not check it. Violating it produces "well-defined but incorrect" behaviour: the SortedSet correctly follows its comparator rules, but the result may not match Set semantics. The most common violation is using a Comparator that considers two distinct non-equal objects to be equal (like comparing Persons only by name) — the second person with the same name is silently dropped. Every SortedSet must provide a comparator() method. If the set uses natural ordering (no Comparator was supplied), comparator() returns null — the set relies on Comparable. If a Comparator was provided, comparator() returns that Comparator. This allows generic code to retrieve and use the set's ordering policy.
Java
// ── SortedSet interface hierarchy ─────────────────────────────────────
//
//  Collection
//  └── Set
//      └── SortedSet                  ← this interface
//          └── NavigableSet           ← extends with navigation methods
//              └── TreeSet            ← primary implementation
//              └── ConcurrentSkipListSet ← concurrent implementation

// ── SortedSet contract — ordering guarantees ──────────────────────────
SortedSet<String> sorted = new TreeSet<>();
sorted.add("cherry");
sorted.add("apple");
sorted.add("banana");
sorted.add("date");

// Iteration always in ascending natural order:
for (String s : sorted) System.out.print(s + " ");
// apple banana cherry date — ALWAYS

// toString() shows sorted order:
System.out.println(sorted);  // [apple, banana, cherry, date]

// ── comparator() — retrieve the set's ordering policy ────────────────
SortedSet<String> naturalOrder = new TreeSet<>();
System.out.println(naturalOrder.comparator());  // null — uses Comparable

Comparator<String> byLength = Comparator.comparingInt(String::length);
SortedSet<String> customOrder = new TreeSet<>(byLength);
System.out.println(customOrder.comparator());   // the Comparator instance

// ── Comparator-based equality — NOT equals() ──────────────────────────
// PROBLEM: comparator only considers length — inconsistent with equals()
SortedSet<String> lengthSet = new TreeSet<>(byLength);
lengthSet.add("cat");     // length 3
lengthSet.add("dog");     // length 3 → comparator.compare("dog","cat") == 0
                           // → treated as DUPLICATE → NOT added!
lengthSet.add("horse");   // length 5 — different from 3 → added
System.out.println(lengthSet);   // [cat, horse]  — "dog" silently dropped!
System.out.println(lengthSet.contains("dog"));   // false
System.out.println(lengthSet.contains("cat"));   // true
System.out.println(lengthSet.contains("box"));   // TRUE! "box" has length 3
// "box" is not in the set but comparator says it equals "cat"
// This violates Set semantics — contains("box") should return false

// ── Consistent comparator — correct behaviour ─────────────────────────
SortedSet<String> consistent = new TreeSet<>(
    Comparator.comparingInt(String::length)
              .thenComparing(Comparator.naturalOrder()));
// Length-first, then lexicographic tie-break — consistent with equals()
consistent.add("cat");
consistent.add("dog");   // different string, different comparison result → added
consistent.add("horse");
System.out.println(consistent);   // [cat, dog, horse]

SortedSet Methods — first, last, headSet, tailSet, subSet

SortedSet defines six methods beyond those in Set. The first() and last() methods return the minimum and maximum elements respectively, throwing NoSuchElementException if the set is empty. These are O(log n) for TreeSet. The comparator() method returns the set's Comparator or null for natural ordering. The three range-view methods are the core of SortedSet's additional value. headSet(toElement) returns a view of all elements strictly less than toElement. tailSet(fromElement) returns a view of all elements greater than or equal to fromElement. subSet(fromElement, toElement) returns a view of elements from fromElement (inclusive) to toElement (exclusive). The half-open interval convention [from, to) is consistent with Java's arrays, Stream.range(), and most API conventions. These views are live: modifications to the view are reflected in the backing set and vice versa. Views throw IllegalArgumentException for operations that violate the view's range. Views themselves are SortedSets (actually NavigableSet for TreeSet), so all SortedSet operations are available on the view, including nested range views. The SortedSet interface only supports half-open intervals with fixed inclusivity (left-inclusive, right-exclusive). For full control over inclusivity (closed intervals, open intervals), the NavigableSet extension is needed — it provides the more flexible four-argument subSet(from, fromInclusive, to, toInclusive). Code that needs this control should use NavigableSet rather than SortedSet.
Java
// ── SortedSet methods ────────────────────────────────────────────────
SortedSet<Integer> set = new TreeSet<>(Set.of(1, 3, 5, 7, 9, 11));

// first() and last()
System.out.println(set.first());   // 1  — minimum
System.out.println(set.last());    // 11 — maximum

// headSet(toElement) — elements STRICTLY LESS THAN toElement
SortedSet<Integer> head = set.headSet(7);
System.out.println(head);   // [1, 3, 5] — all elements < 7

// tailSet(fromElement) — elements GREATER THAN OR EQUAL TO fromElement
SortedSet<Integer> tail = set.tailSet(7);
System.out.println(tail);   // [7, 9, 11] — all elements >= 7

// subSet(from, to) — [from, to) — from inclusive, to exclusive
SortedSet<Integer> sub = set.subSet(3, 9);
System.out.println(sub);    // [3, 5, 7] — from 3 (incl) to 9 (excl)

// ── Half-open interval convention ────────────────────────────────────
// [from, to) is consistent with:
// - Arrays: for (int i = from; i < to; i++)
// - Stream.range(from, to)
// - String.substring(from, to)
//
// headSet(5) means "everything before 5" = [..., 4]
// tailSet(5) means "5 and everything after" = [5, 6, ...]
// Together, headSet(5) and tailSet(5) partition the set at 5

// ── Partitioning a set ────────────────────────────────────────────────
SortedSet<Integer> numbers = new TreeSet<>(
    Set.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
int pivot = 5;

SortedSet<Integer> below    = numbers.headSet(pivot);  // [1, 2, 3, 4]
SortedSet<Integer> atOrAbove = numbers.tailSet(pivot); // [5, 6, 7, 8, 9, 10]

// Verify: union covers all elements, no overlap
assert below.size() + atOrAbove.size() == numbers.size();
assert Collections.disjoint(below, atOrAbove);

// ── Live view mutations ───────────────────────────────────────────────
SortedSet<String> names = new TreeSet<>(
    Set.of("Alice", "Bob", "Carol", "Dave", "Eve"));
SortedSet<String> aToD = names.subSet("A", "E");
System.out.println(aToD);   // [Alice, Bob, Carol, Dave]

aToD.remove("Bob");         // removes "Bob" from original set too
System.out.println(names);  // [Alice, Carol, Dave, Eve] — Bob removed

names.add("Ann");           // "Ann" < "E" — within range — appears in view
System.out.println(aToD);   // [Alice, Ann, Carol, Dave]

names.add("Frank");         // "Frank" > "E" — outside view range
System.out.println(aToD);   // [Alice, Ann, Carol, Dave] — Frank not visible

Programming to SortedSet — Generic Sorted Set Code

The value of the SortedSet interface is enabling generic code that works with any sorted set implementation — TreeSet, ConcurrentSkipListSet, or custom implementations — without coupling to a specific class. Method parameters typed as SortedSet accept any sorted set, making the code more flexible and testable. Writing methods that accept SortedSet rather than TreeSet follows the principle of programming to the interface. The method communicates "I need a sorted set" rather than "I need specifically a TreeSet." A caller can pass a TreeSet in single-threaded code or a ConcurrentSkipListSet in concurrent code. Tests can pass a hand-crafted sorted set. The implementation detail of which red-black tree or skip list is used is irrelevant to the method's logic. The six SortedSet-specific methods are sufficient for many range-based algorithms: pagination over sorted data, extraction of elements within a range, efficient minimum and maximum retrieval, and partitioning at a given value. When NavigableSet operations (floor, ceiling, descending iteration) are needed, the parameter should be typed as NavigableSet to communicate the richer requirement.
Java
// ── Generic sorted set operations ────────────────────────────────────
// Accept SortedSet<T> — works with TreeSet, ConcurrentSkipListSet, etc.
public static <T> List<T> getPage(SortedSet<T> set,
                                   T fromExclusive,
                                   int pageSize) {
    SortedSet<T> from = (fromExclusive == null)
        ? set
        : set.tailSet(fromExclusive);  // elements after the cursor

    // Skip the cursor element itself if it is in the set
    // (tailSet is inclusive; we want exclusive)
    List<T> page = new ArrayList<>();
    Iterator<T> it = from.iterator();

    // Skip fromExclusive if present
    if (fromExclusive != null && it.hasNext() &&
            set.contains(fromExclusive)) {
        it.next();  // skip the cursor
    }

    while (it.hasNext() && page.size() < pageSize) {
        page.add(it.next());
    }
    return page;
}

// Usage:
SortedSet<String> names = new TreeSet<>(
    Set.of("Alice", "Bob", "Carol", "Dave", "Eve", "Frank"));

List<String> page1 = getPage(names, null, 3);   // [Alice, Bob, Carol]
List<String> page2 = getPage(names, "Carol", 3); // [Dave, Eve, Frank]

// ── Range count — how many elements in [from, to) ────────────────────
public static <T> int countInRange(SortedSet<T> set, T from, T to) {
    return set.subSet(from, to).size();  // O(log n) to create view + O(k) to count
}

SortedSet<Integer> scores = new TreeSet<>(
    Set.of(45, 62, 71, 78, 85, 91, 96));
System.out.println(countInRange(scores, 70, 90));  // 2 (71, 78)

// ── Minimum element satisfying a condition ────────────────────────────
public static <T> Optional<T> firstSatisfying(SortedSet<T> set,
                                               Predicate<T> predicate) {
    for (T element : set) {           // iterates in sorted order
        if (predicate.test(element)) {
            return Optional.of(element);  // first (smallest) satisfying element
        }
    }
    return Optional.empty();
}

// First score >= 70 (passing grade):
Optional<Integer> firstPassing = firstSatisfying(scores, s -> s >= 70);
System.out.println(firstPassing.orElse(-1));  // 71
// Note: NavigableSet.ceiling(70) is O(log n) and more efficient
// but firstSatisfying is generic for arbitrary predicates

// ── Programmatic sorted set creation ─────────────────────────────────
// Factory method that returns appropriate implementation by context:
public static <T extends Comparable<T>> SortedSet<T> createSortedSet(
        boolean concurrent) {
    return concurrent
        ? new ConcurrentSkipListSet<>()
        : new TreeSet<>();
}

Related Topics in Collections Framework

Collections Overview
The Java Collections Framework (JCF) is a unified architecture for representing and manipulating groups of objects. It provides a set of interfaces that define the operations a collection must support, a set of abstract classes that provide partial implementations, and a set of concrete implementations optimised for different use cases. Every Java developer uses collections daily — lists for sequences, sets for uniqueness, maps for key-value pairs, and queues for ordering — and choosing the right implementation for the right use case is one of the most fundamental practical skills in Java.
Iterable
Iterable<E> is the root interface of the Java Collections hierarchy. Any class that implements Iterable can be used in a for-each loop. It declares a single abstract method: iterator(), which returns an Iterator<E> that the for-each loop uses to traverse the elements. Implementing Iterable is all that is required to make a custom data structure work with Java's enhanced for loop, the Stream API, and any method that accepts an Iterable.
Collection Interface
Collection<E> is the root interface of the main collection hierarchy, extending Iterable<E>. It defines the common operations that all collection types must support: adding elements, removing elements, checking containment, querying size, clearing, converting to an array, and bulk operations. List, Set, and Queue all extend Collection. Map does not extend Collection because a map operates on key-value pairs rather than individual elements.
ArrayList
ArrayList is a resizable-array implementation of the List interface. It is the most commonly used collection in Java, providing dynamic sizing on top of a standard array. Elements are stored in contiguous memory, enabling O(1) random access by index. When the internal array is full, ArrayList automatically allocates a larger array and copies all elements. ArrayList is not thread-safe and preserves insertion order, allowing duplicates.
Prev
TreeSet
Next
NavigableSet