Dart SplayTreeMap
last modified April 4, 2025
In Dart, SplayTreeMap is a self-balancing binary search tree that maintains entries in sorted order. It provides efficient lookup, insertion, and deletion operations.
SplayTreeMap implements the Map interface and keeps keys sorted according to their natural order or a custom comparator. It automatically reorganizes itself to optimize access patterns.
Creating a SplayTreeMap
The simplest way to create a SplayTreeMap is using the constructor. Entries are automatically sorted by key.
import 'dart:collection';
void main() {
var scores = SplayTreeMap<String, int>();
scores['Bob'] = 85;
scores['Alice'] = 90;
scores['Charlie'] = 95;
print(scores);
}
We create a SplayTreeMap of name-score pairs. The keys are automatically sorted in ascending order. Notice the insertion order doesn't affect the final order.
$ dart main.dart
{Alice: 90, Bob: 85, Charlie: 95}
Custom Sorting with Comparator
We can provide a custom comparator to define our own sorting order for keys.
import 'dart:collection';
void main() {
var products = SplayTreeMap<String, double>(
(a, b) => b.compareTo(a) // Sort in descending order
);
products['Laptop'] = 999.99;
products['Mouse'] = 19.99;
products['Keyboard'] = 49.99;
print(products);
}
The comparator function reverses the natural string ordering. This results in products being sorted from Z to A alphabetically.
$ dart main.dart
{Mouse: 19.99, Laptop: 999.99, Keyboard: 49.99}
Accessing First and Last Elements
SplayTreeMap provides efficient access to its first and last elements due to its sorted nature.
import 'dart:collection';
void main() {
var temperatures = SplayTreeMap<DateTime, double>();
temperatures[DateTime(2023, 1, 15)] = -5.2;
temperatures[DateTime(2023, 1, 10)] = -8.1;
temperatures[DateTime(2023, 1, 20)] = 2.4;
print('First date: ${temperatures.firstKey()}');
print('Last date: ${temperatures.lastKey()}');
print('Lowest temp: ${temperatures[temperatures.firstKey()]}');
print('Highest temp: ${temperatures[temperatures.lastKey()]}');
}
We store temperature readings with dates as keys. The firstKey and lastKey methods give us the earliest and latest dates efficiently.
$ dart main.dart First date: 2023-01-10 00:00:00.000 Last date: 2023-01-20 00:00:00.000 Lowest temp: -8.1 Highest temp: 2.4
Range Operations
SplayTreeMap supports efficient range queries using from, to, and between operations.
import 'dart:collection';
void main() {
var studentGrades = SplayTreeMap<int, String>();
studentGrades[101] = 'A';
studentGrades[102] = 'B';
studentGrades[103] = 'C';
studentGrades[104] = 'A';
studentGrades[105] = 'B';
print('Grades from ID 102:');
print(studentGrades.from(102));
print('\nGrades between 102 and 104:');
print(studentGrades.range(102, 104));
}
We can efficiently retrieve subsets of the map based on key ranges. The from method gets all entries from a key onward, while range gets entries between two keys.
$ dart main.dart
Grades from ID 102:
{102: B, 103: C, 104: A, 105: B}
Grades between 102 and 104:
{102: B, 103: C}
Performance Optimization with Splaying
SplayTreeMap automatically moves frequently accessed elements closer to the root for faster access.
import 'dart:collection';
void main() {
var cache = SplayTreeMap<String, String>();
// Initial population
for (var i = 0; i < 100; i++) {
cache['key$i'] = 'value$i';
}
// Access pattern - frequent access to key42
for (var i = 0; i < 1000; i++) {
var value = cache['key42']; // This access becomes faster over time
if (i % 100 == 0) {
print('Accessed key42 ${i + 1} times');
}
}
}
The splaying behavior optimizes access to frequently used keys. After many accesses, 'key42' will be near the root of the tree for faster lookup.
$ dart main.dart Accessed key42 1 times Accessed key42 101 times Accessed key42 201 times Accessed key42 301 times Accessed key42 401 times Accessed key42 501 times Accessed key42 601 times Accessed key42 701 times Accessed key42 801 times Accessed key42 901 times
Best Practices
- Sorted Data: Use when you need data sorted by keys.
- Access Patterns: Ideal for uneven access distributions.
- Comparator: Provide one for custom sorting logic.
- Key Types: Ensure keys are comparable or provide comparator.
Source
Dart SplayTreeMap Documentation
This tutorial covered Dart's SplayTreeMap with practical examples demonstrating its key features and usage patterns for sorted key-value collections.
Author
List all Dart tutorials.