Exercise 2.1に関しては，ArrayStackを拡張したMyArrayStackに「効率の悪い」 addAllを実装する例を示します．MyArrayStack.h の中からincludeされているex2_1.hは，
void addAll(int i, MyArrayStack<T>& x) {
for (int j = 0; j < x.size(); j++){
add(i + j, x.get(j));
}
}
のように，addをx.size() 回繰り返して実装しています．size() - i個の要素を後ろにずらす add をx.size() 回繰り返す効率の悪いプログラムですが，動くことは動きます．
動作チェックをおこなうプログラム check_ex2_1.cppを
g++ --std=c++11 -Wall -O2 -o check_ex2_1 check_ex2_1.cppでコンパイルし．
./check_ex2_1で実行してOKが出ることで，このex2_1.hが正しく動作することを確認できます．以下のように，誤ったプログラム
void addAll(int i, MyArrayStack<T>& x) {
for (int j = 0; j < x.size(); j++){
add(i, x.get(j)); // i番目に要素をaddしていくと，xの要素が逆順になる
}
}
を実行すると，
NG as=[80, 70, 60, 50, 40, 30, 20, 10, 1, 2, 3, 4, 5], bs=[10, 20, 30, 40, 50, 60, 70, 80] as.addall(bs, 0) : output: [80, 70, 60, 50, 40, 30, 20, 10, 1, 2, 3, 4, 5] expected: [10, 20, 30, 40, 50, 60, 70, 80, 1, 2, 3, 4, 5]のように，間違いを検出してくれます(このチェックプログラムで検出できない間違いもあります)．
領域が足りない場合に現在の resize をそのまま呼び出しても，元のMyArrayStackのサイズ n に対して n * 2 のサイズしか確保できないので注意が必要です．加えようとする MyArrayStack のサイズが m だとすると n + m の領域が必要ですが，n * 2 >= n + m という保証はありません．別のresize を用意するか，resize相当のことをaddAll中に書く必要があります．
サイズ1のxsをaddAllする操作を繰り返しても，addを繰り返した場合と比較してそれほど遅くならない(たかだか定数倍しか遅くならない)ということも，「efficient implementation」のためには必要な条件になります．「必ずresizeする」という実装の場合は，この点で問題となります．
Exercise 2.2に関しては，ArrayStackを使ったMyRandomQueue.h を示します．
#includeMyRandomQueueはArrayStackを持っていて，addは後ろに付け加えるだけですが，removeは#include #include #include #include "ArrayStack.h" template class MyRandomQueue { ods::ArrayStack as; public: MyRandomQueue() :as() {} int size() {return as.size();} void add(T x) {as.add(x); } // replace this function T remove() { // return as.remove(rand() % as.size()); return as.remove(as.size() - 1); } };
T remove() {
return as.remove(rand() % as.size());
}
のように，ArrayStackのランダムな要素をArrayStackのremoveを使って取り除いて返します．removeが平均すると要素数に比例する実行時間がかかるため，これは効率が悪い (設問の仕様を満たさない) プログラムですが，動作は正しいものになっています．
動作チェックをおこなうプログラム check_ex2_2.cppを
g++ --std=c++11 -Wall -O2 -o check_ex2_2 check_ex2_2.cppでコンパイルし．
./check_ex2_2で実行してOKが出ることで確認できます．removeを
T remove() {
return as.remove(as.size() - 1);
}
に変更して実行すると，
not shuffled xs=[10, 20, 30, 40, 50, 60, 70, 80] output=[80, 70, 60, 50, 40, 30, 20, 10]のようなエラーが出ます．これは常に最後の要素をremove するので効率は問題ありませんが， 取り出される順番がいつも同じなので，このようなエラーが出ます．
#include "ArrayDeque.h"
#include "array.h"
#include "utils.h"
template<class T>
class MyTreque {
ods::ArrayDeque<T> ad;
public:
MyTreque() :ad() {}
int size() { return ad.size(); }
T get(int i) { return ad.get(i); }
T set(int i, T x) { return ad.set(i, x); }
void add(int i, T x) { return ad.add(i, x); }
T remove(int i) { return ad.remove(i); }
void clear() { ad.clear(); }
};
これは，add(i, x), remove(i) の実行時間が O(1+min{1,n-i,|n/2-i|}) であるという条件は満たしませんが，Listインタフェースは実装しているため，動くことは動きます．
動作チェックをおこなうプログラム check_ex2_3.cppを
g++ --std=c++11 -Wall -O2 -o check_ex2_3 check_ex2_3.cppでコンパイルし．
./check_ex2_3で実行してOKが出ます．
DualArrayDequeの考え方を拡張して解くことができますArrayStackを2つで Dequeを効率的に実現できるわけですが，ArrayDequeを2つ使うとどうなるでしょうか? ArrayStackを2つ使う時は，1回balanceを呼び出すと，O(n)のコストがかかったのですが，ArrayDeque ではfrontとbackの差が2以上になった時にbalanceを呼び出すようにするとO(1)のコストで実現できます．
締切は，5/31(日) 23:59．締切を過ぎても2020年7月末までは6割を上限に採点する．