SplayTreeMap seems to lost key when custom compare function is provided

iDecode 0
Viewed 19

Minimum reproducible code:

void main() {
  var map = SplayTreeMap<String, int>((k1, k2) => k1.length - k2.length);
  map['foo'] = 2;
  map['bar'] = 1;
  map.forEach((k, v) => print('[$k]: $v'));
}

The output is:

[foo]: 1

Not only the value is swapped but also the bar key seems to be lost. However, the following code returns true.

print(map.containsKey('bar')); // true

So, how is this possible?

dart
1 Answers

If you read the documentation for SplayTreeMap you find:

Keys of the map are compared using the compare function passed in the constructor, both for ordering and for equality.

https://api.dart.dev/stable/2.18.0/dart-collection/SplayTreeMap-class.html

The relevant part here being that it is also used for "equality". So since both your keys (Strings) have the same length, they are being seen as equal since your k1.length - k2.length would return 0 (which means they should be seen as equal).

Since they are equal, SplayTreeMap will not add 'bar' as a second entry but instead see 'bar' as the same key as 'foo' and updates the value stored for this key.

julemand1010
Related