t_wの輪郭

Feedlyでフォローするボタン

配列

2022/2/16 23:05:00

プログラミングにおける配列

配列またはベクトル(科学技術計算分野の用語で1次元配列)。

特徴

高速な参照,ランダム アクセスに優れる。

要素の挿入・削除は遅い(最後尾 O(1)、途中 O(n))。

検索はソート時 O(1), 非ソート時 O(n) 時間かかる?

実装

添字で値に対応付けられたもの。データがメモリー上に連続しているかどうかはこの定義に直接の関係はない。単純な配列で,非負整数を対応づけるのに最小の実装方法であるだけ。

分類

添字の種類による分類

単純な配列。要素の型・大きさが固定である場合。添字nはメモリ上に連続した値の先頭からn番目を表わす。

連想配列。添字に非負整数型以外のデータを使えるようにしたもの。ハッシュPerlRuby)や二分木C++ std::map)などで実装されている。

記憶領域確保の仕方による分類

静的配列。予め決められた要素数のみ格納化。

動的配列。要素数に合わせて領域を伸縮させる。動的に確保された静的配列のことではない。

多次元配列

矩形配列。一般的な多次元配列で,n 次元内の要素数が横並びのもの。

不規則配列(ジャグ配列)。n 次元内の要素数が不揃いのもの。

let a = [10, 20, 30, 40, 50];

for element in a.iter() {
    println!("the value is: {}", element);
}
/*
the value is: 10
the value is: 20
the value is: 30
the value is: 40
the value is: 50
*/