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.

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  #include  #include  template  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<:unique_ptr> > arrays_; int size_, capacity_; public: LogNVector() { // TODO } LogNVector(const LogNVector& other) : LogNVector() { // TODO } LogNVector(std::initializer_list 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  #include "log_n_vector.h" using std::cout; using std::endl; int main() { LogNVector v = {0, 11, 22, 33, 44, 55, 66, 77, 88, 99, 110, 121}; cout  
$ 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 
  v[O][O] vIO] vI1] v[2] v[21[0] v21vI2]12 v[21[3] v[X] VIX  v[O][O] vIO] vI1] v[2] v[21[0] v21vI2]12 v[21[3] v[X] VIX