Goでダブルポインタを知った話 - カミナシエンジニアブログ

こんにちは。カミナシソフトウェアエンジニアのAomanです。

最近ちょこちょこアルゴリズムやデータ構造、Goのキャッチアップしています。

そんな中、go.devのブログ Go blog のとある記事でダブルポインタを使用するコードに出会いました。筆者は今まで、RubyやJavaScript/TypeScriptなどの言語を多く触っていたためか、お恥ずかしながらダブルポインタを使うコードを初めて見たので「なんなのだこれは…」と戸惑いました。本記事ではそんなダブルポインタが使われていたコードについて、簡単にご紹介したいと思います。

そもそもダブルポインタとは？

その名の通りポインタのポインタのことなのですが、わからない方は下記の記事がわかりやすくまとまっており参考になると思います。

daeudaeu.com

ダブルポインタと聞いて、まずはじめに思った感想は「そんなもの必要？」です。今まで使ったことがなかったので使用例の発想があまり思い浮かびませんでした。関数の引数や返り値をダブルポインタにすることで、関数内外でポインタを書き換えたい場合に使用することが多いようです。

簡単な例として、int型のダブルポインタを関数に渡してポインタを書き換えるコードを書いてみます。

func changeTo222(ptr **int) {
    *ptr = toPtr(222)
}

func toPtr(i int) *int {
    return &i
}

func main() {
    var ptr *int
    var dptr **int
    ptr = toPtr(111)
    // dptrは111のダブルポインタ
    dptr = &pt

    fmt.Printf("value: %v\n", **dptr) // → value: 111    
    changeTo222(dptr)
    fmt.Printf("value: %v\n", **dptr) // → value: 222
}

出会ったコード

ダブルポインタに出会ったのは When To Use Generics という、Genericsの使い所を説明している記事です。

実際に例示されていたコードは下記で、Binary Search Tree(二分探索木) のデータ構造を実装するコードでした。Tree構造体のfindメソッドの返り値でダブルポインタが使われていますね！

// Tree is a binary tree.
type Tree[T any] struct {
    cmp  func(T, T) int
    root *node[T]
}

// A node in a Tree.
type node[T any] struct {
    left, right  *node[T]
    val          T
}

// find returns a pointer to the node containing val,
// or, if val is not present, a pointer to where it
// would be placed if added.
func (bt *Tree[T]) find(val T) **node[T] {
    pl := &bt.root
    for *pl != nil {
        switch cmp := bt.cmp(val, (*pl).val); {
        case cmp < 0:
            pl = &(*pl).left
        case cmp > 0:
            pl = &(*pl).right
        default:
            return pl
        }
    }
    return pl
}

// Insert inserts val into bt if not already there,
// and reports whether it was inserted.
func (bt *Tree[T]) Insert(val T) bool {
    pl := bt.find(val)
    if *pl != nil {
        return false
    }
    *pl = &node[T]{val: val}
    return true
}

一つ一つ簡単に実装を見ていきます。

まず、構造体の node と Tree が定義されています。

node : ツリーの一つ一つの要素のオブジェクトです。node自体の値と、ツリーの左右のnodeを保持します。左(小)右(大)のような関係でnodeを保持します。
Tree : ツリーの根っことなるルートnodeと、node同士の大小を比較するcmp関数を保持します。このcmp関数を持つ理由は、nodeに様々な型を挿入できるようにGenericsで定義されているためです。

// Genericsを利用することで、nodeにどんな型の値が入ってもOK
type node[T any] struct {
    left, right  *node[T]
    val          T
}

type Tree[T any] struct {
    cmp  func(T, T) int
    root *node[T]
}

この両方の構造体内で、nodeをポインタとして保持していますね。

Tree構造体には find と Insert メソッドが実装されています。

find メソッドは、引数で渡されたvalと同値のnodeを探します。見つかれば、そのnodeのダブルポインタを返します。見つからなかった場合は、valが挿入されるべきnodeのダブルポインタを返します。この見つからなかった場合の動作については、Insertメソッドの実装で理由がわかります。

func (bt *Tree[T]) find(val T) **node[T] {
        // pl変数にルートノードのダブルポインタを入れる
    pl := &bt.root

        // ツリーの下へ下へと探していく。対象のvalがplノードより小さければ左、大きければ右を検索。
        // valと同値のnodeが見つかるor末端までたどり着くまでループ(末端まで行くと*pl==nilになる)
    for *pl != nil {
        switch cmp := bt.cmp(val, (*pl).val); {
        case cmp < 0:
            pl = &(*pl).left
        case cmp > 0:
            pl = &(*pl).right
        default:
            return pl
        }
    }
    return pl
}

次に Insert メソッドです。引数で渡されたvalをツリーの適切な位置に挿入します。挿入が出来たらtrueを返し、すでにvalが存在していればfalseを返します。

このメソッド内で先ほどのfindが使われています！findメソッドでは見つからなかった場合、挿入すべき場所のnodeのダブルポインタが返ってくるため、その位置のポインタに新しいnodeを挿入することが出来ます！

func (bt *Tree[T]) Insert(val T) bool {
      // valを検索
    pl := bt.find(val)

    // *plがnil出ない場合、すでにvalが存在するということなのでfalseを返す
    if *pl != nil {
        return false
    }

    // **ダブルポインタの値(ポインタ)に新しいnodeを挿入する**
    *pl = &node[T]{val: val}

    return true
}

このようにfindメソッドでダブルポインタを返すことで、検索した時に存在しない場所のポインタに対し、新たなnodeを挿入することが出来るんですね。これを理解したとき、なるほど〜となりました。

ダブルポインタを使わない場合

例えば先ほどのTree構造体にパブリックなSearchメソッド（存在していればtrueを返す）を定義した場合、下記のようにfindメソッドを流用し実装することが出来ます。

func (bt *Tree[T]) Search(val T) bool {
    return *bt.find(val) != nil
}

しかし、ダブルポインタを使わない場合、InsertとFindの両方で使用出来る、汎用的なfindメソッドを定義することが難しいかと思うので、下記のようにInsertとFind両方で検索ロジックが必要になってしまいそうです。

func newNode[T any](val T) *node[T] {
    return &node[T]{
        left:  nil,
        right: nil,
        val:   val,
    }
}

func (bt *Tree[T]) Insert(val T) bool {
    pl := bt.root

outer:
    for pl != nil {
        switch cmp := bt.cmp(val, pl.val); {
        case cmp < 0:
            if pl.left == nil {
                pl.left = newNode(val)
                break outer
            }
            pl = pl.left
        case cmp > 0:
            if pl.right == nil {
                pl.right = newNode(val)
                break outer
            }
            pl = pl.right
        default:
            return false
        }
    }

    return true
}

func (bt *Tree[T]) Search(val T) bool {
    pl := bt.root

    for pl != nil {
        switch cmp := bt.cmp(val, pl.val); {
        case cmp < 0:
            pl = pl.left
        case cmp > 0:
            pl = pl.right
        default:
            return true
        }
    }

    return false
}