Start of Tutorial > Start of Trail > Start of Lesson

Search

The SortedMap Interface

A SortedMapis a Mapthat maintains its entries in ascending order, sorted according to the keys' natural order, or according to a Comparator provided at SortedMap creation time. (Natural order and Comparators are discussed in the section on Object Ordering.) In addition to the normal Map operations, the Map interface provides operations for:

• Range-view: Performs arbitrary range operations on the sorted map.
• Endpoints: Returns the first or last key in the sorted map.
• Comparator access: Returns the Comparator used to sort the map (if any).

public interface SortedMap extends Map {
    Comparator comparator();

    SortedMap subMap(Object fromKey, Object toKey);
    SortedMap headMap(Object toKey);
    SortedMap tailMap(Object fromKey);

    Object first();
    Object last();
}

This interface is the Map analogue of SortedSet.

Map Operations

The operations that SortedMap inherits from Map behave identically on sorted maps and normal maps with two exceptions:

• The Iterator returned by the iterator operation on any of the sorted map's Collection-views traverse the collections in key-order.
• The arrays returned by the Collection-views' toArray operations contain the keys, values, or entries in key-order.

Although it isn't guaranteed by the interface, the toString method of the Collection-views in all the JDK's SortedMap implementations returns a string containing all the elements of the view, in key-order.

For example, consider the following snippet:

SortedMap m = new TreeMap();
m.put("Sneezy", "common cold");
m.put("Sleepy", "narcolepsy");
m.put("Grumpy", "seasonal affective disorder");

System.out.println(m.keySet());
System.out.println(m.values());
System.out.println(m.entrySet());

Running this snippet produces this output:

[Grumpy, Sleepy, Sneezy]
[seasonal affective disorder, narcolepsy, common cold]
[Grumpy=seasonal affective disorder, Sleepy=narcolepsy, Sneezy=common cold]

Standard Constructors

By convention, all Map implementations provide a standard constructor that takes a Map, and SortedMap implementations are no exception. This constructor creates a SortedMap object that orders its entries according to their keys' natural order. Additionally, by convention, SortedMap implementations provide two other standard constructors:

• One that takes a Comparator and returns a new (empty) SortedMap sorted according to the specified Comparator.
• One that takes a SortedMap and returns a new SortedMap containing the same mappings as the given SortedMap, and sorted according to the same Comparator (or using the elements' natural ordering, if the specified SortedMap did too). Note that it is the compile-time type of the argument that determines whether this constructor is invoked in preference to the ordinary Map constructor, and not its runtime type!

The first of these standard constructors is the normal way to create an empty SortedMap with an explicit Comparator. The second is similar in spirit to the standard Map constructor: It creates a copy of a SortedMap with the same ordering, but with a programmer specified implementation type.

The following snippet illustrates how this works:

final Comparator FUNNY_COMPARATOR = ... ;
Map m = new TreeMap(FUNNY_COMPARATOR);

// ... code to populate m

Map m2 = new TreeMap(m);           // invokes TreeMap(Map)
Map m3 = new TreeMap((SortedMap)m) // invokes TreeMap(SortedMap)

Note that m2.comparator() will return null while m3.comparator() will return FUNNY_COMPARATOR. In other words, m2 is sorted according to its keys' natural ordering, while m3 is sorted according to the ordering induced by FUNNY_COMPARATOR.

Comparison to SortedSet

Because this interface is a precise Map analogue of SortedSet, all of the idioms and code examples in the SortedSet section apply to SortedMap, with only trivial modifications.

Start of Tutorial > Start of Trail > Start of Lesson

Search