ZetCode

Dart SplayTreeSet

最后修改于 2025 年 4 月 4 日

在 Dart 中，SplayTreeSet 是 Set 的一种自平衡二叉搜索树实现。它以排序顺序维护元素，并提供高效的操作。

SplayTreeSet 实现 Set 接口并自动对元素进行排序。它使用 splay 树操作，为大多数操作提供摊销 O(log n) 的性能。

创建 SplayTreeSet

创建 SplayTreeSet 最简单的方法是使用构造函数。

main.dart 
import 'dart:collection';

void main() {
  var numbers = SplayTreeSet<int>();
  numbers.addAll([5, 3, 7, 1, 9]);
  
  print(numbers);
}

我们创建一个 SplayTreeSet 整数集合。addAll 方法一次添加多个元素。集合会自动以排序顺序维护元素。

$ dart main.dart
{1, 3, 5, 7, 9}

使用 Comparator 进行自定义排序

我们可以提供自定义比较器来定义我们自己的排序顺序。

main.dart 
import 'dart:collection';

void main() {
  var names = SplayTreeSet<String>((a, b) => b.compareTo(a));
  names.addAll(['Alice', 'Bob', 'Charlie', 'David']);
  
  print(names);
}

这会创建一个按字母反向排序的 SplayTreeSet。比较器函数定义了集合中元素的排序方式。

$ dart main.dart
{David, Charlie, Bob, Alice}

第一个和最后一个元素

SplayTreeSet 提供对第一个和最后一个元素的有效访问。

main.dart 
import 'dart:collection';

void main() {
  var prices = SplayTreeSet<double>();
  prices.addAll([19.99, 9.99, 29.99, 14.99]);
  
  print('First: ${prices.first}');
  print('Last: ${prices.last}');
  print('Elements >= 15: ${prices.from(15.0)}');
}

我们访问集合中的最小和最大元素。from 方法返回大于或等于给定值的元素的视图。

$ dart main.dart
First: 9.99
Last: 29.99
Elements >= 15: {19.99, 29.99}

范围操作

SplayTreeSet 支持使用 from、to 和 between 进行高效的范围查询。

main.dart 
import 'dart:collection';

void main() {
  var years = SplayTreeSet<int>();
  years.addAll([2000, 2010, 2020, 2030, 2040]);
  
  print('Years after 2020: ${years.from(2021)}');
  print('Years up to 2030: ${years.to(2030)}');
  print('Years 2010-2030: ${years.range(2010, 2030)}');
}

这些操作返回原始集合的视图。它们很高效，因为它们利用了树结构，而无需创建新集合。

$ dart main.dart
Years after 2020: {2030, 2040}
Years up to 2030: {2000, 2010, 2020, 2030}
Years 2010-2030: {2010, 2020, 2030}

SplayTreeSet 中的自定义对象

使用自定义对象时，我们必须提供比较器或实现 Comparable。

main.dart 
import 'dart:collection';

class Product implements Comparable<Product> {
  final String name;
  final double price;
  
  Product(this.name, this.price);
  
  @override
  int compareTo(Product other) => price.compareTo(other.price);
  
  @override
  String toString() => '$name: \$$price';
}

void main() {
  var products = SplayTreeSet<Product>();
  products.addAll([
    Product('Laptop', 999.99),
    Product('Phone', 699.99),
    Product('Tablet', 399.99)
  ]);
  
  print(products);
}

Product 类实现 Comparable 来定义自然排序。SplayTreeSet 使用它来按价格对产品进行排序。

$ dart main.dart
{Tablet: $399.99, Phone: $699.99, Laptop: $999.99}

最佳实践

来源

Dart SplayTreeSet 文档

本教程介绍了 Dart 的 SplayTreeSet，并通过实际示例演示了其关键功能和用于排序集合的用法模式。

作者

我叫 Jan Bodnar，我是一名充满热情的程序员，拥有丰富的编程经验。我自 2007 年以来一直在撰写编程文章。迄今为止，我已撰写了 1,400 多篇文章和 8 本电子书。我在教授编程方面拥有十多年的经验。

列出 所有 Dart 教程。