Dart中SplayTreeSet插入元素时如何获取其插入位置？

SplayTreeSet 本身没有提供插入时直接返回元素索引的API——它是基于排序树实现的有序集合，核心优化方向是快速插入、删除和查找操作，维护索引这类线性结构属性会额外增加成本，因此官方没有内置相关方法。

你提到用length - 1获取位置确实不可靠：SplayTreeSet会根据指定的比较器自动给元素排序，插入的元素会被放到符合排序规则的位置，几乎不会固定在集合末尾。

要在插入时直接得到元素的索引，可以用以下两种实用方式：

方法一：统计前置元素数量 #

根据集合的比较器逻辑，统计所有排在待插入元素之前的元素个数，这个数值就是插入后的索引。

示例（默认升序比较器）：

import 'dart:collection';

void main() {
  var set = SplayTreeSet<int>();
  set.addAll([2, 4, 6]);
  
  int newElement = 5;
  // 统计所有小于5的元素数量，即插入后的索引
  int insertIndex = set.where((e) => e < newElement).length;
  
  set.add(newElement);
  print(insertIndex); // 输出2，对应5在集合中的索引
}

如果是自定义降序比较器，只需把判断条件改成e > newElement即可。

方法二：二分查找优化性能 #

当集合元素较多时，遍历统计的效率为O(n)，可以借助二分查找快速定位插入位置（O(log n)），需要依赖collection包的binarySearch方法：

import 'dart:collection';
import 'package:collection/collection.dart';

void main() {
  var set = SplayTreeSet<int>();
  set.addAll([2, 4, 6]);
  
  int newElement = 5;
  var sortedList = set.toList(); // SplayTreeSet的toList()返回有序列表
  int searchResult = binarySearch(sortedList, newElement);
  
  // binarySearch找不到元素时返回 -(插入位置 + 1)，需转换为实际索引
  int insertIndex = searchResult >= 0 ? searchResult : -(searchResult + 1);
  
  set.add(newElement);
  print(insertIndex); // 输出2
}

这种方式更适合大数据量场景，性能优势显著。

需要注意：如果待插入元素已存在于集合中，add方法不会执行插入操作，此时计算出的索引就是该元素已有的位置。

内容的提问来源于stack exchange，提问作者Fabrizio