amcbn

Dynamic Array (std::vector replacement)

Oct 24th, 2023 (edited)
756
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.33 KB | Source Code | 0 0
  1. // [A][M][C][B][N]
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. template<typename _Type>
  7. class dynamic_array {
  8. private:
  9.     _Type* table = nullptr;
  10.     int _capacity = 0;
  11.     int _size = 0;
  12.     void reserve(int _new_capacity) {
  13.         _Type* new_table = new _Type[_new_capacity];
  14.         for (int i = 0; i < _new_capacity; ++i) {
  15.             new_table[i] = i < this->_size ? table[i] : _Type();
  16.         }
  17.         delete[] table;
  18.         table = new_table;
  19.         this->_capacity = _new_capacity;
  20.     }
  21.     constexpr int fsb(int number) const {
  22.         for (int i = 0; i <= 4; ++i) {
  23.             number |= number >> (1 << i);
  24.         }
  25.         return (number + 1) >> 1;
  26.     }
  27.     constexpr int nfsb(int number) const {
  28.         return number ? fsb(number) << 1 : 1;
  29.     }
  30.     constexpr int lfsb(int number) const {
  31.         return number ? fsb(number) >> 1 : 0;
  32.     }
  33. public:
  34.     dynamic_array() {
  35.  
  36.     }
  37.     dynamic_array(int _size) {
  38.         resize(_size);
  39.     }
  40.     void resize(int _new_size) {
  41.         reserve(nfsb(_new_size));
  42.         _size = _new_size;
  43.     }
  44.     void assign(int _new_size, _Type _new_value) {
  45.         resize(_new_size);
  46.         for (int i = 0; i < _new_size; ++i) {
  47.             table[i] = _new_value;
  48.         }
  49.     }
  50.     int size() const {
  51.         return _size;
  52.     }
  53.     int capacity() const {
  54.         return _capacity;
  55.     }
  56.     bool empty() const {
  57.         return _size == 0;
  58.     }
  59.     _Type& operator[](int index) {
  60.         assert(index < this->_size);
  61.         return table[index];
  62.     }
  63.     _Type& front() {
  64.         assert(this->_size > 0);
  65.         return table[0];
  66.     }
  67.     _Type& back() {
  68.         assert(this->_size > 0);
  69.         return table[_size - 1];
  70.     }
  71.     void push_back(_Type new_value) {
  72.         if (_size == _capacity) {
  73.             reserve(nfsb(_capacity));
  74.         }
  75.         table[_size++] = new_value;
  76.     }
  77.     void pop_back() {
  78.         assert(this->_size > 0);
  79.         table[--_size] = _Type();
  80.         if (_size == lfsb(_capacity)) {
  81.             reserve(lfsb(_capacity));
  82.         }
  83.     }
  84.     void clear() {
  85.         delete[] table;
  86.         table = nullptr;
  87.         _capacity = 0;
  88.         _size = 0;
  89.     }
  90.     ~dynamic_array() {
  91.         clear();
  92.     }
  93. };
  94.  
  95. int main() {
  96.     dynamic_array<int> dynarr;
  97.     // push_back
  98.     dynarr.push_back(1);
  99.     // resize
  100.     dynarr.resize(3);
  101.     // size
  102.     cout << "Size: " << dynarr.size() << '\n';
  103.     // capacity
  104.     cout << "Capacity: " << dynarr.capacity() << '\n';
  105.     // pop_back
  106.     dynarr.pop_back();
  107.     cout << "Size: " << dynarr.size() << '\n';
  108.     cout << "Capacity: " << dynarr.capacity() << '\n';
  109.     // operator[]
  110.     for (int i = 0; i < dynarr.size(); ++i) {
  111.         cout << dynarr[i] << ' ';
  112.     }
  113.     cout << '\n';
  114.     // assign
  115.     dynarr.assign(5, 7);
  116.     dynarr.push_back(9);
  117.     cout << "Size: " << dynarr.size() << '\n';
  118.     // empty
  119.     cout << "Empty: " << boolalpha << dynarr.size() << '\n';
  120.     // front
  121.     cout << "Front: " << dynarr.front() << '\n';
  122.     // back
  123.     cout << "Back: " << dynarr.back() << '\n';
  124.     for (int i = 0; i < dynarr.size(); ++i) {
  125.         cout << dynarr[i] << ' ';
  126.     }
  127.     cout << '\n';
  128.     // clear
  129.     dynarr.clear();
  130.     cout << "Size: " << dynarr.size() << '\n';
  131.     cout << "Empty: " << boolalpha << dynarr.size() << '\n';
  132. }
  133.  
Advertisement
Add Comment
Please, Sign In to add comment