Created
February 16, 2020 16:13
-
-
Save eyelash/87a3fe849b31a37c58eca4ef398a71dc to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdlib> | |
| #include <atomic> | |
| #include <memory> | |
| template <class T> class Storage { | |
| T* storage; | |
| const std::size_t capacity; | |
| std::atomic<std::size_t> size; | |
| std::atomic<std::size_t> reference_count; | |
| public: | |
| Storage(std::size_t capacity): capacity(capacity), size(0), reference_count(0) { | |
| storage = static_cast<T*>(std::malloc(capacity * sizeof(T))); | |
| } | |
| Storage(const Storage&) = delete; | |
| ~Storage() { | |
| for (std::size_t i = 0; i < size; ++i) { | |
| storage[i].~T(); | |
| } | |
| std::free(storage); | |
| } | |
| Storage& operator =(const Storage&) = delete; | |
| std::size_t get_capacity() const { | |
| return capacity; | |
| } | |
| const T* get(std::size_t index) const { | |
| return storage + index; | |
| } | |
| bool try_insert(std::size_t index, const T& element) { | |
| if (index < capacity && size.compare_exchange_strong(index, index + 1)) { | |
| new (storage + index) T(element); | |
| return true; | |
| } | |
| return false; | |
| } | |
| void retain() { | |
| reference_count.fetch_add(1); | |
| } | |
| bool release() { | |
| return reference_count.fetch_sub(1) == 1; | |
| } | |
| }; | |
| template <class T> class ImmutableVector { | |
| Storage<T>* storage; | |
| std::size_t size; | |
| ImmutableVector(Storage<T>* storage, std::size_t size): storage(storage), size(size) { | |
| storage->retain(); | |
| } | |
| public: | |
| ImmutableVector(): ImmutableVector(new Storage<T>(4), 0) {} | |
| ImmutableVector(const ImmutableVector& vector): ImmutableVector(vector.storage, vector.size) {} | |
| ~ImmutableVector() { | |
| if (storage->release()) { | |
| delete storage; | |
| } | |
| } | |
| ImmutableVector& operator =(const ImmutableVector& vector) { | |
| if (vector.storage != storage) { | |
| if (storage->release()) { | |
| delete storage; | |
| } | |
| storage = vector.storage; | |
| storage->retain(); | |
| } | |
| size = vector.size; | |
| return *this; | |
| } | |
| ImmutableVector insert(std::size_t index, const T& element) const { | |
| if (storage->try_insert(index, element)) { | |
| return ImmutableVector(storage, size + 1); | |
| } | |
| const std::size_t new_capacity = std::max<std::size_t>(size * 2, 4); | |
| Storage<T>* new_storage = new Storage<T>(new_capacity); | |
| for (std::size_t i = 0; i < index; ++i) { | |
| new_storage->try_insert(i, *storage->get(i)); | |
| } | |
| new_storage->try_insert(index, element); | |
| for (std::size_t i = index; i < size; ++i) { | |
| new_storage->try_insert(i + 1, *storage->get(i)); | |
| } | |
| return ImmutableVector(new_storage, size + 1); | |
| } | |
| ImmutableVector push_back(const T& element) const { | |
| return insert(size, element); | |
| } | |
| ImmutableVector erase(std::size_t index) const { | |
| const std::size_t new_capacity = std::max<std::size_t>((size - 1) * 2, 4); | |
| if (index == size - 1 && new_capacity > storage->get_capacity() / 2) { | |
| return ImmutableVector(storage, size - 1); | |
| } | |
| Storage<T>* new_storage = new Storage<T>(new_capacity); | |
| for (std::size_t i = 0; i < index; ++i) { | |
| new_storage->try_insert(i, *storage->get(i)); | |
| } | |
| for (std::size_t i = index + 1; i < size; ++i) { | |
| new_storage->try_insert(i - 1, *storage->get(i)); | |
| } | |
| return ImmutableVector(new_storage, size - 1); | |
| } | |
| ImmutableVector pop_back() const { | |
| return erase(size - 1); | |
| } | |
| const T& operator [](std::size_t index) const { | |
| return *storage->get(index); | |
| } | |
| const T* begin() const { | |
| return storage->get(0); | |
| } | |
| const T* end() const { | |
| return storage->get(size); | |
| } | |
| }; |
Also, it isn't exception safe - you can leak Storage on insert/erase if T throws when copied.
Not sure if you are worried about exception safety, but it would be nice to have the same safety as std::vector.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
You might want to comment the code. It is very subtle that storage size is separate from vector size and that the underlying reasoning is so that push_back can use the same vector as the original since the original will never access past its own size.
I wonder if using something like std::span as part of the implementation would make this more obvious. (also more compile time, but you wouldn't need std::span, you could use a trimmed down thing of your own)