C++で速度だけを気にしてスタックとキューを作製する


クラスにしないほうがそもそも速いような気もする．

全体的に参照乱発，エラーチェックなしという構成のため，バグを出さずに運用するのは難しい？

###### ※1/14追記 メモリリークを避けるためにデストラクタも実装すべき（コメント感謝）

# スタック

## コード
コンストラクタでサイズを指定．サイズを超える数のデータを入れたらアウト．
indexとmax_size比べてエラーチェック実装できそう．

```c++: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
```

##使い方
```c++:how_to
int size = 10;
myStack<int> stack(size);
stack.push(5);
cout << stack.pop() << endl;
```

# キュー

## コード

こちらも指定サイズを超えるとアウト．
headとtailを比較して，エラーチェック実装できると思う．

```c++: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
```

##使い方
```c++:how_to
int size = 10;
myQueue<int> queue(size);
queue.enqueue(4);
cout << queue.dequeue() << endl;
```

# 速度比較
せっかくなので比べてみる

## コード
[ここ](http://minus9d.hatenablog.com/entry/20130817/1376725888 "minus9d's diary")を参考にどの程度早くなるか試してみました．

```c++: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;
}
```

結果

```bash: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`下で二つのスタックはほぼ同じ速度になりました．（コメント感謝）


　
結論：最適化オプションすごい