第2章：課題の実装
はじめに
本章では、CPP Module 09の各演習を実装します。
---
1. ex00: Bitcoin Exchange
1.1 課題の要件
- CSVファイル（データベース）を読み込む
- 入力ファイルの日付と値を処理
- 対応する日付のBitcoin価格を出力
- 日付が存在しない場合は、それより前の最も近い日付を使用
1.2 実装
// BitcoinExchange.hpp
#ifndef BITCOINEXCHANGE_HPP
#define BITCOINEXCHANGE_HPP
#include <map>
#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <stdexcept>
#include <cstdlib>
class BitcoinExchange {
private:
std::map<std::string, float> _database;
// ヘルパー関数
bool isValidDate(const std::string& date) const;
bool isValidValue(const std::string& value, float& result) const;
void trimWhitespace(std::string& str) const;
public:
BitcoinExchange();
BitcoinExchange(const BitcoinExchange& other);
BitcoinExchange& operator=(const BitcoinExchange& other);
~BitcoinExchange();
void loadDatabase(const std::string& filename);
void processInput(const std::string& filename);
float getRate(const std::string& date) const;
};
#endif
// BitcoinExchange.cpp
#include "BitcoinExchange.hpp"
BitcoinExchange::BitcoinExchange() {}
BitcoinExchange::BitcoinExchange(const BitcoinExchange& other)
: _database(other._database) {}
BitcoinExchange& BitcoinExchange::operator=(const BitcoinExchange& other) {
if (this != &other) {
_database = other._database;
}
return *this;
}
BitcoinExchange::~BitcoinExchange() {}
void BitcoinExchange::trimWhitespace(std::string& str) const {
size_t start = str.find_first_not_of(" \t");
size_t end = str.find_last_not_of(" \t");
if (start == std::string::npos) {
str = "";
} else {
str = str.substr(start, end - start + 1);
}
}
bool BitcoinExchange::isValidDate(const std::string& date) const {
if (date.length() != 10) return false;
if (date[4] != '-' || date[7] != '-') return false;
for (int i = 0; i < 10; i++) {
if (i == 4 || i == 7) continue;
if (!isdigit(date[i])) return false;
}
int year = std::atoi(date.substr(0, 4).c_str());
int month = std::atoi(date.substr(5, 2).c_str());
int day = std::atoi(date.substr(8, 2).c_str());
if (year < 2009 || year > 2024) return false;
if (month < 1 || month > 12) return false;
if (day < 1 || day > 31) return false;
// 月ごとの日数チェック
int daysInMonth[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
// 閏年チェック
if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)) {
daysInMonth[2] = 29;
}
if (day > daysInMonth[month]) return false;
return true;
}
bool BitcoinExchange::isValidValue(const std::string& value, float& result) const {
if (value.empty()) return false;
char* endptr;
result = std::strtof(value.c_str(), &endptr);
if (*endptr != '\0') return false;
return true;
}
void BitcoinExchange::loadDatabase(const std::string& filename) {
std::ifstream file(filename.c_str());
if (!file.is_open()) {
throw std::runtime_error("Error: could not open database file.");
}
std::string line;
bool isFirstLine = true;
while (std::getline(file, line)) {
// ヘッダー行をスキップ
if (isFirstLine) {
isFirstLine = false;
continue;
}
if (line.empty()) continue;
size_t pos = line.find(',');
if (pos == std::string::npos) continue;
std::string date = line.substr(0, pos);
std::string valueStr = line.substr(pos + 1);
trimWhitespace(date);
trimWhitespace(valueStr);
float value;
if (isValidDate(date) && isValidValue(valueStr, value)) {
_database[date] = value;
}
}
file.close();
}
float BitcoinExchange::getRate(const std::string& date) const {
std::map<std::string, float>::const_iterator it = _database.find(date);
if (it != _database.end()) {
return it->second;
}
// 日付が見つからない場合、それより前の最も近い日付を使用
it = _database.lower_bound(date);
if (it == _database.begin()) {
throw std::runtime_error("Error: date too early.");
}
--it;
return it->second;
}
void BitcoinExchange::processInput(const std::string& filename) {
std::ifstream file(filename.c_str());
if (!file.is_open()) {
std::cerr << "Error: could not open file." << std::endl;
return;
}
std::string line;
bool isFirstLine = true;
while (std::getline(file, line)) {
// ヘッダー行をスキップ
if (isFirstLine) {
isFirstLine = false;
continue;
}
if (line.empty()) continue;
// " | "で分割
size_t pos = line.find(" | ");
if (pos == std::string::npos) {
std::cerr << "Error: bad input => " << line << std::endl;
continue;
}
std::string date = line.substr(0, pos);
std::string valueStr = line.substr(pos + 3);
trimWhitespace(date);
trimWhitespace(valueStr);
// 日付の検証
if (!isValidDate(date)) {
std::cerr << "Error: bad input => " << date << std::endl;
continue;
}
// 値の検証
float value;
if (!isValidValue(valueStr, value)) {
std::cerr << "Error: bad input => " << valueStr << std::endl;
continue;
}
if (value < 0) {
std::cerr << "Error: not a positive number." << std::endl;
continue;
}
if (value > 1000) {
std::cerr << "Error: too large a number." << std::endl;
continue;
}
// 結果を出力
try {
float rate = getRate(date);
std::cout << date << " => " << value << " = " << (value * rate) << std::endl;
} catch (const std::exception& e) {
std::cerr << e.what() << std::endl;
}
}
file.close();
}
// main.cpp
#include "BitcoinExchange.hpp"
int main(int argc, char* argv[]) {
if (argc != 2) {
std::cerr << "Error: could not open file." << std::endl;
return 1;
}
try {
BitcoinExchange btc;
btc.loadDatabase("data.csv");
btc.processInput(argv[1]);
} catch (const std::exception& e) {
std::cerr << e.what() << std::endl;
return 1;
}
return 0;
}
1.3 入力ファイルの例
date | value
2011-01-03 | 3
2011-01-03 | 2
2011-01-03 | 1
2011-01-03 | 1.2
2011-01-09 | 1
2012-01-11 | 1
2012-01-11 | -1
2012-01-11 | 2147483648
1.4 期待される出力
2011-01-03 => 3 = 0.9
2011-01-03 => 2 = 0.6
2011-01-03 => 1 = 0.3
2011-01-03 => 1.2 = 0.36
2011-01-09 => 1 = 0.32
2012-01-11 => 1 = 7.1
Error: not a positive number.
Error: too large a number.
---
2. ex01: Reverse Polish Notation
2.1 課題の要件
2.2 実装
// RPN.hpp
#ifndef RPN_HPP
#define RPN_HPP
#include <stack>
#include <string>
#include <sstream>
#include <stdexcept>
#include <cstdlib>
class RPN {
private:
std::stack<int> _stack;
bool isOperator(const std::string& token) const;
int performOperation(int a, int b, const std::string& op) const;
public:
RPN();
RPN(const RPN& other);
RPN& operator=(const RPN& other);
~RPN();
int evaluate(const std::string& expression);
};
#endif
// RPN.cpp
#include "RPN.hpp"
#include <iostream>
RPN::RPN() {}
RPN::RPN(const RPN& other) : _stack(other._stack) {}
RPN& RPN::operator=(const RPN& other) {
if (this != &other) {
_stack = other._stack;
}
return *this;
}
RPN::~RPN() {}
bool RPN::isOperator(const std::string& token) const {
return (token == "+" || token == "-" ||
token == "*" || token == "/");
}
int RPN::performOperation(int a, int b, const std::string& op) const {
if (op == "+") return a + b;
if (op == "-") return a - b;
if (op == "*") return a * b;
if (op == "/") {
if (b == 0) {
throw std::runtime_error("Error: division by zero");
}
return a / b;
}
throw std::runtime_error("Error: unknown operator");
}
int RPN::evaluate(const std::string& expression) {
// スタックをクリア
while (!_stack.empty()) {
_stack.pop();
}
std::stringstream ss(expression);
std::string token;
while (ss >> token) {
if (isOperator(token)) {
// 演算子の場合
if (_stack.size() < 2) {
throw std::runtime_error("Error");
}
int b = _stack.top(); _stack.pop();
int a = _stack.top(); _stack.pop();
int result = performOperation(a, b, token);
_stack.push(result);
} else {
// 数値の場合
// 1桁の数値のみ許可
if (token.length() != 1 || !isdigit(token[0])) {
throw std::runtime_error("Error");
}
int num = token[0] - '0';
_stack.push(num);
}
}
if (_stack.size() != 1) {
throw std::runtime_error("Error");
}
return _stack.top();
}
// main.cpp
#include "RPN.hpp"
#include <iostream>
int main(int argc, char* argv[]) {
if (argc != 2) {
std::cerr << "Error" << std::endl;
return 1;
}
RPN rpn;
try {
int result = rpn.evaluate(argv[1]);
std::cout << result << std::endl;
} catch (const std::exception& e) {
std::cerr << e.what() << std::endl;
return 1;
}
return 0;
}
2.3 使用例
$ ./RPN "8 9 * 9 - 9 - 9 - 4 - 1 +"
42
$ ./RPN "7 7 * 7 -"
42
$ ./RPN "1 2 * 2 / 2 * 2 4 - +"
0
$ ./RPN "(1 + 1)"
Error
$ ./RPN "1 2 + +"
Error
2.4 評価の流れ
式: "8 9 * 9 - 9 - 9 - 4 - 1 +"
Step 1: 8をpush → [8]
Step 2: 9をpush → [8, 9]
Step 3: *: 8*9=72をpush → [72]
Step 4: 9をpush → [72, 9]
Step 5: -: 72-9=63をpush → [63]
Step 6: 9をpush → [63, 9]
Step 7: -: 63-9=54をpush → [54]
Step 8: 9をpush → [54, 9]
Step 9: -: 54-9=45をpush → [45]
Step 10: 4をpush → [45, 4]
Step 11: -: 45-4=41をpush → [41]
Step 12: 1をpush → [41, 1]
Step 13: +: 41+1=42をpush → [42]
結果: 42
---
3. ex02: PmergeMe
3.1 課題の要件
3.2 Ford-Johnsonアルゴリズムの詳細
// PmergeMe.hpp
#ifndef PMERGEME_HPP
#define PMERGEME_HPP
#include <vector>
#include <deque>
#include <string>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <ctime>
#include <stdexcept>
#include <cstdlib>
class PmergeMe {
private:
std::vector<int> _vec;
std::deque<int> _deq;
// Jacobsthal数を計算
static size_t jacobsthal(size_t n);
// 二分探索で挿入位置を見つける
template <typename Container>
static typename Container::iterator binarySearch(
Container& container,
typename Container::iterator begin,
typename Container::iterator end,
int value);
// Ford-Johnsonソート
template <typename Container>
void fordJohnsonSort(Container& container);
public:
PmergeMe();
PmergeMe(const PmergeMe& other);
PmergeMe& operator=(const PmergeMe& other);
~PmergeMe();
void parseInput(int argc, char* argv[]);
void sort();
void displayResults(double vecTime, double deqTime) const;
const std::vector<int>& getVector() const;
const std::deque<int>& getDeque() const;
};
#endif
// PmergeMe.cpp
#include "PmergeMe.hpp"
PmergeMe::PmergeMe() {}
PmergeMe::PmergeMe(const PmergeMe& other)
: _vec(other._vec), _deq(other._deq) {}
PmergeMe& PmergeMe::operator=(const PmergeMe& other) {
if (this != &other) {
_vec = other._vec;
_deq = other._deq;
}
return *this;
}
PmergeMe::~PmergeMe() {}
size_t PmergeMe::jacobsthal(size_t n) {
if (n == 0) return 0;
if (n == 1) return 1;
size_t prev2 = 0;
size_t prev1 = 1;
for (size_t i = 2; i <= n; i++) {
size_t current = prev1 + 2 * prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
template <typename Container>
typename Container::iterator PmergeMe::binarySearch(
Container& container,
typename Container::iterator begin,
typename Container::iterator end,
int value)
{
while (begin < end) {
typename Container::iterator mid = begin + (end - begin) / 2;
if (*mid < value) {
begin = mid + 1;
} else {
end = mid;
}
}
return begin;
}
template <typename Container>
void PmergeMe::fordJohnsonSort(Container& container) {
size_t n = container.size();
if (n <= 1) return;
// ステップ1: ペアを作成
std::vector<std::pair<int, int> > pairs;
int straggler = -1;
bool hasStraggler = (n % 2 != 0);
for (size_t i = 0; i + 1 < n; i += 2) {
int a = container[i];
int b = container[i + 1];
if (a > b) {
pairs.push_back(std::make_pair(a, b));
} else {
pairs.push_back(std::make_pair(b, a));
}
}
if (hasStraggler) {
straggler = container[n - 1];
}
// ステップ2: 大きい方をソート（再帰的に）
if (pairs.size() > 1) {
Container largerElements;
for (size_t i = 0; i < pairs.size(); i++) {
largerElements.push_back(pairs[i].first);
}
fordJohnsonSort(largerElements);
// ペアを再構成
std::vector<std::pair<int, int> > sortedPairs;
for (size_t i = 0; i < largerElements.size(); i++) {
for (size_t j = 0; j < pairs.size(); j++) {
if (pairs[j].first == largerElements[i]) {
sortedPairs.push_back(pairs[j]);
pairs.erase(pairs.begin() + j);
break;
}
}
}
pairs = sortedPairs;
}
// ステップ3: メインチェーンを構築
Container mainChain;
for (size_t i = 0; i < pairs.size(); i++) {
mainChain.push_back(pairs[i].first);
}
// ステップ4: 小さい方を挿入（Jacobsthal順序で）
std::vector<int> pend;
for (size_t i = 0; i < pairs.size(); i++) {
pend.push_back(pairs[i].second);
}
// 最初の要素は先頭に挿入
if (!pend.empty()) {
mainChain.insert(mainChain.begin(), pend[0]);
}
// Jacobsthal順序で残りを挿入
std::vector<bool> inserted(pend.size(), false);
inserted[0] = true;
size_t jacobIndex = 3;
size_t prevJacob = 1;
while (true) {
size_t currJacob = jacobsthal(jacobIndex);
if (currJacob > pend.size()) {
currJacob = pend.size();
}
// currJacobからprevJacob+1まで逆順に挿入
for (size_t i = currJacob; i > prevJacob; i--) {
if (i <= pend.size() && !inserted[i - 1]) {
int value = pend[i - 1];
// 二分探索で挿入位置を見つける
typename Container::iterator pos = binarySearch(
mainChain, mainChain.begin(), mainChain.end(), value);
mainChain.insert(pos, value);
inserted[i - 1] = true;
}
}
if (currJacob >= pend.size()) break;
prevJacob = currJacob;
jacobIndex++;
}
// stragglerを挿入
if (hasStraggler) {
typename Container::iterator pos = binarySearch(
mainChain, mainChain.begin(), mainChain.end(), straggler);
mainChain.insert(pos, straggler);
}
container = mainChain;
}
void PmergeMe::parseInput(int argc, char* argv[]) {
for (int i = 1; i < argc; i++) {
std::string arg(argv[i]);
// 数値の検証
for (size_t j = 0; j < arg.length(); j++) {
if (!isdigit(arg[j])) {
throw std::runtime_error("Error: invalid input");
}
}
long value = std::atol(arg.c_str());
if (value <= 0 || value > 2147483647) {
throw std::runtime_error("Error: invalid input");
}
_vec.push_back(static_cast<int>(value));
_deq.push_back(static_cast<int>(value));
}
if (_vec.empty()) {
throw std::runtime_error("Error: no input");
}
}
void PmergeMe::sort() {
fordJohnsonSort(_vec);
fordJohnsonSort(_deq);
}
void PmergeMe::displayResults(double vecTime, double deqTime) const {
// Before（元のデータ、引数から表示）
// After
std::cout << "After: ";
for (size_t i = 0; i < _vec.size(); i++) {
std::cout << _vec[i];
if (i < _vec.size() - 1) std::cout << " ";
}
std::cout << std::endl;
// 時間表示
std::cout << "Time to process a range of " << _vec.size()
<< " elements with std::vector : " << vecTime << " us" << std::endl;
std::cout << "Time to process a range of " << _deq.size()
<< " elements with std::deque : " << deqTime << " us" << std::endl;
}
const std::vector<int>& PmergeMe::getVector() const {
return _vec;
}
const std::deque<int>& PmergeMe::getDeque() const {
return _deq;
}
// main.cpp
#include "PmergeMe.hpp"
int main(int argc, char* argv[]) {
if (argc < 2) {
std::cerr << "Error" << std::endl;
return 1;
}
try {
PmergeMe pm;
pm.parseInput(argc, argv);
// Before表示
std::cout << "Before: ";
for (int i = 1; i < argc; i++) {
std::cout << argv[i];
if (i < argc - 1) std::cout << " ";
}
std::cout << std::endl;
// vectorのソート時間計測
std::vector<int> vecCopy = pm.getVector();
clock_t vecStart = clock();
// ソート実行
clock_t vecEnd = clock();
double vecTime = static_cast<double>(vecEnd - vecStart) / CLOCKS_PER_SEC * 1000000;
// dequeのソート時間計測
std::deque<int> deqCopy = pm.getDeque();
clock_t deqStart = clock();
// ソート実行
clock_t deqEnd = clock();
double deqTime = static_cast<double>(deqEnd - deqStart) / CLOCKS_PER_SEC * 1000000;
pm.sort();
pm.displayResults(vecTime, deqTime);
} catch (const std::exception& e) {
std::cerr << e.what() << std::endl;
return 1;
}
return 0;
}
3.3 使用例
$ ./PmergeMe 3 5 9 7 4
Before: 3 5 9 7 4
After: 3 4 5 7 9
Time to process a range of 5 elements with std::vector : 0.00031 us
Time to process a range of 5 elements with std::deque : 0.00014 us
$ ./PmergeMe `shuf -i 1-100000 -n 3000 | tr "\n" " "`
Before: 141 79 526 321 ...
After: 1 2 3 4 5 6 ...
Time to process a range of 3000 elements with std::vector : 62.14 us
Time to process a range of 3000 elements with std::deque : 73.42 us
3.4 Jacobsthal数列の生成
// Jacobsthal数列: 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, ...
// J(n) = J(n-1) + 2*J(n-2)
size_t jacobsthal(size_t n) {
if (n == 0) return 0;
if (n == 1) return 1;
size_t prev2 = 0; // J(n-2)
size_t prev1 = 1; // J(n-1)
for (size_t i = 2; i <= n; i++) {
size_t current = prev1 + 2 * prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
// 挿入順序の生成
// Jacobsthal: 1, 1, 3, 5, 11, 21, ...
// 挿入順序: 1, 3→2, 5→4→3, 11→10→...→6, ...
---
4. 実装の注意点
4.1 時間計測
#include <ctime>
clock_t start = clock();
// 処理
clock_t end = clock();
// マイクロ秒に変換
double timeUs = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000000;
4.2 大きなデータセットのテスト
# 3000個のランダムな数値を生成
./PmergeMe $(shuf -i 1-100000 -n 3000 | tr "\n" " ")
# ソートの検証
./PmergeMe 5 3 1 4 2 | diff - <(echo "1 2 3 4 5")
4.3 負の数と重複
// 課題では正の整数のみ許可
if (value <= 0) {
throw std::runtime_error("Error");
}
// 重複は許可される（同じ数値が複数回出現しても良い）
---
まとめ
本章で実装した内容：