Skip to content

Vector

Vector is Dynamic array structure in c++

Operations & time complexity

Member Function Running Time
push_back() $O(1) amortized$
pop_back() $O(1)$
empty() $O(1)$
reserve() $O(n)$
operator [] $O(1)$

Implementation

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
using size_t = unsigned long;

template<typename T>
class Vector {
    size_t _size;
    size_t _capacity;
    T* _buf;
    public:
    // constructors

    // Vector(SomeType); //"ordinary constructor"
    Vector(int k) {
       _size = 0;
       _capacity = k;
       _buf = new T[_capacity];
    }
    // Vector(); //default constructor
    Vector() {
        _size = 0;
        _capacity = 0;
        _buf = new T[_capacity];
    }
    // Vector(const &X); // copy constructor
    // Vector(&&X); //move constructor
    // &Vector operator=(const Vector&); //copy assignment: cleanup target and copy
    // &Vector operator=(Vector&&); // move assignment: cleanup target and move
    //~Vector(); //destructor: cleanup
    ~Vector() {
        delete[] _buf;
    }

    // capacity: 
    size_t size() {
        return _size;
    }

    void resize(size_t n) {
        _size = n;
    }

    size_t capacity() {
        return _capacity;
    };
    bool empty() {
        return _size == 0;
    };
    // unsigned int max_size();
    void reserve(size_t n) {
        //Requests that the vector capacity be at least enough to contain n elements.
        if (_size >= n) return;
        T* _temp = new T[n];

        for (size_t i = 0; i < _size; i++) {
            _temp[i] = _buf[i];
        }
        _capacity = n;
        delete[] _buf;
        _buf = _temp;
    }
    // shrink_to_fit()


    //element access:
    T back();
    // operator[]()
    T& operator[](int idx) {
        return _buf[idx];
    }
    T operator[](int idx) const{
        return _buf[idx];
    }
    // at()
    // front()
    // data() 

    //Modifiers
    void clear() {
        resize(0);
    };
    void push_back(T const &val) {
        if (_size == _capacity) {
            if (_capacity) {
            reserve(_capacity << 1);
            } else {
                reserve(1);
            }
        }
        _buf[_size++] = val;
    };
    void pop_back() {
        _size--;
    };
    // assign()
    // insert()
    // erase()
    // emplace()
    // emplace_back


    //Iterators 
    T* begin() {
        return &_buf[0];
    }
    T* end() {
        return &_buf[0] + _size;
    };
    //T* rbegin();
    //T* rend();
    //T* const cbegin();
    //T* const cend();
    //T* const crbegin();
    //T* const crend();
};
  1. Letters Shop :star::star: :link:

Stack

Analysis (Later..)

You can add some mathematical things here using KaTex

as a block tag $$ T(N) = O(N*M) $$

or as a inline tag $T(N) = O(N) $

Contributers

08.13.2019 :tada: jchrys

Comments