C++でvectorコンテナを自作実装する方法

C++の標準ライブラリで提供されるstd::vectorの動作を理解するために、独自の動的配列クラスを実装します。この記事では、イテレータ、メモリ管理、要素アクセス、変更操作などの実装手順をコード例とともに解説します。

メンバ変数

std::vectorと同様に、内部では3つのポインタ（イテレータ）で管理します。std::stringとは異なり、サイズやキャパシティはこれらのポインタの差分から計算します。

namespace myvector {

template<class T>
class vector {
public:
    using iterator = T*;
    using const_iterator = const T*;

private:
    iterator _start;      // 先頭要素を指す
    iterator _finish;     // 最後の要素の次を指す
    iterator _end_of_storage; // 確保したメモリの末尾の次を指す
};
}

図にすると以下のように配置されます。

  • _start から _finish の範囲が有効な要素
  • _finish から _end_of_storage の範囲が予約済みの空き容量

サイズとキャパシティは次のように計算できます。

size_t size() const { return _finish - _start; }
size_t capacity() const { return _end_of_storage - _start; }

イテレータ

前方イテレータ

iterator begin() { return _start; }
const_iterator begin() const { return _start; }
iterator end() { return _finish; }
const_iterator end() const { return _finish; }

容量管理

メモリ確保（reserve）

void reserve(size_t n) {
    if (n > capacity()) {
        size_t old_size = size();
        iterator new_buffer = new T[n];

        if (_start) {
            for (size_t i = 0; i < old_size; ++i) {
                new_buffer[i] = _start[i];
            }
        }

        delete[] _start;
        _start = new_buffer;
        _finish = _start + old_size;
        _end_of_storage = _start + n;
    }
}

重要な注意点:

  1. 古いサイズを保存する必要があります。_finish は _start の再割り当て後に計算しますが、size() は古い _start と _finish の差分に依存するため、事前に保存しておかないと正しい値が得られません。
  2. 要素コピーには memcpy ではなくループを使用します。memcpy は浅いコピーしか行わず、std::string のようなリソース管理型では不適切です。

サイズ変更（resize）

void resize(size_t n, const T& val = T()) {
    if (n <= size()) {
        _finish = _start + n;
    } else {
        reserve(n);
        while (_finish != _start + n) {
            *_finish = val;
            ++_finish;
        }
    }
}

T() はデフォルト値を生成します。組み込み型（int など）でもデフォルトコンストラクタが呼び出され、0 で初期化されます。

要素アクセス

添え字演算子（operator[]）

T& operator[](size_t pos) {
    assert(pos < size());
    return _start[pos];
}

front / back

T& front() { return *_start; }
T& back() { return *(_finish - 1); }

変更操作

末尾追加（push_back）

void push_back(const T& val) {
    if (_finish == _end_of_storage) {
        reserve(capacity() == 0 ? 2 : capacity() * 2);
    }
    *_finish = val;
    ++_finish;
}

末尾削除（pop_back）

void pop_back() {
    assert(_finish > _start);
    --_finish;
}

任意位置への挿入（insert）

iterator insert(iterator pos, const T& val) {
    assert(pos >= _start && pos <= _finish);

    if (_finish == _end_of_storage) {
        size_t offset = pos - _start;
        reserve(capacity() == 0 ? 2 : capacity() * 2);
        pos = _start + offset; // 再割り当て後はイテレータが無効になるため修正
    }

    for (iterator it = _finish; it > pos; --it) {
        *it = *(it - 1);
    }
    *pos = val;
    ++_finish;
    return pos;
}

イテレータの無効化に注意：再割り当て後は pos も無効になるため、オフセットを使って再設定します。

任意位置の削除（erase）

iterator erase(iterator pos) {
    assert(pos >= _start && pos < _finish);

    for (iterator it = pos; it < _finish - 1; ++it) {
        *it = *(it + 1);
    }
    --_finish;
    return pos;
}

スワップ（swap）

void swap(vector& other) {
    std::swap(_start, other._start);
    std::swap(_finish, other._finish);
    std::swap(_end_of_storage, other._end_of_storage);
}

クリア（clear）

void clear() { _finish = _start; }

コンストラクタ、デストラクタ、代入演算子

デフォルトコンストラクタとコピーコンストラクタ

vector() : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}

vector(const vector& other)
    : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {
    reserve(other.capacity());
    for (const auto& elem : other) {
        push_back(elem);
    }
}

イテレータコンストラクタ

template<class InputIterator>
vector(InputIterator first, InputIterator last)
    : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {
    while (first != last) {
        push_back(*first);
        ++first;
    }
}

任意のイテレータ型を受け付けるため、テンプレートを使用します。型推論の衝突を避けるため、iterator 型に限定しません。

要素数指定コンストラクタ

explicit vector(size_t n, const T& val = T())
    : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {
    resize(n, val);
}

// int型のオーバーロード：関数オーバーロード解決のため
vector(int n, const T& val = T())
    : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {
    resize(static_cast<size_t>(n), val);
}

vector<int> v(2, 100); のようなコードで、コンパイラが int を InputIterator と推論してしまう問題を回避するため、int 版も用意します。

デストラクタ

~vector() {
    delete[] _start;
    _start = _finish = _end_of_storage = nullptr;
}

代入演算子

vector& operator=(const vector& other) {
    if (this != &other) {
        vector temp(other);
        swap(temp);
    }
    return *this;
}

コピー＆スワップ技法を使用して、例外安全かつ簡潔に実装します。

完全なソースコード

#pragma once
#include <cassert>

namespace myvector {

template<class T>
class vector {
public:
    using iterator = T*;
    using const_iterator = const T*;

    // デフォルトコンストラクタ
    vector() : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}

    // 要素数指定
    explicit vector(size_t n, const T& val = T())
        : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {
        resize(n, val);
    }

    vector(int n, const T& val = T())
        : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {
        resize(static_cast<size_t>(n), val);
    }

    // イテレータコンストラクタ
    template<class InputIterator>
    vector(InputIterator first, InputIterator last)
        : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {
        while (first != last) {
            push_back(*first);
            ++first;
        }
    }

    // コピーコンストラクタ
    vector(const vector& other)
        : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {
        reserve(other.capacity());
        for (const auto& elem : other) {
            push_back(elem);
        }
    }

    // デストラクタ
    ~vector() {
        delete[] _start;
        _start = _finish = _end_of_storage = nullptr;
    }

    // 代入演算子
    vector& operator=(const vector& other) {
        if (this != &other) {
            vector temp(other);
            swap(temp);
        }
        return *this;
    }

    // イテレータ
    iterator begin() { return _start; }
    const_iterator begin() const { return _start; }
    iterator end() { return _finish; }
    const_iterator end() const { return _finish; }

    // 容量
    size_t size() const { return _finish - _start; }
    size_t capacity() const { return _end_of_storage - _start; }
    bool empty() const { return _start == _finish; }

    void resize(size_t n, const T& val = T()) {
        if (n <= size()) {
            _finish = _start + n;
        } else {
            reserve(n);
            while (_finish != _start + n) {
                *_finish = val;
                ++_finish;
            }
        }
    }

    void reserve(size_t n) {
        if (n > capacity()) {
            size_t old_size = size();
            iterator new_buffer = new T[n];

            if (_start) {
                for (size_t i = 0; i < old_size; ++i) {
                    new_buffer[i] = _start[i];
                }
            }

            delete[] _start;
            _start = new_buffer;
            _finish = _start + old_size;
            _end_of_storage = _start + n;
        }
    }

    // 要素アクセス
    T& operator[](size_t pos) {
        assert(pos < size());
        return _start[pos];
    }

    const T& operator[](size_t pos) const {
        assert(pos < size());
        return _start[pos];
    }

    T& front() { return *_start; }
    const T& front() const { return *_start; }
    T& back() { return *(_finish - 1); }
    const T& back() const { return *(_finish - 1); }

    // 変更操作
    void push_back(const T& val) {
        if (_finish == _end_of_storage) {
            reserve(capacity() == 0 ? 2 : capacity() * 2);
        }
        *_finish = val;
        ++_finish;
    }

    void pop_back() {
        assert(_finish > _start);
        --_finish;
    }

    iterator insert(iterator pos, const T& val) {
        assert(pos >= _start && pos <= _finish);

        if (_finish == _end_of_storage) {
            size_t offset = pos - _start;
            reserve(capacity() == 0 ? 2 : capacity() * 2);
            pos = _start + offset;
        }

        for (iterator it = _finish; it > pos; --it) {
            *it = *(it - 1);
        }
        *pos = val;
        ++_finish;
        return pos;
    }

    iterator erase(iterator pos) {
        assert(pos >= _start && pos < _finish);

        for (iterator it = pos; it < _finish - 1; ++it) {
            *it = *(it + 1);
        }
        --_finish;
        return pos;
    }

    void swap(vector& other) {
        std::swap(_start, other._start);
        std::swap(_finish, other._finish);
        std::swap(_end_of_storage, other._end_of_storage);
    }

    void clear() { _finish = _start; }

private:
    iterator _start;
    iterator _finish;
    iterator _end_of_storage;
};

} // namespace myvector

タグ: Vector C++ STL イテレータ メモリ管理

5月30日 17:22 投稿

ホットタグ

©2026 異端開発室