JustAnotherCatgirl

My vector

Nov 30th, 2023 (edited)
183
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.92 KB | None | 0 0
  1. #include <memory>
  2. #include <utility>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <exception>
  6. #include <stdexcept>
  7. #include <iostream>
  8.  
  9. namespace container {
  10.  
  11.     template <typename T = int, typename Alloc = std::allocator<T>>
  12.     class vector {
  13.         using alloc_t = std::allocator_traits<Alloc>;
  14.        
  15.         std::allocator<T> alloc;
  16.         size_t size_stored;
  17.         size_t pow_alloc;
  18.         T *data;
  19.        
  20.         constexpr static size_t upper_2_power(size_t n) {
  21.             return 8*sizeof(size_t) - __builtin_clzl(n);
  22.         }
  23.        
  24.         void realloc(size_t n, bool init = false) {
  25.             size_t bytes = 1 << pow_alloc;
  26.             if (n <= bytes) return;
  27.             size_t new_pow = upper_2_power(n);
  28.             T* new_data = alloc_t::allocate(alloc, 1 << new_pow);
  29.             if (!init) {
  30.                 for (size_t i = 0; i < size_stored; ++i)
  31.                     new_data[i] = data[i];
  32.                 alloc_t::deallocate(alloc, data, 1 << pow_alloc);
  33.             }
  34.             pow_alloc = new_pow;
  35.             data = new_data;
  36.         }
  37.         void shrink() {
  38.             T* new_data = alloc_t::allocate(alloc, size_stored);
  39.             for (size_t i = 0; i < size_stored; ++i)
  40.                 new_data[i] = data[i];
  41.             alloc_t::deallocate(alloc, data, pow_alloc);
  42.             data = new_data;
  43.         }
  44. public:
  45.         vector() : alloc{}, size_stored{0}, pow_alloc{0}, data{nullptr} {}
  46.         vector(size_t n) : vector(n, T{}) {}
  47.         vector(size_t n, T val) : alloc{}, size_stored{n}, pow_alloc{0}, data{nullptr} {
  48.             realloc(n, true);
  49.             for (T* p = data; p < data + size_stored; ++p)
  50.                 *p = val;
  51.         }
  52.         vector(const vector& other) : alloc{}, size_stored{other.size_stored}, pow_alloc{0}, data{nullptr} {
  53.             realloc(other.size(), true);
  54.             for (size_t i = 0; i < other.size(); ++i)
  55.                 data[i] = other.data[i];
  56.         }
  57.         vector& operator=(const vector& other) {
  58.             size_stored = other.size_stored;
  59.             realloc(other.size(), true);
  60.             for(size_t i = 0; i < other.size(); ++i)
  61.                 data[i] = other.data[i];
  62.             return *this;
  63.         }
  64.         vector(vector&& other) : alloc{}, size_stored{0}, pow_alloc{0}, data{nullptr} {
  65.             std::swap(size_stored, other.size_stored);
  66.             std::swap(pow_alloc, other.pow_alloc);
  67.             std::swap(data, other.data);
  68.             std::swap(alloc, other.alloc);
  69.         }
  70.         vector& operator=(vector&& other) {
  71.             size_stored = std::exchange(other.size_stored, 0);
  72.             pow_alloc = std::exchange(other.pow_alloc, 0);
  73.             data = std::exchange(other.data, nullptr);
  74.             std::swap(alloc, other.alloc);
  75.             return *this;
  76.         }
  77.         ~vector() {
  78.             if (data != nullptr)
  79.                 alloc_t::deallocate(alloc, data, 1 << pow_alloc);
  80.         }
  81.         T& operator[](size_t i) noexcept {
  82.             return data[i];
  83.         }
  84.         T& get(size_t i) noexcept(false) {
  85.             if (i >= size_stored)
  86.                 throw std::out_of_range("Vector index out of range");
  87.             return data[i];
  88.         }
  89.         size_t size() const noexcept {
  90.             return size_stored;
  91.         }
  92.         size_t capacity() const noexcept {
  93.             return 1 << pow_alloc;
  94.         }
  95.         void push_back(T v) {
  96.             if (size_stored >= pow_alloc)
  97.                 realloc(size_stored+1);
  98.             data[size_stored] = v;
  99.             ++size_stored;
  100.         }
  101.         void pop_back() {
  102.             --size_stored;
  103.             if (size_stored < pow_alloc/2)
  104.                 shrink();
  105.         }
  106.         void print() const noexcept {
  107.             for (size_t i = 0; i < size_stored; ++i)
  108.                 std::cout << data[i] << ' ';
  109.             std::cout.put('\n');
  110.         }
  111.     };
  112.  
  113. } //namespace container
  114.  
  115.  
Advertisement
Add Comment
Please, Sign In to add comment