Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <memory>
- #include <utility>
- #include <cstdlib>
- #include <cstring>
- #include <exception>
- #include <stdexcept>
- #include <iostream>
- namespace container {
- template <typename T = int, typename Alloc = std::allocator<T>>
- class vector {
- using alloc_t = std::allocator_traits<Alloc>;
- std::allocator<T> alloc;
- size_t size_stored;
- size_t pow_alloc;
- T *data;
- constexpr static size_t upper_2_power(size_t n) {
- return 8*sizeof(size_t) - __builtin_clzl(n);
- }
- void realloc(size_t n, bool init = false) {
- size_t bytes = 1 << pow_alloc;
- if (n <= bytes) return;
- size_t new_pow = upper_2_power(n);
- T* new_data = alloc_t::allocate(alloc, 1 << new_pow);
- if (!init) {
- for (size_t i = 0; i < size_stored; ++i)
- new_data[i] = data[i];
- alloc_t::deallocate(alloc, data, 1 << pow_alloc);
- }
- pow_alloc = new_pow;
- data = new_data;
- }
- void shrink() {
- T* new_data = alloc_t::allocate(alloc, size_stored);
- for (size_t i = 0; i < size_stored; ++i)
- new_data[i] = data[i];
- alloc_t::deallocate(alloc, data, pow_alloc);
- data = new_data;
- }
- public:
- vector() : alloc{}, size_stored{0}, pow_alloc{0}, data{nullptr} {}
- vector(size_t n) : vector(n, T{}) {}
- vector(size_t n, T val) : alloc{}, size_stored{n}, pow_alloc{0}, data{nullptr} {
- realloc(n, true);
- for (T* p = data; p < data + size_stored; ++p)
- *p = val;
- }
- vector(const vector& other) : alloc{}, size_stored{other.size_stored}, pow_alloc{0}, data{nullptr} {
- realloc(other.size(), true);
- for (size_t i = 0; i < other.size(); ++i)
- data[i] = other.data[i];
- }
- vector& operator=(const vector& other) {
- size_stored = other.size_stored;
- realloc(other.size(), true);
- for(size_t i = 0; i < other.size(); ++i)
- data[i] = other.data[i];
- return *this;
- }
- vector(vector&& other) : alloc{}, size_stored{0}, pow_alloc{0}, data{nullptr} {
- std::swap(size_stored, other.size_stored);
- std::swap(pow_alloc, other.pow_alloc);
- std::swap(data, other.data);
- std::swap(alloc, other.alloc);
- }
- vector& operator=(vector&& other) {
- size_stored = std::exchange(other.size_stored, 0);
- pow_alloc = std::exchange(other.pow_alloc, 0);
- data = std::exchange(other.data, nullptr);
- std::swap(alloc, other.alloc);
- return *this;
- }
- ~vector() {
- if (data != nullptr)
- alloc_t::deallocate(alloc, data, 1 << pow_alloc);
- }
- T& operator[](size_t i) noexcept {
- return data[i];
- }
- T& get(size_t i) noexcept(false) {
- if (i >= size_stored)
- throw std::out_of_range("Vector index out of range");
- return data[i];
- }
- size_t size() const noexcept {
- return size_stored;
- }
- size_t capacity() const noexcept {
- return 1 << pow_alloc;
- }
- void push_back(T v) {
- if (size_stored >= pow_alloc)
- realloc(size_stored+1);
- data[size_stored] = v;
- ++size_stored;
- }
- void pop_back() {
- --size_stored;
- if (size_stored < pow_alloc/2)
- shrink();
- }
- void print() const noexcept {
- for (size_t i = 0; i < size_stored; ++i)
- std::cout << data[i] << ' ';
- std::cout.put('\n');
- }
- };
- } //namespace container
Advertisement
Add Comment
Please, Sign In to add comment