slice と map の中身

読了目安 約4分

slice と map の内部構造を知り、関数に渡したときの共有や走査順序の非保証といった罠を、エディタで実際に踏んで確かめます。

Web のコードでは、「関数に渡した slice が、なぜか呼び出し元でも変わっていた」のような形で、slice と map の中身の仕組みが表に出てきます。

slice の正体

slice の実体は、3 つの値を束ねた小さな構造です。

• 裏にある配列の、slice の始点を指すポインタ
• 長さ（len）：いま入っている要素数
• 容量（cap）：確保済みのメモリに入る要素数

slice の変数そのものは要素を持たず、裏にある配列を指しているだけです。

append で何が起きるか

package main

import "fmt"

func main() {
	s := []int{}
	for i := 0; i < 10; i++ {
		s = append(s, i)
		fmt.Printf("len=%d cap=%d\n", len(s), cap(s))
	}
}

容量に余裕があるうちは、append は同じ配列の次の位置に書いて長さを 1 増やすだけです。 容量が尽きると、より大きい配列を新しく確保し、全要素をコピーしてから追加します。 実行結果で cap がおよそ 2 倍に跳ねた行が、その瞬間です。

競プロの計算量の直感で言えば、append 1 回はならし O(1) です。

関数に渡したときに共有される

package main

import "fmt"

func double(nums []int) {
	for i := range nums {
		nums[i] *= 2
	}
}

func main() {
	scores := []int{10, 20, 30}
	double(scores)
	fmt.Println(scores)
}

関数に slice を渡すときにコピーされるのは 3 つ組だけで、裏の配列は共有されたままです。 関数の中で nums[i] を書き換えると、呼び出し元の scores も変わります。

次のコードの出力を予想してから、実行してください。

package main

import "fmt"

func main() {
	a := []int{1, 2, 3, 4}
	b := a[:2]        // a の先頭 2 要素を切り出す
	b = append(b, 99) // b に 1 つ追加する

	fmt.Println("a:", a)
	fmt.Println("b:", b)
}

a の 3 番目が 99 に書き換わります。 b は a と同じ配列を指していて、長さ 2 に対して容量は 4 あるので、append は確保し直さず共有配列の 3 番目（つまり a[2]）に書き込むからです。

map の計算量と順序

map の読み書きが平均 O(1) であることは、競プロの感覚どおりです。 ただし、map を range で走査する順序は保証されず、Go は実行のたびに順序をわざと変えます。

package main

import "fmt"

func main() {
	stock := map[string]int{"apple": 3, "banana": 5, "cherry": 7}
	for i := 0; i < 3; i++ {
		for name, n := range stock {
			fmt.Printf("%s=%d ", name, n)
		}
		fmt.Println()
	}
}

同じ map を 3 回走査しているのに、順序が揃わないはずです（偶然揃ったら何度か実行してください）。 「たまたま挿入順に出てきた」ことに依存したコードは、別の実行で壊れます。

make とゼロ値と nil map

Go では、変数を宣言しただけでゼロ値（型ごとに決まった初期値）が入ります。

• int は 0、string は空文字列、そして slice と map は nil
• nil の slice は寛容で、len は 0 を返し、append もできる
• nil の map は読み取れるが、書き込むと panic する

package main

import "fmt"

func main() {
	var m map[string]int
	fmt.Println("読み取りは動く:", m["a"]) // ゼロ値の 0 が返る
	m["a"] = 1                              // ここで panic する
	fmt.Println("ここには到達しない")
}

書き込む map は、make で作ってから使います。

m := make(map[string]int) // 空の map を確保する
s := make([]int, 0, 100)  // 長さ 0、容量 100 の slice

slice の make に容量を渡すと append の確保し直しが減るので、要素数の見当が付いているなら先に確保しておきます。

競プロの道具との対応

試してみよう

さきほど踏んだ「append が a を書き換える」罠を、自分の手で直してください。

package main

import "fmt"

func main() {
	a := []int{1, 2, 3, 4}

	// b を「a と配列を共有しない、独立した slice」に変える
	b := a[:2]

	b = append(b, 99)
	fmt.Println("a:", a) // [1 2 3 4] のままにしたい
	fmt.Println("b:", b) // [1 2 99] にしたい
}

ヒント: make で長さ 2 の slice を作り、copy(b, a) で複製してから append します。 直せたら cap(b) も出力して、なぜ共有が切れたのかを自分の言葉で説明できるか確かめてください。