Iterators – look and say sequence algorithm

Look and say sequence is fun little exercise.. here is the code

#include <iostream>
#include <vector>
#include <string>
#include <numeric>

std::string looknsay(int num){
  // initialize vector with vector of ints.
  // add default seed value to it [1].
  std::vector<std::vector<int>> look_n_say_seq{{1}};
  // iterate over until the number n is reached.
  for(int n = 0; n <= num; n++){
    auto latest_sequence = look_n_say_seq.back();
    std::vector<int> next_sequence;
   // keep a pair of iterators to move across the latest sequence from vector.
    auto i = latest_sequence.begin();
    auto j = latest_sequence.begin();
    while(i < latest_sequence.end()){
      for(;*i==*j && j < latest_sequence.end();++j){}
      // distance will give the count
      next_sequence.push_back(std::distance(i, j));
      // *i will give the actual number to iterate on
      next_sequence.push_back(*i);
      i = j;
    }
    // insert newly created sequence into the vector.
    look_n_say_seq.push_back(next_sequence);
  }
  auto latest_sequence = look_n_say_seq.back();
 // accumulate - join vector of ints to make string and return
  return std::accumulate(std::next(latest_sequence.begin()), 
                         latest_sequence.end(),
                          std::to_string(*latest_sequence.begin()),
                          [](std::string s, int i){return s += std::to_string(i);});
}
int main(){
  std::cout << looknsay(0) << '\n';
  std::cout << looknsay(1) << '\n'; // 11
  std::cout << looknsay(2) << '\n'; // 21
  std::cout << looknsay(3) << '\n'; // 1211
  std::cout << looknsay(4) << '\n'; // 111221
  std::cout << looknsay(5) << '\n'; // 312211
}

Implicit type conversion – tricky scenario

Here are some of the scenarios where the implicit  type conversion can be unintuitive  and tricky.

  • implicit conversion between int, float and bool
    #include <iostream>
    
    void print(char x){
      std::cout << "in the print method that has char arg\n";
    
    }
    
    void print(int x){
      std::cout << "in the print method that has int arg\n";
    }
    
    void print(bool x){
      std::cout << "in the print method that has bool arg\n";
    }
    
    int main(){
    int x =1;
    char ch = 'c';
    char * c = &ch;
    print(*c); // in the print method that has char arg
    print(*c+1); //in the print method that has int arg
    return 0;
    }

c++ OOP Grammar

The c++ language is a pure object oriented language. c++ has a lot of rules and extensive grammar. It’s very hard to write exhaustive list but I am including here what I understood.

Constructors:

  • c++compiler provides 5 types of constructors if user has not provide any.
  • c++ constructors has to be public in order to be able to make instances of the class.
  • Example:
    class Vehicle{};
    1. Default Constructor:
      • c++ compiler provides a default constructor without any parameters.
      • If any of other constructors are defined by user, compiler does not provide the default constructor.
      • if user provides any (parameterized or non-parameterized ) constructor,
        the compiler still provides other 4 constructors.
      • class Vehicle {
          public: 
            Vehicle(){};
        };
    2. Copy Constructor:
      • c++ compiler provides a copy constructor that does member wise copy.
      • the parameter must be reference otherwise there is a compiler error.
      • the parameter should be CONST but not necessary.
      • if a copy constructor is provided without default/parameterized constructor, then user must provide default/parameterized constructor.
      • If an object is not created and assigned to another object, then copy assignment is called.
      • class Vehicle {
          public: 
            Vehicle(const Vehicle &v){};
            Vehicle(const Vehicle& obj){
            std::cout << "copy constructor called..\n";
          }
        };
      • If a class has reference or const members, then compiler does not provide default constructor. Example:
      • class A{
          int & _a;
          public:
            A(int & a):_a{a}{};
            // We need to use initializer list in copy
           // constructor to initialize/copy a reference
           // and a const member variable.
            A(const A& rhs):_a{rhs._a}{};
            A& operator=(const A& rhs){
              _a = rhs._a;
              return *this;
            };
        };
        
        class B{
          public:
            int * _b;
            B(int * b):_b{b}{};
        };
        
        
        class C{
          public:
            const int _c;
            C(const int c):_c{c}{};
        };
        
        
        int main(){
          int x = 1;
          A a(x);
        
          B b(&x);
          B b1 = b;
        
          std::cout << *b1._b << '\n' ;
        
          C c(10);
        }
    3. Copy assignment operator
      • c++ compiler provides a copy assignment operator that does member wise copy.
      • the parameter should be CONST but not necessary.
      • if a copy assignment operator is provided without default/parameterized constructor, then default/parameterized constructor is OPTIONAL.
      • If an object is created and then assigned to another object, then copy assignment is called.
      • class Vehicle {
        public: 
          Vehicle& operator=(constVehicle&& obj){
            std::cout << "move assignment operator called..\n";
            return *this;
          }
        };
    4.  Move constructor
      • c++ compiler provides a move constructor that moves the member variables.
      • If an object is not created and then moved to another object, then move operator is called.
      • if a move constructor is provided without default/parameterized constructor, then user must provide default/parameterized constructor .
    5. Move assignment Operator
      • c++ compiler provides a move assignment operator that moves the member variables.
      • If an object is created and then moved to another object, then move operator is called.
      • if a move assignment operator is provided without default/parameterized constructor, then default/parameterized constructor is OPTIONAL.

Following is code with all the examples:

class MyClass{
  public:
  MyClass() = default;

  MyClass(const MyClass& obj){
    std::cout << "copy constructor called..\n";
  }

  MyClass(MyClass && obj){
    std::cout << "move constructor called..\n"; 
  };

  MyClass& operator=(const MyClass& obj){
    std::cout << "copy assignment operator called..\n";
    return *this;
  }

  MyClass& operator=(const MyClass&& obj){
    std::cout << "move assignment operator called..\n";
    return *this;
  }
};

int main(){
  MyClass obj;
  MyClass obj2(obj); // copy assignment operator called..

  MyClass obj3;
  obj3 = obj; // copy assignment operator called..

  MyClass obj4;
  obj4 = std::move(obj); // move assignment operator called..

  MyClass obj5(std::move(obj2)); // move constructor called..

  std::cout << "test \n";
  return 0;
}

Converting Constructor

If a class provides parameterized constructor then it works as converting constructor. It can be used to instantiate the object but it is confusing. Example:

class X{
  int i;
  public:
    X(int i):i(i){}
    void print(){
      std::cout << i << '\n';
    }
};

int main(){
  X x = 20; // confusing!!
  x.print();
  return 0;
}

Use explicit keyword in order to prevent the converting constructor.

Destructor

destructor is provided for class unless user has provided one. Virtual destructors should be provided in order to achieve polymorphic behavior. The subclass object should be deleted with a base class pointer.

With a virtual destructor defined, the subclass destructor is called before base class.

Method overriding

  • if a sub-class defines a method with same name as from base class, then the method HIDES ALL the methods with the same name from base class (regardless of signatures of the methods.).
  • if a method is defined as a public method in base class and overridden as private or protected in the sub classes, it still will be publicly available.
  • Const and non const methods are different from each other.
  • Methods should be defined as ‘virtual’ in order to achieve polymorphic behavior.
    Example:

    class BaseClass{
      public:
      virtual void vprint(){
        std::cout << "in the BaseClass\n";
      }
      void print(){
        std::cout << "in the BaseClass\n";
      }
    };
    
    class SubClass: public BaseClass{
      public:
      virtual void vprint(){
        std::cout << "in the SubClass\n";
      }
      void print(){
        std::cout << "in the SubClass\n";
      }
    };
    
    void global_print(BaseClass & b){
      b.print(); //in the BaseClass
      b.vprint();// in the SubClass
    }
    
    int main(){
      BaseClass * b = new SubClass();
      b->print(); //in the BaseClass
      b->vprint(); // in the SubClass
    }
    
    

override keyword

c++11 introduced override keyword which can be used after method name in order to specify the method is overridden. If the keyword is not used, the virtual method can still be overridden in subclass. The advantages of override keyword:

  • override keyword ensures the method with same signature is defined in base class else it gives compilation error.
  • Its good documentation.

Method Overloading

  • Methods with (same name and ) default values to parameters are consider ambiguous. Example:
  •    int print(char x){
        std::cout << "in the print method that returns int\n";
       }
       int print(char x = 'c'){
          std::cout << "in the print method that returns int\n";
       }
    };

    Inheritance

  • Base class public member variables can not initialized using initializer lists.
  • class MyBaseClass{
      public:
      int _b;
    };
    
    class MyClass : public MyBaseClass{
      public:
      int _m;
      MyClass(int m): _m{m}, _b{0}{} // compiler error: 
    };
  • They should be instantiated by following ways:
  • class MyBaseClass{
      public:
      int _b;
      MyBaseClass(int b):_b{b}{}
    };
    
    class MyClass : public MyBaseClass{
      public:
      int _m;
      MyClass(int m, int b): _m{m}, MyBaseClass(b){}; // base class needs to have a parameterized constructor.
      // or MyClass(int m, int b): _m{m}{
      //    _b = b;
      //  };
    };

General method rules

  • constructors can not be virtual.
  • destructors should be virtual if the class is going to get inherited and polymorphic behavior is expected.
  • If a method takes non-const reference then a rvalue constant can not be passed to it. example:
  • void print(int& i){
      std::cout << i << '\n';
    }
    
    int main(){
      print(10);
      return 0;
    }
    
    //Solution: use constant reference like const int & i or int && i

     

  • Some methods like printing output to console using ostream << operator, the method must be defined as a friend method.
    class MyClass{
      int i;
      public:
        MyClass():i{18}{};
        friend std::ostream& operator << (std::ostream & o, MyClass & obj){
          o << obj.i << '\n';
        return o;
        }
    };
    
    int main(){
      MyClass m;
      std::cout << m << '\n';
      return 0;
    }
  • class defined with final keyword is not inheritable.
    class Class final{}; // this class is not inheritable now

Static Variables

  • static variables should be initialized outside the class definition. This is generally done in .cpp (implementation file). If the static members of class are not defined, then they generate an error like undefined member or reference. Example:
    class Class{
    public:
      static int count;
    
      void print(){
        count++;
        std::cout << count << '\n';
      }
    };
    
    int Class::count = 10;
    
    int main(){
      Class c;
      c.print();
      std::cout << Class::count<< '\n';
    }

Static Methods

  • Static methods can not be virtual because polymorphic behavior is limited to instances.
  • static methods can not be const else following error is generated.
    class StaticConst{
      static print() const {
        std::cout << "inside static const function \n";
      }
    };
    
    StaticConst::print(); // static member function cannot have 'const' qualifier
  • Static methods can have same name and signature as of non-static methods.

Sizeof Rules

  • if a class/struct does not have any member variables in it, its size is generally 1.
  • if a class/struct has a virtual method(s) then its size increases by 8 bytes in 64 bit linux/unix system. So a class with no member variables and 1+ any number of virtual methods, the size is 8 bytes.
  • Static variables size is not considered in the size of class/object.

Example:

class Class{
  public:
  static int count;

  virtual void print(){
    std::cout << count << '\n';
  }
};

int Class::count = 10;

int main(){
  Class c;
  c.print();
  std::cout << sizeof(c)<< '\n'; //8
}

Const member variables

  • if the const variables are defined in a class, they must be initialized else using them causes compilation error. Example:
    class X{
      public:
      const int m, n;
    
      void print(){
      std::cout << "m = " << m << " n = " << n << '\n';
      }
    };
    
    // error: call to implicitly-deleted default constructor of 'X'
      X x;
    // default constructor of 'X' is implicitly deleted because field 'm' of const-qualified type 'const int' would not be initialized
        const int m, n;

Automatic type casting

c++ allows method overloading, means the methods can have a same name but should have different signature (different return type and parameters). The automatic type casting has issues in defining method names including constructors.

For an example:

  1. int – float and vice versa
  2. int – double and vice versa
  3. int – char and vice versa
  4. any user defined type conversion

because of the automated type casting, methods(including constructors) with same name and castable types does not compile, example:

following code does not compile:

class MyClass{
  int x;
public:
   int print(char x){
    std::cout << "in the print method that returns int\n";
    return 0;
   }

   char print(char x){
    std::cout << "in the print method that returns char\n";
    return 'c';
   }

   double print(char x){
    std::cout << "in the print method that returns double\n";
    return 0.0;
   }
};

// Solution: use templates in place of defining so many methods with
// automatic type casted methods.

Initializer list

  • Initializer list must be used when using following types of member variable
    • the member variable is const like const int or const char
    • the member variable is a reference
    • initialization of base class.
    • name of variable is same as member function

Default and Delete keywords

  • c++11 provides default and delete keywords to control the method declaration.
  • non-parameterized constructors can be defined using default method as
    class MyClass{ 
      int x; 
      public:
        MyClass() = default; // this class has both constructors
        MyClass(char x){ };
  • Delete keyword introduced in c++11 is very useful like
    • making objects only movable and not copyable
    • implementing very famous design pattern like singleton.
    • deleting operator overridden methods for various purposes.
      • delete & operator method to stop users from taking address of objects.

Function Pointers

Way to call a function pointer is little bit cryptic. Example:
There is a struct with one function that returns addition. To store the pointer we can use auto but calling is the function is done as follows:

struct S{
  const int i = 10;
  S(const int _i):i{_i}{};

  int add(int x){
    return x+i;
  }
};

  S s(11);
  auto fptr = &S::add;
  std::cout << (s.*fptr)(11) << '\n'; // prints 22

 

std::queue operations

Iteration:

Iteration is very basic and important operation of any container type like std::vector, std::deque or std::list.

std::queue<int> q;
for(int i = 0; i <= 10; i++){
  q.push(i);
}
for(int i = 0; i <= 10; i++){
  std::cout << q.pop() << '\n';
}

Shuffle Queue:

Shuffling with extra space (using another deque)can be done as follows:

#include <iostream>
#include <queue>
#include <algorithm>
#include <random>
#include <deque>

int main(){
  std::queue<int> q;
  for(int i = 0; i <= 10; i++){
    q.push(i);
  }
 
 std::deque<int> d;
 for(int i = 0; i <= 10; i++){
  d.push_back(q.pop());
 }

  unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
  std::shuffle (d.begin(), d.end(), std::default_random_engine(seed));


  std::queue<int> empty;
  std::swap(q, empty);

  std::for_each(d.begin(), d.end(), [&q](const auto & i){q.push(i);});
  std::for_each(d.begin(), d.end(), [&q](const auto & i){std::cout << i << '\n';});
  
  for((int i = 0; i <= 10; i++){
   std::cout << q.pop() << '\n';
  }
  
}

Linked list using smart pointers

mike-alonzo-3347-unsplash

I have observed and code several versions of linked lists and came with my own implementation of linked list. This linked list uses smart pointers and supports operations like insert after, insert before, reverse and print etc for the list.

#include <iostream>
#include <memory>

template <typename T>
struct Node{
  T value;
  bool head = false;
  std::shared_ptr<Node<T>> next;

  Node(): head(true), value(-1){}; // head with -1 value
  Node(T value): head(false), value(value){}; // node

  std::shared_ptr<Node<T>> add_next(T value){
  next = std::make_shared<Node<T>>(value);
  return next;
  }
};

template<typename T>
struct List{
  std::shared_ptr<Node<T>> head;
  std::shared_ptr<Node<T>> tail;

  List(){
   head = std::make_shared<Node<T>>();
   tail = head;
  }

  void add_node(T value){
    tail->add_next(value);
    tail = tail->next; 
  }

 void print(){
   std::cout << std::string(100, '-') << '\n';
   auto current = head;
   while(current != nullptr){
     std::cout << current->value << '\t';
     current = current->next;
   }
   std::cout << '\n' << std::string(100, '-') << '\n';
 }

void reverse(){
  auto current = head;
  std::shared_ptr<Node<T>> next, prev;
  while(current != nullptr){
    next = current->next;
    current->next = prev;
    prev = current;
    current = next;
   }
   head = prev;
 }

void insert_after(T after_value, T value){
  auto current = head;
  while(current != nullptr){
   if(current->value == after_value){
     auto temp_next = current->next;
     auto node = create_node(value);
     current->next = node;
     node->next = temp_next;
     break;
   }
   current = current->next;
  }
 }

void insert_before(T before_value, T value){
  auto current = head;
  std::shared_ptr<Node<T>> prev;
  while(current != nullptr){
   if(current->value == before_value){
     auto node = create_node(value);
     node->next = current;
     prev->next = node;
   }
   prev = current;
   current = current->next;
  }
 }

 std::shared_ptr<Node<T>> create_node(T value){
   return std::make_shared<Node<T>>(value); 
  }
};

int main(){
 List<int> l; // initialize the linked list

 for(int i = 1; i <= 10; i++){
   l.add_node(i);
 }
  l.print();
  l.reverse();
  l.print();
  l.reverse();
  l.insert_after(1, 2);
  l.print(); 
  l.insert_before(8, 18);
  l.print(); 
  return 0;
}

Output:

g++ --std=c++17 linked_list.cpp -g -o linked_list && ./linked_list
-----------------------------------------------------------------------------------------------------
-1 1 2 3 4 5 6 7 8 9 10
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
10 9 8 7 6 5 4 3 2 1 -1
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-1 1 2 2 3 4 5 6 7 8 9 10
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-1 1 2 2 3 4 5 6 7 18 8 9 10
----------------------------------------------------------------------------------------------------

reverse in O(log n) time

The basic framework for divide and conquer algorithm can be used for any operations like reverse, checking if array is sorted etc. The possible implementation of reversing a string/vector is given as follows which takes O(n) time where n is size of collection string/vector.

template<class BidirIt>
void reverse(BidirIt first, BidirIt last)
{
 while ((first != last) && (first != --last)) {
 std::iter_swap(first++, last);
 }
}

Better algorithm for this can be given as follows:

#include <iostream>
#include <algorithm>
#include <string>

template <typename T>
void reverse_rotate(T first, T last){
 if((first == last) || std::next(first) == last) return;
 T middle = first;
 std::advance(middle, std::distance(first, last)/2);
 reverse_rotate(first, middle);
 reverse_rotate(middle, last);
 std::rotate(first, middle, last);
}

int main(){
 std::string s = "This is super cool";
 reverse_rotate(s.begin(), s.end());
 std::cout << s << '\n';
}

is_sorted in O(log n) time

Checking if array is sorted is simple, compare consecutive elements to check if next element is greater than the previous element. This takes O(n) time. The possible implementation of std::is_sorted is given as follows:

template <class ForwardIterator>
 bool is_sorted (ForwardIterator first, ForwardIterator last)
{
 if (first==last) return true;
 ForwardIterator next = first;
 while (++next!=last) {
 if (*next<*first) // or, if (comp(*next,*first)) for version (2)
 return false;
 ++first;
 }
 return true;
}

Here I came with an algorithm which is like quick sort and uses O(log n) time. Here is the implementation.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

template <typename T>
bool check_sorted(T start, T finish, bool sorted = true){
 if(start == finish) return true;

if(std::next(start) == finish) return *start <= *finish;

T middle = start;
 std::advance(middle, std::distance(start, finish)/2);

sorted &= check_sorted(start, middle);
 sorted &= check_sorted(middle, finish-1);
 return sorted;
}

int main(){
 std::vector<int> v(20);
 std::iota(v.begin(), v.end(), 1);
 bool sorted = check_sorted(v.begin(), v.end());
 std::cout << "v is sorted? : " << sorted << '\n';

std::vector<int> v2 {20, 1, 3, 5, 2, 1, 4, 19, 18, 10};
 sorted = check_sorted(v2.begin(), v2.end());
 std::cout << "v2 is sorted?: " << sorted << '\n';

std::vector<int> v3 {1,1,1,1,1,1,1,1,1,1,1,1,1,1};
 sorted = check_sorted(v3.begin(), v3.end());
 std::cout << "v3 is sorted?: " << sorted << '\n';

std::vector<int> v4 {10,1,1,1,1,1,1,1,1,1,1,1,1,1};
 sorted = check_sorted(v4.begin(), v4.end());
 std::cout << "v4 is sorted?: " << sorted << '\n';
}