クラスにしないほうがそもそも速いような気もする．
全体的に参照乱発，エラーチェックなしという構成のため，バグを出さずに運用するのは難しい？
※1/14追記 メモリリークを避けるためにデストラクタも実装すべき（コメント感謝）
スタック
コード
コンストラクタでサイズを指定．サイズを超える数のデータを入れたらアウト．
indexとmax_size比べてエラーチェック実装できそう．
stack.h
#ifndef STACK_H
#define STACK_H
template <class T>
class myStack{
public: //カプセル化なんてなかった
T *data;
int index;
int max_size;
myStack(){};
myStack(int size);
T &pop();
void push(T &city);
};
template <class T>
myStack<T>::myStack(int size){
data = new T[size];
index = 0;
max_size = size;
}
template <class T>
T &myStack<T>::pop(){
return data[--index];
}
template <class T>
void myStack<T>::push(T &c){
data[index++] = c;
}
#endif
使い方
how_to
int size = 10;
myStack<int> stack(size);
stack.push(5);
cout << stack.pop() << endl;
キュー
コード
こちらも指定サイズを超えるとアウト．
headとtailを比較して，エラーチェック実装できると思う．
queue.h
#ifndef QUEUE_H
#define QUEUE_H
template <class T>
class myQueue{
public: //カプセル化なんてなかった
T *data;
int head, tail;
int max_size;
myQueue(){};
myQueue(int size);
T &dequeue();
void enqueue(T &city);
};
template <class T>
myQueue<T>::myQueue(int size){
data = new T[size];
head = tail = 0;
max_size = size;
}
template <class T>
T &myQueue<T>::dequeue(){
if(head == max_size) head = 0;
return data[head++];
}
template <class T>
void myQueue<T>::enqueue(T &c){
if(tail == max_size) tail = 0;
data[tail++] = c;
}
#endif
使い方
how_to
int size = 10;
myQueue<int> queue(size);
queue.enqueue(4);
cout << queue.dequeue() << endl;
速度比較
せっかくなので比べてみる
コード
ここを参考にどの程度早くなるか試してみました．
chrono
#include <iostream>
#include <stack>
#include <queue>
#include "stack.h"
#include "queue.h"
#include <chrono>
#include <time.h>
#define size 100000000
using namespace std;
int main(int argc, char **argv){
stack<int> stl_stack;
myStack<int> mystack(100);
queue<int> stl_queue;
myQueue<int> myqueue(100);
int hoge;
int *rands = (int *) malloc(sizeof(int) * size);
srand((unsigned int)time(NULL));
for(int i = 0; i < size; i++)
rands[i] = rand();
auto start = chrono::system_clock::now();
for(int i = 0; i < size; i++){
stl_stack.push(rands[i]);
hoge = stl_stack.top();
stl_stack.pop();
}
auto end = chrono::system_clock::now();
auto diff = end - start;
cout << "elapsed time stl_stack = "
<< chrono::duration_cast<chrono::milliseconds>(diff).count()
<< " msec." << endl;
start = chrono::system_clock::now();
for(int i = 0; i < size; i++){
mystack.push(rands[i]);
hoge = mystack.pop();
}
end = chrono::system_clock::now();
diff = end - start;
cout << "elapsed time my stack = "
<< chrono::duration_cast<chrono::milliseconds>(diff).count()
<< " msec." << endl;
start = chrono::system_clock::now();
for(int i = 0; i < size; i++){
stl_queue.push(rands[i]);
hoge = stl_queue.front();
stl_queue.pop();
}
end = chrono::system_clock::now();
diff = end - start;
cout << "elapsed time stl_queue = "
<< chrono::duration_cast<chrono::milliseconds>(diff).count()
<< " msec." << endl;
start = chrono::system_clock::now();
for(int i = 0; i < size; i++){
myqueue.enqueue(rands[i]);
hoge = myqueue.dequeue();
}
end = chrono::system_clock::now();
diff = end - start;
cout << "elapsed time my queue = "
<< chrono::duration_cast<chrono::milliseconds>(diff).count()
<< " msec." << endl;
return 0;
}
結果
result
$ ./a.out # 最適化オプション無し
elapsed time stl_stack = 6942 msec.
elapsed time my stack = 855 msec.
elapsed time stl_queue = 5322 msec.
elapsed time my queue = 1062 msec.
$ ./a.out # -O1で最適化
elapsed time stl_stack = 1023 msec.
elapsed time my stack = 505 msec.
elapsed time stl_queue = 1418 msec.
elapsed time my queue = 665 msec.
※1/14追記
stack<int,vector<int> > stl_stack;
という形でSTLのスタックを宣言してやると，-O1下で二つのスタックはほぼ同じ速度になりました．（コメント感謝）
結論：最適化オプションすごい