オフィスアワーがそろそろ始まるよ!()

container

動的配列、リスト、ハッシュマップのような、データの集まりを表現するデータ構造をコンテナと呼びます。Zenの標準ライブラリではstd.containerで、次のコンテナを提供しています。

コンテナ 説明
ArrayList 動的配列
Buffer 格納する値がu8の動的配列
HashMap キーの型、データの型、ハッシュ関数を指定可能な連想配列
AutoHashMap キーの型、データの型は指定可能だが、デフォルトのハッシュ関数をもつ連想配列
BufMap キーの型とデータの型とが[]u8の連想配列
BufSet []u8キーがデータになるセット
SinglyLinkedList 単方向リスト
TailQueue 双方向リスト

BufferBufMapBufSetを除くと、これらのコンテナはジェネリックです。つまり、特定の型に依存しておらず、任意型のコンテナを作り出すことができます。

全てのコンテナ型はメモリアロケータを要求します。要素を追加する操作では、メモリ確保に失敗するとerror.OutOfMemoryが返ります。

よく使うコンテナであるArrayListAutoHashMapTailQueueについて説明します。

ArrayList

ArrayList(T)T型の値を格納する動的配列です。

ArrayListの主要なメソッドは次のとおりです。新しく要素を追加するメソッドでは、メモリ確保失敗時に、error.OutOfMemoryが返ります。

  • deinit() void: インスタンスの後始末をします。確保したメモリを解放します。
  • len() usize: 現在保有している要素数を取得します。
  • at(i: usize) *T: i番目の要素のポインタを取得します。
  • toSlice() []T: リストをスライスとして取得します。メモリ領域の所有権はArrayList側にあります。
  • append(item: T) !void: リストの一番後ろに要素を1つ追加します。
  • appendSlice(items: []T) !void: リストの一番後ろに要素を複数個追加します。
  • insert(n: usize, item: T) !void: n番目に要素を1つ追加します。
  • insertSlice(n: usize, items: []T) !void: n番目に要素を複数個追加します。
  • pop() T: 要素を1つリストから削除して、取得します。リストが空の場合、安全性保護付き未定義動作を引き起こします。
  • popOrNull() ?T: pop()と似ていますが、リストが空の場合、nullが返ります。
  • orderedRemove(i: usize) T: i番目の要素を取り除き、その値を返します。取り除く要素以外の順番は保証されます。計算量はO(n)です。
  • swapRemove(i: usize) T: i番目の要素を取り除き、その値を返します。i番目の要素には、代わりに末尾の要素が入ります。計算量はO(1)です。

ArrayListの利用例を示します。

examples/ch09-std/container/src/array_list.zen:4:39

const heap = std.heap;
const ArrayList = std.container.ArrayList;
test "ArrayList" {
    // アロケータの準備
    var bytes: [1024]u8 = undefined;
    var allocator = heap.FixedBufferAllocator{ .buffer = bytes[0..] };

    // `usize`を格納するArrayListの初期化。`deinit`でメモリを解放
    var list = ArrayList(usize){ .allocator = &allocator };
    defer list.deinit();

    // リストの後ろに要素を追加
    try list.append(1);
    try list.append(5);

    // `len`で現在の要素数を取得、`at`で要素アクセス
    ok(list.len() == usize(2));
    ok(list.at(0).* == usize(1));

    // `insert`で`1`番目に`10`を挿入    
    try list.insert(1, 10);
    ok(list.len() == usize(3));
    ok(list.at(1).* == usize(10));

    // `pop`で後ろから要素を取り出す
    ok(list.pop() == 5);
    ok(list.len() == 2);

    // `popOrNull`ではコンテナがからの場合、`null`が返る
    var sum_of_remained: usize = 0;
    while (list.popOrNull()) |value| {
        sum_of_remained += value;
    } else {
        ok(sum_of_remained == 11);
    }
}

下記の2つのメソッドは、動的配列の容量に関連するメソッドです。実際に値を保有しているかどうかとは別に、ArrayListが確保しているメモリ領域の大きさを容量と呼びます。appendごとに新しくメモリ領域を割り当てるのは、非効率的です。そのため、ArrayListではappend時に容量が不足する場合、ある計算式に基づいて多めにメモリ領域を確保します。

  • capacity() usize: メモリの再割当てなしに、Tの値を格納できる個数を返します。
  • ensureCapacity(new_capacity: usize) !void: new_capacity以上の容量を確保します。

examples/ch09-std/container/src/array_list.zen:41:60

test "ArrayList capacity" {
    // アロケータの準備
    var bytes: [1024]u8 = undefined;
    var allocator = heap.FixedBufferAllocator{ .buffer = bytes[0..] };

    // `usize`を格納するArrayListの初期化。`deinit`でメモリを解放
    var list = ArrayList(usize){ .allocator = &allocator };
    defer list.deinit();

    // 初期化時点では容量は`0`
    ok(list.capacity() == 0);

    // 一度メモリを確保すると容量は`8`
    try list.append(1);
    ok(list.capacity() == 8);

    // `16`以上の容量を確保、容量計算により`20`になる
    try list.ensureCapacity(16);
    ok(list.capacity() == 20);
}

次の2つのメソッドは、確保したメモリの所有権が移動するメソッドです。メモリ解放の責任は、メモリの所有権を受け取る側になります。

  • fromOwnedSlice(allocator: Allocator, slice: []T) @This(): allocatorによって確保されたsliceの所有権を取得し、ArrayListを作成します。
  • toOwnedSlice() []T: 保有しているメモリの所有権を手放し、スライスを返します。

examples/ch09-std/container/src/array_list.zen:62:85

test "Ownership" {
    // アロケータの準備
    var bytes: [1024]u8 = undefined;
    var allocator = heap.FixedBufferAllocator{ .buffer = bytes[0..] };

    // メモリを動的確保し、使用 (初期化) する
    var owned = try heap.alloc(&allocator, usize, 10);
    for (owned) |*v, i| {
        v.* = i;
    }

    // 動的確保されたメモリから`ArrayList`のインスタンスを作成する
    var list = ArrayList(usize).fromOwnedSlice(&allocator, owned);
    ok(list.len() == 10);
    ok(list.at(9).* == 9);

    // 所有権を手放して、スライスを返す
    var owned_again = list.toOwnedSlice();
    ok(list.len() == 0);
    for (owned_again) |*v, i| {
        ok(v.* == i);
    }
    heap.free(&allocator, owned_again);
}

AutoHashMap

ハッシュ関数としてWyHashを使用するハッシュマップです。

AutoHashMapの主要なメソッドを以下に示します。新しくエントリを作成するメソッドでは、メモリ確保失敗時に、error.OutOfMemoryが返ります。

ここで、Kは任意のキーを表す型、Vは任意のデータを表す型、KVstruct { key: K, value: V }です。

  • deinit() void: インスタンスの後始末をします。確保したメモリを解放します。
  • clear() void: 全てのエントリを削除します。
  • count() usize: 保有しているエントリ数を取得します
  • ensureCapacity(expected_count: usize) !void: expected_count以上の容量を確保します。
  • put(key: K, value: V) !?KV: 新しいエントリを追加します。キーが同じエントリが既にある場合、古い値を返します。
  • putNoClobber(key: K, value: V) !void: キーが登録されていなければ、新しいエントリを追加します。キーの登録がないことをアサーションで検査しています。
  • get(key: K) ?*KV: キーが一致するエントリのポインタを取得します。
  • getValue(key: K) ?V: キーが一致するエントリのデータを取得します。
  • contains(key: K) bool: キーが登録されていればtrue、そうでなければfalseが返ります。
  • remove(key: K) ?KV: 与えたキーを持つエントリを削除します。キーが一致するエントリがあれば削除したエントリが、そうでなければnullが返ります。

AutoHashMapの利用例を示します。

examples/ch09-std/container/src/hash_map.zen:5:42

const heap = std.heap;
const AutoHashMap = std.container.AutoHashMap;
test "AutoHashMap" {
    // アロケータの準備
    var bytes: [1024]u8 = undefined;
    var allocator = heap.FixedBufferAllocator{ .buffer = bytes[0..] };

    // キーが`i32`、データが`[]u8`のハッシュマップ
    var map = AutoHashMap(i32, []u8){ .allocator = &allocator };
    // `deinit`でメモリを解放
    defer map.deinit();

    ok(map.count() == 0);
    var previous = try map.put(1, &"one");
    // 重複するキーがなければ`null`が返る
    ok(previous == null);
    ok(map.count() == 1);

    // 既にキーが登録されている`1`を登録する
    previous = try map.put(1, &"1");
    // 前回登録したキーとデータのペアが返ってくる
    ok(previous.?.key == 1);
    equalSlices(u8, "one", previous.?.value);

    // キーが登録されていれば`true`が返る
    ok(map.contains(1));
    // キーに紐づくデータを取得する。キーが登録されていなければ`null`が返る
    equalSlices(u8, "1", map.getValue(1).?);
    ok(map.getValue(2) == null);

    // マップから登録を削除する
    var removed = map.remove(1);
    // 削除されたキーとデータのペアが返ってくる
    ok(removed.?.key == 1);
    equalSlices(u8, "1", removed.?.value);

    ok(map.count() == 0);
}

TailQueue

双方向リストです。ArrayListAutoHashMapと違い、内部にアロケータを持ちません。これはノードの所有権が常に、TailQueue側ではなく、呼び出し側にあることを意味します。

TailQueueのフィールドは下記の通りです。

  • first: リストの先頭ノードです。
  • last: リストの末尾ノードです。
  • len: リスト内のノード数です。

TailQueueの主要なメソッドを以下に示します。ここでTは格納するデータ型、Nodeは双方向リストのノードstruct { prev: ?*Node, next: ?*Node, data: T }です。

  • allocateNode(allocator: heap.Allocator) !*Node: 新しいノードを作成します。
  • destroyNode(allocator: heap.Allocator) void: ノードを解放します。
  • createNode(data: T, allocator: heap.Allocator) !*Node: 新しいノードを作成し、dataで初期化します。
  • append(new_node: *Node) void: リストの末尾にノードを追加します。
  • prepend(new_node: *Node) void: リストの先頭にノードを追加します。
  • insertAfter(node: *Node, new_node: *Node) void: nodeの後ろにnew_nodeを挿入します。
  • insertBefore(node: *Node, new_node: *Node) void: nodeの前にnew_nodeを挿入します。
  • remove(node: *Node) void: nodeを削除します。
  • pop() ?*Node: リストの末尾ノードを取り除きます。
  • popFirst() ?*Node: リストの先頭ノードを取り除きます。
  • concatByMoving(list1: *Self, list2: *Self) void: list1の後ろにlist2を連結します。list2のノードは空になります。

examples/ch09-std/container/src/linked_list.zen:7:62

test "TailQueue" {
    var bytes: [1024]u8 = undefined;
    var allocator = heap.FixedBufferAllocator{ .buffer = bytes[0..] };

    // `u32`のノードを持つ`TailQueue`を作成
    var list = TailQueue(u32){};

    // ノード作成
    var one = try list.createNode(1, &allocator);
    var two = try list.createNode(2, &allocator);
    var three = try list.createNode(3, &allocator);
    var four = try list.createNode(4, &allocator);
    var five = try list.createNode(5, &allocator);
    // ノード解放
    defer {
        list.destroyNode(one, &allocator);
        list.destroyNode(two, &allocator);
        list.destroyNode(three, &allocator);
        list.destroyNode(four, &allocator);
        list.destroyNode(five, &allocator);
    }

    list.append(two);              // {2}
    list.append(five);             // {2, 5}
    list.prepend(one);             // {1, 2, 5}
    list.insertBefore(five, four); // {1, 2, 3}
    list.insertAfter(two, three);  // {1, 2, 3, 4, 5}

    // 前から順番に探索
    {
        var it = list.first; // ?*Node
        var index: u32 = 1;
        while (it) |node| : (it = node.next) {
            ok(node.data == index);
            index += 1;
        }
    }

    // 後ろから逆順に探索
    {
        var it = list.last; // ?*Node
        var index: u32 = 1;
        while (it) |node| : (it = node.prev) {
            ok(node.data == 6 - index);
            index += 1;
        }
    }

    var first = list.popFirst(); // {2, 3, 4, 5}
    var last = list.pop(); // {2, 3, 4}
    list.remove(three); // {2, 4}

    ok(list.first.?.data == 2);
    ok(list.last.?.data == 4);
    ok(list.len == 2);
}

☰ 人の生きた証は永遠に残るよう ☰
Copyright © 2018-2019 connectFree Corporation. All rights reserved.
Zen, the Zen three-circles logo and The Zen Programming Language are trademarks of connectFree corporation in Japan and other countries.