第1章：STLの歴史と設計思想
はじめに
ft_containersは、C++標準テンプレートライブラリ（STL）のコンテナを再実装するプロジェクトです。本章では、STLの歴史と設計思想を学び、プロジェクト全体の構造を理解します。
---
1. STLの歴史
1.1 Alexander Stepanovの構想
STLの父、Alexander Stepanovは1970年代からジェネリックプログラミングの研究を続けていました。
年表:
1976: Stepanov、ソ連でジェネリックプログラミングを研究開始
1979: Bjarne Stroustrup、C with Classesを開発
1983: C++誕生
1987: Stepanov、HP研究所に移籍
1988: Ada向けジェネリックライブラリを開発
1992: Andrew Koenig、Stepanovを C++標準化委員会に紹介
1993: Stepanov、C++向けSTLを開発
1994: STLがC++標準に採用
1998: C++98標準化（STL含む）
1.2 Stepanovの設計哲学
> "I believe that iterator theories are as central to Computer Science > as theories of rings or Banach spaces are central to Mathematics." > — Alexander Stepanov
Stepanovの核心的アイデア：
- アルゴリズムとデータ構造の分離
- イテレータによる抽象化
- ゼロオーバーヘッド原則
// 従来のアプローチ：各コンテナにソートを実装
class IntArray {
void sort();
};
class LinkedList {
void sort();
};
// STLのアプローチ：アルゴリズムを分離
template<typename Iterator>
void sort(Iterator first, Iterator last);
// あらゆるコンテナに適用可能
std::sort(array.begin(), array.end());
std::sort(vector.begin(), vector.end());
---
2. STLの構成要素
2.1 コンテナ
データを格納する構造：
シーケンスコンテナ:
+--------+--------+--------+
| vector | deque | list |
+--------+--------+--------+
|動的配列|両端配列|双方向 |
| | |リスト |
+--------+--------+--------+
連想コンテナ:
+--------+--------+--------+--------+
| set |multiset| map |multimap|
+--------+--------+--------+--------+
|一意集合|重複集合|キー値 |重複キー|
+--------+--------+--------+--------+
コンテナアダプタ:
+--------+--------+-----------+
| stack | queue |priority_q |
+--------+--------+-----------+
|LIFO |FIFO |優先度付き |
+--------+--------+-----------+
2.2 イテレータ
コンテナとアルゴリズムを繋ぐ抽象化：
// イテレータのカテゴリ
InputIterator // 読み取り専用、前進のみ
OutputIterator // 書き込み専用、前進のみ
ForwardIterator // 読み書き、前進のみ
BidirectionalIterator // 読み書き、双方向
RandomAccessIterator // 読み書き、ランダムアクセス
イテレータの階層:
RandomAccessIterator
↑
BidirectionalIterator
↑
ForwardIterator
↑ ↑
InputIterator OutputIterator
2.3 アルゴリズム
// 検索
find, find_if, count, count_if
// ソート
sort, stable_sort, partial_sort
// 変換
transform, copy, replace, remove
// 数値
accumulate, inner_product
2.4 ファンクタ（関数オブジェクト）
template<typename T>
struct less {
bool operator()(const T& a, const T& b) const {
return a < b;
}
};
// 使用例
std::sort(v.begin(), v.end(), std::less<int>());
---
3. ft_containersの要件
3.1 実装対象
必須:
├── vector<T>
├── map<Key, Value>
├── stack<T>
└── set<T> (C++98準拠の場合)
ユーティリティ:
├── iterators_traits
├── reverse_iterator
├── enable_if (C++11風だがC++98で実装)
├── is_integral
├── equal, lexicographical_compare
└── pair, make_pair
3.2 C++98準拠
ft_containersはC++98標準に準拠する必要があります：
// 使用可能
template<typename T>
class vector;
// 使用不可（C++11以降）
auto, nullptr, constexpr, noexcept
range-based for, initializer_list
move semantics, variadic templates
3.3 名前空間
namespace ft {
template<typename T, typename Alloc = std::allocator<T> >
class vector;
template<typename Key, typename T,
typename Compare = std::less<Key>,
typename Alloc = std::allocator<std::pair<const Key, T> > >
class map;
// ...
}
---
4. テンプレートの基礎
4.1 クラステンプレート
template<typename T>
class Container {
private:
T* _data;
size_t _size;
public:
Container() : _data(NULL), _size(0) {}
void push(const T& value) {
// ...
}
T& operator[](size_t index) {
return _data[index];
}
};
// 使用
Container<int> intContainer;
Container<std::string> stringContainer;
4.2 メンバテンプレート
template<typename T>
class vector {
public:
// 通常のコンストラクタ
vector(size_t n, const T& val);
// テンプレートコンストラクタ（範囲）
template<typename InputIterator>
vector(InputIterator first, InputIterator last);
};
4.3 テンプレート特殊化
// 汎用版
template<typename T>
struct is_integral {
static const bool value = false;
};
// 特殊化版
template<>
struct is_integral<int> {
static const bool value = true;
};
template<>
struct is_integral<char> {
static const bool value = true;
};
---
5. アロケータ
5.1 std::allocator
STLコンテナはアロケータを使用してメモリを管理します：
template<typename T>
class allocator {
public:
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef const T* const_pointer;
typedef const T& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
template<typename U>
struct rebind {
typedef allocator<U> other;
};
pointer allocate(size_type n) {
return static_cast<pointer>(::operator new(n * sizeof(T)));
}
void deallocate(pointer p, size_type n) {
(void)n;
::operator delete(p);
}
void construct(pointer p, const_reference val) {
new(p) T(val); // placement new
}
void destroy(pointer p) {
p->~T();
}
};
5.2 rebind
異なる型のアロケータを取得：
// mapでの使用例
// map<int, string>は内部でノードを確保する
typedef std::pair<const int, std::string> value_type;
// ノード型
struct Node {
value_type data;
Node* left;
Node* right;
// ...
};
// value_type用アロケータからNode用アロケータを取得
typedef typename Alloc::template rebind<Node>::other node_allocator;
---
6. 例外安全性
6.1 例外安全性のレベル
No-throw guarantee（例外を投げない）:
- デストラクタ
- swap操作
Strong guarantee（強い保証）:
- 例外発生時、操作前の状態を維持
- insert, push_back（失敗時は変更なし）
Basic guarantee（基本保証）:
- 例外発生時も不変条件を維持
- リソースリークなし
6.2 実装での考慮
template<typename T, typename Alloc>
void vector<T, Alloc>::push_back(const T& value) {
if (_size == _capacity) {
// 1. 新しいメモリを確保
size_t new_cap = _capacity ? _capacity * 2 : 1;
pointer new_data = _alloc.allocate(new_cap);
try {
// 2. 既存要素をコピー
for (size_t i = 0; i < _size; ++i) {
_alloc.construct(new_data + i, _data[i]);
}
// 3. 新要素を追加
_alloc.construct(new_data + _size, value);
} catch (...) {
// コピー中に例外が発生したら、確保したメモリを解放
_alloc.deallocate(new_data, new_cap);
throw;
}
// 4. 古いデータを破棄
for (size_t i = 0; i < _size; ++i) {
_alloc.destroy(_data + i);
}
_alloc.deallocate(_data, _capacity);
_data = new_data;
_capacity = new_cap;
} else {
_alloc.construct(_data + _size, value);
}
++_size;
}
---
7. プロジェクト構造
7.1 ディレクトリ構成
ft_containers/
├── Makefile
├── includes/
│ ├── vector.hpp
│ ├── map.hpp
│ ├── stack.hpp
│ ├── set.hpp (オプション)
│ ├── iterator.hpp
│ ├── iterator_traits.hpp
│ ├── reverse_iterator.hpp
│ ├── type_traits.hpp (enable_if, is_integral)
│ ├── utility.hpp (pair, make_pair)
│ ├── algorithm.hpp (equal, lexicographical_compare)
│ └── rb_tree.hpp (赤黒木)
├── srcs/
│ └── main.cpp (テスト)
└── tests/
├── vector_test.cpp
├── map_test.cpp
└── ...
7.2 ヘッダーの依存関係
type_traits.hpp
↑
iterator_traits.hpp
↑
┌──────┴──────┐
↓ ↓
iterator.hpp reverse_iterator.hpp
↓ ↓
└──────┬──────┘
↓
vector.hpp
↓
stack.hpp
rb_tree.hpp
↓
┌──────┴──────┐
↓ ↓
map.hpp set.hpp
---
まとめ
本章で学んだこと：
次章では、vector（動的配列）の実装を学びます。