Question

02. Log N Vector

Due Sunday by 11:59pm

Points 149

O(log(N)) Vector

std::vector is pretty cool but it has one big problem: every once in a while, push_back has to create a whole new array and copy a bunch of elements which is O(n)! Luckily, we can do better, in terms of Big-O. The goal of this homework is to write a class that behaves like a vector but without the O(n) push_back.

Whenever we run out of space, we'll still allocate an array that's twice as big as the last one but instead of copying all the old elements to it, we'll keep all the current elements where they are and store new ones in the new array until it's full. One way to implement this is to have an std::vector of arrays. If our vector is called "v", then v[0] is an array of size 1, v[1] would be an array of size 2, v[2] would have size 4, ..., v[x] would have a size of 2x.

v[O][O] vIO] vI1] v[2] v[21[0] v21vI2]12 v[21[3] v[X] VIX

Before you start writing code, figure out how to take an index into our data structure and convert it to the index in "v". For example, index 0 corresponds to v[0][0] and index 6 corresponds to v[2][3]. Feel free to talk to anyone, especially other students, for help with this part of the assignment!

Starter Code

log_n_vector.h

#ifndef _log_n_vector_h_
#define _log_n_vector_h_

#include <cmath>
#include <memory>
#include <vector>

template <typename T>
class LogNVector {
  // These member variables are suggested and not required!
  // Feel free to use change the variable names or types, as long as you
  // follow the spirit of the assignment.
  std::vector<std::unique_ptr<T[]> > arrays_;
  int size_, capacity_;
public:
  LogNVector() {
    // TODO
  }
  LogNVector(const LogNVector& other) : LogNVector() {
    // TODO
  }
  LogNVector(std::initializer_list<T> ilist) : LogNVector() {
    // TODO
  }
  ~LogNVector() {
    // TODO
  }

  int size() const noexcept {
    // TODO
  }
  int capacity() const noexcept {
    // TODO
  }
  void push_back(const T& value) {
    // TODO
  }
  const T& operator[](int index) const {
    // TODO
  }
  T& operator[](int index) {
    // TODO
  }
};

#endif // _log_n_vector_h_

manual_test.cpp

#include <iostream>

#include "log_n_vector.h"

using std::cout;
using std::endl;

int main() {
  LogNVector<int> v = {0, 11, 22, 33, 44, 55, 66, 77, 88, 99, 110, 121};
  cout << "v[0] == " << v[0] << ",    &v[0] == " << &v[0] << endl;
  for (int j = 1; j < v.size(); ++j) {
    // All the elements in the same array should have sequential addresses.
    // For example, &v[2] == &v[1] + 1
    // However, there's no guarantee that &v[1] == &v[0] + 1.
    cout << "v[" << j << "] == " << v[j] << ",    "
         << "&v[" << j << "] - &v[" << j - 1 << "] == "
         << &v[j] - &v[j - 1] << endl;
  }
  return 0;
}

$ clang -pedantic -Wall -lm -lstdc++ -lpthread -std=c++14 -o example log_n_vector/manual_test.cpp
$ ./example

v[0] == 0,    &v[0] == 0xd57c20
v[1] == 11,    &v[1] - &v[0] == 16
v[2] == 22,    &v[2] - &v[1] == 1
v[3] == 33,    &v[3] - &v[2] == -9
v[4] == 44,    &v[4] - &v[3] == 1
v[5] == 55,    &v[5] - &v[4] == 1
v[6] == 66,    &v[6] - &v[5] == 1
v[7] == 77,    &v[7] - &v[6] == 33
v[8] == 88,    &v[8] - &v[7] == 1
v[9] == 99,    &v[9] - &v[8] == 1
v[10] == 110,    &v[10] - &v[9] == 1
v[11] == 121,    &v[11] - &v[10] == 1

Answer 1

main.cpp
-------------------------------------------------------------------
#include <iostream>

#include "log_n_vector.h"

using std::cout;
using std::endl;

int main() {
    LogNVector<int> v = {0, 11, 22, 33, 44, 55, 66, 77, 88, 99, 110, 121};
    cout << "v[0] == " << v[0] << ",    &v[0] == " << &v[0] << endl;
    for (int j = 1; j < v.size(); ++j) {
      
        cout << "v[" << j << "] == " << v[j] << ",    "
             << "&v[" << j << "] - &v[" << j - 1 << "] == "
             << &v[j] - &v[j - 1] << endl;
    }
    return 0;
}
--------------------------------------------------------------------
log_n_vector.h
-----------------------------------
#ifndef _log_n_vector_h_
#define _log_n_vector_h_

#include <cmath>
#include <memory>
#include <vector>

template <typename T>
class LogNVector {

private:
    std::vector<std::unique_ptr<T[]> > arrays;
    int size_;
    int capacity_;

public:
    LogNVector() {
        this->size_ = 0;
        this->capacity_ = 0;
    }

    LogNVector(const LogNVector& other) : LogNVector() {
        int size = other.size();
        for(int k = 0; k < size; k++)
            this->push_back(other[k]);
    }

    LogNVector(std::initializer_list<T> ilist) : LogNVector() {
        typename std::initializer_list<T>::iterator iter;
        for (iter = ilist.begin(); iter != ilist.end(); iter++)
            this->push_back(*iter);
    }

    ~LogNVector() {
        // Destructor not necessary. Already handled by std::unique_ptr
        /*int numArrays = this->arrays.size() - 1;
        while(numArrays >= 0)
        {
          this->arrays[numArrays].reset();
          --numArrays;
        }*/
    }

public:
    int size() const noexcept {
        return this->size_;
    }
    int capacity() const noexcept {
        return this->capacity_;
    }

public:
    void push_back(const T& value) {

        if(this->size_ == this->capacity_)
            this->createNextArray();

        int lastArr = this->getLastArrNum();
        int arrNextLoc = this->size_ - getConsecMaxArrSize(lastArr - 1);

        this->arrays[lastArr][arrNextLoc] = value;
        size_ += 1;
    }

public:
    const T& operator[](int index) const {
        int arrNum = log2(index + 1);
        int position = index - getConsecMaxArrSize(arrNum - 1);
        return this->arrays[arrNum][position];
    }
    T& operator[](int index) {
        int arrNum = log2(index + 1);
        int position = index - getConsecMaxArrSize(arrNum - 1);
        return this->arrays[arrNum][position];
    }

private:
    void createNextArray()
    {

        int nextSize = getArrMaxSize( getLastArrNum() + 1 );
        this->arrays.emplace_back(new T[nextSize]);
        this->capacity_ += nextSize;
    }

    int getLastArrNum() const
    {

        return this->arrays.size() - 1;

        //return log2(capacity + 2) - 1;
    }

    int getArrMaxSize(int num) const
    {

        if(num < 0)
            return 0;
        return exp2(num);
    }

    int getConsecMaxArrSize(int num) const
    {

        int total = 0;
        for (int k = 0; k <= num; k++)
            total += getArrMaxSize(k);
        return total;
    }

};

#endif