要素の挿入と「フィルタリング」

1. 1 つの要素の挿入

もし昔、メモ帳で手作業でリストを編集したことがあるなら、問題はもう分かっているはずです。途中に 1 行を挿入するには、下の行を全部ずらす必要がありますし、「不要な」行を削除するには、穴が残らないようにリストをきれいに「詰める」必要があります。スライスでもまったく同じで、違うのは、メモ帳の代わりに backing array があり、消しゴムの代わりに copy、append、そして時には clear を使うことです。

これから、小さなアプリケーションを 1 つ題材にして進めます。数値の「タスク」を扱うミニマネージャです。たとえば、「タスクの優先度」や「重要度のスコア」のような整数のリストがあるとしましょう。ここで、任意の位置に新しい要素を挿入できるようにし、条件に合う要素だけをフィルタリングできるようにしたいのです（たとえば、>= min の値だけを残す、など）。

スライスの途中に要素を挿入するときには、2 つのことを行う必要があります。まず場所を見つけ、その次に末尾を失わないことです。Go では、len による「場所」は通常 append で作られ、末尾は copy でずらします。これは、行列の中で人を横にずらしていくのに似ています。まず列が「長く」なって（場所ができて）、そのあと右側に立っている人を丁寧に移動させて、間に入るわけです。

重要なのは、copy は重なり合う範囲でも動作できる、という点です。つまり、同じ backing array の中で「右へずらす」操作は、普通に行えるのです。

言葉で見る挿入の流れ

s = [10, 20, 30, 40] で、位置 i = 2 に 99 を挿入したいとします。

1. 長さを 1 増やす（最後に何でもよい「空」の要素を 1 つ追加する）
2. 末尾を右にずらす：i から最後までの要素を i+1 に移動する
3. 99 を s[i] に書き込む

この流れを「詩」のままで終わらせないために、関数にしてみましょう。

package main

import "fmt"

func insertAt(s []int, i int, v int) []int {
	if i < 0 || i > len(s) {
		return s // bad index — do nothing
	}

	s = append(s, 0)      // 1) increased len by 1
	copy(s[i+1:], s[i:])  // 2) shifted the tail to the right
	s[i] = v              // 3) wrote the new value
	return s
}

func main() {
	s := []int{10, 20, 30, 40}
	s = insertAt(s, 2, 99)

	fmt.Println(s) // [10 20 99 30 40]
}

i > len(s) という条件に注目してください（>= ではありません）。len(s) の位置への挿入は正当な操作です。つまり、これは単に末尾に追加するだけで、「列を押し広げる」のではなく、最後尾に並ぶということです。

なぜ先に append、そのあとに copy なのか

初心者はしばしば、長さを増やす前に古いスライスのままで「末尾をずらそう」とします。気持ちは分かります。copy が何となく「スライスを拡張してくれそう」に見えるからです。しかし copy は len を変えません。単に既存の要素を書き換えるだけです。ですから、長さを増やさずに右へずらそうとすると、スライス境界の不正で panic になったり、静かに意図しない値を書き換えたりします。

2 つの考え方を比べてみましょう。

• 「要素を右へ移動させたい」——これはデータの話です。
• 「右側に場所が必要だ」——これは len の話です。

Go で「長さの場所」は append で作られます（あるいは、事前にバッファを拡張した後で reslice する方法もありますが、ここでは append を使います）。

小さな「反例」を見てみましょう（これは必ずしもコンパイルできるとは限らず、しばしば落ちるので、アドバイスではなく注意書きとして見てください）。

package main

import "fmt"

func main() {
	s := []int{1, 2, 3}
	i := 1

	// BAD IDEA: there is no len room in s for shifting right.
	// copy(s[i+1:], s[i:]) // probably panic: slice bounds out of range

	fmt.Println(s)
}

正しいメンタルモデルはこうです。挿入は必ず長さを変える操作なので、ほぼ常に append(...) が必要であり、s = ... を必ず代入し直します。

3. 要素ブロックの挿入

次は少しだけ難しくします。1 つではなく、まとまったブロックを挿入するのです。たとえば、[10, 20, 30] があり、位置 1 に [7, 8] を挿入して、[10, 7, 8, 20, 30] にしたいとします。

ロジックは同じで、ただし「+1」の代わりに「+k」を使います。ここで k = len(add) です。

ここで面白いのは、len をどうやって一気に k 増やすか、です。学習用として便利なのは、k 個のゼロを追加する方法です。

s = append(s, make([]int, k)...)

これは魔法のように見えますが、実際はとても素直です。make([]int, k) は長さ k のスライスを作り、値はゼロで埋められます。そして ... がそれを append の引数として要素列に「展開」します。

関数を実装してみましょう。

package main

import "fmt"

func insertSlice(s []int, i int, add []int) []int {
	if i < 0 || i > len(s) {
		return s
	}

	k := len(add)
	if k == 0 {
		return s // nothing to insert
	}

	s = append(s, make([]int, k)...)
	copy(s[i+k:], s[i:]) // shift the tail right by k
	copy(s[i:], add)     // copy the insertion into the freed space
	return s
}

func main() {
	s := []int{10, 20, 30}
	s = insertSlice(s, 1, []int{7, 8})

	fmt.Println(s) // [10 7 8 20 30]
}

ここで copy が 2 回続くのは正常です。1 回目は場所を空け、2 回目は必要な値でその場所を埋めます。順番を逆にすると、まだずらす必要があるものを先に上書きしてしまうので、結果は……かなり創造的になります。そしてアルゴリズムにおける創造的な結果は、たいてい芸術ではなくバグです。

4. フィルタリング: 新しいスライス vs in-place

フィルタリングとは、元のリストから条件を満たす要素だけを残すことです。たとえば「>= 50 の値をすべて残す」といった具合です。見た目は単純ですが、すぐに「結果をどこに入れるのか？」という問題にぶつかります。

基本的なアプローチは 2 つあります。

• 新しいスライスを作る（元のものは触らない）
• 同じ backing array の中で「圧縮」し、長さを減らす（in-place）

どちらも正しい方法です。ただし性質が違うので、なんとなくではなく、意識して選ぶことが大切です。

新しいスライスへのフィルタリング

新しいスライスへのフィルタリングは、初心者にとって最も脳に優しい方法です。入力 s があり、out を作り、条件に合う要素をそこへ追加し、最後に out を返します。元の s はそのまま残ります（これはしばしば安心で、扱いやすいです）。

通常は out を長さ 0 で作り、あらかじめ容量を確保しておくことで、再アロケーションを何度も起こさないようにします。

out := make([]int, 0, len(s))

「min 以上の要素を残す」関数を書きましょう。

package main

import "fmt"

func filterMinNew(s []int, min int) []int {
	out := make([]int, 0, len(s))
	for _, v := range s {
		if v >= min {
			out = append(out, v)
		}
	}
	return out
}

func main() {
	s := []int{10, 50, 30, 80, 40}
	t := filterMinNew(s, 40)

	fmt.Println("s =", s) // s = [10 50 30 80 40]
	fmt.Println("t =", t) // t = [50 80 40]
}

これはほとんど自然文のように読めます。「out を作り、s を走査し、v が条件に合えば out に追加する」。学習中であれば、微小な最適化よりこちらの方が大事なことも多いです。

In-place フィルタリング: out := s[:0]

In-place フィルタリングとは、同じ backing array を使いながら、「良い要素」が先頭に並ぶようにし、結果の長さを小さくする方法です。データが大きくて余計なアロケーションを増やしたくないときに便利です。ただし、内部で元の配列を変更するので、慎重に考える必要があります。

定番のトリック（公式に普通で、広く使われています）は次の通りです。

out := s[:0]

これは何を意味するのでしょうか。つまり、同じ backing array を使いつつ、「結果はまだ空です（len = 0）が、内部には場所があります」と言っているのです。あとは append で条件に合う要素を out に積んでいけば、それらは backing array の先頭から書き込まれます。最終的に out は s と同じ backing array を参照しつつ、より短い長さと「圧縮された」値を持つことになります。

実装してみましょう。

package main

import "fmt"

func filterMinInPlace(s []int, min int) []int {
	out := s[:0] // same backing array, but len = 0
	for _, v := range s {
		if v >= min {
			out = append(out, v)
		}
	}
	return out
}

func main() {
	s := []int{10, 50, 30, 80, 40}
	out := filterMinInPlace(s, 40)

	fmt.Println("out =", out) // out = [50 80 40]
	fmt.Println("s   =", s)   // s   = [50 80 40 80 40] (contents changed!)
}

はい、s の出力は奇妙に見えます。でもバグではありません。実際に backing array の先頭を結果の値で上書きしたので、末尾は「そのまま残っている」だけです。通常は、そこをもう有効なリストとは見なしません。

in-place フィルタリング後の末尾と clear

in-place フィルタリングの後には、2 つの「真実の層」があります。

• out — 正しい結果（短い len、圧縮済み）
• 古い s — これは歴史的な痕跡です。len は以前のままで、backing array の一部が書き換えられているからです

末尾（cap の範囲内で len(out) の後ろにある要素）は、見た目の問題だけでなく、メモリ保持の面でも危険です。要素が参照型なら、文字列、ポインタ、別のスライス、マップ、インターフェースなどがその位置にある場合、ガベージコレクタは backing array の末尾にある参照を見て、データがまだ到達可能だと判断することがあります。論理的にはもう「削除した」つもりでもです。

今回の int では大きな問題にはなりませんが、習慣としては早めに身につけておくとよいです。

関数を「末尾の衛生処理」つきにしてみましょう。

package main

import "fmt"

func filterMinInPlaceAndClearTail(s []int, min int) []int {
	out := s[:0]
	for _, v := range s {
		if v >= min {
			out = append(out, v)
		}
	}

	// The tail in the original backing array is no longer needed.
	// For int it is not required, but as a habit it is useful.
	clear(s[len(out):])

	return out
}

func main() {
	s := []int{10, 50, 30, 80, 40}
	out := filterMinInPlaceAndClearTail(s, 40)

	fmt.Println("out =", out) // out = [50 80 40]
	fmt.Println("s   =", s)   // s   = [50 80 40 0 0]
}

重要なのは、clear は長さを変えない、ということです。指定した範囲に zero value を書くだけです。s[len(out):] を消去すると、末尾はゼロで埋まります（この例では 0 です）。参照型であれば、そこは nil や空の値になり、ガベージコレクタがメモリを「手放し」やすくなります。

感覚でなく、どう選ぶか

実際の現場では、「正しい/間違い」というより、「何が保守しやすいか」と「何がメモリ効率に優れるか」の勝負になることが多いです。初心者には、たいてい「新しいスライス」の方が勝ちます。なぜなら、分かりやすく、元データを変更せず、aliasing や末尾、思わぬ上書きの驚きが少ないからです。

In-place フィルタリングは、何をしているかをきちんと理解していて、新しいバッファを確保したくないときに有用です。大きなデータを扱うコード、ループ、パーサ、ログ処理などで好まれます。ただしその場合でも、余分な参照でメモリを保持しないよう、clear で末尾を消すことがよくあります。

気持ちを楽にするための簡単なルールを覚えておいてください。in-place を選んだなら、古いスライス s を真実のソースだと思うのをやめることです。真実は今や out にあります。

5. ミニアプリケーション: 「タスク」の挿入とフィルタリング

ここで、小さなコンソールプログラムの骨組みを組み立てます。整数のリスト（私たちの「タスク」）を保持し、挿入とフィルタリングができるようにします。美しい CLI パーサーは作りません（それは別の分野です）。代わりに、fmt.Scan を使ってコマンドを読む単純なループを作り、スライスに集中します。

コマンドは次のとおりです。

• push x — 末尾に追加する
• ins i x — 位置 i に x を挿入する
• min m — >= m の要素だけ残す（new と in-place の両方を示す）
• print — リストを表示する
• exit — 終了する

コマンド読み取りループの骨組み

package main

import (
	"fmt"
)

func main() {
	tasks := make([]int, 0, 16)

	for {
		var cmd string
		if _, err := fmt.Scan(&cmd); err != nil {
			break // stdin ended
		}

		if cmd == "exit" {
			break
		}
		if cmd == "print" {
			fmt.Println(tasks)
		}
	}
}

今のところ print と exit 以外は何もできませんが、これは良い「骨格」です。tasks があり、ループがあり、コマンド読み取りがあります。ここに挿入を追加していきましょう。

push と ins を追加する

package main

import "fmt"

func insertAt(s []int, i int, v int) []int {
	if i < 0 || i > len(s) {
		return s
	}
	s = append(s, 0)
	copy(s[i+1:], s[i:])
	s[i] = v
	return s
}

func main() {
	tasks := make([]int, 0, 16)

	for {
		var cmd string
		if _, err := fmt.Scan(&cmd); err != nil {
			break
		}

		if cmd == "push" {
			var x int
			fmt.Scan(&x)
			tasks = append(tasks, x)
		}

		if cmd == "ins" {
			var i, x int
			fmt.Scan(&i, &x)
			tasks = insertAt(tasks, i, x)
		}

		if cmd == "print" {
			fmt.Println(tasks)
		}

		if cmd == "exit" {
			break
		}
	}
}

ここで重要なのは、tasks = insertAt(tasks, i, x) として結果を保存していることです。挿入は長さを変え、再アロケーションを起こすこともあるので、戻り値を無視してはいけません（これは append と同じルールです）。

2 つの方法でフィルタリングを追加する

2 つの関数を作ります。1 つは新しいスライス版、もう 1 つは in-place 版です。

package main

import "fmt"

func filterMinNew(s []int, min int) []int {
	out := make([]int, 0, len(s))
	for _, v := range s {
		if v >= min {
			out = append(out, v)
		}
	}
	return out
}

func filterMinInPlace(s []int, min int) []int {
	out := s[:0]
	for _, v := range s {
		if v >= min {
			out = append(out, v)
		}
	}
	clear(s[len(out):]) // tail is no longer needed
	return out
}

func main() {
	tasks := []int{10, 50, 30, 80, 40}

	fmt.Println(filterMinNew(tasks, 40))     // [50 80 40]
	fmt.Println(filterMinInPlace(tasks, 40)) // [50 80 40]
}

この例だけでも違いが分かります。filterMinNew は元の tasks を壊しませんが、filterMinInPlace は壊します（正確には、「backing array を結果用に再利用します」）。これは正常です。要するに、意識して選べばよいのです。

6. よくある間違い

間違い 1: 右へずらす前に長さを増やすのを忘れる。
挿入時に、初心者は copy(s[i+1:], s[i:]) と書く一方で、s = append(s, 0) を忘れたり、ブロックなら k だけ拡張するのを忘れたりします。その結果、スライス境界の不正で panic になるか、データが静かに壊れます。挿入はほぼ常に len を増やすことから始まります。

間違い 2: 挿入時の i の境界を取り違え、末尾への挿入を禁止してしまう。
もし i >= len(s) をチェックして元のスライスを返してしまうと、正しいケースである「末尾に挿入する」操作を誤って禁止してしまいます。挿入に許されるインデックスは 0 から len(s) まで、両端を含みます。

間違い 3: in-place フィルタリングで元のスライスが変わらないと思い込む。
パターン out := s[:0] は、backing array を再利用するためにあります。つまり、元の s は先頭から書き換えられます。コードのどこかで s を表示し続けて「壊れた」と驚いているなら、問題は Go ではなく期待の方です。

間違い 4: 要素が参照型のとき、in-place フィルタリング後の末尾を管理しない。
圧縮後、「余分な」要素は len(out) の外にあり、しかし backing array の cap の内側には残っています。そこに参照があると、clear(s[len(out):]) でゼロにしない限り、メモリを保持し続けることがあります。in-place フィルタリングの後に clear を入れるという丁寧な習慣は、不快な驚きを減らし、「見えない要素はまだ生きている」という実践的なモデルにも合っています。