vectorを頑張って作ろうとする
当記事はCCS Advent Calendar 2018の22日目の記事です
昨日(21日目)の記事↓
[まだ公開されてないようです]
C++には便利な関数やクラスが備わっています。
その一つにvectorがあります
今回はそいつを実装していくぞい!
※間違ったことを言ってる可能性があります
※実装したコードの解説はかなり少なめで、使った技術の解説()が主となっています
※当サークルのC言語講座、C++講座レベルの知識があることが前提の記事となっています
※実は当初はvector、tuple、functionの3本立ての予定でした
vector
そもそもvectorってなんじゃい!
って方のために軽く紹介とテストをしていこうかと。
vectorとは
newで確保してdeleteで開放する普通の動的配列はdeleteし忘れるとメモリが大変なことになってしまうし、途中で要素を追加するときとか結構面倒。
億劫すぎてお空ちゃんになるまである。
そこでvector!
vectorは脳死で要素の追加や削除をさせてくれる上に、自分が消滅するときに開放も行ってくれます。
まさに悪魔の力。
代表的なメンバ関数
- push_back(T obj)
配列末尾に引数にしたやつを要素として追加する。
- size(void)
配列のサイズを返す。
指定要素の削除。(開放されるのかは・・・しらないです・・・)
- clear(void)
要素全削除(開放はされない)。
指定したところに新要素追加
他にも色々便利なのがある上に、引数の違う同名関数も存在しますが今回実装していくのはここらへんに絞ろうと思います。
使ってみよう!
実際に使ってみましょう。
用意したサンプルコードがこちら
#include <iostream> #include <vector> using namespace std; class Vec2{ private: int x, y; public: Vec2(int _x, int _y): x(_x), y(_y){} void show(){ cout << "(x, y) = " << "(" << x << ", " << y << ")" << endl; } }; int main(){ vector<int> num; for(int i = 0; i < 5; i++){ num.push_back(i); } cout << "Add value to num" << endl; for(int i : num){ cout << i << " "; } cout << endl << endl; cout << "Add value to chara" << endl; vector<char> chara = {'C', 'h', 'r', 'n', 'o'}; for(char c : chara){ cout << c; } cout << endl << endl; cout << "Clear num" << endl; chara.clear(); for(int i = 0; i < (int)chara.size(); i++){ cout << chara[i]; } cout << endl << endl; cout << "Add value to Vec2" << endl; vector<Vec2> vec2 = {{3, 3}, {0, 4}}; for(int i = 0; i < (int)vec2.size(); i++){ vec2[i].show(); } cout << endl; return 0; } }
出力はこうなりました。
Add value to num 0 1 2 3 4 Add value to chara Chrno Clear num Add value to Vec2 (x, y) = (3, 3) (x, y) = (0, 4)
push_backでの要素の追加、sizeによる要素数取得、clearによる全要素削除なされてますね
また例のように、通常の配列のように、(obj) = {a, b, c, d, ...}の形式で初期化することもできます
例ではクラスだけですが、構造体はもちろん、共用体(Tupleの章で紹介)、列挙体(当記事ではあつかってないです.自分で調べてください(投げやり).当アドベントカレンダーでも扱っている記事があります.)でも大丈夫ですqiita.com
Cによる実装
方針
Cだと構造体に関数を入れることができないので、面倒だけどvectorのポインタを引数に取ってどうこうするしかなさそう
また、デストラクタも作成できないため自動開放機能をもたせることは困難・・・
free関数を作成してそれを呼び出すように心がけなくてはいけません
(実は次の項目で載せたプログラムはC言語では関数オーバーロードができないことを知らずに書いてました.衝突を避けるためにget_Intなどとしたほうが良さそうです)
そしてこうなった
コード
// Vector.h #pragma once typedef struct{ int *array; int size; }Vector_Int; int get(Vector_Int *vector, int index); void push_back(Vector_Int *vector, int value); void erase(Vector_Int *vector, int erase); void clear(Vector_Int *vector); int size(Vector_Int *vector); void vec_free(Vector_Int *vector);
// Vector.cpp #include "Vector.h" #include <stdlib.h> #include<stdio.h> int get(Vector_Int *vector, int index){ if(index < vector->size){ return vector->array[index]; } return -1; } void push_back(Vector_Int *vector, int value){ int *new_array = (int*)malloc(sizeof(int) * (vector->size + 1)); for(int i = 0; i < vector->size; i++){ new_array[i] = vector->array[i]; } new_array[vector->size] = value; if(vector->size != 0){ free(vector->array); } vector->array = new_array; vector->size++; } void erase(Vector_Int *vector, int index){ for(int i = index; i < vector->size - 1; i++){ vector->array[i] = vector->array[i + 1]; } vector->size--; if(vector->size == 0){ free(vector->array); } } void clear(Vector_Int *vector){ free(vector->array); vector->size = 0; } int size(Vector_Int *vector){ return vector->size; } void vec_free(Vector_Int *vector){ free(vector->array); vector->size = 0; }
// main.c #include "Vector.h" #include <stdio.h> int main(){ Vector_Int vec; int num[5] = {1, 0, 6, 5, 3}; // 末尾にどんどん追加していく for(int i = 0; i < 5; i++){ push_back(&vec, num[i]); } // 追加したことを確認するために出力 for(int i = 0; i < size(&vec); i++){ printf("vec[%d] = %d\n", i, get(&vec, i)); } printf("size = %d\n\n", size(&vec)); // 2番目のやつ、つまり6を削除 erase(&vec, 2); // 削除できたか確認 for(int i = 0; i < size(&vec); i++){ printf("vec[%d] = %d\n", i, get(&vec, i)); } printf("size = %d\n\n", size(&vec)); // 全部削除 clear(&vec); // 削除できたか確認 for(int i = 0; i < size(&vec); i++){ printf("vec[%d] = %d\n", i, get(&vec, i)); } printf("size = %d\n\n", size(&vec)); vec_free(&vec); return 0; }
出力
vec[0] = 1 vec[1] = 0 vec[2] = 6 vec[3] = 5 vec[4] = 3 size = 5 vec[0] = 1 vec[1] = 0 vec[2] = 5 vec[3] = 3 size = 4 size = 0
とりあえずそれっぽく動いてはいる・・・が・・・
問題点
- 今回は律儀にget関数やsize関数を使って中身の配列にアクセスしていたが、vec.array[0]、vec.sizeのように直接アクセスすることができてしまう
- 引数に毎度アドレスを入れるのが面倒
- 自動開放してくれない
- 配列として使ってるんだからvec[0]で配列0番目にアクセスできるようにしたい
- 他の型のやつを別に実装しなくてはならない
C++のクラスを使えばいくつかは解消できます
クラスを使った実装
方針
C版の関数をvectorクラスのメンバ関数にしていき、vec_freeはデストラクタにすることで自動開放を実現
クラスにしていくだけなので解説はほとんどないです・・・(Cも全然解説してなかったけど)
こうなった
コード
// Vector.h #pragma once class Vector{ protected: int arysize; int maxsize; public: Vector(void): arysize(0), maxsize(0) {} virtual void erase(int index) = 0; void clear(void); int size(void); };
// Vector.cpp #include "Vector.h" void Vector::clear(){ arysize = 0; } int Vector::size(){ return arysize; }
// Vector_Int.h #pragma once #include "Vector.h" #include <stdlib.h> class Vector_Int : public Vector{ protected: int *array; public: Vector_Int(void): Vector(), array(NULL) {} ~Vector_Int(void){ if(array != NULL){ delete array; } } int get(int index); void push_back(int value); void erase(int index) override; void insert(int index, int value); };
// Vector_Int.cpp #include "Vector_Int.h" int Vector_Int::get(int index){ return array[index]; } void Vector_Int::push_back(int value){ if(arysize == maxsize){ int *temp = new int[maxsize + 5]; for(int i = 0; i < arysize; i++){ temp[i] = array[i]; } delete array; array = temp; maxsize += 5; } array[arysize] = value; arysize++; } void Vector_Int::erase(int index){ for(int i = index; i < arysize - 1; i++){ array[i] = array[i + 1]; } arysize--; } void Vector_Int::insert(int index, int value){ if(arysize == maxsize){ int *temp = new int[maxsize + 5]; for(int i = 0; i < index - 1; i++){ temp[i] = array[i]; } delete array; array = temp; maxsize += 5; } for(int i = arysize; i > index; i--){ array[i] = array[i - 1]; } array[index] = value; arysize++; }
// main.cpp #include "Vector_Int.h" #include <iostream> void show(Vector_Int& vec){ for(int i = 0; i < vec.size(); i++){ std::cout << "vec[" << i << "] = " << vec.get(i) << std::endl; } std::cout << "size = " << vec.size() << std::endl << std::endl; } int main(){ Vector_Int vec; // 7, 8, 3をとりあえず入れてみて確認 int num[3] = {7, 8, 4}; for(int i : num){ vec.push_back(i); } show(vec); // 1番目、つまり8を削除して確認 vec.erase(1); show(vec); // 1番目に9を挿入、つまり7, 9, 3になるはずなので確認 vec.insert(1, 9); show(vec); // 全要素削除して確認 vec.clear(); show(vec); return 0; }
出力
vec[0] = 7 vec[1] = 8 vec[2] = 4 size = 3 vec[0] = 7 vec[1] = 4 size = 2 vec[0] = 7 vec[1] = 9 vec[2] = 4 size = 3 size = 0
いいかんじ
なんか実際のvectorはメモリ確保するときに多めに確保するらしく、またclearではメモリ解放がなされないようなのでそれに従いました(実際こんなんなのかは知りませんが・・・)
C版と比べたらだいぶ使いやすくなった・・・けどまだまだ・・・
問題点
- 配列として使ってるんだからvec[0]で配列0番目にアクセスできるようにしたい
- 他の型のやつを別に実装しなくてはならない
とりあえず[]によるアクセスをできるようにしていきましょう
演算子オーバーロードを使った実装
演算子オーバーロードとは
C++では引数型違いの同名関数を作成、使用可能ですが演算子もオーバーロードすることができ、これによって今までできなかった自作クラスに対して*や+を使用することができるようになります
- 四則演算のオーバーロード
四則演算は次のように記述することでオーバーロードできます
/返り値の型/ operator/演算子/ (/演算対象(足し算で言うと足す数みたいな)の型と仮引数名/){ //処理を記述 return /返り値/ }
例えば、xとyの二次元座標を扱うVec2型の構造体に対して、+演算子により単純にxとyをそれぞれ足し合わせたものを返すようにする場合はこのようになります
struct Vec2{ int x, y; Vec2(int _x, int _y): x(_x), y(_y){} Vec2 operator+ (Vec2& obj){ Vec2 ret_obj(this->x + obj.x, this->y + obj.y); return ret_obj; } void show(){ std::cout << "(" << x << ", " << y << ")" << std::endl; } };
テストするために下のようなmain関数を書きました
int main(){ Vec2 a(2, 0), b(3, 3); Vec2 c = a + b; c.show(); }
出力結果
(5, 3)
ちゃんと足せてますね
楽勝すぎる、完全に理解した
😇「と思っていたのかぁ?」
こんな構造体を用意しました
struct test{ int a; test(int x):a(x){} int operator+ (test& x){ return 0; } };
これに対してmainをこのようにします
int main(){ test a(0); const test b(0); std::cout << a + a << std::endl; return 0; };
すると出力は
0
普通やんってかんじですが、a + aをa + bやb + bにするとコンパイルエラーになります
それもそのはず、引数がtest&では途中で書き換えられてしまう可能性があります
そのような処理をconst修飾子のついた変数を渡すわけにはいかないのです
ということで、このようにすればa + bを計算することができるようになります
#include <iostream> struct test{ int a; test(int x):a(x){} int operator+ (test& x){ return 0; } int operator+ (const test& x){ return 1; } }; int main(){ test a(0); const test b(0); std::cout << a + b << " " << a + a << std::endl; return 0; };
出力結果は
1 0
ちゃんとできるようになりました
ちなみにこれ、test&の方を消しても大丈夫です(出力は1 1)
constが非const&引数として渡されると改ざんの危険がありますが、非constがconst&引数として渡されてもなんの危険もありませんからね(ただし、非const&のほうがより適してるので両方存在する場合はそっち)
では足される側がconstの場合はどうしたらいいのかというと・・・
関数をconst化します
なんじゃそりゃってかんじですが
void func() const{ }
のようにすると、その関数内でメンバ変数の変更、非constメンバ関数の仕様が禁止されます
これを利用することでconst + constやconst +非constに対応することができるようになります
例えばこんなかんじにすると
#include <iostream> struct test{ int a; test(int x):a(x){} int operator+ (test& x){ return 0; } int operator+ (const test& x){ return 1; } int operator+ (test& x) const{ return 2; } int operator+ (const test& x) const{ return 3; } }; int main(){ test a(0); const test b(0); std::cout << a + b << " " << a + a << " " << b + a << " " << b + b << std::endl; return 0; };
出力は
1 0 2 3
いいかんじですね
先程同様、(test&)を削除しても大丈夫です
・・・とはなりませんでした
a + aは両方非constなため(const test&)、(test&)constとの一致度が同じになってしまい、衝突してしまいます
どっちかを消せば一応解決です
どの組み合わせでも処理を変える気ないなくて面倒なら(const&)constのみ、念のために・・・という場合は全部定義しておくのが良さそうです
本当はもっと定義しておいたほうが良さそうなのあるかもしれませんが・・・同型同士に関しては今回はここまでで・・・
あ、今回は実験のために返り値を定数にしましたが、+にかかわらず処理内容はその演算子っぽいものにしましょう
同型同士といいましたが、他の型に対しても定義することができます
例
#include <iostream> struct Vec2{ int x, y; Vec2(int _x, int _y): x(_x), y(_y){} Vec2 operator+(int& num){ Vec2 ret_obj(this->x + num, this->y + num); return ret_obj; } void show(){ std::cout << "(" << x << ", " << y << ")" << std::endl; } }; int main(){ Vec2 a(2, 0); int b = 3; Vec2 c = a + b; c.show(); }
出力
(5, 3)
できました
こちらでもconstの問題はありますが同型同士と同じようなかんじなので割愛
- 以外の四則演算子や%、=もほぼ同じです(+が*や%になる)
また、今回は二次元座標を表す構造体を作りました
二次元座標に対する同型同士の掛け算の処理は内積と外積の2種類がありますが、関数オーバーロード同様に返り値の型違いでオーバーロードできないので注意してください
諦めてどちらかをメンバ関数にしましょう・・・
- 添字演算子
まず添字演算子とはなんぞい、というと配列の[]これです
これをオーバーロードすることで配列感マシマシ
とりあえず、添字演算子はこんなかんじで記述する
(返り値の型) operator[] (int n){ // 処理を記述 return (返り値) }
引数のnはarray[5]でいう5です
まぁ、使用例を見ていきましょう
#include <iostream> struct Vec2{ int x, y; Vec2(int _x = 0, int _y = 0): x(_x), y(_y){} void show(){ std::cout << "(" << x << ", " << y << ")" << std::endl; } }; class Array_Vec2{ private: Vec2 *array; public: Array_Vec2(int num_elm): array(new Vec2[num_elm]()){} Vec2& operator[] (int n){ return array[n]; } }; int main(){ const int ARRAY_SIZE = 3; Vec2 a(2, 0); Array_Vec2 vecary(ARRAY_SIZE); vecary[1] = a; for(int i = 0; i < ARRAY_SIZE; i++){ vecary[i].show(); } return 0; }
出力
(0, 0) (2, 0) (0, 0)
ちゃんと配列のようになってますね
ただ注意が必要なのは、operator[]の返り値の方をVec2&からVec2にすると出力は
(0, 0) (0, 0) (0, 0)
となってしまいます
&がなくなったことにより参照渡し(array[n]そのものを渡す)から値渡し(array[n]が持っていた値を渡す)(←ここらへんの説明は強い人が見たらいやいや・・・と言われてしまう可能性ありそうですが、まあそんな認識でとりあえず大丈夫なはず)になってしまうためです
array[1]とはもはやなんのつながりもないものに対して代入をしているので当然array[1]にはなんの影響もありません
これでどうすればvectorを配列っぽく使えるか見えてきましたね
ちなみに、Java版vectorのArrayListは[]が定義されておらずget関数でわざわざ要素を呼び出すという面倒な仕様になったますが、あれはJavaは演算子オーバーロードをサポートしてないからです(Stringはなんかできますが・・・)
結局vectorはどうなったの
vector.hだけの記載にしますが、こうなりました
// Vector_Int.h #pragma once #include "Vector.h" #include <stdlib.h> class Vector_Int : public Vector{ protected: int *array; public: Vector_Int(void): Vector(), array(NULL) {} ~Vector_Int(void){ if(array != NULL){ delete array; } } void push_back(int value); void erase(int index) override; void insert(int index, int value); int& operator[](int n){ return array[n]; } };
例のとほぼ変わらないです
特に解説することも・・・なさそう・・・
問題点
- 他の型のやつを別に実装しなくてはならない
この問題を解決するためにクラステンプレートとかいう闇技術を使用します
クラステンプレートを用いた実装
方針
クラステンプレート化して他のchar型など組み込み式の他の方やユーザー定義の型にも対応させる
クラステンプレートとは
まず、クラステンプレートはテンプレートの一種です
ほとんど同じだけど型が違う処理を、仮の型名を定めて一つ書いただけでいろいろな型に対応できるようにしてくれるのがテンプレートです
最も単純なものとしてテンプレート関数があります
まあ下手すぎる説明より例を見たほうがいいでしょう
どんな型でも2乗してその型のまま返してくれるテンプレート版square関数を作ってみました
コード
#include <iostream> using namespace std; template <typename T> T square(T x){ return x * x; } int main(){ int a = 9; double b = 1.1; char c = 5; a = square(a); b = square(b); c = square(c); cout << a << " " << b << " " << (int)c << endl; }
出力
81 1.21 25
char型はcoutで出力すると対応する文字が出力されてしまうのでintでキャストしましたが、ちゃんとどれも2乗されています
templateで次の関数がテンプレート関数であることを宣言、
Tはその関数内なら返り値の型、引数の型、途中で宣言する変数の型など、なんにでも使えます
また、先程の例では省略しましたがテンプレート関数を使うときに<"型">と記述することでそのテンプレート関数をどの型のものとして使うかを明示できます
つまり、先程のmain関数をこのようにすると・・・
#include <iostream> using namespace std; template <typename T> T square(T x){ return x * x; } int main(){ int a = 9; double b = 1.1; char c = 5; a = square<int>(a); b = square<int>(b); c = square<char>(c); cout << a << " " << b << " " << (int)c << endl; }
こうなります
81 1 25 <|| double型であるbをint版squareに渡すことで、引数bが(int)1.1、つまり1として扱われ、1 * 1で1がbに代入されたというわけです 何個もオーバーロードする必要もなく、どの型を使うかの明示もしやすくてとても便利 しかしこれは実際はあらゆる型に対応した関数ではなく、対応した型バージョンの関数を作ってくれるものなので、使った型の分だけコンパイル時間や実行ファイルサイズが増大してしまいます これは他の種類のテンプレートでも同じです また、正直これは私はあんま理解できてないんですが、テンプレートは一つのコンパイル単位に実装をまとめる必要があります つまりヘッダーファイルに実装を書くというなんとも奇妙なことをしなくてはならんわけです 今回使うクラステンプレートもだいたい同じようなかんじですが、例を見たほうがわかりやすいでしょう >|cpp| #include <iostream> using namespace std; template <typename T> class test{ private: int a; T b; public: test(int _a, T _b): a(_a), b(_b){} int get_a(){ return a; } T get_b(){ return b; } }; int main(){ test<char> tes(1053, '!'); cout << tes.get_a() << " " << tes.get_b() << endl; return 0; }
出力
1053 !
aとbの2つのメンバ変数を持つテンプレートクラスtestを作成しました
aはint型ですが、bの方は自由に指定可能です
テンプレート関数は使用時に「(関数名)<(どの型にするか)>」という書き方をしましたが、クラステンプレートは「(クラス名)<(どの型にするか)>」となります
ただし、テンプレート関数とは違い、<型>の省略は通常ではできません
が、テンプレートクラスは、関数でデフォルト引数を設定できるように、デフォルトクラスを設定でき、設定した場合、型を省略して<>にするとTはデフォルトクラスの型として扱われます(<>は省略できないです)
例えば先程のtestテンプレートクラスのtemplate
このように
#include <iostream> using namespace std; template <typename T = double> class test{ private: int a; T b; public: test(int _a, T _b): a(_a), b(_b){} int get_a(){ return a; } T get_b(){ return b; } }; int main(){ test<> tes(1053, 0.00094967); cout << tes.get_a() << " " << tes.get_b() << endl; return 0; }
出力
1053 0.00094967
ちなみに、今回は使いませんが、複数のテンプレート引数を指定することもできます
例えばこんなかんじ
template <typename T, typename U> class test{ private: int a; T b; U c; public: test(int _a, T _b, U _c): a(_a), b(_b), c(_c){} int get_a(){ return a; } T get_b(){ return b; } U get_c(){ return c; } };
Vectorをテンプレート化できそうですね
そして出来上がったのがこれ
// Vector.h #pragma once #include <iostream> template<typename T> class Vector{ protected: T *array; int arysize; int maxsize; public: Vector(void): array(NULL), arysize(0), maxsize(0) {} ~Vector(void){ if(array != NULL){ delete array; } } void push_back(T obj){ if(arysize == maxsize){ T *temp = new T[maxsize + 5]; for(int i = 0; i < arysize; i++){ temp[i] = array[i]; } maxsize += 5; delete array; array = temp; } array[arysize] = obj; arysize++; } void insert(int index, T obj){ if(arysize == maxsize){ T *temp = new T[maxsize + 5]; for(int i = 0; i < arysize; i++){ temp[i] = array[i]; } maxsize += 5; delete array; array = temp; } for(int i = arysize; i > index; i--){ array[i] = array[i - 1]; } array[index] = obj; arysize++; } void erase(int index){ for(int i = index; i < arysize - 1; i++){ array[i] = array[i + 1]; } arysize--; } void clear(void){ arysize = 0; } int size(void){ return arysize; } T& operator[](int n){ return array[n]; } };
// main.cpp #include "Vector.h" int main(){ int num[] = {3, 3, 4}; Vector<int> vec_int; for(int i = 0; i < 3; i++){ vec_int.push_back(num[i]); } for(int i = 0; i < vec_int.size(); i++){ std::cout << vec_int[i] << " "; } std::cout << std::endl << std::endl; const char *str[] = { "KamenRide ", "ZI-O"}; Vector<const char*> vec_charp; for(int i = 0; i < 2; i++){ vec_charp.push_back(str[i]); } for(int i = 0; i < vec_charp.size(); i++){ std::cout << vec_charp[i]; } std::cout << std::endl << std::endl; vec_charp[1] = "DECADE"; for(int i = 0; i < vec_charp.size(); i++){ std::cout << vec_charp[i]; } std::cout << std::endl << std::endl; vec_charp.insert(0, "Final"); for(int i = 0; i < vec_charp.size(); i++){ std::cout << vec_charp[i]; } std::cout << std::endl << std::endl; return 0; }
出力
3 3 4 KamenRide ZI-O KamenRide DECADE FinalKamenRide DECADE
うまくいきましたね
ジオウにカメンライドした後にディケイドにカメンライドするのセンスないけど許して・・・
平ジェネ観にいきてぇ・・・
おしまい
これでこの記事はおしまい
本当はもう少しクラステンプレート掘り下げたかったのと、Cでもできるけど本サークル2年生以下はあまり知らなそうで、クラステンプレートよかゲーム制作に役立ちそうそうな可変長引数の関数とか紹介したかったんですが、時間やばいのともともと低い説明力がどんどん低下していってるのを感じてきてるのでやめます・・・逆にわからなくなりそう・・・