C++

---

Languages

• C++ programs are compiled and are architectural-dependent, which means you have to compile the source code for different OS/machines to work.
• JAVA produces bytecode which is machine independent as machines have machine-specific JVM available.
• Python is an interpreted Language and runs/executes code line by line and generates output for each line and then looks at the next line.
• Javascript is a high-level, prototype-based object-oriented multi-paradigm, interpreted or JIT compiles, dynamic single-threaded, garbage-collected programming language with first-class functions and a non-blocking event loop concurrency model., more close to python in some sense.

Datatypes in C++

• int
• char
• long
• float
• double
• char*
• long long = long = long long int
• unsigned, signed
• bool

Type conversion

• C way

  • (double)x / y
  • blindly typecasts

• C++ way

  • static_cast<double> $x / y$
  • only typecasts if possible, otherwise it throws an error.

• char + char = int

• char - char = int

• int + int = int

• int - int = int

• int / int = int

• int * int = int

• int + double= double

• int - double = double

• int / double = double

• double / int = double

• double / double = double

• double * int = double

Precedence

Trick: PUMA'S REBL TAC

• Parenthesis (),[],{}
• Unary +,-,++,--,*(deref) , &(ref)
  • Postfix operator has higher precedence over deref or Prefix operator.
• Multiplicative *, /
• Addition +,-
• Shift >>, <<
• Relational <, >, <=, >=
• Equality =
• Binary &,|, ~
• Logical &&, ||, !
• Ternary ?:
• Assignment =, +=
• Comma ,

Associativity

Trick : AUT

• Only these are Right to left Associative
  • Ternary
  • Unary
  • Assignment
• Rest of them are L to R.

Array and its various ways of declaration.

// = sign may be ommitted here
int arr[] = {1,2,3};
int arr[4] = {1,2,3,4}
int arr[10]; // each elements have garbage value
int arr[10] = {} // Imp: set all elements to 0
int arr[10] = {0} // first to zero and rest to zero
int arr[10] = {9} // Imp: first to nine and rest to zero

// 2d array
int arr[2][3] = {{1,2,3}, {4,5,6}};
// no of rows are optional but no. of columns are compulsory.
int arr[][3] = {{1,2,3}, {4,5,6}};
int arr[][3] = {{1,2,3}, {4,5,6}};
char words[2][10] = {"shaurya", "singhal"} // valid

caution

• No index out of bound Checking in c++. 😭
• The C++ runtime does not perform bounds checking on array indices, so if an array named arr is declared of size 3 and you try to access arr[5], there is no telling what will happen. The program might crash due to a segmentation fault, or it might keep running while giving potentially incorrect results.
• Arrays are always passed as pointers to functions and length cannot be determined using sizeof(arr)/sizeof(arr[0]) inside function, therefore have to pass the length of the array as an argument to the function.
• Provides cache spatial locality of reference as arrays are stored continuously.
• Have to know the size before we create them. Solution: Vector.
• counting int array will give you the address of the first integer, whereas counting char array will print all characters till null character.

    int arr[10] = {1,2,3};
    char ch_arr[10] = {'1','2','3', '\0'};
    cout<<arr<<endl; // print address of 1(arr[0])
    cout<<ch_arr<<endl; // print "123".

References in C++

• Creates an alias.
• Must be assigned when declared.
• Cannot refer to another location.
• Cannot be null.
• Avoid copying larger objects during function calls.
• Helps in modifying the passed parameters to function.

Pointers in C++

• Can be assigned later.
• Can refer to another location.
• Can be null.
• Avoid copying larger objects during function calls.
• Helps in modifying the passed parameters to function.
• helps in returning multiple values. (just pass variables as a pointer as arguments to a function and assign return values to them).
• Helps in Dynamic Memory Allocation.
• In Implementing Data structures.
• * and ++ are both unary operators and have right-to-left associativity.
• Subtraction b/w pointers (p1-p2) is possible if both points to the same array and p1>=p2.
• Addition, multiplication, and division are not feasible on pointers.

Pointers and Array

    arr[0] is same as *(arr+0) = 0[arr]
    arr[2][1] is same as *(*(arr+2)+1) = 2[arr][1]

---

    int marks[] = {10,20,30};
    int* p = marks;

    cout<<marks // addresss of marks[0] = 0x7ffe6fdb5170
    cout<<p // addresss of marks[0] = 0x7ffe6fdb5170

    cout<<&marks // addresss of marks[0] = 0x7ffe6fdb5170
    cout<<&p // addresss of pointer variable p = 0x7ffe6fdb5168

    // ***** Imporant
    cout<<sizeof(marks) // 3*4 = 12
    cout<<sizeof(p) // 4

    cout<< marks++ // error
    cout<< ++p // address of marks[1]

    p =  marks // valid
    marks = p // error

    // this concept is differnt for character/char array(i.e. char*)
    char val='A';
    cout<<&val<<endl; // prints A rather than adress of A,
    // it is because of operator overloading of <<,
    // we can still print adress of char using typecasting of char adress (char*) to void*
    cout<<(void*) &val <<endl; // prints address here.

2d Array

• Using Static memory Allocation

#include <iostream>
using namespace std;

int main() {
  const int row = 2, col = 2;
  // static array initialization
  int staticArr[row][col] = { {1, 2}, {3, 4}};
  cout << "Static two-dimensional array: ";
  for(int i=0; i<row; i++)
    for(int j=0; j<col; j++)
      cout << staticArr[i][j] << " ";
  cout << endl;

• Using Dynamic memory Allocation

    // 2d array of size (10,20) + taking input in it
    int row =10, col=20;
    int** arr = new int*[row];
    for(int i=0; i<row; i++){
        arr[i] = new int[col];
        for(int j=0; j<col; j++){
            cin>>arr[i][j];
        }
    }

    // print
    for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            cout<<arr[i][j]<<" ";
        }
        cout<<endl;
    }

    // deletion
    for(int i=0; i<row; i++){
        delete [] arr[i];
    }
    delete [] arr;

• Can be stored in memory in

  • Row Major Order (RMO)
    • Store continuously row-wise
  • Column Major Order (CMO)
    • Store continuously col wise

• Gate Formulas

  • All Below Formulas Video

    • LB: Lower bound

    • UB: Upper bound

    • A[LB: HB] or A[LB...UB] => array has indexing from LB to HB both inclusive.

    • Number of elements in A[LB: UB] = UB - LB + 1

    • Address of A[i] when Array is stored in memory.

      • = Base + width * (Relative index)
      • = Base + width * (i - LB), Usually LB = 0 as A[0...n-1]
      • = Base + width * (i).

    • In 2D arrays(m X n)

      • Number of elements in A[LBi: UBi][LBj: UBj] = (UBi - LBi + 1) * (UBj - LBj + 1) .

      • If stored in Row Major Order in Memory, then address of A[i][j] will be:-

        • = Base + width * (Relative index)
        • = Base + width * (Number of elements before (i,j) th element), [TIP: for (0,0), relative index is 0, for (0, 1), relative index is 1, ... ]
        • = Base + width [(i - LBi) n + (j - LBj)]
        • = Base + width [i m + j]
        • 

      • If stored in Column Major Order in Memory, then address of A[i][j] will be:-

        • = Base + width * (Relative index)
        • = Base + width * (Number of elements before (i,j) th element), [TIP: for (0,0), relative index is 0, for (1, 0), relative index is 1, ... ]
        • = Base + width [(i - LBi) + (j - LBj) n]
        • = Base + width [i + j m]

Pairs with automatic destructuring

    vector<pair<int, bool>> vp;

    vp.push_back(make_pair(2,true));
    vp.push_back({3,false}); // automatci destructuring
    vp.push_back({4,false});
    vp.push_back({5,true});

    for(auto x: vp){
        cout << vp.first << " " << vp.second <<endl;
    }

    // auto Destructing - GOOD
    for(auto [a,b]: vp){
        cout << a << " " << b <<endl;
    }

Recursion on array and strings

• on Array,

  • doing a + 1, reduces size by 1, or take an index variable to indicate the starting point of the array.

  • Note in character array if the array is empty then at index 0, we will have null '\0'.

    char str[100];
    bool isTrue = str[0]=='\0'; // true aayega
    ```

  • check length of character array using s[i]!='\0'

    for(int i=0; s[i]!='\0'; i++){/* Do some work */}
    ```

• on String

  • do str.substr(index) or take a index variable to indicate the starting point of string.
  • Note in string as well if string is empty "" then at index 0 we will have null '\0'.

Global variables in C++

• variables declared outside any function, even main() are accessed by anyone, any function, any class and hence are called global variables.
• Should not use as it breaks the PURE function concept of the functional programming paradigm.

C-string

• C string is a 1D character array and is terminated by null character '\0'

    // Note: cout<<(address of char array a) -> prints value till found '\0'.
    // Note: cout<<(address of int array a) -> prints address..
    char name[] = {'s', 'h', 'a', 'u', 'r', 'y', 'a'}
    cout<<name; // will print name array complete. // may have a problem, so always put null character if declaring this way.
    char name[] = {'s', 'h', 'a', 'u', 'r', 'y', 'a', '\0'}; // recommended
    cout<<name; // more predictable or else do like
    char name[] ="shaurya" // complier will automatically add '\0'

• Utility function to work with cstring are available in <cstring> like

  1. strcpy(s1,s2)
  2. strcmp(s1,s2)
  3. strcat(s1,s2)
  4. strlen(s1)
  5. strch(s1,ch) // returns pointer to ch in s1
  6. strstr(s1,"sub") // return substring `sub` reference

C++ String

• C++ string is builtin on top of cstring and is a string class that stores characters as a sequence of bytes.
• Memory is allocated dynamically (no need to get the length of the string first).
• available in #include<string>
• take input via cin (till whitespace)
• use getline(cin, variable) to get the complete line as input

Imp: Appending characters/string to a string

```cpp
    `s += "something" // O(1) as no new string is created.`
    // Why? as internally it is implemented as character arr/vector and doing `+=` is like doing vector.push_back(), that's why string have push_back()/pop_back() method
    `s = s + "something" // O(n) as here new string is created.`
```

• Checking if a character exists in a string or not.

  • return str.find(ch) != string::npos

• str.method()

    - member functions
        - constructor()
        - destructor()
        - operator = ()

    - Iterator
        - begin() // important
        - end() // important
        - rbegin()
        - rend()

    - Capacity
        - capacity()
        - size() // important
        - length() // important
        - resize()
        - max_size()
        - clear()

    - element access
        - using indexing str[i], operator []() // important
        - at()
        - back() // get last item but does not pop it
        - front()

    - modifiers
        - operator +=() // with other variations <=, < ,> ...
        - append()
        - push_back()
        - pop_back() // only pops it does not return the popped value.
        - assign()
        - erase()
        - replace()

    - other
        - c_str() // get cstring from c++ string
        - substr(begin_index, length_of_substring) // **important
        - compare()
        - copy(chararray, length, position)
        - swap()
        - find(substring) // returns first occurence of substring
        - rfind(substring) // returns last occurence of substring
        - find_first_of(string) // returns first occurence of any character in string
        - find_last_of(string)
        - insert(position, string_to_insert)

cin vs cin.getline()

• getline also takes space b/w values as one entity.
• same as input() in python.

    // cin.getline(arr, maxsize, [delimiter]) // default delimiter='\n'
    char para[1000];
    cin.getline(para, 1000);
    cin.getline(para, 1000, ' '); // becomes cin
    cin.getline(para, 1000, '.'); // keep taking at max 1000 chars or till you got .

cin.get()

• can read chars including tabs('\t'), whitespace, ; , , or other special characters.

getline(cin, str)

• only for taking string as input in str

typedefs

    typedef long long int ll
    typedef unsigned long int ull

    // *** Testing long
    cout<<sizeof(long long)<<endl; // 8
    cout<<sizeof(long long int)<<endl; //8
    cout<<sizeof(long)<<endl; //8

    string str = "shaurya";
    string::iterator it;

    for(auto it = str.begin(); it != str.end(); it++){
        cout<<*it<<" ";
    }

    string::reverse_iterator it;

    for(auto rit = str.rbegin(); rit != str.rend(); rit++){
        cout<<*rit<<" ";
    }

struct vs class

• Use struct to bundle multiple items together.

• Everything is public by default in struct and private by default in class. Else everything is the same!

• when in a hurry use struct or pair(why? because, the default public).

  struct Pair{
      int first;
      int second;
  };
  
  Pair p;
  p.first = 1;
  p.second = 2;
  // or Pair p = {1, 2}
  // or Pair p{1, 2}
  // or change order using : Pair p = {.second = 1, .first= 2} called dedicated Initialization.
  cout<<p.first<<" " << p.second<<endl;
  // Note
  Pair *ptr = &p;
  (*ptr).first = 4
  // or
  ptr->second = 5

Dynamic Memory Allocation via new

• operator new
  • returns the pointer to the memory allocated.
  • always used for dynamic memory allocation.
  • calls the constructor for objects of class or struct

OOPS

• Use when we have many entities like working with database(models), making Banking Softwares, Designing Bank System etc.
• Concepts
  • Class
  • Object
  • Abstraction (APIs)
  • Data Hiding (Access Modifiers)
  • Encapsulation
  • 4 different Special Functions that are always available in a class
    • Constructor
    • Destructor
    • Copy Constructor
    • Copy Assignment Operator
  • Shallow Copy and Deep Copy
  • Inheritance, Composition.
    • C++ supports five types of inheritance they are as follows:
      • 1. Single inheritance
      • 2. Multilevel inheritance
      • 3. Multiple inheritance
      • 4. Hierarchical inheritance
      • 5. Hybrid inheritance
  • Polymorphism
  • Interfaces
    • An interface describes the behavior or capabilities of a C++ class without committing to a particular implementation of that class. The C++ interfaces are implemented using abstract classes,
    • A class is made abstract by declaring at least one of its functions as a pure virtual function. A pure virtual function is specified by placing "= 0" in its declaration.
    • Example: The following function is a pure virtual function.
      • cpp virtual void func() = 0;

C++ Ambiguity during Inheritance

• There may be a possibility that a class may inherit member functions with the same name from two or more base classes, and the derived class may not have functions with the same name as those of its base classes. If the derived class object needs to access one of the same-named member functions of the base classes, it results in ambiguity as it is not clear to the compiler which base’s class member function should be invoked.
• Avoid ambiguity using scope resolution operator
  • cpp object.class_name::method_name();

Polymorphism

• Polymorphism is considered one of the important features of Object-Oriented Programming. Polymorphism is a concept that allows you to perform a single action in different ways. Polymorphism is the combination of two Greek words. The poly means many, and morphs means forms. So polymorphism means many forms. Let’s understand polymorphism with a real-life example.

• Real Life Example: A person at the same time can have different characteristics. Like a man at the same time is a father, a husband, and an employee. So the same person possesses different behavior in different situations. This is called polymorphism.

• Two Types of Polymorphism

  • 1. Compile Time Polymorphism (static/early Binding)
    • Function Overloading
    • Operator Overloading
    • Default Arguments
  • 2. Runtime Polymorphism (Dynamic/late Binding)
    • The Runtime Polymorphism can be achieved by inheritance only.
    • Function Overriding
    • Operator Overriding
    • Virtual Functions: so to call function based on the object rather than pointer. (A way to achieve function overriding).
    • Happens when we have a baseclass pointer pointing to a subclass object. (Vehicle* v = new car), btw vice-versa is not possible.
    • Let both Vehicle and Car have a print function.
    • v -> print() will call vehicles print, not car prints.
    • but if we make function in the vehicle virtual then the car's print will be called.
    • Why? Let employee is a base-class and teacher, gardener, manager are sub-classes and each(base and sub) have a calculateSalary() method. we want to store all salaries of different employees in an array.
    • since the array can only hold homogeneous values. we have to use Employee* salaries[100] we can push each object of base classes into it. and call calculateSalary() in a loop. It works only if calculateSalary() is virtual in base-class.

Passing function to a function in cpp

• pass bool (&fun)(int a, int b) as a parameter.
  • It is a declaration of function [wrapping function name in parenthesis and add & is to avoid copy].

    // look last parameter
    void sortByMe(int*arr, int*arrend, bool (&fun)(int a, int b))

    bool cmp(int a, int b){
        return a<b;
    }

    sortByMe(arr,arr+n, cmp)

• Example 2

void wrapper(void (&gift)()){
    cout<<"wrapper"<<endl;
    gift();
}

void first_class_function(){
    cout<<"first class function"<<endl;
}

int main(){
    /** code here */
    wrapper(first_class_function);
    return 0;
}

Questions answered!

• What is Amortized Analysis?

  • Ans: Analysing the complexity approximately that if work is equally distributed, what is the work each one is doing. - Actual time complexity is sum of all subtasks, some of them is big & some is small but when you some them it is averaged out. - 1,1,1,1,n,1,1,1,1,n,1,1,1,1 = (2n+12)/n = O(1) - 1,2,1,1,4,1,1,1,1,8,1,1,1,1,1,1,1,1 = can be seen as each of them is doing 1.5 work rather than some 1 some 4,8,16. This is Amortized.

• What is Use of tail recursion in compiler or how it optimizes the performance?

  • add goto statement and change parameter explicitely and make instruction jump to start.

  • Ex 1: Print n natural numbers

      // tail recursion
      void printNumbers(int n){
          if(n < 0) return;
          cout << n << " ";
          printNumbers(n-1);
      }

  // Tail Recursion after Optimization (TRO)
  // Done Automatically by Compilers in Compiler's Code Optimization phase
  // Avoid adding a new entry to call Stack.
  // Avoid call registration, CALL/JUMP and RETURN Function instructions.
  // Converting call stack calls(recursive calls) to iterative
  // Hence optimizing performance
  void printNNumbers(int n){
      label comeback:
      if(n  < 0) return;
  
      cout<<n<<" ";
      n = n-1;
      goto comeback ;
  }

  • Ex 2: Calculation of Factorial

  // not-tail recursion  (head recursion)
  // Why? Because after the recurion is done, I still have operations to perform, multiply by n here.
  int fact(int n){
      if(n==0){
          return 1;
      }
      return n * fact(n-1);
  }

  // tail recursion
  void fact(int n, int &ans){
      if(n == 0){
          ans = 1
          return;
      }
      ans = ans * n;
      fact(n-1, ans);
  }
  
  int fact(int n){
      int ans = 1;
      factHelper(n, ans);
      return ans;
  }

  // Tail Recursion Optimization (TRO)
  void factHelper(int n, int &ans){
      label comeback:
      if(n == 0){
          ans = 1
          return;
      }
      ans = ans * n;
      n = n-1;
      goto comeback ;
  }
  int fact(int n){
      int ans = 1;
      factHelper(n, ans);
      return ans;
  }

Questions to be answered!

• NP Hard Problems?

• expansion of logn is a harmonic sum of the first n natural number(1+1/2+1/3+1/4+1/5+...)?

C++11 features

• Anonymous functions
  • return type will be inferred as bool by the compiler.

sort(a, a+n, [] (Student s1, Student s2) {
        return s1.name < s2.name
});

String Tokenization in C++

int main(){
    string input;
    getline(cin, input);

    istringstream is(input);
    string token;
    while(getline(is, token, ' ')){
        // token contains words seperated by space
        // use token.size()!=0 to avoid words without anything in it.
    }
}

vector<string> split(string& s, char delimiter) {
    vector<string> res;
    stringstream is(s);
    string token;

    while(getline(is, token, delimiter)) {
        if(token.size() != 0) res.push_back(token);
    }

    return res;
}

Xor using accumulator

accumulate(nums.begin(), nums.end(), 0, bit_xor<>());

Stream Manipulators

cout << floatValue; // print floating point with 4 decimal point
cout << fixed << floatValue; // print floating point with 6 decimal point
cout << fixed  << setprecision(x) << floatValue; // print floating point with x decimal point

cout << boolValue // print 0 for 0, 1 for 1
cout << boolalpha << boolValue // print false for 0, true for 1
cout << noboolalpha << boolValue // remove boolalpha effect if used previously in code

Adding spaces in digits

    const int N = 100000000;

    const int N = 1'00'000'000; // Both works

Thank you

• 🎉 You made it here. I believed in you.
• You are Awesome and a CPP Pro. 🫂