Exercise 2.2に関しては，ArrayStackを使ったMyRandomQueue.h を示します．
#include <cstdlib>
#include <random>
#include <tuple>
#include <algorithm>
#include "ArrayStack.h"
template<class T>
class MyRandomQueue {
ods::ArrayStack<T> 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);
}
};
MyRandomQueueはArrayStackを持っていて，addは後ろに付け加えるだけですが，removeは
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)のコストで実現できます．
Exercise 2.5に関しては，ArrayDequeを拡張したMyArrayDequeにrがnに小さい際には効率の悪い rotateを実装する例を示します．MyArrayDeque.h の中からincludeされているex2_5.hは，
void rotate(int r) {
int n = size();
for (int i = 0; i < r; i++) {
T v = remove(n - 1);
add(0, v);
}
}
のように，必ずr回の繰り返しをおこなう実装をしています(O(n))．rがnに近い場合はもっと効率的に動く（O(1+min{r, n - r})）ように実装できます．
動作チェックをおこなうプログラム check_ex2_5.cppを
g++ --std=c++11 -Wall -O2 -o check_ex2_5 check_ex2_5.cppでコンパイルし．
./check_ex2_5で実行してOKが出ることで，このex2_5.hが正しく動作することを確認できます．以下のように，誤ったプログラム
void rotate(int r) {
int n = size();
for (int i = 0; i < r; i++) {
T v = remove(n - 2);
add(0, v);
}
}
を実行すると，
NG as=[98, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 99] as.rotate(1) : output: [98, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 99] expected: [99, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98]のように，間違いを検出してくれます(このチェックプログラムで検出できない間違いもあります)．
締切は，5/29(日) 23:59．締切を過ぎても2022年7月末までは6割を上限に採点する．