dartのpackage:collectionを完全に理解する（ジェネリクスがわからない人向け）

dartの外部パッケージのcollectionには標準ライブラリにはない便利なリスト操作のためのメソッドが追加されています。

ただジェネリクスに対する理解がないと公式ドキュメントを読んでも使い方がわからないと思いますので、サンプル付きで解説します。

公式APIドキュメント

この記事ではバージョン1.17.0を使用しています。

Dart3から標準ライブラリにnonNulls, firstOrNull, lastOrNull, singleOrNull, elementAtOrNull, indexedが追加されました。Dart3でdart:collectionに入った配列操作系のメンバーが便利 で解説しています。

読む前に

collectionパッケージは使用するときに以下のimportが必要です。
サンプルコードでは省略します。

import 'package:collection/collection.dart';

特に便利なものの一覧

• whereNotNull
  • リストからnullを除外したものを返します。
• elementAtOrNull
  • 範囲外の要素へアクセスした場合に例外ではなくnullを返します。
• firstOrNull, lastOrNull
  • リストの最初、または最後の要素を取得します。リストが空の場合にはnullを返します。
• sorted
  • ソートされたリストを新しく作って返します。非破壊メソッドです。
• max, min
  • 最大、最小値を取得します。
• sum
  • 合計を取得します。
• mapIndexed
  • mapするとき、同時にindexを取得することができます。asMap不要です。
• expandindexed
  • expandするとき、同時にindexを取得することができます。

IterableNullableExtension

リストの要素にnullが入る可能性のあるときに使えます。

whereNotNull

リストからnullを除外したものを返します。

const list = [1, 2, null, 3, 4];
final nonNullList = list.whereNotNull().toList();
// [1, 2, 3, 4]

このメソッドの良いところは型から?が外れるところです。

const list = [1, 2, null, 3, 4];
// List<int?>

final nonNullList = list.whereNotNull().toList();
// List<int>

whereを使って自分でnullを除外することもできますが、

final nonNullList = list.where((element) => element != null).toList();
// List<int?>

型はList<int?>のままになります。

?がついたままだとnullを除外しても必ずnullチェックが必要になりますが、whereNotNullではその必要がありません。

list.map((element) => element.sign);
// Error: Property 'sign' cannot be accessed on 'int?' because it is potentially null.

このメソッドはwhereType<X>()を使った下記のコードと同じ動作をします。

const list = [1, 2, null, 3, 4];
final nonNullList = list.whereType<int>().toList();
// List<int>

IterableExtension

Iterable<T> に機能を追加します。List、Map、Setなどで使えます。

firstOrNull, lastOrNull

リストの最初、または最後の要素を取得します。リストが空の場合にはnullを返します。
dart標準のList.first, List.lastはリストが空の場合にはErrorになります。

const list = <int>[];
print(list.first);
// Uncaught Error: Bad state: No element

print(list.firstOrNull);
// null

singleOrNull

リストの要素が一つだけの場合にその要素を取得します。

const list = [1];
print(list.singleOrNull);
// 1

リストが空の場合、または要素が２つ以上ある場合はnullが返ります。

const list = [1, 2, 3];
print(list.singleOrNull);
// null

elementAtOrNull

メソッド定義

T? elementAtOrNull(int index)

Listの要素対してアクセスする場合に、範囲外の要素へアクセスしようとすると例外が発生します。

const list = [0, 1, 2];
print(list[3]);
// Uncaught Error: RangeError (index): Index out of range: index should be less than 3: 3
print(list.elementAt(3));
// Uncaught Error: RangeError (index): Index out of range: index should be less than 3: 3

elementAtOrNullは範囲外の要素へアクセスした場合にはnullが返ります。

const list = [0, 1, 2];
print(list.elementAtOrNull(3));
// null

firstWhereOrNull, lastWhereOrNull

メソッド定義

T? firstWhereOrNull(bool test(T element))

firstWhereで条件にマッチする最初の要素を見つけるとき、条件にマッチするものがない場合にnullを返します。

const list = ['6', '8', '2'];
final first = list.firstWhereOrNull((element) {
  return int.parse(element).isOdd;
});
print(first);
// null

firstWhereIndexedOrNull, lastWhereIndexedOrNull

メソッド定義

T? firstWhereIndexedOrNull(bool test(int index, T element))

firstWhereをするとき、同時にindexを取得することができます。

const list = ['6', '8', '2'];
final first = list.firstWhereIndexedOrNull((index, element) {
  return element == index.toString();
});
print(first);
// 2

foldIndexed

メソッド定義

R foldIndexed<R>(R initialValue, R combine(int index, R previous, T element))

foldをするとき、同時にindexを取得することができます。

const list = [8, 6, 4];
final result = list.reversed.foldIndexed(0, (index, previous, element) {
  return previous + element * pow(10, index).toInt();
});
print(result);
// 864

groupListsBy

メソッド定義

Map<K, List<T>> groupListsBy<K>(K keyOf(T element))

class Person {
  const Person(this.name, this.sex);
  final String name;
  final String sex;

  @override
  String toString() {
    return name;
  }
}

void main() {
  const list = [
    Person('Bob', 'male'),
    Person('Alice', 'female'),
    Person('John', 'male'),
  ];

  print(list.groupListsBy<String>((e) => e.sex));
  // {
  //   male: [Bob, John],
  //   female: [Alice]
  // }
}

groupSetsBy

メソッド定義

Map<K, Set<T>> groupSetsBy<K>(K keyOf(T element))

groupListsByのSet版です。

groupFoldBy

メソッド定義

Map<K, G> groupFoldBy<K, G>(K keyOf(T element), G combine(G? previous, T element))

groupListsByしたあとに、foldをします。

class Person {
  const Person(this.name, this.sex);
  final String name;
  final String sex;
}

void main() {
  const list = [
    Person('Bob', 'male'),
    Person('Alice', 'female'),
    Person('John', 'male'),
  ];

  // 性別ごとに人数を数える
  print(list.groupFoldBy<String, int>((e) => e.sex, (previous, element) {
    return (previous ?? 0) + 1;
  }));
  // {male: 2, female: 1}
}

none

メソッド定義

bool none(bool test(T))

リスト内の要素すべてが条件を満たさないことを検証します。
これはiterable.every((x) => !test(x))や、!iterable.any(test)と同じです。

const list = [3, 7, 9, 13, 21, 37];
print(list.none((e) => e.isEven));
// true

sample

メソッド定義

List<T> sample(int count, [Random? random])

リストから指定された数の要素をランダムに選んで返します。

const list = [3, 7, 9, 13, 21, 37];
print(list.sample(3));
// [13, 21, 37]

sorted

メソッド定義

List<T> sorted(Comparator<T> compare)

ソートされたリストを作って返します。標準で用意されているsortは破壊的なので元のリストを変更しますが、sortedは新しくリストを作るため、元のリストを破壊しません。

const list = [3, 1, 4, 2, 5];

print(list.sorted((a, b) => a - b));
// [1, 2, 3, 4, 5]

print(list)
// [3, 1, 4, 2, 5] 元のリストは変更されない

list.sort();
print(list);
// [1, 2, 3, 4, 5] 元のリストが変更される

splitAfter, splitBefore

メソッド定義

Iterable<List<T>> splitAfter(bool test(T element))

条件を満たす要素のあとでリストを分割します。

// 奇数が出現したあとで要素を分割する。
const list = [90, 28, 71, 24, 85, 3, 44, 49, 13, 95];
print(list.splitAfter((e) => e.isOdd));
// ([90, 28, 71], [24, 85], [3], [44, 49], [13], [95])

splitBeforeは条件を満たす要素の前で分割します。

const list = [90, 28, 71, 24, 85, 3, 44, 49, 13, 95];
print(list.splitBefore((e) => e.isOdd));
// ([90, 28], [71, 24], [85], [3, 44], [49], [13], [95])

splitAfterIndexed, splitBeforeIndexedもあります。

splitBetween

メソッド定義

Iterable<List<T>> splitBetween(bool test(T first, T second))

条件を満たす要素のところで分割をしますが、条件を見るときに前後の要素を見ることができます。

// 前の要素より小さい数字が出現した箇所で分割
const list = [90, 28, 71, 24, 85, 3, 44, 49, 13, 95];
print(list.splitBetween((e1, e2) => e1 > e2));
// ([90], [28, 71], [24, 85], [3, 44, 49], [13, 95])

IterableNumberExtension

List<数値型>に機能を追加します。

average

リストの平均を取得します。

const list = [80, 56, 67, 91, 44];
print(list.average);
// 67.6

リストが空の場合Errorになります。

max, min

最大、最小値を取得します。reduceを使って書くよりも読みやすいと思います。

const list = [80, 56, 67, 91, 44];
print(list.max);
// 91
print(list.min);
// 44

リストが空の場合にはErrorになります。

minOrNull, maxOrNull

最大、最小値を取得します。

min, maxではリストが空の場合にErrorになります。

const list = <int>[];
print(list.max);
// Uncaught Error: Bad state: No element

Errorにして欲しくない場合はminOrNull、maxOrNullが使えます。

const list = <int>[];
print(list.maxOrNull);
// null

sum

合計を取得します。

const list = [80, 56, 67, 91, 44];
print(list.sum);
// 338

リストが空の場合は値が0になります。

IterableComparableExtension

min, max, minOrNull, maxOrNull

数値型でないクラスのリストに対してもmin, maxを使えるようにします。

Comparableが実装されたクラスであれば使うことができます。
stringはComparableが実装されており、辞書順に並び替えることができます。

const list = ['A', 'B', 'C', 'D', 'E'];
print(list.max);
// E

自分で作ったクラスであってもComparable<T>を実装することでmin, maxを使うことができます。

// テストの点数を保存するクラス
class TestResult implements Comparable<TestResult> {
  int math;  // 数学の点数
  int english;  // 英語の点数
  TestResult(this.math, this.english);
  
  @override
  int compareTo(other) {
    // 2つのテストの合計点で比較する
    return (math + english).compareTo((other.math + other.english));
  }
  
  @override
  String toString() {
    return "Math: $math, English: $english";
  }
}

void main() {
  var list = [
    TestResult(90, 80),
    TestResult(75, 60),
    TestResult(40, 30),
  ];
  // テストの合計点が最大の結果を取得する
  print(list.max);
  // Math: 90, English: 80
}

isSorted

メソッド定義

bool isSorted([Comparator<T>? compare])

リストがソートされているかどうかを返します。

print(['A', 'B', 'C'].isSorted());
// true

print(['B', 'C', 'A'].isSorted());
// false

ListExtensions

List に機能を追加します。

binarySearch

メソッド定義

int binarySearch(E element, int Function(E, E) compare)

二分探索で要素がリスト内の何番目にあるのかを検索します。二分探索の計算量は$\mathcal{O}(\log n)$です。
リストはソートされている必要があります。

const list = [0, 1, 2, 3, 4, 5];
print(list.binarySearch(1, (a, b) => a.compareTo(b)));
// 1

要素が見つからないとき、結果は-1になります。

print(list.binarySearch(999, (a, b) => a.compareTo(b)));
// -1

binarySearchBy

メソッド定義

int binarySearchBy<K extends Comparable<K>>(
        E element, K Function(E element) keyOf, [int start = 0, int? end])

二分探索でリスト内の要素を探索しますが、その際にキーを指定することができます。
以下の例ではTestResultのnameで要素を探します。
キーに指定することができるのはComparableを実装したもののみです。

class TestResult {
  String name;
  int math;
  int english;
  TestResult(this.name, this.math, this.english); 
}

void main() {
  var a = TestResult('A', 90, 80);
  var b = TestResult('B', 75, 60);
  var c = TestResult('C', 40, 30);
  var list = [a, b, c];
  
  // name を見て要素を探す
  print(list.binarySearchBy(c, (element) => element.name));
  // 2
}

第3、第4引数には検索する範囲を指定することができます。

var a = TestResult('A', 90, 80);
var b = TestResult('B', 75, 60);
var c = TestResult('C', 40, 30);
var d = TestResult('D', 30, 40);
var e = TestResult('E', 20, 65);
var list = [a, b, c, d, e];

// 3〜5番目の要素の範囲で探す
print(list.binarySearchBy(a, (element) => element.name, 2, 4));
// -1

binarySearchByCompare

メソッド定義

int binarySearchByCompare<K>(
        E element, K Function(E element) keyOf, int Function(K, K) compare,
        [int start = 0, int? end])

二分探索でリスト内の要素を探索しますが、その際に指定するキーがComparableを実装していなくても、比較する実装を与えることで探索できるようにします。

以下の例ではTestResultのmathはintでComparableを実装していませんが、第3引数で比較する関数を渡しています。

class TestResult {
  String name;
  int math;
  int english;
  TestResult(this.name, this.math, this.english); 
}

void main() {
  var a = TestResult('A', 20, 80);
  var b = TestResult('B', 30, 60);
  var c = TestResult('C', 40, 30);
  var d = TestResult('D', 50, 40);
  var e = TestResult('E', 60, 65);
  var list = [a, b, c, d, e];
    
  print(list.binarySearchByCompare<int>(
    d,
    (element) => element.math,
    (e1, e2) => e1.compareTo(e2),
  ));
  // 3
}

equals

メソッド定義

bool equals(
  List<E> other,
  [Equality<E> equality = const DefaultEquality()]
)

other に指定したリストと同じ順番で同じ要素を持っている場合 true を返します。

const listA = [1, 2, 3, 4, 5];
const listB = [1, 2, 3, 4, 5]; 
print(listA.equals(listB));
// true

同じ要素でも順番が違えば false になります。

const listA = [1, 2, 3, 4, 5];
const listB = [1, 3, 5, 2, 4]; 
print(listA.equals(listB));
// false

ただし2次元配列などを考えた場合、比較がうまく行かない場合があります。

var listA = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
];
var listB = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
];

// 同じ内容のリスト同士を比較する
print(listA.equals(listB));
// false

これはデフォルトではリストの要素同士の比較がインスタンス同士の比較になり、2次元配列の中のリストは別のインスタンスであるため、別のリストとして判定されてしまいます。

オプションの第2引数には比較するための実装を指定することができ、collectionライブラリにはList同士を比較するためのいくつかの実装が用意されています。

List同士を比較するListEqualityを使えば以下のように書くことができます。

print(listA.equals(listB, ListEquality<int>()));
// true

expandIndexed

メソッド定義

Iterable<R> expandIndexed<R>(
    Iterable<R> Function(int index, E element) expand) sync*

標準のexpandメソッドと同様ですが、同時にindexを取得することができます。

const list = [1, 2, 3, 4, 5];
print(list.expandIndexed((index, element) {
  return [element, 0];
}));
// (1, 0, 2, 0, 3, 0, 4, 0, 5, 0)

forEachIndexed

メソッド定義

void forEachIndexed(void Function(int index, E element) action)

標準のforEachメソッドと同様ですが、同時にindexを取得することができます。

const list = [1, 2, 3, 4, 5];
list.forEachIndexed((index, element) => print("$index: $element"));
// 0: 1
// 1: 2
// 2: 3
// 3: 4
// 4: 5

forEachwhile, forEachIndexedWhile

メソッド定義

void forEachWhile(bool Function(E element) action)

リストの要素に対して必要な限りの回数繰り返し処理をします。与えたメソッドの中でfalseを返した場合に途中で繰り返し処理を終了することができます。

const list = [1, 2, 3];
list.forEachWhile((element) {
  print(element);
  return element.isOdd;
});
// 1
// 2

lowerBound, lowerBoundBy, lowerBoundByCompare

メソッド定義

int lowerBound(E element, int Function(E, E) compare)

二分探索で、与えられた要素がリスト内のどの位置にあるのかを返します。
binarySearchと違って要素が見つからなかった場合に、リストの順序が保たれる追加位置を返します。

var list = [0, 1, 2, 3, 5];
int index = list.lowerBound(4, (a, b) => a - b);
// lowerBoundの結果の位置に要素を挿入するとソートされた状態が保たれる
list.insert(4, index);
print(list);
// [0, 1, 2, 3, 4, 5]

mapIndexed

メソッド定義

Iterable<R> mapIndexed<R>(R Function(int index, E element) convert) sync*

mapするとき、同時にindexを取得することができます。

const list = [1, 2, 3, 4, 5];
print(list.mapIndexed((index, element) => element * index));
// (0, 2, 6, 12, 20)

reverseRange

メソッド定義

void reverseRange(int start, int end)

リストの指定した範囲だけを逆順に並び替えます。破壊的メソッドです。
範囲にstartは含みますが、endは含みません。

var list = [1, 2, 3, 4, 5];
// 3番目から5番目の要素を逆順で並び替える
list.reverseRange(2, 5);
print(list);
// [1, 2, 5, 4, 3]

shuffleRange

メソッド定義

void shuffleRange(int start, int end, [Random? random])

var list = [1, 2, 3, 4, 5];
// 3番目から5番目の要素をランダムに並び替える
list.shuffleRange(2, 5);
print(list);
// [1, 2, 4, 3, 5] 

第3引数に乱数発生器を指定することができます。

メソッド定義

import 'dart:math';
list.shuffleRange(2, 5, Random.secure());

slice

メソッド定義

ListSlice<E> slice(int start, [int? end])

リストから指定した範囲を切り出したビューを作成します。このビューは元のリストを参照しているため、このビューを使用している間は元のリストのサイズを変更してはいけません。

このビューに対してリストの操作を行うことで、リストの一部分だけに操作を適用することができます。

const list = [1, 2, 3, 4, 5];
print(list.slice(2, 5).contains(1));
// false

slices

メソッド定義

Iterable<List<E>> slices(int length) sync*

与えられた長さごとにリストを区切って返します。

const list = [1, 2, 3, 4, 5];
print(list.slices(2));
// ([1, 2], [3, 4], [5])

sortBy

メソッド定義

void sortBy<K extends Comparable<K>>(K Function(E element) keyOf,
    [int start = 0, int? end])

keyOfで指定された要素を使って自然順で並び替えます。破壊的メソッドです。

class Person {
  Person(this.firstName, this.lastName);
  String firstName;
  String lastName;
}

void main() {
  var list = [
    Person('Bob', 'Johnson'),
    Person('Alice', 'Marshall'),
    Person('John', 'Williams')
  ];
  
  // firstNameで並び替え
  list.sortBy((element) => element.firstName);
  // [Alice Marshall, Bob Johnson, John Williams]

  // lastNameで並び替え
  list.sortBy((element) => element.lastName);
  // [Bob Johnson, Alice Marshall, John Williams]
}

sortByCompare

メソッド定義

void sortByCompare<K>(
    K Function(E element) keyOf, int Function(K a, K b) compare,
    [int start = 0, int? end])

keyOfで指定された要素を使って自然順で並び替えます。sortByのComparatorを指定できるバージョンです。

class Person {
  Person(this.firstName, this.lastName, this.age);
  String firstName;
  String lastName;
  int age;
  
  @override
  String toString() {
    return "$firstName $lastName ($age)";
  }
}

void main() {
  var list = [
    Person('Bob', 'Johnson', 35),
    Person('Alice', 'Marshall', 57),
    Person('John', 'Williams', 23)
  ];
  
  // firstNameで並び替え
  list.sortByCompare<int>((element) => element.age, (a, b) => a - b);
  print(list);
  // [John Williams (23), Bob Johnson (35), Alice Marshall (57)]
}

sortRange

メソッド定義

void sortRange(int start, int end, int Function(E a, E b) compare)

リスト内の指定した範囲をソートします。

var list = [5, 2, 1, 8, 3];
list.sortRange(2, 5, (a, b) => a -b);
print(list);
// [5, 2, 1, 3, 8]

swap

メソッド定義

void swap(int index1, int index2)

リスト内の2つの要素を交換します。

var list = [0, 1, 2, 3, 4];
list.swap(2, 3);
print(list);
// [0, 1, 3, 2, 4]

whereIndexed, whereNotIndexed

メソッド定義

Iterable<E> whereIndexed(bool Function(int index, E element) test) sync*

whereするとき、同時にindexを取得することができます。

const list = [4, 1, 9, 3, 5];
print(list.whereIndexed((index, element) => index == element));
// (1, 3)

IterableIterableExtension

flattened

2次元配列を１次元配列にします（平坦化）。

print([[1, 2], [3, 4]].flattened);
// (1, 2, 3, 4)

３次元配列以上のものを指定しても１階層の平坦化しかできません。

print([
  [
    [1, 2],
    [3, 4]
  ],
  [
    [5, 6],
    [7, 8]  
  ]
].flattened);
// ([1, 2], [3, 4], [5, 6], [7, 8])

ComparatorExtension

Comparatorに機能を追加します。

inverse

与えられたComparatorを逆順にします。ある順に並べるComparatorを使ってソートする場合、.inverseを使うだけで逆順にソートされます。

var list = ['B', 'E', 'A', 'D', 'C'];
list.sort(compareAsciiLowerCase);
print(list);
// [A, B, C, D, E]

list.sort(compareAsciiLowerCase.inverse);
print(list);
// [E, D, C, B, A]

compareBy

メソッド定義

Comparator<R> compareBy<R>(T Function(R) keyOf)

あまりいい活用例が思いつかないので考え中

Functions

単体で利用できる便利メソッドです。

binarySearch

メソッド定義

int binarySearch<E>(List<E> sortedList, E value,
    {int Function(E, E)? compare})

リストを二分探索します。リストの要素がComparableを実装している場合は第３引数のcompareを省略することができます。

const list = [0, 1, 2, 3, 4, 5];
print(binarySearch(list, 2));
// 2

equalsIgnoreAsciiCase

ASCII文字の大文字小文字を無視して2つの文字列が等しいかどうか判定します。
ASCII文字以外はそのまま比較します。

print(equalsIgnoreAsciiCase('A', 'a'));  // true
print(equalsIgnoreAsciiCase('a', 'B'));  // false
print(equalsIgnoreAsciiCase('Æ', 'æ'));  // false

groupBy

メソッド定義

Map<T, List<S>> groupBy<S, T>(Iterable<S> values, T Function(S) key)

リストをグループ化します。グループ化する際のキーを指定することができます。
同じ機能のIterableExtension<T>.groupListsByも使えます。

class Person {
  const Person(this.name, this.sex);
  final String name;
  final String sex;

  @override
  String toString() {
    return name;
  }
}

void main() {
  const list = [
    Person('Bob', 'male'),
    Person('Alice', 'female'),
    Person('John', 'male'),
  ];

  print(groupBy<Person, String>(list, (e) => e.sex));
  // {
  //   male: [Bob, John],
  //   female: [Alice]
  // }
}

maxBy, minBy

メソッド定義

S? maxBy<S, T>(Iterable<S> values, T Function(S) orderBy,
    {int? Function(T, T)? compare})

リストの要素から最大、最小のものを取得します。orderByで要素のどの変数を利用して並び替えるかを指定することができます。

リストが空の場合はnullが返ります。

class Person {
  const Person(this.name, this.age);
  final String name;
  final int age;

  @override
  String toString() {
    return "$name ($age)";
  }
}

void main() {
  const list = [
    Person('Bob', 13),
    Person('Alice', 47),
    Person('John', 29),
  ];

  // age(年齢)で並び替えたときの最大を取得する
  print(maxBy<Person, int>(list, (e) => e.age));
  // Alice (47)
}

insertionSort

メソッド定義

void insertionSort<E>(List<E> elements,
    {int Function(E, E)? compare, int start = 0, int? end})

リストを挿入ソートで並び替えます。挿入ソートは平均計算量が$\mathcal{O}(n^2)$なのでdart標準のsortよりは遅いですが、in-placeアルゴリズムなのでメモリを節約することができます。

dart標準のソートはDual-pivot quicksortで、平均計算量は$\mathcal{O}(n \log n)$です。

var list = [3, 6, 1, 2, 9, 5];
insertionSort(list);
print(list);
// [1, 2, 3, 5, 6, 9]

lastBy

メソッド定義

Map<T, S> lastBy<S, T>(Iterable<S> values,T key(S))

指定されたkey別にリストを集計し、それぞれのkeyごとに最後の要素を集めて返します。

class Person {
  const Person(this.name, this.age);
  final String name;
  final int age;

  @override
  String toString() {
    return name;
  }
}

void main() {
  const list = [
    Person('Bob', 13),
    Person('Alice', 13),
    Person('Charlie', 13),
    Person('John', 29),
  ];

  print(lastBy<Person, int>(list, (e) => e.age));
  // {13: Charlie, 29: John}
}

mergeSort

メソッド定義

void mergeSort<E>(List<E> elements,
    {int start = 0, int? end, int Function(E, E)? compare})

リストをマージソートで並び替えます。

マージソートは最悪計算量が$\mathcal{O}(n \log n)$で、クイックソートの$\mathcal{O}(n^2)$よりも良いですが、空間計算量が$\mathcal{O}$必要です。通常はクイックソートの方が高速です。安定ソートです。

var list = [3, 6, 1, 2, 9, 5];
mergeSort(list);
print(list);
// [1, 2, 3, 5, 6, 9]

reverse

メソッド定義

void reverse<E>(List<E> elements, [int start = 0, int? end])

リストの順序を反転させます。in-placeアルゴリズムです。

var list = [1, 2, 3, 4, 5];
reverse(list);
print(list);
// [5, 4, 3, 2, 1]

shuffle

メソッド定義

void shuffle(List elements, [int start = 0, int? end, Random? random])

リストをランダムに並び替えます。

var list = [1, 2, 3, 4, 5];
shuffle(list);
print(list);
// [2, 5, 1, 4, 3]

Compatrator

通常あるオブジェクトをソートできるようにする場合は、Comparableを実装しますが、場合によってはソート順が一意に決まらないことがあります。

例えばD B a cという文字列があった場合、a c B Dと並び替えたり、a B c Dと並び替えることもできます。こういった場合に並び順だけを指定する関数を作ってソート処理に渡すことができるようになっています。この関数をComparatorと呼びます。

Comparator

typedef Comparator<T> = int Function(T a, T b);

dart標準のsortメソッドにもComparatorを渡せるようになっており、以下のように独自のComparatorを定義してソートすることができます。

var numSorter = (int a, int b) {
  return a - b;
};

void main() {
  var list = [3, 1, 6, 2, 4];
  list.sort(numSorter);
  print(list);
  // [1, 2, 3, 4, 6]
}

一般的には文字列に関する並び替えで使うことが多いですが、collection packageにはいくつかのComparatorがあらかじめ定義されていて使うことができます。

compareAsciiLowerCase

ASCII文字をすべて小文字としてソートします。ASCII文字以外は変換しません。

const list = ['D', 'a', 'C', 'b'];
print(list.sorted(compareAsciiLowerCase));
// [a, b, C, D]

compareAsciiLowerCaseNatural

ASCII文字の大文字は小文字に変換されたあと自然順でソートされます。

compareAsciiUpperCase

ASCII文字をすべて大文字に変換したあとソートします。ASCII文字以外は変換しません。

compareAsciiUpperCaseNatural

ASCII文字の小文字は大文字に変換されたあと自然順でソートされます。

compareNatural

文字列を自然順でソートします。

例えばASCII順でソートされた文字列

[a, a1, a10, a9, aa]

を自然順でソートすると

[a, a1, a9, a10, aa]

となります。辞書順ではa10よりa9の方が先ですが、人間にとってはa9が先にくるほうが自然です。このような並び方を自然順(Natural sort order)と呼びます。

compareNaturalでは自然順のComparatorを提供します。

var list = ["a", "a1", "a9", "a10", "aa"];
print(list.sorted(compareNatural));
// [a, a1, a9, a10, aa]

Classes

BoolList

bool型trueとfalseだけを表すので1bitで足りますが、メモリ上はそうなっていません。dartのboolサイズは実装依存ですが、iPhoneでは8byte(64bit)になっているようです。これは処理しやすいようにレジスタのサイズに合わせていているものと思います。

さて、1bitで表現できる情報に64bitの入れ物を使っていますので少量使うだけなら問題ありませんが、List<bool>で大量のbool変数を扱う場合にはメモリの無駄づかいが気になってきます。このような場合に使えるのがBoolListです。

内部的にはint型変数に隙間なく詰め込むことでメモリを節約しています。intに詰め込むとメモリを節約できますが、出し入れするときに複雑なビット演算が必要になります。このクラスはそれを代行してお手軽に扱えるようにしてくれます。

var list = BoolList.generate(100, (index) => index.isOdd);
print(list);
// [false, true, false, true, ...

CanonicalizedMap<C, K, V>

キーを正規化したMapを作成します。

たとえばMapのキーを文字列にして、大文字小文字を区別したくない場合に使うことができます。

コンストラクタ定義

CanonicalizedMap(C canonicalize(K key), {bool isValidKey(K key)?})

// キーをすべて小文字に正規化する
var map = CanonicalizedMap<String, String, int>((key) => key.toLowerCase()); 
map['test'] = 1;
map['Test'] = 2; // test と Test は同じキーとして扱われる
map['hoge'] = 3;

print(map);　// {Test: 2, hoge: 3}
print(map['TEST']); // 2

CanonicalizedMap<C, K, V>はLinkedHashMap<K, V>に独自の==オペレーターとhashCodeを実装して使うよりもより効率的です。CanonicalizedMapではキーの正規化が一度だけ行われるためです。

CombinedIterableView

コンストラクタ定義

CombinedIterableView(Iterable<Iterable<T>> _iterables)

複数のIterableを組み合わせて一つのIterableにします。
これはViewなので、内部で元のIterableを参照します。

const list = CombinedIterableView([[1, 2, 3], [4, 5, 6], [7, 8, 9]]);
print(list);
// (1, 2, 3, 4, 5, 6, 7, 8, 9)

CombinedMapView<K, V>

コンストラクタ定義

CombinedMapView(Iterable<Map<K, V>> _maps)

複数のMapを組み合わせて平坦化された一つのMapビューを作成します。
これはViewなので、内部で元のMapを参照します。

const map1 = { 'foo': 'bar' };
const map2 = { 'hoge': 'fuga' };
print(CombinedMapView([map1, map2]));
// {foo: bar, hoge: fuga}

CombinedListView

コンストラクタ定義

CombinedListView(List<List<T>> _lists)

CombinedIterableViewのList版です。

Equality

リストやその要素が等価であることを確認する方法を提供します。

dartのリストは==演算子をオーバーライドしていないため、同じ要素を持つリスト同士を比較しても等価と判定されないことがあります。

var list1 = [1, 2, 3];
var list2 = [1, 2, 3];
print(list1 == list2);
// false

たとえばListEqualityを使うとリスト同士の比較は下のように書くことができます。

var list1 = [1, 2, 3];
var list2 = [1, 2, 3];
print(ListEquality().equals(list1, list2));
// true

CaseInsensitiveEquality

大文字小文字を無視して文字列を比較するEqualityです。

print(CaseInsensitiveEquality().equals('a', 'A'));
// true

DeepCollectionEquality

2つのリストやMapを深い等価比較で同一であるかどうか判定します。

一次元の配列であればListEqualityを使うことで2つのリストが同じであるかどうか判定することができました。しかし、2次元配列のようにリストの中にリスト、リストの中にMapが入っているような場合には判定ができません。

var list1 = [[1, 2], [3, 4]];
var list2 = [[1, 2], [3, 4]];
print(ListEquality().equals(list1, list2));            // false

このような場合にDeepCollectionEqualityはより深い等価比較を行います。

print(DeepCollectionEquality().equals(list1, list2));  // true

DeepCollectionEquality()は比較つする2つのリストがソートされている必要がありますが、DeepCollectionEquality.unorderedコンストラクタを使うことでソートされていなくても判定することができます。

var list1 = [[1, 2], [3, 4]];
var list2 = [[3, 4], [1, 2]];
print(DeepCollectionEquality().equals(list1, list2));            // false
print(DeepCollectionEquality.unordered().equals(list1, list2));  // true

比較可能な対象はList、Set、Iterable、Mapです。

DefaultEquality

オブジェクト自身の==やhashCodeを使って等価比較を行うEqualityです。
いろんなメソッドのデフォルト値として使われています。

EqualityBy

コンストラクタ定義

EqualityBy(F comparisonKey(E), [Equality<F> inner = const DefaultEquality<Never>()])

Equalityを生成します。例えば下記のようなEmployeeクラスがあったとき、

class Employee {
  Employee(this.id, this.name);
  final int id;
  final String name;
}

EqualityByを使って、idで等価比較するEqualityを作ることができます。

var person1 = Employee(123, 'Bob');
var person2 = Employee(208, 'Bob');
var employeeEquality = EqualityBy((Employee e) => e.id);

print(employeeEquality.equals(person1, person2));
// false (名前は一緒だけどidが違うので別人として判定される)

EqualityMap

Equalityを使ってキーの等価判定を行うMapを作ります。
キーの大文字小文字を無視したMapを作りたいとき、CaseInsensitiveEqualityを使って以下のようにMapを作れます。

var map = EqualityMap<String, String>(CaseInsensitiveEquality());
map['foo'] = 'bar';
map['FOO'] = 'Bar';
print(map);
// {foo: Bar} 大文字小文字の違いが無視されるので要素がひとつだけになる

CanonicalizedMapでは正規化方法が指定できるが、EqualityMapでは指定できないためキーは最初に入った要素のものが使用される。

EqualitySet

EqualityMapのSet版です。。

ListEquality, IterableEquality

List同士を比較するEqualityです。比較する2つのリストの長さが等しく、同じ位置にある要素同士が同じものであれば2つのリストは等しいとみなされます。

var list1 = [1, 2, 3];
var list2 = [1, 2, 3];
print(ListEquality().equals(list1, list2));
// true

MapEquality

Map同士を比較するEqualityです。比較する2つのMapの要素数が等しく、同じKeyに対するValueのペアがすべて等しければ2つのMapは等しいとみなされます。

var map1 = { 'foo': 'bar' };
var map2 = { 'foo': 'bar' };
print(MapEquality().equals(map1, map2));
// true

SetEquality

Set同士を比較するEqualityです。比較する2つのSetの長さが等しく、要素が同じ組で構成されている場合に2つのSetは等しいとみなされます。

var set1 = {1, 2, 3, 4, 5};
var set2 = {1, 2, 3, 4, 5};
print(SetEquality().equals(set1, set1));
// true

UnorderedIterableEquality

ソートされていないリスト同士を比較するEqualityです。Comparable<T>が実装されていなくても使うことができます。

var list1 = [1, 2, 3, 4, 5];
var list2 = [4, 1, 3, 5, 2];
print(UnorderedIterableEquality().equals(list1, list2));
// true

Delegating

使い道がよくわからない

Queue

先入れ先出し(Fisrt In, First Out: FIFO)のデータ構造、待ち行列を提供します。

QueueList

QueueとListの両方の効率的な実装です。

dartには標準でListQueueが存在しますが、それとほぼ同じような実装になっているようです。多少効率的っぽいですが、わざわざこちらの実装を使わなくても良さそうに見えます。

PriorityQueue

優先度付きキューです。入れた順番に関わらず、優先度が高いものから順に取り出すことができます。

class Ticket {
  Ticket(this.priority, this.title);
  int priority;
  String title;
  
  @override
  String toString() {
    return title;
  }
}

void main() {  
  var queue = PriorityQueue<Ticket>((e1, e2) => e1.priority.compareTo(e2.priority));
  queue.add(Ticket(100, 'normal'));
  queue.add(Ticket(1, 'emergency'));
  queue.add(Ticket(50, 'high'));
  
  print(queue.removeFirst());  // emergency
  print(queue.removeFirst());  // high
  print(queue.removeFirst());  // normal
}

要素に優先度で比較するComparator<T>を実装していれば、PriorityQueueのコンストラクタ引数を省略することができます。

class Ticket implements Comparable<Ticket> {
  Ticket(this.priority, this.title);
  int priority;
  String title;
  
  @override
  int compareTo(Ticket other) {
    return priority.compareTo(other.priority);
  }
  
  @override
  String toString() {
    return title;
  }
}

void main() {  
  var queue = PriorityQueue<Ticket>();
  queue.add(Ticket(100, 'normal'));
  queue.add(Ticket(1, 'emergency'));
  queue.add(Ticket(50, 'high'));
  print(queue.removeFirst());
  print(queue.removeFirst());
  print(queue.removeFirst());
}

HeapPriorityQueue

PriorityQueueのデフォルト実装です。PriorityQueueを使うとこの実装が利用されます。HeapPriorityQueueを直接使うのではなく、PriorityQueueを使うようにしたほうが良いでしょう。

Iterable Zip

IterableZip

コンストラクタ定義

IterableZip(Iterable<Iterable<T>> iterables)

複数の配列から順番に値を取り出して新しい配列にします。いろんな言語でzip関数として実装されているものです。

var list = IterableZip([
  [24, 56, 67, 89],
  ['Bob', 'Alice', 'John', 'Jimmy']
]);
print(list);
// ([24, Bob], [56, Alice], [67, John], [89, Jimmy])

Union

複数のSetを組み合わせて使う機能を提供します。

UnionSet

コンストラクタ定義

UnionSet(Set<Set<E>> sets, {bool disjoint = false})
UnionSet.from(Iterable<Set<E>> sets, {bool disjoint = false})

複数のSetを組み合わせて一つのSetに見えるViewを作成します。

var set = UnionSet.from(
  [
    {1, 2},
    {3, 4},
    {5},
  ],
);
print(set);
// {1, 2, 3, 4, 5}

与えれたSetに含まれている要素が重複しないことがわかっている場合は引数disjointをtrueにすることで各種操作が効率的になります。

UnionSetController

中身のSetがころころと変わる場合にUnionSetを便利に作ることができるクラスです。

final setController = UnionSetController<int>();

var set1 = {1, 2, 3};
var set2 = {4, 5, 6};

setController.add(set1);
setController.add(set2);
print(setController.set);
// {1, 2, 3, 4, 5, 6}

setController.remove(set2);
print(setController.set);
// {1, 2, 3}

NonGrowable

NonGrowableListView

あるリストから長さが固定されているリストのViewを生成します。
addやremoveなどのリストの長さを変えるような操作を行うとUnsupportedErrorが発生します。

var baseList = [1, 2, 3, 4, 5];
var list = NonGrowableListView(baseList);

list.add(6);
// Uncaught Error: Unsupported operation: Cannot change the length of a fixed-length list

sortのようにリストの長さが変わらない操作であれば実行することができます。

var baseList = [1, 2, 3, 4, 5];
var list = NonGrowableListView(baseList);
list.sort();
// No Error

Unmodifiable

変更不可能なViewを生成します。

UnmodifiableListView

あるリストから変更不可能なリストのViewを生成します。

var baseList = [1, 2, 3, 4, 5];
var list = UnmodifiableListView(baseList);

list.add(6);
// Uncaught Error: Unsupported operation: Cannot add to an unmodifiable list

baseList.add(6);
// 元のリストには追加できる

UnmodifiableMapView

あるMapから変更不可能なMapのViewを生成します。

var months = {1: 'January', 2: 'February', 3: 'March'};
var map = UnmodifiableMapView(months);
map.remove(1);
// Uncaught Error: Unsupported operation: Cannot modify unmodifiable map

UnmodifiableSetView

あるSetから変更不可能なSetのViewを生成します。

var baseSet = {1, 2, 3, 4, 5};
var set = UnmodifiableSetView(baseSet);
set.remove(1); 
// Uncaught Error: Unsupported operation: Cannot modify an unmodifiable Set

Graph

グラフ構造に対して使える関数です。

stronglyConnectedComponents

メソッド定義

List<Set<T>> stronglyConnectedComponents<T>(Map<T, Iterable<T>> graph)

有向グラフに対して強連結成分分解を行います。

Wikipediaの解説のままですが、以下のような有向グラフがあるとき

有向グラフはコード上でMap<T, Iterable<T>>を使って以下のように表現できます。
各頂点に対して、エッジの集合を記載します。

const Map<String, List<String>> graph = {
  'A': ['B'],
  'B': ['C', 'E', 'F'],
  'C': ['D', 'G'],
  'D': ['C', 'H'],
  'E': ['A', 'F'],
  'F': ['G'],
  'G': ['F'],
  'H': ['D', 'G'],
};

このとき、エッジがない頂点であっても頂点の情報はMapに含める必要があります。
このグラフに対して強連結成分分解を行うには以下のようにします。

var scc = stronglyConnectedComponents(graph);
print(scc);
// [{E, B, A}, {H, D, C}, {F, G}]

transitiveClosure

Map<T, Set<T>> transitiveClosure<T>(Map<T, Iterable<T>> graph)

有向グラフから推移閉包を求めます。各頂点からの到達可能性を表すグラフを得ることができます。

var tc = transitiveClosure(graph);
// {
//   A: {B, C, E, F, D, G, H, A},
//   B: {C, E, F, D, G, H, A, B},
//   C: {D, G, C, H, F},
//   D: {C, H, D, G, F},
//   E: {A, F, B, C, E, D, G, H},
//   F: {G, F},
//   G: {F, G},
//   H: {D, G, C, H, F}
// }