固定長シーケンシャルコンテナ FixedArrayList

コンパイル時に要素数が確定する、スタック領域を利用したシンプルなリストである。全要素が連続したメモリブロックに格納され、ランダムアクセスがO(1)で行える。

// FixedArrayList.hpp
#pragma once
#include "LinearList.hpp"

namespace ds {

template<typename T, std::size_t N>
class FixedArrayList : public LinearList<T> {
protected:
    T buffer_[N];                 // 静的配列による連続領域
public:
    FixedArrayList() noexcept {
        this->data_   = buffer_; // 基底クラスにバッファを渡す
        this->size_   = 0;
    }

    [[nodiscard]] constexpr std::size_t max_size() const noexcept {
        return N;
    }
};

} // namespace ds

可変長シーケンシャルコンテナ HeapArrayList

実行時に容量を決定し、ヒープ領域から動的にメモリを確保する。必要に応じて容量を拡張・縮小できるため、柔軟性が高い。

リサイズ時の安全性要件

• メモリリークを起こさない
• 既存データの整合性を保つ
• 例外発生時もオブジェクトは利用可能な状態を維持

// HeapArrayList.hpp
#pragma once
#include "LinearList.hpp"
#include "MemoryException.hpp"

namespace ds {

template<typename T>
class HeapArrayList : public LinearList<T> {
protected:
    std::size_t cap_;  // 現在確保済みの容量
public:
    explicit HeapArrayList(std::size_t initial_cap)
        : cap_(initial_cap) {
        this->data_ = new T[cap_];
        if (!this->data_) {
            throw MemoryException("Failed to allocate HeapArrayList");
        }
        this->size_ = 0;
    }

    [[nodiscard]] std::size_t capacity() const noexcept {
        return cap_;
    }

    void reserve(std::size_t new_cap) {
        if (new_cap == cap_) return;

        T* new_block = new(std::nothrow) T[new_cap];
        if (!new_block) {
            throw MemoryException("Reserve failed: out of memory");
        }

        const std::size_t copy_len = (this->size_ < new_cap) ? this->size_ : new_cap;
        for (std::size_t i = 0; i < copy_len; ++i) {
            new_block[i] = std::move(this->data_[i]);
        }

        T* old_block = this->data_;

        this->data_ = new_block;
        this->size_ = copy_len;
        cap_        = new_cap;

        delete[] old_block;   // 古いブロックを解放
    }

    ~HeapArrayList() {
        delete[] this->data_;
    }
};

} // namespace ds

使用例

// main.cpp
#include "FixedArrayList.hpp"
#include "HeapArrayList.hpp"
#include <iostream>

int main() {
    // 固定長リスト
    ds::FixedArrayList<int, 4> fixed;
    for (int v : {7, 3, 9, 2}) fixed.push_back(v);
    std::cout << "Fixed capacity: " << fixed.max_size() << '\n';

    // 可変長リスト
    ds::HeapArrayList<double> dyn(3);
    dyn.push_back(1.2);
    dyn.push_back(3.4);
    dyn.push_back(5.6);
    dyn.reserve(6);   // 容量を拡張
    dyn.push_back(7.8);
    std::cout << "Dynamic capacity: " << dyn.capacity() << '\n';
}