immutable_vector.cpp

#include <memory>
#include <cstdlib>
#include <cassert>

template <typename T>
class immutable_vector_data {
public:
    static constexpr size_t kInitialCapacity = 1;

    immutable_vector_data(size_t capacity = kInitialCapacity)
        : elements{new T[capacity]}
    {}

    immutable_vector_data(const immutable_vector_data& other, size_t size, size_t capacity)
        : elements{new T[capacity]}
        , size{size}
        , capacity{capacity}
    {
        assert(size <= capacity);
        for (size_t i = 0; i < size; ++i) {
            (elements.get())[i] = (other.elements.get())[i];
        }
    }

    std::unique_ptr<T[]> elements = nullptr;
    size_t size = 0;
    size_t capacity = 1;
};

template <typename T>
class immutable_vector {
public:
    immutable_vector()
        : _data{new immutable_vector_data<T>}
    {}

    immutable_vector push_back(T t) const {
        if (_data->size == _size) {
            if (_data->size == _data->capacity) {
                _data = std::make_shared<immutable_vector_data<T>>(*_data, _data->size, _data->capacity * 2);
            }
            _data->elements[_data->size] = std::move(t);
            ++_data->size;
            return immutable_vector{_data, _size + 1};
        }

        _data = std::make_shared<immutable_vector_data<T>>(*_data, _size, _data->capacity * 2);
        return push_back(std::move(t));
    }

    immutable_vector pop_back() const {
        return immutable_vector{_data, _size - 1};
    }

    size_t size() const {
        return _size;
    }

    const T& operator[](size_t i) const {
        return _data->elements[i];
    }

    const T* begin() const {
        return _data->elements.get();
    }

    const T* end() const {
        return _data->elements.get() + _size;
    }

private:
    size_t _size = 0;
    mutable std::shared_ptr<immutable_vector_data<T>> _data = nullptr;

    immutable_vector(std::shared_ptr<immutable_vector_data<T>> data, size_t n)
        : _data{std::move(data)}
        , _size{n}
    {
        assert(_data->size >= n);
    }
};

int main() {
    const immutable_vector<int> v0;

    assert(v0.size() == 0);

    const auto v1 = v0.push_back(0);
    const auto v2 = v1.push_back(1);
    const auto v3 = v2.push_back(2);

    assert(v1.size() == 1);
    assert(v2.size() == 2);
    assert(v3.size() == 3);

    assert(v1[0] == 0);

    assert(v2[0] == 0);
    assert(v2[1] == 1);

    assert(v3[0] == 0);
    assert(v3[1] == 1);
    assert(v3[2] == 2);

    const auto v4 = v3.pop_back();

    assert(v2.size() == v4.size());
    assert(std::equal(v2.begin(), v2.end(), v4.begin()));

    const auto v5 = v4.push_back(5);

    assert(v5[0] == 0);
    assert(v5[1] == 1);
    assert(v5[2] == 5);

    // check everything

    assert(v0.size() == 0);
    assert(v1.size() == 1);
    assert(v2.size() == 2);
    assert(v3.size() == 3);
    assert(v4.size() == 2);

    assert(v1[0] == 0);

    assert(v2[0] == 0);
    assert(v2[1] == 1);

    assert(v3[0] == 0);
    assert(v3[1] == 1);
    assert(v3[2] == 2);

    assert(v4[0] == 0);
    assert(v4[1] == 1);

    assert(v5[0] == 0);
    assert(v5[1] == 1);
    assert(v5[2] == 5);
}