第2章：課題の実装
はじめに
本章では、CPP Module 08の各演習を実装します。
---
1. ex00: Easy find
1.1 課題の要件
- 関数テンプレート
easyfindを実装 - 第1引数: 整数型のコンテナ
- 第2引数: 検索する整数
- 見つかったらその位置のイテレータを返す
- 見つからなければ例外を投げる
1.2 実装
// easyfind.hpp
#ifndef EASYFIND_HPP
#define EASYFIND_HPP
#include <algorithm>
#include <exception>
class NotFoundException : public std::exception {
public:
const char* what() const throw() {
return "Element not found in container";
}
};
template <typename T>
typename T::iterator easyfind(T& container, int value) {
typename T::iterator it = std::find(container.begin(), container.end(), value);
if (it == container.end()) {
throw NotFoundException();
}
return it;
}
// const版
template <typename T>
typename T::const_iterator easyfind(const T& container, int value) {
typename T::const_iterator it = std::find(container.begin(), container.end(), value);
if (it == container.end()) {
throw NotFoundException();
}
return it;
}
#endif
// main.cpp
#include "easyfind.hpp"
#include <iostream>
#include <vector>
#include <list>
#include <deque>
int main() {
std::cout << "=== Vector Test ===" << std::endl;
std::vector<int> vec;
for (int i = 0; i < 10; i++) {
vec.push_back(i * 2);
}
try {
std::vector<int>::iterator it = easyfind(vec, 6);
std::cout << "Found: " << *it << std::endl;
std::cout << "Position: " << std::distance(vec.begin(), it) << std::endl;
} catch (const std::exception& e) {
std::cout << e.what() << std::endl;
}
try {
easyfind(vec, 7);
} catch (const std::exception& e) {
std::cout << "7 not found: " << e.what() << std::endl;
}
std::cout << "\n=== List Test ===" << std::endl;
std::list<int> lst;
for (int i = 0; i < 5; i++) {
lst.push_back(i * 10);
}
try {
std::list<int>::iterator it = easyfind(lst, 30);
std::cout << "Found: " << *it << std::endl;
} catch (const std::exception& e) {
std::cout << e.what() << std::endl;
}
std::cout << "\n=== Deque Test ===" << std::endl;
std::deque<int> deq;
deq.push_back(100);
deq.push_back(200);
deq.push_back(300);
try {
std::deque<int>::iterator it = easyfind(deq, 200);
std::cout << "Found: " << *it << std::endl;
} catch (const std::exception& e) {
std::cout << e.what() << std::endl;
}
return 0;
}
1.3 期待される出力
=== Vector Test ===
Found: 6
Position: 3
7 not found: Element not found in container
=== List Test ===
Found: 30
=== Deque Test ===
Found: 200
1.4 なぜtypenameが必要か
template <typename T>
typename T::iterator easyfind(T& container, int value) {
// ...
}
T::iteratorは依存名（dependent name）です。コンパイラはTが何であるかを知らないため、T::iteratorが型なのか静的メンバなのか判断できません。
// Tが何であるかによって解釈が変わる
T::iterator * x; // 型なら: iterator型のポインタxを宣言
// 静的メンバなら: iterator * x の乗算
typenameキーワードは、これが型であることをコンパイラに伝えます。
---
2. ex01: Span
2.1 課題の要件
Spanを実装addNumber: 1つの数を追加shortestSpan: 最小の差を返すlongestSpan: 最大の差を返す2.2 実装
// Span.hpp
#ifndef SPAN_HPP
#define SPAN_HPP
#include <vector>
#include <algorithm>
#include <exception>
#include <limits>
class Span {
private:
std::vector<int> _numbers;
unsigned int _capacity;
public:
// コンストラクタ
Span();
Span(unsigned int n);
Span(const Span& other);
Span& operator=(const Span& other);
~Span();
// メンバ関数
void addNumber(int number);
template <typename Iterator>
void addNumbers(Iterator begin, Iterator end) {
size_t distance = std::distance(begin, end);
if (_numbers.size() + distance > _capacity) {
throw CapacityExceededException();
}
_numbers.insert(_numbers.end(), begin, end);
}
int shortestSpan() const;
int longestSpan() const;
// ゲッター
unsigned int size() const;
unsigned int capacity() const;
// 例外クラス
class CapacityExceededException : public std::exception {
public:
const char* what() const throw() {
return "Span capacity exceeded";
}
};
class NotEnoughElementsException : public std::exception {
public:
const char* what() const throw() {
return "Not enough elements to calculate span";
}
};
};
#endif
// Span.cpp
#include "Span.hpp"
Span::Span() : _capacity(0) {}
Span::Span(unsigned int n) : _capacity(n) {
_numbers.reserve(n);
}
Span::Span(const Span& other)
: _numbers(other._numbers), _capacity(other._capacity) {}
Span& Span::operator=(const Span& other) {
if (this != &other) {
_numbers = other._numbers;
_capacity = other._capacity;
}
return *this;
}
Span::~Span() {}
void Span::addNumber(int number) {
if (_numbers.size() >= _capacity) {
throw CapacityExceededException();
}
_numbers.push_back(number);
}
int Span::shortestSpan() const {
if (_numbers.size() < 2) {
throw NotEnoughElementsException();
}
// ソートしたコピーを作成
std::vector<int> sorted = _numbers;
std::sort(sorted.begin(), sorted.end());
// 隣接要素の差の最小値を求める
int minSpan = std::numeric_limits<int>::max();
for (size_t i = 1; i < sorted.size(); i++) {
int diff = sorted[i] - sorted[i - 1];
if (diff < minSpan) {
minSpan = diff;
}
}
return minSpan;
}
int Span::longestSpan() const {
if (_numbers.size() < 2) {
throw NotEnoughElementsException();
}
// 最小値と最大値の差
std::vector<int>::const_iterator minIt = std::min_element(_numbers.begin(), _numbers.end());
std::vector<int>::const_iterator maxIt = std::max_element(_numbers.begin(), _numbers.end());
return *maxIt - *minIt;
}
unsigned int Span::size() const {
return _numbers.size();
}
unsigned int Span::capacity() const {
return _capacity;
}
// main.cpp
#include "Span.hpp"
#include <iostream>
#include <cstdlib>
#include <ctime>
int main() {
std::cout << "=== Basic Test ===" << std::endl;
Span sp = Span(5);
sp.addNumber(6);
sp.addNumber(3);
sp.addNumber(17);
sp.addNumber(9);
sp.addNumber(11);
std::cout << "Shortest span: " << sp.shortestSpan() << std::endl;
std::cout << "Longest span: " << sp.longestSpan() << std::endl;
std::cout << "\n=== Large Test (10000 elements) ===" << std::endl;
Span bigSpan(10000);
std::srand(std::time(NULL));
for (int i = 0; i < 10000; i++) {
bigSpan.addNumber(std::rand());
}
std::cout << "Shortest span: " << bigSpan.shortestSpan() << std::endl;
std::cout << "Longest span: " << bigSpan.longestSpan() << std::endl;
std::cout << "\n=== Range Insert Test ===" << std::endl;
Span rangeSpan(100);
std::vector<int> nums;
for (int i = 0; i < 50; i++) {
nums.push_back(i * 2);
}
rangeSpan.addNumbers(nums.begin(), nums.end());
std::cout << "Size after range insert: " << rangeSpan.size() << std::endl;
std::cout << "Shortest span: " << rangeSpan.shortestSpan() << std::endl;
std::cout << "Longest span: " << rangeSpan.longestSpan() << std::endl;
std::cout << "\n=== Exception Test ===" << std::endl;
// 容量超過
try {
Span smallSpan(2);
smallSpan.addNumber(1);
smallSpan.addNumber(2);
smallSpan.addNumber(3); // 例外
} catch (const std::exception& e) {
std::cout << "Capacity exception: " << e.what() << std::endl;
}
// 要素不足
try {
Span emptySpan(5);
emptySpan.addNumber(1);
emptySpan.shortestSpan(); // 例外
} catch (const std::exception& e) {
std::cout << "Not enough elements: " << e.what() << std::endl;
}
return 0;
}
2.3 期待される出力
=== Basic Test ===
Shortest span: 2
Longest span: 14
=== Large Test (10000 elements) ===
Shortest span: 0
Longest span: 2147483647
=== Range Insert Test ===
Size after range insert: 50
Shortest span: 2
Longest span: 98
=== Exception Test ===
Capacity exception: Span capacity exceeded
Not enough elements: Not enough elements to calculate span
2.4 効率的なshortestSpanの計算
ソートを使用する理由：
// 非効率: O(n^2)
int shortestSpan() const {
int minSpan = INT_MAX;
for (size_t i = 0; i < _numbers.size(); i++) {
for (size_t j = i + 1; j < _numbers.size(); j++) {
int diff = std::abs(_numbers[i] - _numbers[j]);
minSpan = std::min(minSpan, diff);
}
}
return minSpan;
}
// 効率的: O(n log n)
int shortestSpan() const {
std::vector<int> sorted = _numbers;
std::sort(sorted.begin(), sorted.end()); // O(n log n)
int minSpan = INT_MAX;
for (size_t i = 1; i < sorted.size(); i++) {
minSpan = std::min(minSpan, sorted[i] - sorted[i-1]);
}
return minSpan;
}
ソート後は隣接要素のみを比較すればよいため、O(n)で最小差を見つけられます。
---
3. ex02: Mutated abomination
3.1 課題の要件
std::stackをイテレート可能にするMutantStackクラスを実装std::stackのすべての機能を維持3.2 std::stackの内部構造
// std::stackの定義（簡略化）
template <typename T, typename Container = std::deque<T>>
class stack {
protected:
Container c; // 内部コンテナ
public:
void push(const T& value) { c.push_back(value); }
void pop() { c.pop_back(); }
T& top() { return c.back(); }
bool empty() const { return c.empty(); }
size_t size() const { return c.size(); }
};
std::stackはアダプタパターンで実装されています。内部コンテナcはprotectedメンバなので、派生クラスからアクセス可能です。
3.3 実装
// MutantStack.hpp
#ifndef MUTANTSTACK_HPP
#define MUTANTSTACK_HPP
#include <stack>
template <typename T>
class MutantStack : public std::stack<T> {
public:
// コンストラクタ・デストラクタ
MutantStack() : std::stack<T>() {}
MutantStack(const MutantStack& other) : std::stack<T>(other) {}
MutantStack& operator=(const MutantStack& other) {
if (this != &other) {
std::stack<T>::operator=(other);
}
return *this;
}
~MutantStack() {}
// イテレータ型の定義
typedef typename std::stack<T>::container_type::iterator iterator;
typedef typename std::stack<T>::container_type::const_iterator const_iterator;
typedef typename std::stack<T>::container_type::reverse_iterator reverse_iterator;
typedef typename std::stack<T>::container_type::const_reverse_iterator const_reverse_iterator;
// イテレータ取得
iterator begin() { return this->c.begin(); }
iterator end() { return this->c.end(); }
const_iterator begin() const { return this->c.begin(); }
const_iterator end() const { return this->c.end(); }
reverse_iterator rbegin() { return this->c.rbegin(); }
reverse_iterator rend() { return this->c.rend(); }
const_reverse_iterator rbegin() const { return this->c.rbegin(); }
const_reverse_iterator rend() const { return this->c.rend(); }
};
#endif
// main.cpp
#include "MutantStack.hpp"
#include <iostream>
#include <list>
int main() {
std::cout << "=== MutantStack Test ===" << std::endl;
MutantStack<int> mstack;
mstack.push(5);
mstack.push(17);
std::cout << "Top: " << mstack.top() << std::endl;
mstack.pop();
std::cout << "Size: " << mstack.size() << std::endl;
mstack.push(3);
mstack.push(5);
mstack.push(737);
mstack.push(0);
std::cout << "\n=== Iterator Test ===" << std::endl;
MutantStack<int>::iterator it = mstack.begin();
MutantStack<int>::iterator ite = mstack.end();
++it;
--it;
std::cout << "Elements: ";
while (it != ite) {
std::cout << *it << " ";
++it;
}
std::cout << std::endl;
std::cout << "\n=== Reverse Iterator Test ===" << std::endl;
std::cout << "Reverse: ";
for (MutantStack<int>::reverse_iterator rit = mstack.rbegin();
rit != mstack.rend(); ++rit) {
std::cout << *rit << " ";
}
std::cout << std::endl;
std::cout << "\n=== Copy Test ===" << std::endl;
MutantStack<int> copy(mstack);
std::cout << "Copy top: " << copy.top() << std::endl;
std::cout << "Copy size: " << copy.size() << std::endl;
std::cout << "\n=== std::stack compatibility ===" << std::endl;
std::stack<int> s(mstack);
std::cout << "std::stack top: " << s.top() << std::endl;
return 0;
}
3.4 期待される出力
=== MutantStack Test ===
Top: 17
Size: 1
=== Iterator Test ===
Elements: 5 3 5 737 0
=== Reverse Iterator Test ===
Reverse: 0 737 5 3 5
=== Copy Test ===
Copy top: 0
Copy size: 5
=== std::stack compatibility ===
std::stack top: 0
3.5 std::listとの比較
課題では、std::listと同じ動作をすることを確認します：
// MutantStack版
MutantStack<int> mstack;
mstack.push(5);
mstack.push(17);
// ...
for (auto it = mstack.begin(); it != mstack.end(); ++it) {
std::cout << *it << " ";
}
// std::list版
std::list<int> lst;
lst.push_back(5);
lst.push_back(17);
// ...
for (auto it = lst.begin(); it != lst.end(); ++it) {
std::cout << *it << " ";
}
出力は同じになるべきです。
3.6 なぜthis->cが必要か
iterator begin() { return this->c.begin(); }
テンプレートクラスで基底クラスのメンバにアクセスする場合、this->を使わないと依存名として認識されません。
// エラーになる可能性
iterator begin() { return c.begin(); } // cが見つからない
// 正しい
iterator begin() { return this->c.begin(); } // this経由でアクセス
---
4. 実装の注意点
4.1 イテレータの無効化
// 危険なコード
std::vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.begin(); it != vec.end(); ++it) {
if (*it == 3) {
vec.erase(it); // イテレータが無効化される
}
}
// 安全なコード
for (auto it = vec.begin(); it != vec.end(); ) {
if (*it == 3) {
it = vec.erase(it); // 次の有効なイテレータを取得
} else {
++it;
}
}
4.2 constの正しい使用
// 読み取り専用の場合はconst版を使用
template <typename T>
typename T::const_iterator easyfind(const T& container, int value) {
return std::find(container.begin(), container.end(), value);
}
// Spanのアクセサはconst
int Span::shortestSpan() const {
// _numbersを変更しない
}
4.3 例外安全性
void Span::addNumber(int number) {
// 事前条件のチェック
if (_numbers.size() >= _capacity) {
throw CapacityExceededException();
}
// 条件を満たしてから変更
_numbers.push_back(number);
}
---
まとめ
本章で実装した内容：