Created
February 16, 2020 16:13
-
-
Save eyelash/87a3fe849b31a37c58eca4ef398a71dc to your computer and use it in GitHub Desktop.
This file contains hidden or 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); | |
| } | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.