第2章：vector - 動的配列
はじめに
vectorは最も基本的なSTLコンテナです。連続したメモリ領域に要素を格納し、動的にサイズを変更できます。
---
1. vectorの特性
1.1 データ構造
vector内部:
┌─────┬─────┬─────┬─────┬─────┬─────┐
│ 1 │ 2 │ 3 │ 4 │ │ │
└─────┴─────┴─────┴─────┴─────┴─────┘
↑ ↑ ↑
_data _size _capacity
_data: 配列の先頭へのポインタ
_size: 実際の要素数
_capacity: 確保されたメモリ容量
1.2 計算量
| 操作 | 計算量 | |------|--------| | operator[] | O(1) | | push_back | 償却O(1) | | pop_back | O(1) | | insert | O(n) | | erase | O(n) | | begin/end | O(1) | | size/capacity | O(1) |
1.3 メモリ再確保戦略
// 典型的な戦略: 2倍ずつ増やす
size_t new_capacity = _capacity ? _capacity * 2 : 1;
// なぜ2倍？
// - 1.5倍: メモリ効率は良いが、再確保が多い
// - 2倍: 再確保回数とメモリ効率のバランス
// - 3倍以上: メモリを無駄に使う
// 償却計算量がO(1)になる条件:
// 増加率 > 1 であれば、n回のpush_backの総コストはO(n)
---
2. 基本実装
2.1 クラス定義
namespace ft {
template<typename T, typename Alloc = std::allocator<T> >
class vector {
public:
// 型定義
typedef T value_type;
typedef Alloc allocator_type;
typedef typename allocator_type::reference reference;
typedef typename allocator_type::const_reference const_reference;
typedef typename allocator_type::pointer pointer;
typedef typename allocator_type::const_pointer const_pointer;
typedef typename allocator_type::size_type size_type;
typedef typename allocator_type::difference_type difference_type;
// イテレータ型
typedef pointer iterator;
typedef const_pointer const_iterator;
typedef ft::reverse_iterator<iterator> reverse_iterator;
typedef ft::reverse_iterator<const_iterator> const_reverse_iterator;
private:
allocator_type _alloc;
pointer _data;
size_type _size;
size_type _capacity;
public:
// コンストラクタ・デストラクタ
explicit vector(const allocator_type& alloc = allocator_type());
explicit vector(size_type n, const value_type& val = value_type(),
const allocator_type& alloc = allocator_type());
template<typename InputIterator>
vector(InputIterator first, InputIterator last,
const allocator_type& alloc = allocator_type());
vector(const vector& x);
~vector();
vector& operator=(const vector& x);
// イテレータ
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
// 容量
size_type size() const;
size_type max_size() const;
void resize(size_type n, value_type val = value_type());
size_type capacity() const;
bool empty() const;
void reserve(size_type n);
// 要素アクセス
reference operator[](size_type n);
const_reference operator[](size_type n) const;
reference at(size_type n);
const_reference at(size_type n) const;
reference front();
const_reference front() const;
reference back();
const_reference back() const;
// 変更
template<typename InputIterator>
void assign(InputIterator first, InputIterator last);
void assign(size_type n, const value_type& val);
void push_back(const value_type& val);
void pop_back();
iterator insert(iterator position, const value_type& val);
void insert(iterator position, size_type n, const value_type& val);
template<typename InputIterator>
void insert(iterator position, InputIterator first, InputIterator last);
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
void swap(vector& x);
void clear();
// アロケータ
allocator_type get_allocator() const;
};
} // namespace ft
2.2 コンストラクタとデストラクタ
// デフォルトコンストラクタ
template<typename T, typename Alloc>
vector<T, Alloc>::vector(const allocator_type& alloc)
: _alloc(alloc), _data(NULL), _size(0), _capacity(0) {}
// fillコンストラクタ
template<typename T, typename Alloc>
vector<T, Alloc>::vector(size_type n, const value_type& val,
const allocator_type& alloc)
: _alloc(alloc), _data(NULL), _size(0), _capacity(0) {
if (n > 0) {
_data = _alloc.allocate(n);
_capacity = n;
for (size_type i = 0; i < n; ++i) {
_alloc.construct(_data + i, val);
++_size;
}
}
}
// rangeコンストラクタ
template<typename T, typename Alloc>
template<typename InputIterator>
vector<T, Alloc>::vector(InputIterator first, InputIterator last,
const allocator_type& alloc)
: _alloc(alloc), _data(NULL), _size(0), _capacity(0) {
// is_integralを使って、fillコンストラクタとの衝突を解決
typedef typename ft::is_integral<InputIterator>::type Integral;
_init_range(first, last, Integral());
}
// ヘルパー関数
template<typename T, typename Alloc>
template<typename InputIterator>
void vector<T, Alloc>::_init_range(InputIterator first, InputIterator last,
ft::false_type) {
// 本当のイテレータの場合
for (; first != last; ++first) {
push_back(*first);
}
}
template<typename T, typename Alloc>
template<typename Integer>
void vector<T, Alloc>::_init_range(Integer n, Integer val, ft::true_type) {
// 整数型の場合（fillコンストラクタとして扱う）
_data = _alloc.allocate(n);
_capacity = n;
for (size_type i = 0; i < static_cast<size_type>(n); ++i) {
_alloc.construct(_data + i, val);
++_size;
}
}
// コピーコンストラクタ
template<typename T, typename Alloc>
vector<T, Alloc>::vector(const vector& x)
: _alloc(x._alloc), _data(NULL), _size(0), _capacity(0) {
*this = x;
}
// デストラクタ
template<typename T, typename Alloc>
vector<T, Alloc>::~vector() {
clear();
if (_data) {
_alloc.deallocate(_data, _capacity);
}
}
// 代入演算子
template<typename T, typename Alloc>
vector<T, Alloc>& vector<T, Alloc>::operator=(const vector& x) {
if (this != &x) {
clear();
if (_capacity < x._size) {
if (_data) {
_alloc.deallocate(_data, _capacity);
}
_data = _alloc.allocate(x._size);
_capacity = x._size;
}
for (size_type i = 0; i < x._size; ++i) {
_alloc.construct(_data + i, x._data[i]);
}
_size = x._size;
}
return *this;
}
2.3 イテレータ
template<typename T, typename Alloc>
typename vector<T, Alloc>::iterator vector<T, Alloc>::begin() {
return _data;
}
template<typename T, typename Alloc>
typename vector<T, Alloc>::const_iterator vector<T, Alloc>::begin() const {
return _data;
}
template<typename T, typename Alloc>
typename vector<T, Alloc>::iterator vector<T, Alloc>::end() {
return _data + _size;
}
template<typename T, typename Alloc>
typename vector<T, Alloc>::const_iterator vector<T, Alloc>::end() const {
return _data + _size;
}
template<typename T, typename Alloc>
typename vector<T, Alloc>::reverse_iterator vector<T, Alloc>::rbegin() {
return reverse_iterator(end());
}
template<typename T, typename Alloc>
typename vector<T, Alloc>::reverse_iterator vector<T, Alloc>::rend() {
return reverse_iterator(begin());
}
---
3. 容量管理
3.1 size, capacity, max_size
template<typename T, typename Alloc>
typename vector<T, Alloc>::size_type vector<T, Alloc>::size() const {
return _size;
}
template<typename T, typename Alloc>
typename vector<T, Alloc>::size_type vector<T, Alloc>::capacity() const {
return _capacity;
}
template<typename T, typename Alloc>
typename vector<T, Alloc>::size_type vector<T, Alloc>::max_size() const {
return _alloc.max_size();
}
template<typename T, typename Alloc>
bool vector<T, Alloc>::empty() const {
return _size == 0;
}
3.2 reserve
template<typename T, typename Alloc>
void vector<T, Alloc>::reserve(size_type n) {
if (n > max_size()) {
throw std::length_error("vector::reserve");
}
if (n > _capacity) {
pointer new_data = _alloc.allocate(n);
// 既存要素をコピー
for (size_type i = 0; i < _size; ++i) {
_alloc.construct(new_data + i, _data[i]);
_alloc.destroy(_data + i);
}
// 古いメモリを解放
if (_data) {
_alloc.deallocate(_data, _capacity);
}
_data = new_data;
_capacity = n;
}
}
3.3 resize
template<typename T, typename Alloc>
void vector<T, Alloc>::resize(size_type n, value_type val) {
if (n < _size) {
// 縮小：余分な要素を破棄
while (_size > n) {
_alloc.destroy(_data + _size - 1);
--_size;
}
} else if (n > _size) {
// 拡大：必要に応じてメモリを確保
if (n > _capacity) {
reserve(n);
}
// 新しい要素を構築
while (_size < n) {
_alloc.construct(_data + _size, val);
++_size;
}
}
}
---
4. 要素アクセス
4.1 operator[] と at
template<typename T, typename Alloc>
typename vector<T, Alloc>::reference
vector<T, Alloc>::operator[](size_type n) {
return _data[n];
}
template<typename T, typename Alloc>
typename vector<T, Alloc>::const_reference
vector<T, Alloc>::operator[](size_type n) const {
return _data[n];
}
template<typename T, typename Alloc>
typename vector<T, Alloc>::reference
vector<T, Alloc>::at(size_type n) {
if (n >= _size) {
throw std::out_of_range("vector::at");
}
return _data[n];
}
template<typename T, typename Alloc>
typename vector<T, Alloc>::const_reference
vector<T, Alloc>::at(size_type n) const {
if (n >= _size) {
throw std::out_of_range("vector::at");
}
return _data[n];
}
4.2 front と back
template<typename T, typename Alloc>
typename vector<T, Alloc>::reference vector<T, Alloc>::front() {
return _data[0];
}
template<typename T, typename Alloc>
typename vector<T, Alloc>::reference vector<T, Alloc>::back() {
return _data[_size - 1];
}
---
5. 要素の変更
5.1 push_back と pop_back
template<typename T, typename Alloc>
void vector<T, Alloc>::push_back(const value_type& val) {
if (_size == _capacity) {
size_type new_cap = _capacity ? _capacity * 2 : 1;
reserve(new_cap);
}
_alloc.construct(_data + _size, val);
++_size;
}
template<typename T, typename Alloc>
void vector<T, Alloc>::pop_back() {
if (_size > 0) {
_alloc.destroy(_data + _size - 1);
--_size;
}
}
5.2 insert
template<typename T, typename Alloc>
typename vector<T, Alloc>::iterator
vector<T, Alloc>::insert(iterator position, const value_type& val) {
size_type pos = position - begin();
if (_size == _capacity) {
size_type new_cap = _capacity ? _capacity * 2 : 1;
reserve(new_cap);
}
// positionをreserve後に再計算
position = begin() + pos;
// 後ろの要素を1つずつ後ろにずらす
for (iterator it = end(); it != position; --it) {
_alloc.construct(&(*it), *(it - 1));
_alloc.destroy(it - 1);
}
// 新しい要素を挿入
_alloc.construct(&(*position), val);
++_size;
return position;
}
template<typename T, typename Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n,
const value_type& val) {
if (n == 0) return;
size_type pos = position - begin();
if (_size + n > _capacity) {
size_type new_cap = _size + n;
if (new_cap < _capacity * 2) {
new_cap = _capacity * 2;
}
reserve(new_cap);
}
position = begin() + pos;
// 後ろの要素をn個分後ろにずらす
for (iterator it = end() + n - 1; it >= position + n; --it) {
_alloc.construct(&(*it), *(it - n));
_alloc.destroy(it - n);
}
// 新しい要素を挿入
for (size_type i = 0; i < n; ++i) {
_alloc.construct(&(*(position + i)), val);
}
_size += n;
}
5.3 erase
template<typename T, typename Alloc>
typename vector<T, Alloc>::iterator
vector<T, Alloc>::erase(iterator position) {
_alloc.destroy(&(*position));
// 後ろの要素を前にずらす
for (iterator it = position; it + 1 != end(); ++it) {
_alloc.construct(&(*it), *(it + 1));
_alloc.destroy(it + 1);
}
--_size;
return position;
}
template<typename T, typename Alloc>
typename vector<T, Alloc>::iterator
vector<T, Alloc>::erase(iterator first, iterator last) {
size_type n = last - first;
// 範囲内の要素を破棄
for (iterator it = first; it != last; ++it) {
_alloc.destroy(&(*it));
}
// 後ろの要素を前にずらす
for (iterator it = first; it + n != end(); ++it) {
_alloc.construct(&(*it), *(it + n));
_alloc.destroy(it + n);
}
_size -= n;
return first;
}
5.4 clear と swap
template<typename T, typename Alloc>
void vector<T, Alloc>::clear() {
while (_size > 0) {
pop_back();
}
}
template<typename T, typename Alloc>
void vector<T, Alloc>::swap(vector& x) {
std::swap(_alloc, x._alloc);
std::swap(_data, x._data);
std::swap(_size, x._size);
std::swap(_capacity, x._capacity);
}
---
6. 比較演算子
template<typename T, typename Alloc>
bool operator==(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs) {
if (lhs.size() != rhs.size()) {
return false;
}
return ft::equal(lhs.begin(), lhs.end(), rhs.begin());
}
template<typename T, typename Alloc>
bool operator!=(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs) {
return !(lhs == rhs);
}
template<typename T, typename Alloc>
bool operator<(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs) {
return ft::lexicographical_compare(
lhs.begin(), lhs.end(),
rhs.begin(), rhs.end()
);
}
template<typename T, typename Alloc>
bool operator<=(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs) {
return !(rhs < lhs);
}
template<typename T, typename Alloc>
bool operator>(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs) {
return rhs < lhs;
}
template<typename T, typename Alloc>
bool operator>=(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs) {
return !(lhs < rhs);
}
// 非メンバswap
template<typename T, typename Alloc>
void swap(vector<T, Alloc>& x, vector<T, Alloc>& y) {
x.swap(y);
}
---
まとめ
本章で学んだこと：
- vectorの特性: 連続メモリ、動的サイズ
- メモリ管理: reserve, resize, capacityの関係
- 要素アクセス: operator[], at, front, back
- 要素の変更: push_back, pop_back, insert, erase
- 例外安全性: 強い保証を提供する実装
次章では、map/set（赤黒木）の実装を学びます。