SplayTreeMap<K, V> class

A Map of objects that can be ordered relative to each other.

The map is based on a self-balancing binary tree. It allows most single-entry operations in amortized logarithmic time.

Keys of the map are compared using the compare function passed in the constructor, both for ordering and for equality. If the map contains only the key a, then map.containsKey(b) will return true if and only if compare(a, b) == 0, and the value of a == b is not even checked. If the compare function is omitted, the objects are assumed to be Comparable, and are compared using their Comparable.compareTo method. Non-comparable objects (including null) will not work as keys in that case.

To allow calling operator [], remove or containsKey with objects that are not supported by the compare function, an extra isValidKey predicate function can be supplied. This function is tested before using the compare function on an argument value that may not be a K value. If omitted, the isValidKey function defaults to testing if the value is a K.

Notice: Do not modify a map (add or remove keys) while an operation is being performed on that map, for example in functions called during a forEach or putIfAbsent call, or while iterating the map (keys, values or entries).

Example:

final planetsByMass = SplayTreeMap<double, String>((a, b) => a.compareTo(b));

To add data to a map, use operator[]=, addAll or addEntries.

planetsByMass[0.06] = 'Mercury';
planetsByMass
    .addAll({0.81: 'Venus', 1.0: 'Earth', 0.11: 'Mars', 317.83: 'Jupiter'});

To check if the map is empty, use isEmpty or isNotEmpty. To find the number of map entries, use length.

print(planetsByMass.isEmpty); // false
print(planetsByMass.length); // 5

The forEach method calls a function for each key/value entry of the map.

planetsByMass.forEach((key, value) {
  print('$key \t $value');
  // 0.06    Mercury
  // 0.11    Mars
  // 0.81    Venus
  // 1.0     Earth
  // 317.83  Jupiter
});

To check whether the map has an entry with a specific key, use containsKey.

final keyOneExists = planetsByMass.containsKey(1.0); // true
final keyFiveExists = planetsByMass.containsKey(5); // false

To check whether the map has an entry with a specific value, use containsValue.

final earthExists = planetsByMass.containsValue('Earth'); // true
final plutoExists = planetsByMass.containsValue('Pluto'); // false

To remove an entry with a specific key, use remove.

final removedValue = planetsByMass.remove(1.0);
print(removedValue); // Earth

To remove multiple entries at the same time, based on their keys and values, use removeWhere.

planetsByMass.removeWhere((key, value) => key <= 1);
print(planetsByMass); // {317.83: Jupiter}

To conditionally add or modify a value for a specific key, depending on whether there already is an entry with that key, use putIfAbsent or update.

planetsByMass.update(1, (v) => '', ifAbsent: () => 'Earth');
planetsByMass.putIfAbsent(317.83, () => 'Another Jupiter');
print(planetsByMass); // {1.0: Earth, 317.83: Jupiter}

To update the values of all keys, based on the existing key and value, use updateAll.

planetsByMass.updateAll((key, value) => 'X');
print(planetsByMass); // {1.0: X, 317.83: X}

To remove all entries and empty the map, use clear.

planetsByMass.clear();
print(planetsByMass.isEmpty); // false
print(planetsByMass); // {}

See also:

  • Map, the general interface of key/value pair collections.
  • HashMap is unordered (the order of iteration is not guaranteed).
  • LinkedHashMap iterates in key insertion order.
Mixed in types

Constructors

SplayTreeMap([int compare(K key1, K key2)?, bool isValidKey(dynamic potentialKey)?])
SplayTreeMap.from(Map other, [int compare(K key1, K key2)?, bool isValidKey(dynamic potentialKey)?])
Creates a SplayTreeMap that contains all key/value pairs of other.
factory
SplayTreeMap.fromIterable(Iterable iterable, {K key(dynamic element)?, V value(dynamic element)?, int compare(K key1, K key2)?, bool isValidKey(dynamic potentialKey)?})
Creates a SplayTreeMap where the keys and values are computed from the iterable.
factory
SplayTreeMap.fromIterables(Iterable<K> keys, Iterable<V> values, [int compare(K key1, K key2)?, bool isValidKey(dynamic potentialKey)?])
Creates a SplayTreeMap associating the given keys to values.
factory
SplayTreeMap.of(Map<K, V> other, [int compare(K key1, K key2)?, bool isValidKey(dynamic potentialKey)?])
Creates a SplayTreeMap that contains all key/value pairs of other. Example:
factory

Properties

entries Iterable<MapEntry<K, V>>
The map entries of this.
read-onlyoverride
hashCode int
The hash code for this object.
read-onlyinherited
isEmpty bool
Whether there is no key/value pair in the map.
read-onlyoverride
isNotEmpty bool
Whether there is at least one key/value pair in the map.
read-onlyoverride
keys Iterable<K>
The keys of this.
read-onlyoverride
length int
The number of key/value pairs in the map.
read-onlyoverride
runtimeType Type
A representation of the runtime type of the object.
read-onlyinherited
values Iterable<V>
The values of this.
read-onlyoverride

Methods

addAll(Map<K, V> other) → void
Adds all key/value pairs of other to this map.
override
addEntries(Iterable<MapEntry<K, V>> newEntries) → void
Adds all key/value pairs of newEntries to this map.
inherited
cast<RK, RV>() Map<RK, RV>
Provides a view of this map as having RK keys and RV instances, if necessary.
inherited
clear() → void
Removes all entries from the map.
override
containsKey(Object? key) bool
Whether this map contains the given key.
override
containsValue(Object? value) bool
Whether this map contains the given value.
override
firstKey() → K?
The first key in the map.
firstKeyAfter(K key) → K?
Get the first key in the map that is strictly larger than key. Returns null if no key was not found.
forEach(void f(K key, V value)) → void
Applies action to each key/value pair of the map.
override
lastKey() → K?
The last key in the map.
lastKeyBefore(K key) → K?
The last key in the map that is strictly smaller than key.
map<K2, V2>(MapEntry<K2, V2> transform(K key, V value)) Map<K2, V2>
Returns a new map where all entries of this map are transformed by the given convert function.
inherited
noSuchMethod(Invocation invocation) → dynamic
Invoked when a nonexistent method or property is accessed.
inherited
putIfAbsent(K key, V ifAbsent()) → V
Look up the value of key, or add a new entry if it isn't there.
override
remove(Object? key) → V?
Removes key and its associated value, if present, from the map.
override
removeWhere(bool test(K key, V value)) → void
Removes all entries of this map that satisfy the given test.
inherited
toString() String
A string representation of this object.
inherited
update(K key, V update(V value), {V ifAbsent()?}) → V
Updates the value for the provided key.
override
updateAll(V update(K key, V value)) → void
Updates all values.
override

Operators

operator ==(Object other) bool
The equality operator.
inherited
operator [](Object? key) → V?
The value for the given key, or null if key is not in the map.
override
operator []=(K key, V value) → void
Associates the key with the given value.
override