mkdir ~/mis2を実行する． http://opendatastructures.orgのc++ edition, c++ sources ( C++ sources(講義独自版) ) からダウンロードしたファイルをホームフォルダの下のmis2に置く．ods.cpp.tgzというファイルができた時は，
cd ~/mis2 tar zxvf ods-cpp.tgzods-cpp.tarというファイルができた時は，
cd ~/mis2 tar xvf ods-cpp.tarを実行するとcppというフォルダができる．Finderからダブルクリックしてもアーカイブユーティリティが立ち上がり展開されるので，そちらでも良い．
#include "array.h"
#include <iostream>
int main(){
int n;
std::cin >> n;
ods::array<int> a(n);
for (int i = 0; i < n; i++){
a[i] = i * i;
}
for (int m; std::cin >> m && m > 0;){
if (m < n){
std::cout << a[m] << std::endl;
}
}
return 0;
}
これは，最初に入力した大きさの配列aを作り，n番目の中身をn*nで埋め，その後，
入力されたmが正の間，aのm番目の要素を返すだけのプログラムである．
これを，
cd ~/mis2/cpp g++ -o arrayTest -O3 arrayTest.cpp array.cppでコンパイルし，
./arrayTestで実行
100 2 5 88 0のような入力を与えて実行してみる．
5 3 10 -1 2
./arrayTest < array.in > array.outのように，出力もファイルに入れると入力と出力を区別しやすい
void add(int i, T x) {
if (n + 1 > a.length) resize();
for (int j = i; j < n; j++)
a[j + 1] = a[j];
a[i] = x;
n++;
}
if (a.length >= 3 * n) resize();remove()のプログラムの上の行を削除して，remove()ではshrinkしないことにした時に，空のArrayStackからm回のadd, removeを任意の順序で実行した時のresizeの総実行時間は?
#include "ArrayStack.h"
#include <iostream>
int main(){
int n = 100;
ods::ArrayStack<int> as;
std::cerr << "making as" << std::endl;
for (int i = 0; i < n; i++){
as.add(i, i);
}
std::cerr << "adding as done" << std::endl;
as.set(88, 199);
as.add(87, 133);
std::cout << as.remove(98) << std::endl;
for (int i = 0; i < 80; i++){
std::cout << "removed = " << as.remove(0) << std::endl;
}
for (int i = 0; i < as.size(); i++){
std::cout << "as.get(" << i << ")=" << as.get(i) << std::endl;
}
return 0;
}
cd ~/mis2/cpp g++ -o arrayStackTest -O3 arrayStackTest.cpp ArrayStack.cppでコンパイルし，
./arrayStackTestで実行
cd ~/mis2/cpp g++ -o arrayStackSpeed -O3 arrayStackSpeed.cppでコンパイルし，
./arrayStackSpeedで実行する．プログラム中のnの値を1000, 10000 に変更してからコンパイル実行してみる．
cd ~/mis2/cpp g++ -o fastArrayStackTest -O3 fastArrayStackTest.cppでコンパイルし，
./fastArrayStackTestで実行する．
cd ~/mis2/cpp g++ -o fastArrayStackSpeed -O3 fastArrayStackSpeed.cppでコンパイルし，
./fastArrayStackSpeedで実行する．プログラム中のnの値を10000 に変更してからコンパイル実行してみる．
#include "ArrayQueue.h"
#include <iostream>
int main(){
int n = 10;
ods::ArrayQueue<int> aq;
for (int i = 0; i < n; i++){
aq.add(i);
}
for (int i = 0; i < n * 10; i++){
std::cout << aq.remove() << std::endl;
aq.add(i * i);
}
return 0;
}
cd ~/mis2/cpp g++ -o arrayQueueTest arrayQueueTest.cpp ArrayQueue.cppでコンパイルし，
./arrayQueueTestで実行する．
#include "ArrayDeque.h"
#include <iostream>
int main(){
int n = 10;
ods::ArrayDeque<int> aq;
for (int i = 0; i < n; i++){
aq.add(i, i);
}
for (int i = 0; i < n; i++){
aq.add(i, -i);
aq.remove(0);
aq.set(i, i * i);
}
for (int i = 0; i < aq.size(); i++){
std::cout << aq.get(i) << std::endl;
}
return 0;
}
cd ~/mis2/cpp g++ -o arrayDequeTest arrayDequeTest.cpp ArrayDeque.cppでコンパイルし，
./arrayDequeTestで実行する．
cd ~/mis2/cpp g++ -o dualArrayDequeTest dualArrayDequeTest.cppでコンパイルし，
./dualArrayDequeTestで実行する．
cp arrayStackTest.cpp rootishArrayStackTest.cppを実行した後，作成されたrootishArrayStackTest.cpp をエディタで編集し，
#include "ArrayStack.h" -> #include "RootishArrayStack.h" ----- ods::ArrayStack<int> as; -> ods::RootishArrayStack<int> as;の書きかえをおこない，
g++ -Wall -O3 -o rootishArrayStackTest rootishArrayStackTest.cppでコンパイル．
./rootishArrayStackTestで実行する．
次にRootishArrayStack.hの先頭に
#include <iostream>を入れ，以下の赤字の2行を加えてみる．
template<class T>
void RootishArrayStack<T>::grow() {
std::cerr << "grow() is called" << std::endl;
blocks.add(blocks.size(), new T[blocks.size()+1]);
}
template<class T>
void RootishArrayStack<T>::shrink() {
std::cerr << "shrink() is called" << std::endl;
int r = blocks.size();
while (r > 0 && (r-2)*(r-1)/2 >= n) {
delete [] blocks.remove(blocks.size()-1);
r--;
}
}