Go言語ソース覗き見〜slicesパッケージ〜
Go言語のバージョン1.21で標準ライブラリに新たに追加された、slicesパッケージのソースコードをざっと読んでみました。
slicesパッケージではスライスを操作するのに便利な様々な関数が用意されています。
この記事ではソースコードに触れつつ主要どころの関数の説明をしていきたいと思います。
※ソースコードで頻出しているジェネリクスの書き方に関しては、先日の記事で説明しているので参照ください。
Equal
func Equal[S ~[]E, E comparable](s1, s2 S) bool { if len(s1) != len(s2) { return false } for i := range s1 { if s1[i] != s2[i] { return false } } return true }
引数に与えられた2つのスライスの要素が全く同じかを判定する関数です。
それぞれのスライスの要素を1から順番に比較していき、等式が成り立たなくなった時点でfalseを返す実装になっています。
引数のスライスの要素はcomparableなものに限られます。要素比較をするので当然ですね。
EqualFunc
func EqualFunc[S1 ~[]E1, S2 ~[]E2, E1, E2 any](s1 S1, s2 S2, eq func(E1, E2) bool) bool { if len(s1) != len(s2) { return false } for i, v1 := range s1 { v2 := s2[i] if !eq(v1, v2) { return false } } return true }
Equal関数とほぼ似ていますが、比較がtrueになるかfalseになるかの判断を引数で与えた関数(eq func(E1, E2) bool
)の返り値で判断するという点がミソです。
ソースコードもEqual関数とほぼ同じで、falseの判断を関数実行で行なっている点のみが異なっています。
またeq
関数で返り値され返せればスライスの比較ができるので、それぞれのスライスの要素型はなんでも良いことになっています。
例えば、こんな感じの使い方ができます。
var numberMap = map[int]string{ 1: "one", 2: "two", 3: "three", 4: "four", 5: "five", } func main() { s1 := []int{1, 2, 3} s2 := []string{"one", "two", "three"} output := slices.EqualFunc(s1, s2, eq) fmt.Println(output) // trueになる s2 = []string{"one", "four", "three"} output = slices.EqualFunc(s1, s2, eq) fmt.Println(output) // falseになる } func eq(e1 int, e2 string) bool { if v, ok := numberMap[e1]; ok && v == e2 { return true } return false }
Compare
func Compare[S ~[]E, E cmp.Ordered](s1, s2 S) int { for i, v1 := range s1 { if i >= len(s2) { return +1 } v2 := s2[i] if c := cmp.Compare(v1, v2); c != 0 { return c } } if len(s1) < len(s2) { return -1 } return 0 }
引数に与えられた2つのスライスの比較をします。1つ目のスライスの長さの方が長ければ1、2つ目のスライスの長さの方が長ければ-1になります。
2つの長さが等しい場合、1つ目の要素から1つずつ比較をしていき、1つ目のスライス要素 > 2つ目のスライス要素となった時点で1、逆であればとの時点で-1を返します。
最後まで要素が等しかった場合(Equal関数でtrueを返すのと等しい)、0を返します。
要素の大小比較をするので、当然引数のスライスの要素はcmp.Ordered
の型に制限されます。
CompareFunc
func CompareFunc[S1 ~[]E1, S2 ~[]E2, E1, E2 any](s1 S1, s2 S2, cmp func(E1, E2) int) int { for i, v1 := range s1 { if i >= len(s2) { return +1 } v2 := s2[i] if c := cmp(v1, v2); c != 0 { return c } } if len(s1) < len(s2) { return -1 } return 0 }
Compare関数とほぼ同じですが、要素の比較をcmp.Compare
ではなく、引数で与えた関数で行うようにしたものです。
Equal関数に対するEqualFuncと非常によく似ていますね。ソースコードもCompare関数とほとんど同じです。
Index
func Index[S ~[]E, E comparable](s S, v E) int { for i := range s { if v == s[i] { return i } } return -1 }
第一引数のスライスに対して、第二引数の値の要素のインデックス値を返す関数です。
該当する要素がなければ-1を返します。
ソースコードも非常にシンプルです。スライスの要素を順番に見ていって、第二引数と等しいかを順に確かめているだけですね。
IndexFunc
func IndexFunc[S ~[]E, E any](s S, f func(E) bool) int { for i := range s { if f(s[i]) { return i } } return -1 }
Index関数と非常に似ていますが、第二引数には関数が与えられます。
第一引数のスライスの要素を走査していき、引数に入れて第二引数の関数を実行した際にtrueを返す要素のインデックスを返します。
Contains
func Contains[S ~[]E, E comparable](s S, v E) bool { return Index(s, v) >= 0 }
Index関数が-1以外を返せばtrue、-1を返せばfalseとなります。
つまり第二引数の要素が第一引数のスライスに存在すればtrueです。
ContainsFunc
func ContainsFunc[S ~[]E, E any](s S, f func(E) bool) bool { return IndexFunc(s, f) >= 0 }
IndexFunc関数が-1以外を返せばtrue、-1を返せばfalseとなります。
第二引数の関数がtrueを返す要素が第一引数のスライスに存在すればtrueです。
Insert
func Insert[S ~[]E, E any](s S, i int, v ...E) S { .... }
スライスsのインデックスiの箇所から、vで指定した値を要素に入れ込みます。
元々インデックスi以降にあった要素は、vの数だけ後ろにずれます。
ソースコードは長いので割愛しますが、
sの要素が増えた際にvのメモリアドレスと重複する際の場合分けなど、若干複雑な処理がされています。
Delete
func Delete[S ~[]E, E any](s S, i, j int) S { _ = s[i:j] // bounds check return append(s[:i], s[j:]...) }
スライスsのインデックスが[i,j)の範囲を削除します。
_ = s[i:j]
を実行することにより、sの範囲外のインデックス値を指定していないことをassertしています。
範囲外のインデックスを指定している場合はここでpanicがおきます。
DeleteFunc
func DeleteFunc[S ~[]E, E any](s S, del func(E) bool) S { i := IndexFunc(s, del) if i == -1 { return s } // Don't start copying elements until we find one to delete. for j := i + 1; j < len(s); j++ { if v := s[j]; !del(v) { s[i] = v i++ } } return s[:i] }
スライスsの要素の内、del関数がtrueを返す要素を削除する関数です。
まずIndexFunc関数を実行してdel関数がtrueの最初の要素のインデックス値を割り出します。
その次のインデックスの要素からsの要素を順に見ていき、del関数がfalseであれば(削除対象でなければ)、
要素を左にずらしていく(削除対象の要素を上書きする形で)、という処理がされていますね。
Replace
func Replace[S ~[]E, E any](s S, i, j int, v ...E) S { .... }
スライスsのインデックスが[i, j)の箇所の要素を、vで置き換える関数です。
ソースコードは長いので割愛します。
Insert関数と同じく、スライスの要素を増やしていく過程でvとメモリアドレスが衝突する場合を分岐分けしており、比較的複雑な処理になっています。
Compact
func Compact[S ~[]E, E comparable](s S) S { if len(s) < 2 { return s } i := 1 for k := 1; k < len(s); k++ { if s[k] != s[k-1] { if i != k { s[i] = s[k] } i++ } } return s[:i] }
スライス2で同じ値が2つ以上連続した場合は、それらを1つの要素にまとめてしまう関数です。
例えば、[]int{1,2,3,3,4,5,5,5,6}
というスライスを[]int{1,2,3,4,5,6}
に変換します。
ソースコードでは、スライスsの要素を順番に見ていきます。そして連続する値を検知した時、その時点でのインデックス(連続した値の中で2番目の要素位置)を変数iに保管しておきます。
そしてそれ以降の値の異なる要素を、インデックスiから詰め直します。
CompactFunc
func CompactFunc[S ~[]E, E any](s S, eq func(E, E) bool) S { if len(s) < 2 { return s } i := 1 for k := 1; k < len(s); k++ { if !eq(s[k], s[k-1]) { if i != k { s[i] = s[k] } i++ } } return s[:i] }
Compact関数と非常によく似ていますが、第二引数の関数がtrueを返す連続した要素を1つにまとめます。
この時残される要素は、連続する中で1番最初の要素になります。
例えば下記のサンプルでは、連続して偶数が出現する場合にまとめるようにしています。
[6, 8, 10]
がまとめられて[6]
になります。
func main() { s := []int{1, 2, 3, 4, 5, 6, 8, 10, 9} output := slices.CompactFunc(s, eq) fmt.Println(output) // expect: [1, 2, 3, 4, 5, 6, 9] } func eq(e1, e2 int) bool { if e1 % 2 == 0 && e2 % 2 == 0 { return true } return false }
Grow
func Grow[S ~[]E, E any](s S, n int) S { if n < 0 { panic("cannot be negative") } if n -= cap(s) - len(s); n > 0 { s = append(s[:cap(s)], make([]E, n)...)[:len(s)] } return s }
スライスsのキャパシティを、残りn個の要素を追加しても拡張する(アロケートし直す)必要がない大きさにまで増やします。
Clip
func Clip[S ~[]E, E any](s S) S { return s[:len(s):len(s)] }
スライスsの無駄なキャパシティを削除し、要素長と同じにします。
ここで使われているコロンを2つ使ったスライスの表現方法ですが、Go仕様にあるFull slice expressions
というものです。
コロンで区切られた値の3つ目は、キャパシティの大きさを指定しています。