第6章：テストと最適化
はじめに
ft_containersの品質を確保するには、包括的なテストが必要です。本章では、テスト戦略とパフォーマンス最適化を学びます。
---
1. テスト戦略
1.1 テストの種類
1. 単体テスト（Unit Test）
- 各関数/メソッドの個別テスト
- 境界条件のテスト
2. 比較テスト
- std:: vs ft:: の結果を比較
- 同一の入力に対して同一の出力を確認
3. パフォーマンステスト
- 大量データでの速度測定
- メモリ使用量の確認
4. エッジケーステスト
- 空のコンテナ
- 単一要素
- 最大サイズ
1.2 テストフレームワーク
シンプルなテストマクロ：
#include <iostream>
#define ASSERT_EQ(a, b) \
do { \
if ((a) != (b)) { \
std::cerr << "FAIL: " << #a << " != " << #b << std::endl; \
std::cerr << " Got: " << (a) << " Expected: " << (b) << std::endl; \
std::cerr << " at " << __FILE__ << ":" << __LINE__ << std::endl; \
return false; \
} \
} while(0)
#define ASSERT_TRUE(x) ASSERT_EQ((x), true)
#define ASSERT_FALSE(x) ASSERT_EQ((x), false)
#define RUN_TEST(test) \
do { \
std::cout << "Running " << #test << "... "; \
if (test()) { \
std::cout << "OK" << std::endl; \
} else { \
std::cout << "FAILED" << std::endl; \
} \
} while(0)
---
2. vectorのテスト
2.1 基本操作のテスト
bool test_vector_push_pop() {
ft::vector<int> ft_v;
std::vector<int> std_v;
// push_back
for (int i = 0; i < 10; ++i) {
ft_v.push_back(i);
std_v.push_back(i);
}
ASSERT_EQ(ft_v.size(), std_v.size());
// 要素の比較
for (size_t i = 0; i < ft_v.size(); ++i) {
ASSERT_EQ(ft_v[i], std_v[i]);
}
// pop_back
while (!ft_v.empty()) {
ASSERT_EQ(ft_v.back(), std_v.back());
ft_v.pop_back();
std_v.pop_back();
}
ASSERT_TRUE(ft_v.empty());
return true;
}
bool test_vector_insert() {
ft::vector<int> ft_v;
std::vector<int> std_v;
// 先頭に挿入
for (int i = 0; i < 5; ++i) {
ft_v.insert(ft_v.begin(), i);
std_v.insert(std_v.begin(), i);
}
ASSERT_EQ(ft_v.size(), std_v.size());
for (size_t i = 0; i < ft_v.size(); ++i) {
ASSERT_EQ(ft_v[i], std_v[i]);
}
// 中間に挿入
ft_v.insert(ft_v.begin() + 2, 100);
std_v.insert(std_v.begin() + 2, 100);
ASSERT_EQ(ft_v.size(), std_v.size());
for (size_t i = 0; i < ft_v.size(); ++i) {
ASSERT_EQ(ft_v[i], std_v[i]);
}
return true;
}
2.2 イテレータのテスト
bool test_vector_iterators() {
ft::vector<int> ft_v;
for (int i = 0; i < 10; ++i) {
ft_v.push_back(i);
}
// 順方向イテレータ
int expected = 0;
for (ft::vector<int>::iterator it = ft_v.begin();
it != ft_v.end(); ++it) {
ASSERT_EQ(*it, expected++);
}
// 逆方向イテレータ
expected = 9;
for (ft::vector<int>::reverse_iterator it = ft_v.rbegin();
it != ft_v.rend(); ++it) {
ASSERT_EQ(*it, expected--);
}
// constイテレータ
const ft::vector<int>& const_v = ft_v;
expected = 0;
for (ft::vector<int>::const_iterator it = const_v.begin();
it != const_v.end(); ++it) {
ASSERT_EQ(*it, expected++);
}
return true;
}
2.3 例外のテスト
bool test_vector_exceptions() {
ft::vector<int> v;
// at() の範囲外アクセス
try {
v.at(0);
return false; // 例外が発生しなかった
} catch (const std::out_of_range&) {
// 期待通り
}
v.push_back(1);
try {
v.at(10);
return false;
} catch (const std::out_of_range&) {
// 期待通り
}
return true;
}
---
3. mapのテスト
3.1 基本操作
bool test_map_insert_find() {
ft::map<int, std::string> ft_m;
std::map<int, std::string> std_m;
// insert
ft_m.insert(ft::make_pair(1, "one"));
ft_m.insert(ft::make_pair(2, "two"));
ft_m.insert(ft::make_pair(3, "three"));
std_m.insert(std::make_pair(1, "one"));
std_m.insert(std::make_pair(2, "two"));
std_m.insert(std::make_pair(3, "three"));
ASSERT_EQ(ft_m.size(), std_m.size());
// find
ft::map<int, std::string>::iterator ft_it = ft_m.find(2);
std::map<int, std::string>::iterator std_it = std_m.find(2);
ASSERT_TRUE(ft_it != ft_m.end());
ASSERT_EQ(ft_it->second, std_it->second);
// 存在しないキー
ASSERT_TRUE(ft_m.find(100) == ft_m.end());
return true;
}
bool test_map_operator_bracket() {
ft::map<std::string, int> m;
m["apple"] = 1;
m["banana"] = 2;
m["cherry"] = 3;
ASSERT_EQ(m["apple"], 1);
ASSERT_EQ(m["banana"], 2);
ASSERT_EQ(m["cherry"], 3);
// 存在しないキーにアクセス → デフォルト値で挿入
ASSERT_EQ(m["date"], 0);
ASSERT_EQ(m.size(), (size_t)4);
return true;
}
3.2 赤黒木の性質チェック
template<typename T>
bool verify_rb_properties(const RBNode<T>* node, const RBNode<T>* nil,
int& black_height) {
if (node == nil) {
black_height = 1; // NILは黒
return true;
}
// 性質4: 赤ノードの子は黒
if (node->color == RED) {
if (node->left->color == RED || node->right->color == RED) {
std::cerr << "Red violation: red node has red child" << std::endl;
return false;
}
}
int left_bh, right_bh;
if (!verify_rb_properties(node->left, nil, left_bh) ||
!verify_rb_properties(node->right, nil, right_bh)) {
return false;
}
// 性質5: 黒高さが等しい
if (left_bh != right_bh) {
std::cerr << "Black height violation" << std::endl;
return false;
}
black_height = left_bh + (node->color == BLACK ? 1 : 0);
return true;
}
bool test_map_rb_properties() {
ft::map<int, int> m;
// ランダムな順序で挿入
int keys[] = {5, 3, 7, 1, 9, 4, 6, 8, 2, 0};
for (int i = 0; i < 10; ++i) {
m.insert(ft::make_pair(keys[i], keys[i] * 10));
// 各挿入後に赤黒木の性質を確認
// (内部構造へのアクセスが必要)
}
return true;
}
---
4. stackのテスト
bool test_stack_basic() {
ft::stack<int> ft_s;
std::stack<int> std_s;
ASSERT_TRUE(ft_s.empty());
for (int i = 0; i < 10; ++i) {
ft_s.push(i);
std_s.push(i);
}
ASSERT_EQ(ft_s.size(), std_s.size());
while (!ft_s.empty()) {
ASSERT_EQ(ft_s.top(), std_s.top());
ft_s.pop();
std_s.pop();
}
ASSERT_TRUE(ft_s.empty());
return true;
}
bool test_stack_comparison() {
ft::stack<int> s1, s2;
for (int i = 0; i < 5; ++i) {
s1.push(i);
s2.push(i);
}
ASSERT_TRUE(s1 == s2);
s1.push(5);
ASSERT_TRUE(s1 > s2);
ASSERT_TRUE(s2 < s1);
return true;
}
---
5. パフォーマンステスト
5.1 時間測定
#include <sys/time.h>
class Timer {
private:
struct timeval _start;
struct timeval _end;
public:
void start() {
gettimeofday(&_start, NULL);
}
double stop() {
gettimeofday(&_end, NULL);
return (_end.tv_sec - _start.tv_sec) * 1000.0 +
(_end.tv_usec - _start.tv_usec) / 1000.0;
}
};
void benchmark_vector() {
const int N = 100000;
Timer timer;
// ft::vector
{
ft::vector<int> v;
timer.start();
for (int i = 0; i < N; ++i) {
v.push_back(i);
}
double ft_time = timer.stop();
std::cout << "ft::vector push_back: " << ft_time << "ms" << std::endl;
}
// std::vector
{
std::vector<int> v;
timer.start();
for (int i = 0; i < N; ++i) {
v.push_back(i);
}
double std_time = timer.stop();
std::cout << "std::vector push_back: " << std_time << "ms" << std::endl;
}
}
void benchmark_map() {
const int N = 100000;
Timer timer;
// ft::map
{
ft::map<int, int> m;
timer.start();
for (int i = 0; i < N; ++i) {
m.insert(ft::make_pair(i, i));
}
double insert_time = timer.stop();
timer.start();
for (int i = 0; i < N; ++i) {
m.find(i);
}
double find_time = timer.stop();
std::cout << "ft::map insert: " << insert_time << "ms, "
<< "find: " << find_time << "ms" << std::endl;
}
// std::map
{
std::map<int, int> m;
timer.start();
for (int i = 0; i < N; ++i) {
m.insert(std::make_pair(i, i));
}
double insert_time = timer.stop();
timer.start();
for (int i = 0; i < N; ++i) {
m.find(i);
}
double find_time = timer.stop();
std::cout << "std::map insert: " << insert_time << "ms, "
<< "find: " << find_time << "ms" << std::endl;
}
}
5.2 メモリ使用量
#include <sys/resource.h>
size_t get_memory_usage() {
struct rusage usage;
getrusage(RUSAGE_SELF, &usage);
return usage.ru_maxrss; // キロバイト単位
}
void benchmark_memory() {
const int N = 100000;
size_t before = get_memory_usage();
ft::vector<int> v;
for (int i = 0; i < N; ++i) {
v.push_back(i);
}
size_t after = get_memory_usage();
std::cout << "Memory used: " << (after - before) << " KB" << std::endl;
}
---
6. 最適化テクニック
6.1 vectorの最適化
// 事前にcapacityを確保
void optimized_push_back(ft::vector<int>& v, int n) {
v.reserve(n); // 再確保を防ぐ
for (int i = 0; i < n; ++i) {
v.push_back(i);
}
}
// swap trickでメモリを解放
void shrink_to_fit(ft::vector<int>& v) {
ft::vector<int>(v).swap(v);
// 一時的なベクトルを作成し、swapする
// 一時ベクトルは現在のsizeぴったりのcapacity
}
6.2 mapの最適化
// hint付きinsert
void optimized_insert(ft::map<int, int>& m) {
ft::map<int, int>::iterator hint = m.begin();
// ソート済みデータの挿入
for (int i = 0; i < 10000; ++i) {
hint = m.insert(hint, ft::make_pair(i, i));
}
// hintが正しければO(1)、そうでなければO(log n)
}
---
7. テストメインファイル
int main() {
std::cout << "=== Vector Tests ===" << std::endl;
RUN_TEST(test_vector_push_pop);
RUN_TEST(test_vector_insert);
RUN_TEST(test_vector_iterators);
RUN_TEST(test_vector_exceptions);
std::cout << "\n=== Map Tests ===" << std::endl;
RUN_TEST(test_map_insert_find);
RUN_TEST(test_map_operator_bracket);
RUN_TEST(test_map_rb_properties);
std::cout << "\n=== Stack Tests ===" << std::endl;
RUN_TEST(test_stack_basic);
RUN_TEST(test_stack_comparison);
std::cout << "\n=== Benchmarks ===" << std::endl;
benchmark_vector();
benchmark_map();
benchmark_memory();
return 0;
}
---
まとめ
本章で学んだこと：
- テスト戦略: 単体、比較、パフォーマンス、エッジケース
- vectorのテスト: 基本操作、イテレータ、例外
- mapのテスト: 挿入、検索、赤黒木の性質
- stackのテスト: 基本操作、比較
- パフォーマンステスト: 時間、メモリ
- 最適化: reserve、hint付きinsert
これでft_containersガイドは完了です。