slice

README

Goのスライスについて

Goのスライスは内部構造まで把握していないと、直感的に正しいだろうと思ってやったことが間違っている、ということが頻発する。

把握しておくべきこと

• len: スライスの要素数を調べる組み込み関数

  • 「配列の長さ」という理解は曖昧。

• cap: スライスの容量を調べる組み込み関数

  • 後述する領域確保に関するパラメータであり、あくまでもインデックスでアクセス可能な範囲は len によって決まる

• make: スライスを生成する組み込み関数

  • 2引数で生成した場合は、 要素数、容量ともに2番目の引数の整数値と同じ値のスライスが生成される。
  • 明示的に3番目の引数で容量を指定することで、要素数と容量が異なるスライスを生成できる。

• []int{0, 1, 2}: スライスをリテラルで生成する場合、要素数も容量ともに同じ値のスライスが生成される。

• スライスのために確保された連続したメモリ領域（容量、capacity）を使い切ってしまった場合、Goのランタイムは もとの容量より大きなメモリ領域を確保して、もとのスライスが格納していたデータを丸ごと新しい領域へコピーする。

  • パフォーマンスの観点から重たい処理であるため、予めスライスが保持しうる要素数が推定できる場合は、できるだけ容量の指定にも気を配るべき。
  • 可変長配列ではあるものの、連結リストとかとは異なるため、そもそもデリート操作などとは相性が悪い（？）

• 簡易スライス式 a[0 : 5]

• 完全スライス式 a[0 : 2 : 4]:

• append: 容量が足りなくなった場合、原則、確保し直すときに容量は倍確保される、と思っておく。

  • 実際にはGoのランタイムに依存する。

完全スライス式について

/* aは配列型かスライス */
/* 0 <= low <= high <= max <= cap(a) */
a[low : high : max]

簡易スライス式を使った a[2 : 4] で生成したスライスは、もとの [10]int 型の配列の 参照していない範囲が自動的に容量になる。 つまり cap(s1) == len(a) - low という関係が成り立つ。 完全スライス式を使って max を指定した場合、新しく生成したスライスの容量は cap(s2) == max - low という関係になる。

何も考えずに簡易スライス式を使うと、もとの配列・スライスに依存した大きな容量を持ったスライスが生成される。

スライスの落とし穴

最大の注意点。 スライス式で生成したスライスは、もとのスライスそのものを共有する。 ただし、スライスの自動拡張が行われると、それぞれ別のスライスを指すようになる。 （確認はしていないが、稀に同じ領域で拡張が行われることもある？）

競技プログラミングでの方針

スライスの副作用を伴わないことが絶対条件（繰り返し使う必要があることがほとんどのため）。

特に関数 append を使い際は注意。

/* s0とs1が同じ配列データを共有するかは不定 */
s1 := append(s0, x) // スライスの自動拡張が起こるかどうかに依存する

容量を大きめに確保したスライスであれば append を愚直に使う実装でもいいかもしれない。

Documentation

Index

• func Concat(s, t []rune) []rune
• func DeleteElement(s []int, i int) []int
• func PincerScan(n int) []int
• func SafeConcat(s, t []rune) []rune
• func SafeDeleteElement(s []int, i int) []int

Functions

func Concat

func Concat(s, t []rune) []rune

Concat returns a *NEW* slice, that have the same and minimum length and capacity.

func DeleteElement

func DeleteElement(s []int, i int) []int

DeleteElement returns a *NEW* slice, that have the same and minimum length and capacity. DeleteElement makes a new slice by using easy slice literal.

func PincerScan

func PincerScan(n int) []int

PincerScan shows how to scan from edge to center.

func SafeConcat

func SafeConcat(s, t []rune) []rune

SafeConcat returns a *NEW* slice, that have the same and minimum length and capacity.

func SafeDeleteElement

func SafeDeleteElement(s []int, i int) []int

SafeDeleteElement returns a *NEW* slice, that have the same and minimum length and capacity. SafeDeleteElement makes a new slice by simply appending each element FROM SCRACH.