Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // [A][M][C][B][N]
- #include <bits/stdc++.h>
- using namespace std;
- template<typename _Type>
- class dynamic_array {
- private:
- _Type* table = nullptr;
- int _capacity = 0;
- int _size = 0;
- void reserve(int _new_capacity) {
- _Type* new_table = new _Type[_new_capacity];
- for (int i = 0; i < _new_capacity; ++i) {
- new_table[i] = i < this->_size ? table[i] : _Type();
- }
- delete[] table;
- table = new_table;
- this->_capacity = _new_capacity;
- }
- constexpr int fsb(int number) const {
- for (int i = 0; i <= 4; ++i) {
- number |= number >> (1 << i);
- }
- return (number + 1) >> 1;
- }
- constexpr int nfsb(int number) const {
- return number ? fsb(number) << 1 : 1;
- }
- constexpr int lfsb(int number) const {
- return number ? fsb(number) >> 1 : 0;
- }
- public:
- dynamic_array() {
- }
- dynamic_array(int _size) {
- resize(_size);
- }
- void resize(int _new_size) {
- reserve(nfsb(_new_size));
- _size = _new_size;
- }
- void assign(int _new_size, _Type _new_value) {
- resize(_new_size);
- for (int i = 0; i < _new_size; ++i) {
- table[i] = _new_value;
- }
- }
- int size() const {
- return _size;
- }
- int capacity() const {
- return _capacity;
- }
- bool empty() const {
- return _size == 0;
- }
- _Type& operator[](int index) {
- assert(index < this->_size);
- return table[index];
- }
- _Type& front() {
- assert(this->_size > 0);
- return table[0];
- }
- _Type& back() {
- assert(this->_size > 0);
- return table[_size - 1];
- }
- void push_back(_Type new_value) {
- if (_size == _capacity) {
- reserve(nfsb(_capacity));
- }
- table[_size++] = new_value;
- }
- void pop_back() {
- assert(this->_size > 0);
- table[--_size] = _Type();
- if (_size == lfsb(_capacity)) {
- reserve(lfsb(_capacity));
- }
- }
- void clear() {
- delete[] table;
- table = nullptr;
- _capacity = 0;
- _size = 0;
- }
- ~dynamic_array() {
- clear();
- }
- };
- int main() {
- dynamic_array<int> dynarr;
- // push_back
- dynarr.push_back(1);
- // resize
- dynarr.resize(3);
- // size
- cout << "Size: " << dynarr.size() << '\n';
- // capacity
- cout << "Capacity: " << dynarr.capacity() << '\n';
- // pop_back
- dynarr.pop_back();
- cout << "Size: " << dynarr.size() << '\n';
- cout << "Capacity: " << dynarr.capacity() << '\n';
- // operator[]
- for (int i = 0; i < dynarr.size(); ++i) {
- cout << dynarr[i] << ' ';
- }
- cout << '\n';
- // assign
- dynarr.assign(5, 7);
- dynarr.push_back(9);
- cout << "Size: " << dynarr.size() << '\n';
- // empty
- cout << "Empty: " << boolalpha << dynarr.size() << '\n';
- // front
- cout << "Front: " << dynarr.front() << '\n';
- // back
- cout << "Back: " << dynarr.back() << '\n';
- for (int i = 0; i < dynarr.size(); ++i) {
- cout << dynarr[i] << ' ';
- }
- cout << '\n';
- // clear
- dynarr.clear();
- cout << "Size: " << dynarr.size() << '\n';
- cout << "Empty: " << boolalpha << dynarr.size() << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment