Vector Implementation - 2

The slippery road is mostly over, the journey of vectors will be a bit smoother from now on.

The pop_back() function

If the user wants to get rid of the last element of the vector, let's reduce the size by 1; that's it! Also, for now, let's do nothing if the vector is already empty. (the inbuilt C++ vector throws an error, though)

Whenever a push_back happens later on, the space could be re-used by some other element.

  void pop_back() {
    if(cur_size)
      cur_size--;
  }

The back() function

The back() function is a simple yet valuable function to access the last element of the vector and mind you, it doesn't just return the value of the last element; it returns the last element by reference.

  int & back() {
    return arr[cur_size - 1];
  }

When I say that it passed the last element by reference, let me explain what that means. Let's say the last element of the vector v is equal to 5 right now. If I do v.back() = 10, the last element will actually change to 10.

Random Access: the [] operator

Now, from arrays, we remember that if we want to access the element at index i of an array arr, we could simply do it using arr[i].

Let's try to make it so that the same can be done with our custom vector.

	int & operator[](int i) {
		return arr[i];
	}

We're basically overloading the [] operator in our class, so that whenever someone does v[i], we return the i^th element of the internal array, by reference.

I hope it's pretty clear from the code implementations of the above functions that their time complexities are O(1)

Overall Code

We've seen the snippets of different parts of the whole code so far. Below is the overall vec class, which has our own custom vector implemented.

class vec {
  int *arr;
  int cur_size, cur_cap;
public:

  // constructing with an array of size 1.
  vec() {
    arr = new int[1];
    cur_size = 0;
    cur_cap = 1;
  }

  void push_back(int num) {
    if(cur_size < cur_cap)
      arr[cur_size] = num, cur_size++;

    else {
      int *new_arr = new int[2*cur_cap];

      for(int i = 0; i < cur_size; ++i)
        new_arr[i] = arr[i];

      delete[] arr;
      arr = new_arr;
      cur_cap *= 2;

      arr[cur_size] = num;
      cur_size++;
    }
  }

  void pop_back() {
    if(cur_size)
      cur_size--;
  }

  void print_all() {
    for(int i = 0; i < cur_size; ++i)
      cout << arr[i] << ' ';
    cout << '\n';
  }

  int size() {
    return cur_size;
  }

  int capacity() {
    return cur_cap;
  }

  int & back() {
    return arr[cur_size - 1];
  }

  int & operator[](int i) {
    return arr[i];
  }
};

Feel free to copy it into an online compiler and play around with it. In fact, I insist.

Templated Vector

Ab itna kuch kar hi liya h, toh yeh bhi sahi (We've already learnt a lot of things, then why not this as well?)

When we used the in-built C++ vector, it wasn't just a DS that could contain int, right? It was a templated class, where if we passed int, it would create a vector of integers; if we passed string, it would create a vector of strings;

In fact, if we passed elephant, it would probably create a vector of elephants as well, as long as an elephant class is created in the code.

In this section, I'll showcase the code to do so. Here goes.

template <typename T>
class vec {
  T *arr;
  int cur_size, cur_cap;
public:

  // constructing with an array of size 1.
  vec() {
    arr = new T[1];
    cur_size = 0;
    cur_cap = 1;
  }

  void push_back(T num) {
    if(cur_size < cur_cap)
      arr[cur_size] = num, cur_size++;

    else { 
      T *new_arr = new T[2*cur_cap]; 

      for(int i = 0; i < cur_size; ++i)
        new_arr[i] = arr[i];

      delete[] arr; 
      arr = new_arr; 
      cur_cap *= 2;

      arr[cur_size] = num;
      cur_size++;
    }
  }

  void pop_back() {
    if(cur_size)
      cur_size--;
  }

  void print_all() {
    for(int i = 0; i < cur_size; ++i)
      cout << arr[i] << ' ';
    cout << '\n';
  }

  int size() {
    return cur_size;
  }

  int capacity() {
    return cur_cap;
  }

  T & back() {
    return arr[cur_size - 1];
  }

  T & operator[](int i) {
    return arr[i];
  }
};

To summarize the code, all we've done is define a template above the class using: template <typename T> and then used T as the type of the relevant variables, instead of using int.