vectorの概要
あまりガッチガチの文章を書くのは得意ではないので、まずはなんとなくの説明を試みようと思います。
vectorはリサイズ機能付きの配列
イメージとしては「リサイズ機能付きの配列」だと思います。
つまりは、ほぼ配列です。
配列のデータ構造
ここでの配列とは↓のことです。
int A[5];
このように書くと、int型のデータを5つ保存できます。
データの構造としてはこのような感じです。
vectorのデータ構造
vectorは以下のように宣言します。
std::vector A(5);
このように書いてできるデータの構造、このような感じです。
… 配列と同じですね。笑
違いが出てくるのはここからです。
vectorのリサイズ
配列は宣言してしまえば、基本的にサイズを変えることはできません(ものすごく頑張ればできるかもしれないですが)。
しかし、vectorはデータの追加があった時、自動的に配列のサイズを拡張します。
vectorは現在確保している配列のサイズをcapacityメソッドで確認することができます。
std::vector<int> A(5);
std::cout << A.capacity() << std::endl;
$ ./a.out
5
先ほど書いた図の通り、サイズは5であることがわかります。
さて、ここからデータを追加してみます。
std::vector<int> A(5);
std::cout << A.capacity() << std::endl;
A.push_back(10);
std::cout << A.capacity() << std::endl;
$ ./a.out
5
10
capacityが5から10に増えました。
どうやら2倍に増えそう？
vectorリサイズ後のサイズ
vectorがリサイズしてくれた後に、どのくらいのサイズを確保してくれるか確かめるために、以下のような実験を行なってみます。
初め、vector Aを宣言します。
5回データを追加して、size、capacityがどうなるかを調べます。
vectorのsizeは「現在、何個のデータが入っているか」を表します。
std::vector<int> A;
for( int i=0; i < 5; i++){
A.push_back(i+1);
std::cout << "size:" << A.size() << " capacity:" << A.capacity() << std::endl;
}
./a.out
size:1 capacity:1
size:2 capacity:2
size:3 capacity:4
size:4 capacity:4
size:5 capacity:8
上記のコードを図示してみると、以下のようになります。
配列がいっぱいの時、データが加えられると、リサイズが発生していることがわかります。
また、リサイズ後は元のサイズの2倍のサイズになっていることもわかります。
vectorリサイズまとめ
- size == capacityの時、データが加えられるとリサイズする。
- リサイズ後のサイズはリサイズ前の2倍
vector実装
c++、cでvectorを実装して、githubにアップロードしてみました(cの方はarrayという名前になってます、分かりずらくて申し訳ありません)。
ざっくりポイントを説明すると、データをmallocで確保していて、配列がいっぱいになると、reallocでメモリを再確保しています。
コメント