NEPLg2 Standard Library - vec - vec
Web Playground
Web Playground

vec

連続れんぞくメモリを用もちいる可変長かへんちょう配列はいれつ

目的もくてき

  • Vec<.T> を提供ていきょうし、push / get / pop / set などの基本きほん操作そうさを共通きょうつう API として使つかえるようにします。
  • alloc/collections の他ほかの構造こうぞうが依存いそんする基礎きそ配列はいれつとして機能きのうします。

実装じっそう

  • Vec<.T> は len / cap / data を持もつ struct で、data は MemPtr<.T> として管理かんりします。
  • push で容量ようりょう不足ぶそくが起おきた場合ばあいは 2 倍ばいへ拡張かくちょうし、typed realloc_ptr で再配置さいはいちします。

注意ちゅうい

  • get / pop は存在そんざいしない位置いちを Option::None で返かえします。
  • set は範囲外はんいがいでは失敗しっぱいにせず、そのままの Vec<.T> を返かえします。
  • 再確保さいかくほが起おきると内部ないぶバッファの番地ばんちは変かわりえます。

計算量けいさんりょう

  • get / set / len / cap / is_empty は O(1) です。
  • push は償却しょうきゃく O(1)、拡張かくちょう発生時はっせいじの最悪さいあく時間じかん計算量けいさんりょうは O(n) です。

使用例しようれい

TEST
#entry main
#target std
#import "std/test" as *
#import "alloc/collections/vec" as *
fn main <()*>()> ():
    assert_eq_i32 0 vec_len new<i32>;
    let a2 <Vec<i32>>:
        new<i32>
        |> push 10
        |> push 20
    assert_eq_i32 2 vec_len a2;
    let b2 <Vec<i32>>:
        new<i32>
        |> push 10
        |> push 20
    match vec_get<i32> b2 1:
        Option::Some x:
            assert_eq_i32 20 x;
        Option::None:
            assert false;
TEST
#entry main
#target std
#import "std/test" as *
#import "alloc/collections/vec" as *
fn main <()*>()> ():
    let v2 <Vec<i32>>:
        vec_with_capacity<i32> 2
        |> push 1
        |> push 2
    match vec_get<i32> v2 0:
        Option::Some x:
            assert_eq_i32 1 x;
        Option::None:
            assert false;
    let w2 <Vec<i32>>:
        vec_with_capacity<i32> 2
        |> push 1
        |> push 2
    assert is_none<i32> vec_get<i32> w2 3;
TEST
#entry main
#target std
#import "alloc/collections/vec" as *
fn main <()*>i32> ():
    let cleared <Vec<i32>>:
        new<i32>
        |> push 11
        |> push 22
        |> vec_clear<i32>
    if eq vec_len cleared 0 0 1

Vec

可変長かへんちょう配列はいれつの本体ほんたい

目的もくてき

  • 要素数ようそすう・容量ようりょう・要素ようそ領域りょういきの先頭せんとうを保持ほじし、alloc/collections の他ほか API から共通きょうつうに扱あつかえるようにします。

実装じっそう

  • len と cap は i32、data は MemPtr<.T> で保持ほじします。
  • 実体じったいの配列はいれつはヒープ上じょうの連続れんぞく領域りょういきです。

注意ちゅうい

  • Vec<.T> 自体じたいは data 領域りょういきの所有権しょゆうけんを持もちます。
  • 再確保さいかくほにより data の番地ばんちが変かわるため、生なまアドレスを長期ちょうきに保持ほじしてはいけません。

計算量けいさんりょう

  • struct 自体じたいの読よみ書かきは O(1) です。

VecDataLen

Vec<.T> の data/len をまとめて返かえす軽量けいりょう struct

目的もくてき

  • 内部ないぶバッファ先頭せんとうと要素数ようそすうを 1 回かいの呼よび出だしで扱あつかえるようにします。
  • sort 系けい helper のように data と len を対ついで読むよむ API で、.Pair に頼たよらず明示的めいじてきな field 名めいを与あたえます。

実装じっそう

  • data は MemPtr<.T>、len は i32 を保持ほじします。

注意ちゅうい

  • data は Vec<.T> の内部ないぶ領域りょういきを指さすため、再確保さいかくほが起おきると無効むこうになります。
  • len は取得時点しゅとくじてんの値あたいであり、その後あとの変更へんこうには追従ついじゅうしません。

計算量けいさんりょう

  • struct 自体じたいの生成せいせいと field 読よみ取とりは O(1) です。

vec_new

既定きてい容量ようりょうの空から Vec<.T> を作つくる

目的もくてき

  • 空からの Vec<.T> を返かえし、push 連鎖れんさの起点きてんとして使つかえるようにします。

実装じっそう

  • 初期しょき容量ようりょうを 8 とし、その byte 数すうだけ typed alloc_ptr<.T> で確保かくほします。
  • len = 0、cap = 8、data = allocated pointer の struct を返かえします。

注意ちゅうい

  • 初期しょき容量ようりょうは固定値こていち 8 です。
  • 確保かくほ失敗しっぱいは unwrap_ok により到達不能とうたつふのうになります。Vec 生成せいせいを Result 化するかどうかは reboot 後続こうぞくで整理せいりします。

計算量けいさんりょう

  • 時間じかん計算量けいさんりょうは O(1)、追加ついかの空間くうかん計算量けいさんりょうも O(1) です。

使用例しようれい

TEST
#entry main
#target std
#import "alloc/collections/vec" as *
fn main <()*>i32> ():
    let v new<i32>;
    if eq vec_len<i32> v 0 0 1

vec_with_capacity

初期しょき容量ようりょうを指定していして Vec<.T> を作つくる

目的もくてき

  • 事前じぜんに必要ひつような容量ようりょうが分わかっている場面ばめんで、再確保さいかくほを減へらした Vec<.T> を作つくります。

実装じっそう

  • 指定していした cap に応おうじて typed alloc_ptr<.T> を呼よび、len = 0 で返かえします。

注意ちゅうい

  • cap = 0 でも動作どうさします。
  • 確保かくほ失敗しっぱいは unwrap_ok により到達不能とうたつふのうになります。

計算量けいさんりょう

  • 時間じかん計算量けいさんりょうは O(1) です。

使用例しようれい

TEST
#entry main
#target std
#import "alloc/collections/vec" as *
fn main <()*>i32> ():
    let v vec_with_capacity<i32> 16;
    if eq vec_cap<i32> v 16 0 1

vec_len

要素数ようそすうを返かえす

目的もくてき

  • Vec<.T> に現在げんざい何個なんこの要素ようそが入はいっているかを返かえします。

実装じっそう

  • struct field len をそのまま返かえします。

注意ちゅうい

  • 変更へんこうを伴ともなわない読よみ取とり API です。

計算量けいさんりょう

  • 時間じかん計算量けいさんりょうは O(1) です。

使用例しようれい

TEST
#entry main
#target std
#import "alloc/collections/vec" as *
fn main <()*>i32> ():
    let v0 new<i32>;
    let v1 push v0 3;
    if eq vec_len<i32> v1 1 0 1

vec_cap

容量ようりょうを返かえす

目的もくてき

  • 現在げんざい確保かくほされている要素数ようそすうぶんの容量ようりょうを返かえします。

実装じっそう

  • struct field cap をそのまま返かえします。

注意ちゅうい

  • 変更へんこうを伴ともなわない読よみ取とり API です。

計算量けいさんりょう

  • 時間じかん計算量けいさんりょうは O(1) です。

使用例しようれい

TEST
#entry main
#target std
#import "alloc/collections/vec" as *
fn main <()*>i32> ():
    let v new<i32>;
    if gt vec_cap<i32> v 0 0 1

vec_data_ptr

内部ないぶデータ領域りょういきの raw address を返かえす

目的もくてき

  • 既存きぞん API との互換ごかんのため、MemPtr<.T> の番地ばんちを i32 として取とり出だします。

実装じっそう

  • field data の MemPtr<.T> を mem_ptr_addr で raw address に戻もどします。

注意ちゅうい

  • 返かえり値あたいは生なまアドレスなので、範囲はんい・寿命じゅみょう・再確保さいかくほを呼よび出だし側がわで管理かんりする必要ひつようがあります。
  • 新規しんきコードでは、できるだけ vec_data_mem_ptr を優先ゆうせんします。

計算量けいさんりょう

  • 時間じかん計算量けいさんりょうは O(1) です。

使用例しようれい

TEST
#entry main
#target std
#import "alloc/collections/vec" as *
fn main <()*>i32> ():
    let v new<i32>;
    if gt vec_data_ptr<i32> v 0 0 1

vec_data_mem_ptr

内部ないぶデータ領域りょういきを MemPtr<.T> として返かえす

目的もくてき

  • alloc/collections 内部ないぶで Vec<.T> の要素ようそ領域りょういきを型付きポインタとして安全あんぜんに扱あつかえるようにします。

実装じっそう

  • field data をそのまま返かえします。

注意ちゅうい

  • 主おもに stdlib 内部ないぶの実装じっそう補助ほじょを想定そうていした API です。
  • 再確保さいかくほが起おきると pointer は無効化むこうかされうるので、長期ちょうき保持ほじは避さけます。

計算量けいさんりょう

  • 時間じかん計算量けいさんりょうは O(1) です。

vec_data_len

内部ないぶバッファ先頭せんとうと要素数ようそすうを同時どうじに返かえす

目的もくてき

  • sort 系けい helper のように data と len を同時どうじに使つかう処理しょりで、field 名めいつきの struct を得えられるようにします。

使用例しようれい

TEST
#entry main
#target std
#import "alloc/collections/vec" as *
#import "core/field" as *
fn main <()*>i32> ():
    let v0 new<i32>;
    let v1 push v0 7;
    let s vec_data_len<i32> v1;
    if and gt mem_ptr_addr get s "data" 0 eq get s "len" 1 0 1

実装じっそう

  • Vec<.T> から data と len を取とり出だし、VecDataLen<.T> として返かえします。

注意ちゅうい

  • data は MemPtr<.T> なので、生なまアドレスが必要ひつような場合ばあいは mem_ptr_addr を通とおします。

計算量けいさんりょう

  • 時間じかん計算量けいさんりょうは O(1) です。

vec_is_empty: 空か判定する

目的:

  • len が 0 なら true を返します。

実装(アルゴリズム):

  • len == 0 を判定します。

注意(重要):

  • 変更操作ではありません。

計算量:

  • O(1)

使い方:

TEST
#entry main
#target std
#import "alloc/collections/vec" as *
fn main <()*>i32> ():
    let v new<i32>;
    if vec_is_empty<i32> v 0 1

vec_push: 末尾に要素を追加する

目的:

  • item を末尾に追加し、新しい Vec を返します。

実装(アルゴリズム):

  • 容量不足なら 2 倍に拡張して realloc します。

注意(重要):

  • 返り値の Vec を受け取り直してください。

計算量:

  • ならし O(1)

使い方:

TEST
#entry main
#target std
#import "alloc/collections/vec" as *
fn main <()*>i32> ():
    let v0 new<i32>;
    let v1 push v0 7;
    if eq vec_len<i32> v1 1 0 1

vec_get: 要素を取得する

目的:

  • idx が範囲内なら Some、範囲外なら None を返します。

実装(アルゴリズム):

  • idx の範囲を判定し、要素を load します。

注意(重要):

  • idx が負のときも None です。

計算量:

  • O(1)

使い方:

TEST
#entry main
#target std
#import "alloc/collections/vec" as *
#import "core/option" as *
fn main <()*>i32> ():
    let v0 new<i32>;
    let v1 push v0 9;
    match vec_get<i32> v1 0:
        Option::Some x:
            if eq x 9 0 1
        Option::None:
            1

vec_set: 要素を上書きする（範囲外は無視）

目的:

  • idx が範囲内なら値を上書きします。

実装(アルゴリズム):

  • idx の範囲を判定し、範囲内のみ store します。

注意(重要):

  • 範囲外は何もしません。

計算量:

  • O(1)

使い方:

TEST
#entry main
#target std
#import "alloc/collections/vec" as *
#import "core/option" as *
fn main <()*>i32> ():
    let v0 new<i32>;
    let v1 push v0 1;
    vec_set<i32> v1 0 5;
    0

vec_pop: 末尾要素を取り出す

目的:

  • 末尾要素を返し、長さを 1 減らします。

実装(アルゴリズム):

  • len==0 なら None、そうでなければ最後の要素を load します。

注意(重要):

  • 返り値は (Vec, Option) のタプルです。

計算量:

  • O(1)

使い方:

TEST
#entry main
#target std
#import "alloc/collections/vec" as *
#import "core/option" as *
fn main <()*>i32> ():
    let v0 new<i32>;
    let v1 push v0 4;
    let p vec_pop<i32> v1;
    0

vec_clear: すべての要素を削除する

目的:

  • len を 0 にして空にします。

実装(アルゴリズム):

  • data はそのままに len だけを 0 にします。

注意(重要):

  • メモリは解放されません。

計算量:

  • O(1)

使い方:

TEST
#entry main
#target std
#import "alloc/collections/vec" as *
fn main <()*>i32> ():
    let v0 new<i32>;
    let v1 push v0 1;
    let v2 vec_clear<i32> v1;
    if eq vec_len<i32> v2 0 0 1

vec_free: メモリを解放する

目的:

  • data を解放します。

実装(アルゴリズム):

  • cap サイズ分の領域を dealloc します。

注意(重要):

  • Vec 自体は値なので解放不要です。

計算量:

  • O(1)

使い方:

TEST
#entry main
#target std
#import "alloc/collections/vec" as *
fn main <()*>i32> ():
    let v new<i32>;
    vec_free<i32> v;
    0

new: vec_new の短縮エイリアス
len: vec_len の短縮エイリアス
cap: vec_cap の短縮エイリアス
push: vec_push の短縮エイリアス

目的:

  • パイプ演算子と組み合わせた記述を簡潔にします。

実装(アルゴリズム):

  • vec_push をそのまま再公開します。

注意(重要):

  • シグネチャは vec_push と同じです。

計算量:

  • ならし O(1)

使い方:

TEST
#entry main
#target std
#import "alloc/collections/vec" as *
fn main <()*>i32> ():
    let v:
        new<i32>
        |> push 1
        |> push 2
    if eq len<i32> v 2 0 1