Swiftには総称（generics）がありますが、C++の総称とはだいぶかけ離れているのでSTLっぽい抽象化をするにはちょっと工夫が必要という話です。
PR: WEB+DB PRESS Vol.84 にSwiftの入門記事を書いたのでよろしく☆
組み込み関数countElements()の定義
まず題材として、抽象的な集合型であるCollectionTypeプロトコルに対する典型的な操作、 countElements() を実装してみましょう。これは以下のように定義されています。
/// Return the number of elements in x.
///
/// O(1) if T.Index is RandomAccessIndexType; O(N) otherwise.
func countElements<T : _CollectionType>(x: T) -> T.Index.Distance
注目すべきはアルゴリズムの複雑さで、T.IndexがRandomAccessIndexTypeのときはO(1)、それ以外、たとえばForwardIndexTypeの場合はO(n)となっています。
T.Indexは添字の型
T.Indexは添字の型です。たとえばStringでは以下のように定義されています。BidirectionalIndexTypeプロトコルを実装しているので、文字列の添字は前後に進むことはできてもランダムアクセスはできないようですね。Swiftの文字列はUnicodeの列で、合成文字も1文字としてカウントする以上、ランダムアクセス出来ないのは納得です。
extension String : CollectionType {
/// A character position in a `String`
struct Index : BidirectionalIndexType, Comparable, Reflectable {
/* 略 */
}
}
CollectionTypeプロトコルが要求する要素
CollectionTypeプロトコルはIndex型とともにsubscript(Index)とvar startIndex:Index、var endIndex:Indexを要求するので、Stringに対して以下の操作ができます。StringはCharacterの集合として使えるということです。
let s = "foo"
// s[0] // subscript(Int)はないので不正
s[s.startIndex] // "f"
s[s.startIndex.successor()] // "o"
CollectionTypeに対してO(n)で動くcountElements()の実装
C.IndexがRandomAccessIndexTypeでない場合、O(n)でいいので、countElements()はひとつひとつカウントするだけでよさそうです。
func myCountElements0<C: CollectionType>(collection: C) -> Int {
var count = 0
for var i = collection.startIndex; i != collection.endIndex; i = i.successor() {
count++
}
return count
}
myCountElements0([1, 2, 3]) // 3
O(1)のcountElements()の考察
さて、オリジナルのcountElements()はC.IndexがRandomAccessIndexTypeのときにアルゴリズムの複雑さがO(1)になるのでした。Indexがランダムアクセス可能な集合型とは、たとえば配列です。
そこでArray型を覗いてみたのですが…なんとArray.Indexは定義されていないようにみえます。しかし let i: Array<Int>.Index = 0 は通るので、どういうからくりか分かりませんがArray.IndexはIntとして存在するようです。ううむ…。
C.IndexがRandomAccessIndexTypeかどうかを動的にチェック
Array.Indexの謎はさておくとして、myCountElementsの内部で、C.IndexがRandomAccessIndexTypeかどうか動的にチェックして動作を切り替えればいいのかなと思い、次のようなコードを書いてみました。myCountElements0()は前述の関数です。
func myCountElements<C: CollectionType>(collection: C) -> Int {
switch collection.startIndex {
case let index as RandomAccessIndexType:
return 0 // とりあえず
default:
return myCountElements0(collection)
}
ところがコンパイルエラー。"Protocol 'RandomAccessIndexType' can only be used as a generic constraint ..."とのことです。というのも、総称プロトコルは型アノテーションとしては使えず、型仮引数の制約（constraint）としてのみ使えるという言語仕様上の制約があるからです。C++だったら抽象型だろうと具象型だろうとCとして型実引数を与えるところですが、Swiftの総称プロトコルに型実引数を与えるには具象型の定義ブロックでtypealiasをするしかないからです。
型仮引数の制約でオーバーロード
myCountElements()の内部で動的にチェックして分岐するのは無理でした。では静的にチェックして分岐することはできるでしょうか。型仮引数の制約でオーバーロードできるかどうか試してみましょう。
// 制約なし版
func myCountElements<C: CollectionType>(collection: C) -> Int {
return 10
}
// 制約あり版
func myCountElements<C: CollectionType where C.Index: RandomAccessIndexType>(collection: C) -> Int {
return 20
}
myCountElements("foo") // 10 <- 制約なし版がよばれる
myCountElements([1, 2, 3, 4, 5]) // 20 <- 制約あり版がよばれる
RandomAccessIndexType#distanceTo()が呼べない問題
どうやら、型仮引数の制約でもオーバーロードできるようです。あとは実装するだけ！制約なし版は前述のmyCountElements0()、制約あり版は次のように実装すればいいでしょうか。
func myCountElements1<C: CollectionType where C.Index: RandomAccessIndexType>(collection: C) -> Int {
let start = collection.startIndex
let end = collection.endIndex
return start.distanceTo(end)
}
しかしまたもやコンパイルエラー。"cannot invoke 'distanceTo' with an argument of type 'C.Index'" だそうですが、これでは何も分かりません。ううむ…。
distanceTo()は、配列でやってみるとたしかに動きます。
var a = [1, 2, 3]
a.startIndex.distanceTo(a.endIndex) // 3
C.IndexをStrideableとして利用
RandomAccessIndexTypeがStrideableにも適合しており、RandomAccessIndexTypeのdistanceTo()とStrideableのdistanceTo()の戻り値がことなるので、もしかしたらコンパイラがただしいメソッドを見つけられないのかもしれない…とおもってIndexの制約をStrideableにしてみると、コンパイルが通りました。ただStrideableから整数を取り出す妥当な方法がないので無理やりIntにキャストしていますが、これが汎用的に動くかどうかは怪しいものです。
func myCountElements2<C: CollectionType where C.Index: Strideable>(collection: C) -> Int {
let start = collection.startIndex
let end = collection.endIndex
let strideable = start.distanceTo(end)
return strideable as Int // このへんが怪しい
}
myCountElements2([1, 2, 3) // 3
戻り値によるdistanceTo()のオーバーロードの解決
そう、Swiftは同名で戻り値型だけが異なるメソッドもオーバーロードできるのです。ということは、制約をRandomAccessIndexTypeにしたままでも、distanceTo()の戻り値を曖昧でないように要求することで動くはず。さらに、RandomAccessIndexTypeのdistanceTo()の戻り値である、RandomAccessIndexType.Distanceは典型的にはIntなので、これをそのまま返せばより汎用的です。
結果
これを踏まえるとO(1)版の実装は以下のようになりました。CollectionType.Index.Distanceを返すようにしたO(n)版も併記しておきます。
func myCountElements<C: CollectionType>(collection: C) -> C.Index.Distance {
var count: C.Index.Distance = 0
for var i = collection.startIndex; i != collection.endIndex; i = i.successor() {
count++
}
return count
}
func myCountElements<C: CollectionType where C.Index: RandomAccessIndexType>(collection: C) -> C.Index.Distance {
let start = collection.startIndex
let end = collection.endIndex
return start.distanceTo(end)
}
myCountElements("foo") // 3 <- O(n)版が使われる
myCountElements([1, 2, 3, 4, 5]) // 5 <- O(1)版が使われる
これでめでたしめでたし。無事集合型を表すCollectionTypeに対して総称的に使え、しかもIndexがランダムアクセス可能であるかどうかでアルゴリズムを使い分ける実装ができました。