配列
2022/2/16 23:05:00
プログラミングにおける配列
配列またはベクトル（科学技術計算分野の用語で1次元配列）。
特徴
高速な参照，ランダム アクセスに優れる。
要素の挿入・削除は遅い（最後尾 O(1)、途中 O(n)）。
検索はソート時 O(1), 非ソート時 O(n) 時間かかる？
実装
添字で値に対応付けられたもの。データがメモリー上に連続しているかどうかはこの定義に直接の関係はない。単純な配列で，非負整数を対応づけるのに最小の実装方法であるだけ。
分類
添字の種類による分類
単純な配列。要素の型・大きさが固定である場合。添字nはメモリ上に連続した値の先頭からn番目を表わす。
連想配列。添字に非負整数型以外のデータを使えるようにしたもの。ハッシュ（Perl，Ruby）や二分木（C++ std::map）などで実装されている。
記憶領域確保の仕方による分類
静的配列。予め決められた要素数のみ格納化。
動的配列。要素数に合わせて領域を伸縮させる。動的に確保された静的配列のことではない。
多次元配列
矩形配列。一般的な多次元配列で，n 次元内の要素数が横並びのもの。
不規則配列（ジャグ配列）。n 次元内の要素数が不揃いのもの。