c++ quick sort

C++ quick sort

Quick sort is a powerful sorting alogrithm. It sort a set in O( n*log(n) ).
There are bad cases which the big O can be O(n^2). However, the case is very very rare.

In order to understand this sorting algoritm, you need to know what recussive funtion..
If you do not know that, think it as using same function over and over; you will see that soon.

Let's say that you would like to sort the following array.

In order to do quick sort, you need two functions.

One is called, "quick_sort." The other one is called "partition."

"quick_sort" calls the "partition".
"partition" picks one of array value( only one!!!!), place the value to right position and return the position of value

quick_sort

void quickSort (int array[], int low, int high)
{
    if( low < high ){

        int position = partition(array, low, high);
        quickSort (array, low, position-1);
        quickSort (array, position+1, high);
    }
    else{
        return;
    }
}

array = arrary that you want to sort
low = first index of set
high = last index of set

The first thing the "quick_sort" is checking whether the low is smaller than high.
It may look strange to you. However, if you read the following three line, you can understand the reason.
After chekcing the condition, "quick_sort" calls "partition" to place one element to right poisiton in the array.
"partition" makes sure one element of the array is in the right position and returns position.

 The position is used to create two "quick_sort"s.

        quickSort (array, low, position-1);   -----> low = low           position -1 = high
        quickSort (array, position+1, high); ------> low = position+1     high = high

"quick_sort" makes "quick_sort"s over and over until low >= high.

This kind of function is called recursive function.


Then I will move on to the "partiton"

 Just like "quick_sort", you have three parameters arary, low high

        int partition (int array[], int low, int high)

 In the you need to have three tools
They are
               i = index
               j = index
               pivot_val = array[ high ]

It would be like this

 If array[i] > pivot_val, increment i by one
        6                3

If array[i] <= pivot_val, switch array[i] and array[j]. and increament i and j by one.
          1                3
        

Do this untill i reach "high"

Then switch array[i] and array[j]

The element is in yellow box is placed right postion. "partiton", returns the position of this.

"quick_sort" calls "quick_sort"s to work on The rest elemnt of array

The power of quick sort is that everytime, if place a element in right postiion, it it will breaks array into small pieces for sorting.

I made a sample code.

-------------------------------------------------------------------------------------------------------------------------
 The following is practice code. If you have suggestion or correction, please feel free to leave comment.

#include <iostream>
#include <functional> // i am using mac so i need this to use namespace std
#include <ctime>
#include <cstdlib>


using namespace std;

void quickSort (int array[], int low, int high);
int partition (int array[], int lcow, int high);

int main()
{
    srand(time(0));
    int array[8] = {7,6,4,1,20,4,5,7};
    int len = 8;

    /*
    // populate array with random number between 0 to 99
    for (int i = 0; i < len; i++)
    {
        array[i] = rand()%100;
    }
    */
    quickSort(array, 0, 7);

    //print
    for (int i = 0; i < len; i++)
    {
        cout << array[i] << " ";
    }
    cout << endl;

}

/*
 * @brief Do quick sort (recursive function)
 * @param int array[] - array that is needed to be sort
 * @param int low - min bound for sorting
 * @param int high - max bound for sorting
 * @return void (call by referece) sorted array
 */
void quickSort (int array[], int low, int high)
{

    if( low < high ){
        // after the partition, val in the position is sorted
        int position = partition(array, low, high);
        cout << "position " << position << endl;
        // sort values before the postion
        quickSort (array, low, position-1);
        // sort values after the position
        quickSort (array, position+1, high);

    }

    // if row and high are same, there is nothing to be sorted, so termimate the sorting
    else{
        return;
    }
}

/*
 * @brief Pick a pivot and put it in the right position
 * @param int array[] - array that is needed to be sort
 * @param int row - min bound for sorting
 * @param int high - max bound for sorting
 * @return index of pivot
 */
int partition (int array[], int low, int high)
{
    int tmp;

    int pivot_val = array[high];

    int j=low;
    int i;
    for(i=low; i<high; i++){
        if( array[i] <= pivot_val ){
            tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
            j++;
        }
    }
    tmp  = array[high];
    array[high] = array[j];
    array[j] = tmp;

    return j;

}





 

c++ bloom filter

c++ bloom filter

Lets say that you have a 500000 lengh sentence

AGEGIOGRNOSEGSNOERNKLDVLLKNFKJEGRKLN...................GAGEADGE

And you want to convince people that there aren''t AAGTR, GTAGG, GGGGG int the string.

One way is chekcing every 5 strings like following. If you do not find them, you can conclude that there are not AAGTR, GTAGG, GGGGG
 
AGEGI
   GEGIO
      EGIOG
          ...........................EADGE
This way works but it is not very good.
For every input you have to compare 499995 times

There is a much better way than this!!!!
You can use bloom filter and the complexity is O(1) ; actually close to O(1), it is not exectly O(1)

Bloom filter is a good data structure that tell you a object is definitly not in the the set of objects.
However, it only can tell you that the object is probably in the set of object; the object may not in the set of objects.

How to

1) First thing you have to do is making a binary array based on a set of object.

Make an int array. The length of array is determined by you. You need to make it big enough; small one is bad too. I will introduce a fomula leter....
If you make one, initialize to zero

2) Then you need obtain objects
If you use the above example, every 5 length of strings are considered as an object.

AGEGIOGRNOSEGSNOERNKLDVLLKNFKJEGRKLN...................GAGEADGE

AGEGI
   GEGIO
      EGIOG
          ...........................EADGE

Once you have a set of objects (5 length characters), apply several hash functions to get hash values for each objects.

The hash values are index of the array. If the array[hashval] is 0, change to 1

While you are putting 1 in the array, you will face hash collision.. like the following..

It is ok, leave them to be 1.


If the array contains all hash values of objects, you are ready to do the bloom filtering


3) let's do bloom filter
    If we use above example, we want to know "AAGTR, GTAGG, GGGGG" are not in the 500000 length sentence.
    Let's assume we use 4 hash functions to build the array.
 
    Use the 4 hash functions on every object
    Each object gives us 4 index of the map. Using the index, check the value of array.
    If any of them has 0, we can say that the object is not definitely in the set.
    If all of them are 1, w can say that the object is probably in the set
                                       index1               index2             index3              index4
    AAGTR                           1                       1                     1                         1
    AAGTR                           0                       1                     1                         1
    GGGGG                          0                        0                      0                        0

    AAGTR is probably in the 500000 length setence
    AAGTR, AAGTR is definitly not in the 500000 length setence.

Instead of looking at every 5 length string of 500000 length string, you just need to use 4 hash functions to figure out AAGTR, AAGTR is definitly not in the 500000 length setence.

It is really powerful tool. Isn't it??
Making the array is not very efficient. However, once you build one, search is super fast!!


Deciding the length of array and number of hash function are very important to create good bloom filter.

I research the fomula from the Internet.
People still do research to figure out the best way to do so..
If you have better one, can me tell me how??

p= probability of hash collioin you want to allow
n= number of objects you are planning to put in array
 
a = array length =  ( ( n ) * ln( p ) )  / (ln(2)^2)

number of hash function = ( a/n ) * ln(2)


I made a sample code.

-------------------------------------------------------------------------------------------------------------------------
 The following is practice code. If you have suggestion or correction, please feel free to leave comment.

#include <iostream>
#include <functional> // i am using mac so i need this to use namespace std
#include <cstdlib>
#include <ctime>
#include <string>
#include <math.h>

using namespace std;

int hashfunction1 (string input);
int hashfunction2 (string input2);
int hashfunction3 (string input3);
int hashfunction4 (string input4);
void populateBloomFilter (int table[], int index);
void testBloomFilter(int table[], string input);



int main(int argc, char*argv[])
{
    string input="";
    string str="";
    char randomletter;

    srand((unsigned)time(NULL));

    //create string that has random char A to Z
    for (int i=0; i<500000; i++){

        // get random char
        randomletter = 'A' + (rand()%26);
        // convert string to char
        str = string(1, randomletter);
        // add string
        input += str;
    }

    // bloom filter table
    int bloomfilterTable [2000000];

    // initialize bloomfilter array to 0
    for (int i = 0; i < 2000000; ++i)
    {
        bloomfilterTable[i]=0;
    }

    //populate the table
    string tmp="";
    int hashVal1=0;
    int hashVal2=0;
    int hashVal3=0;
    int hashVal4=0;
    for (int i=0; i<499995; i++){

        tmp = input.substr(i,5);
        hashVal1 = hashfunction1(tmp);
        hashVal2 = hashfunction2(tmp);
        hashVal3 = hashfunction3(tmp);
        hashVal4 = hashfunction4(tmp);

        populateBloomFilter(bloomfilterTable, hashVal1);
        populateBloomFilter(bloomfilterTable, hashVal2);
        populateBloomFilter(bloomfilterTable, hashVal3);
        populateBloomFilter(bloomfilterTable, hashVal4);
    }


    //create random string with length 5
   
    for(int j=0 ; j<10; j++){
        string testInput="";
        for (int i=0; i<5;i++){
            // get random char
            randomletter = 'A' + (random()%26);
            // convert string to char
            str = string(1, randomletter);
            // add string
            testInput += str;
        }

        //test
        testBloomFilter(bloomfilterTable, testInput);
    }
}

int hashfunction1 (string input)
{
    double output=0;
    double tmp=0;
    for (int i = 0; i < input.length(); ++i)
    {
        output += (input[i]*pow(10,(double)i));
    }

    output +=9678939;
    output = fmod(output, 2000000);

    return (int) output;

}

int hashfunction2 (string input)
{
    double output=0;
    double tmp=0;
    for (int i = 0; i < input.length(); ++i)
    {
        output += (input[i]*pow(10,(double)i));
    }

    output +=11111111;
    output = fmod(output,2000000);

    return (int) output;
}

int hashfunction3 (string input)
{
    double output=0;
    double tmp=0;
    for (int i = 0; i < input.length(); ++i)
    {
        output += (input[i]*pow(10,(double)i));
    }

    output +=7865432;
    output = fmod(output, 2000000);

    return (int) output;
}

int hashfunction4 (string input)
{
    double output = 0;
    double tmp = 0;
    for (int i = 0; i < input.length(); ++i)
    {
        output += (input[i]%192*pow(10,(double)i));
    }

    output = fmod(output, 2000000);

    return (int) output;
}

void populateBloomFilter (int table[], int index)
{
    if( table[index] == 0 ){
        table[index] = 1;
    }

}

void testBloomFilter(int table[], string input)
{
    int val  = hashfunction1(input);
    int val2 = hashfunction2(input);
    int val3 = hashfunction3(input);
    int val4 = hashfunction4(input);

    bool checker1 = (table[val] == 1);
    bool checker2 = (table[val2] == 1);
    bool checker3 = (table[val3] == 1);
    bool checker4 = (table[val4] == 1);

    cout << checker1 << '\t' << checker2 << '\t' << checker3 << '\t'<<  checker4 << endl;
    // above checkers are all true, input is probably in the 2000000 string
    if (checker1 && checker2 && checker3 && checker4 == true ){
        cout << input << " is probably in the 2000000 string" << endl;
    }
    else{
        cout << input << " is definitly not in the 2000000 string" << endl;
    }


}

c++ makefile

C++ Makefile

C++ is object orient programming.
Each object file can be created by its own .cpp and .h file.

For instance, If you have the following files

main.cpp   -----------------> main.cpp uses a object, called person
person.cpp -----------------> person object source file
person.h. -------------------> person object header file

You need to compile these three files at once.

If you would like to compile using a terminal(linux, mac os), you can type it like following
         g++ main.cpp person.cpp

It is pretty simple. right?

But how about this??
You have 100 object files that are need to be comfile.

it would be  like
       g++ main.cpp a.cpp b.cpp c.cpp d.cpp ...................
It would be really painful.. YOU need to type it every file for every compiling.

Fortunately, there is a better option, you can use Makefile

Makefile tells make, a UNIX command, to communicate with c++ compiler to link and compile a program.
If you do not know UNIX, it is ok. Think it as the father of all operacting system(window, linux, mac os and many more....). To be honest, I do not know it well either hahahaha

If you use Makefile, you need to type the compiling command just onece.
After you create Makefile, you just need to type "make" in the terminal.

Format

target : dependency
    system command

Actually, it is really simple. If you remember these two lines, you can make Makefile pretty much.
One thing you need to remember is that this file is space sensitive. make sure you tab for the second line

Example

output: main.o Person.o                         3)
    g++ main.o Person.o -o output
main.o: main.cpp                                   1)
    g++ -c main.cpp
Person.o: Person.cpp Person.h              2)
    g++ -c Person.cpp
clean:                                                      4)
    rm *.o output


1) "g++ -c main.cpp" creates "main.o"

2) "g++ -c Person.cpp" create "Person.o". Person is an object, so you need to add .h and .cpp for depedency

3) after 1) and 2) are done, Makefile will work on making output. "-o output" makes the excutable's name "output"

4) it is optional feature. It is deletion of excutable  and other .o file. After you compile, and want to delete all .o files and output. You can type "make clean". It will do the job for you.

 *excutable = file that runs progream (it is like ".exe" for window and ".jar" for java)

---------------------------------------------------------------------------------------------------------------------------
 The following is practice code. If you have suggestion or correction, please feel free to leave comment.

To compile

make

To delete .o files and output(excutable)

make clean
 

There are four files

1) MakeFile

output: main.o Person.o
    g++ main.o Person.o -o output
main.o: main.cpp
    g++ -c main.cpp
Person.o: Person.cpp Person.h
    g++ -c Person.cpp
clean:
    rm *.o output

2) main.cpp

#include <iostream>
#include <functional> // i am using mac so i need this to use namespace std
#include <string>


#include "Person.h"

using namespace std;

int main( int argc, char *argv[])
{
    Person a("Tom", "Jang");

    a.printInfo();


}

3) Person.h

#include <iostream>
#include <functional> // i am using mac so i need this to use namespace std
#include <string>

using namespace std;

class Person
{
    private:
        string firstName;
        string lastName;
    public:
    Person();
    Person( string fName, string lName );
    void printInfo();

};

4) Person.cpp

#include <iostream>
#include <functional> // i am using mac so i need this to use namespace std
#include <string>

#include "Person.h"

using namespace std;

Person :: Person()
{
    firstName = "empty";
    lastName = "empty2";
}

Person :: Person ( string fName, string lName )
{
    firstName = fName;
    lastName = lName;
}

void Person :: printInfo()
{
    cout << "firstName is " << firstName << endl;
    cout << "lastName is " << lastName << endl;
}




   

 

c++ hashtable with linked list

C++ hashTable with linked list

Hash table is a data structure that allows use to search, edit, delete data nearlyO(1).
If you do not know what the O(1), it is ok.. keep it in you mind that it is super efficient.

Lets dive in with real example!!

let's say that you have list (you can think it as array).
Every element of this list contain name of person.
If you want to search Jane from the start of the list, you have to check every element.
Above example, we just need to check 100000 names.
Technically, it is quite fast if you are searching for 100000 names.
However, if the each elements contain lots of inforamtion, and the number of element is goes up to extrememly large numer, it is a different story. It wil take mintue, hour or more than that.

Let's look at the following.

This time, before we put names in the list, we use a function called hash function.
What the function does is that it takes name as input and return integer number.
This number is going to be the index of name in the list.

If we use this way, search can be done extremely fast!!

How?
If you want to know whether "john" is in the list, you can use hash function to the name. You will get the index, and you will get the result instantly, without looking at other names in the list.

It does not matter how many elements are in the list, you will get what you want from the list instantly

However, this hashfunction has problem...

The above example show that two different name ends with same index number.
If your list can handle onely one name, you are in trouble...
This is called hash collision.

There are severy way to avoid this.

My way is using linked list

There are different implimenation in using hash function with linked list.
My way is following...
    1) The very first element of list is empty
    2) get the hash val
    3) use hash val as index of list
    4) make linked list.

This way, it is not O(1)... but it is still close to O(1).


In the real world, there is no way that we can build hash function without hash collision.
It is like you are predict lottery number correctly every week..

Depend on number of data, field, culture and many other aspects, we  design the hash function differently; there is no right answer.

Lots of smart computer people, professors write research papers to find the best way of builiding hash function.


I made some sample coding for this topic.
---------------------------------------------------------------------------------------------------------------------------


The following is practice code. If you have suggestion or correction, please feel free to leave comment.

#include <iostream>
#include <functional> // i am using mac so i need this to use namespace std
#include <string>

using namespace std;

typedef struct student
{
    int id;
    string fName;
    string lName;
    student * nextStudent;
}Student;

void initTable (Student *table, int len);
void addStudent(int studentId, string firstName, string lastName, Student *table);
int hashFunction(int id);
void searchAndPrint(int studentId, Student *table);
void deleteStudent(Student *table, int len);

int main()
{
    Student * table = new Student [10];
    int len = 10;

    initTable(table, len);


    // insert
    addStudent(12345, "tony", "stark", table);
    addStudent(55555, "bruce", "wayne", table);

    // search and print
    searchAndPrint(55555, table);
    searchAndPrint(34524, table);


    cout << endl;
    // all students info are stored in dynamic memory
    // therefore you have to visit every single student info for the deletion
    // for those student info by the linked listed are deleted by the deleteStudent function
    // the table array is delete by delete []
    // pointers for table and pointers for student info are different pointer type.
    deleteStudent(table, len);

    delete []  table;


}

void initTable (Student *table, int len)
{
    for (int i = 0; i < len; ++i)
    {
        table[i].nextStudent = NULL;
    }
}

void addStudent(int studentId, string firstName, string lastName, Student *table)
{
    // using hash function, convert the id into hashed id
    int hashedID = hashFunction( studentId );   

        Student * pointer = &table[hashedID];

        while(pointer->nextStudent !=NULL){
            pointer = pointer->nextStudent;
        }

        // once we reach to the student who has NULL in nextStudent
        // add student
        Student *tmp = new Student;
        tmp->id = studentId;
        tmp->fName = firstName;
        tmp->lName = lastName;
        tmp->nextStudent = NULL;

        // link
        pointer->nextStudent = tmp;

}

int hashFunction(int id)
{
    int tmp = id;
    int ans =0;

        // add each digit's number ex) 12345 -> 1+2+3+4+5 = 15
        while( tmp != 0 ){
            ans += (tmp % 10);
            tmp /=10;
        }
        // the loop does not handle the last one
        // one more addition is required
        ans += (tmp % 10);
       
        // make the addtion into range of 0 to 9
        ans %= 10;

        return ans;
}

void searchAndPrint(int studentId, Student *table)
{
    // get the hashed id
    int hashedId = hashFunction(studentId);

    Student * tmp = &table[hashedId];

    // search for student
    while ( tmp -> nextStudent !=NULL){
        if (studentId == tmp->id){
            cout << "* found * " << studentId <<endl;
            cout << tmp -> fName << endl;
            cout << tmp -> lName << endl;
            return;
        }
        else{
            tmp = tmp -> nextStudent;
        }
    }

    // check the last one in the hash
    if (tmp ->id == studentId){
            cout << "* found * " << studentId << endl;
            cout << tmp -> fName << endl;
            cout << tmp -> lName << endl;
            return;
    }

    // if you cannot find even at the end
    // there is no such student in the hash
    else{
        cout << "* id is not found * " << studentId <<endl;
        return;
    }

}

void deleteStudent(Student *table, int len)
{

    for (int i = 0; i < len; i++)
    {
        Student* tmp = &table[i];
       
        // delete student info except the last one
        while ( tmp -> nextStudent != NULL){
            Student* tmp2 = tmp->nextStudent;
            tmp->nextStudent = tmp2->nextStudent;
            delete tmp2;
        }
    }



    cout << "deletrion successful" << endl;
   
}

c++ char pointer array

c++ char pointer array

In this post, I am going to talk about char pointer array.
Some people might say that they prefer use string instead of char pointer array.
I was like that.
If you string object
     You do not have to worry about the memory allocation and deletion.
     When you want to concatinate two strings, you just  need + operator.

If you are dealing with small amount of strings, go ahead of string.

But if you are dealing with large amout of string( I am talking about severy giga byte of string file), you btter use char pointer array.

It is faster.
It is based on my experience, believe me hahaha

 Whenever you are using char pointer array, you have to make sure that you allocate enough space for each pointer. Technically, you can use char array pointer with out memory allocation

function a()
{
char * arr[5];
arr[0] = "test";
arr[1] = "test2";
arr[2] = "test3";
arr[3] = "test4";
arr[4] = "test5";
 }
The above can be represent the following image

The problem is that once the array leave the function a, those value "test","test2".."test4" will be gone. In addtion, I cannot use string funtion such as strlen, substr etc....

In order to keep the values, you have to put those values in to special memory.
It is called heap .
If values are stored heap, they will stay until you delete.
If you do not use them, you have to delete.(If you don't, it is memory leak)

allocatiing memory
char * a [3];
    a[0] = new char[5];
    a[1] = new char[5];   --> each array can contain 5 character of array
    a[2] = new char[5];

delete
    delete [] a[0];
    delete [] a[1];     --------> make sure you add []
    delete [] a[2];

It would be like following
    * the first image is 1d char * array
    * the second image is 2d char * array

----------------------------------------------------------------------------------------------------------------------------
The following is practice code. If you have suggestion or correction, please feel free to leave comment.

#include <iostream>
#include <functional> // i am using mac so i need this to use namespace std
#include <string.h>


using namespace std;

void oneDfunction(char* arr[], int len);
void printOneDfunction(char* arr[], int len);
void deleteArray(char* arr[], int len);

// it is quite similar to first dimentional array
// one thing that you have to keep in mind is that you can only ...
// leave blank the first component of array. you have to specify ....
// the length
void twoDfunction(char* arr[][3], int row, int col);
void printTwoDfunction(char* arr[][3], int row, int col);
void deleteTwoDArray(char* arr[][3], int row, int col);

int main()
{
    // one dimentional example

    cout << "one dimetional char pointer array" << endl;
    char * array[5];
    int length = 5;

    oneDfunction(array, length);
    printOneDfunction(array, length);
    deleteArray(array, length);

    cout << endl;

    // two dimentional example

    cout << "two dimentional char pointer array << endl" << endl;
    char * array2[3][3];
    int row = 3;
    int col = 3;

    twoDfunction(array2, row, col);
    printTwoDfunction(array2, row, col);
    deleteTwoDArray(array2, row, col);
}

void oneDfunction(char* arr[], int len)
{
    for (int i=0; i< len; i++){

        // you have to allocate memory for your pointer
        // otherwise your pointer do not point any
        arr[i] = new char[10];
        strcpy(arr[i], "input");

       
        char * tmpP = new char[1];
        *tmpP = (i+'0');

        strcat(arr[i],tmpP);

          delete (tmpP);
    }
}

void printOneDfunction(char* arr[], int len)
{
    for (int i = 0; i < len; ++i)
    {
        cout << arr[i] << endl;
    }
}

void deleteArray(char* arr[], int len)
{
    for (int i =0; i < len; i++){

        // you have to put [], otherwise, you are not deleting your array entirely
        delete [] arr[i];
    }
}


void twoDfunction(char* arr[][3], int row, int col)
{
    int num = 0;
    for (int i = 0; i < row; ++i)
    {
        for (int j = 0; j < col; ++j)
        {
            arr[i][j] = new char [10];
            strcpy(arr[i][j], "input");
            char * tmpP = new char[1];
            *tmpP = (num+'0');
            num++;
            strcat(arr[i][j],tmpP);
              delete (tmpP);
        }
    }
}
void printTwoDfunction(char* arr[][3], int row, int col)
{
    for (int i = 0; i < row; ++i)
    {
        cout << "row " << i << endl;
        for (int j = 0; j < col; ++j)
        {
            cout << arr[i][j] << endl;
        }
        cout << endl;
    }
}
void deleteTwoDArray(char* arr[][3], int row, int col)
{
    for (int i = 0; i < row; ++i)
    {
        for (int j = 0; j < col; ++j)
        {
            delete [] arr[i][j];
        }
    }
}

c++ passing array to functions

c++ passing array to functions

Whenever I work on c++ project, I alway get confused of passing an array to fuction.

I thought that it would be nice to have reference of passing array to function.

There are several ways to work on this issue.
I just have made only some of them, but they always do the job!!

One thing I and you have to keep in mind is that whenever you pass the array, it is call by referece.
Which means that if you change any element of array in the funtion, the changes are remained even the array is out of th funtion.

----------------------------------------------------------------------------------------------------------------------------
The following is practice code. If you have suggestion or correction, please feel free to leave comment.

#include <iostream>
#include <functional> // i am using mac so i need this to use namespace std

using namespace std;

// 1d array functions
void printArray( int arr[], int len);
void add1( int arr[], int len);
void printArray2( int *array, int len);

// 2d array function
// for the array parameter, you can leave blank for the first one
void print2Darray(int array[][3], int len);

// 3d array function
// do you see the pattern?? you can alway make the first one blank
void print3Darray(int array[][2][2], int len);

int main()
{
    int length = 5;

    // 1d array example
    // initialize array to 1
    int array [5] = {1,2,3,4,5};

    // this function's array parameter is array
    cout << "the parameter of array is array" << endl;
    printArray( array, length);

    // this function prove that any function send array as parameter, is call by reference
    // which means that if you change stuff in array in function, the changes are remaind even the array is out of that function
    // when you pass the array to the function, keep it in your mind.
    add1( array, length);

    // this function's array parameter is pointer
    cout << "the parameter of array is pointer; \n due to function add1 all elements are incremented by one" << endl;
    printArray( array, length);
    // this function's array parameter is array
    cout << "the parameter of array is array\n due to function add1 all elements are incremented by one" << endl;
    printArray( array, length);   


    // 2d array example
    int array2d [3][3] = {{1,2,3},{4,5,6},{7,8,9}};

    length=3;
    // this function's array parameter is array
    // i could not use pointer to pass the array
    // if you know how, please let me know
    cout << "2d example" << endl;
    print2Darray(array2d,length);

    // 3d array example
    int array3d [2][2][2]={};
    length =2;
    cout << "3d example" << endl;
    print3Darray(array3d,length);

}

void printArray ( int arr[], int len)
{
    for (int i=0; i<len; i++){
        cout << arr[i] << endl;
    }
}

void add1( int arr[], int len)
{
    for (int i=0; i<len; i++){
        arr[i] += 1;
    }
}

void printArray2 ( int *arr, int len)
{
    for (int i=0; i<len; i++){
        cout << arr[i] << endl;
    }
}

void print2Darray(int array[][3], int len)
{
    for(int i=0; i<len; i++){
        cout << "row "<< i << endl;
        for(int j=0; j<len; j++){
            cout << array[i][j] << " ";
        }
        cout << endl;
    }
}

void print3Darray(int array[][2][2], int len)
{
    for(int i=0; i<len; i++){
        cout << "x "<< i << endl;
        for(int j=0; j<len; j++){
            cout <<  "\ty " << j << endl;
            for(int k=0; k<len; k++){
                cout << "\t\tz " << k << endl;
             }
        }
        cout << endl;
    }
}

c++ call by reference vs call by value

c++ call by reference vs call by value

 lets say that you create a int variable call "a".
 you store a value 1.

In c++ syntax, it would be  " int a = 1 "
For sake of simplity, lets think that your code will stay in memory (RAM) when you run it (I think it is true ).
In one section of memory, your int a is like below

 Your int can be any where in the memory (not true... but let's make it simple. It is almost true), there is gotta be some way to keep tract where your a is in the memory. Otherwise, you do not grab the variable when you need it.
For this reason, when you create a variable, you are actually create two thing. One is what you assign to the variable. The other one is address which is create by the computer ( i think it is by compliler or operating system.. not sure hahahah).

That strange number, 0x7ff58d72bac is the address.

Using these two information, we can do call by reference and call by variable.

Call by value function uses the value of variable.
Call by reference function uses the address of variable.

How can I get the address of variable, there are couple ways...
One way is using operator &.

after declare and initialize the variable, put & ahead of variable name like below

int a =1;
cout << &a << endl;

In below coding I made simple programming that can show you call by value and call by reference.

----------------------------------------------------------------------------------------------------------------------------
The following is practice code. If you have suggestion or correction, please feel free to leave comment.

#include <iostream>

using namespace std;

// call by value
int callByVal( int a )  ;

// call by reference
void callByRef( int & a );

int main()
{
     int a = 1;
     cout << "original a : "<< &a << endl;    
   
     // call by value
     // the function make a copy of a in main
     // the coped value is stored a in callByVal function
     // the function do the calculation
     // return the calculate value to a in main
     // a copy the value
     // a in main and a in callByVal are different
     // if you see the addresses of these two, you can see that they are different
     a = callByVal( a );

     // call by referenece
     // the function takes main a's address
     // by having the a's address, calByRef function knows where the a is in the memory
     // callByRef function uses the main's a to do calculation
     // a in main and a in callByRef are identical
     // if you see the address of these two, you can see that they are same
     callByRef( a );

     // a = 1 + 1 + 2
     cout << "1+1+2 = " << a << endl;
}

int callByVal( int a )
{
    cout << "address of a in call by value " << &a << endl;
    return a + 1;
}

void callByRef( int &a )
{
    cout << "address of a in call by reference" << &a << endl;
    a +=  2;
}

c++ linked list

C++ Linked list

Linked list is a data structure.
It is pretty much like an array that change its sizes.
Each componet of linked list is called a node.
Nodes are linked pointers.

Building linked list is a really good pointer practice. You need to very familiar with pointers to bulid it.

Whenever you are stuck with it, draw it like following.
I think it is the best way to solve any problem with linked list.

          head node                                                                                                                   last node

Every node has next pointer which points to the next node.
The last node's next is null; null indicates the last node of the linked list
----------------------------------------------------------------------------------------------------------------------------
The following is practice code. If you have suggestion or correction, please feel free to leave comment.


 #include <iostream>

using namespace std;

struct Node {
    int data;
    Node * next;
};

// initialize linked list
void initNode( struct Node * node, int val )
{
    node -> data = val;
    node -> next = NULL;

}
// add node
void addNode ( struct Node * node, int val)
{
    // create new node
    // this node will be placed at the end of node
    // that's why newNode -> next is NULL
    Node * newNode = new Node;
    newNode -> data = val;
    newNode -> next = NULL;

    Node * tmp = node;
    //move to the end of linked list
    while ( true ) {
        // when program gets to the end of linked list add new node
        // this new node become the end of linked list
        if ( tmp -> next == NULL ){
            tmp -> next = newNode;
            return;
        }
        tmp = tmp -> next;
    }

}

// add node at the beginning of linked list
void addNodeAtFirst ( struct Node * node, int val)
{
    // make a copy of the first node
    Node * newNode = new Node;
    newNode -> data = node -> data;
    newNode -> next = node -> next;

    // change the fist node of linked lisk to the val
    // point the head of node to new node
    node -> data = val;
    node -> next = newNode;
  

}

// delete all node
void deleteAllNode ( struct Node * node)
{
    Node * tmp = node;

    // delete all node
    // loop stop when it reaches to the last node
    while (tmp -> next != NULL){
        Node * helper = tmp;
        tmp = tmp-> next;
        delete helper;
    }

    // delete the last node
    delete tmp;
}

// print all node
void printNode( struct Node * node)
{
    // case when there is no item in the linked list
    if(node == NULL){
        cout << "there is no item" << endl;
    }
    // print node until the program reaches to the last node
    else{
        Node * tmp = node;
        while ( tmp -> next != NULL){
            cout << tmp -> data << endl;
            tmp = tmp ->next;
        }

        // print last node
        cout << tmp -> data << endl;
    }
}

// seach for specific node
bool searchNode ( struct Node * node, int val)
{
    Node * tmp = node;
    //checking everything except last one

    while( tmp -> next != NULL){
        if (tmp -> data == val){
            return true;
        }
        tmp = tmp-> next;
    }

    //checking the last one
    if( tmp -> data == val)
        return true;
    else
        return false;
}

// delete certain node
void deleteNode ( struct Node * node, int val)
{
    Node * tmp = node;
    Node * tmp2 = node;

    // seach for node
    // tmp and tmp2 point same node for the first node of the linked list
    // after that
    // tmp points the current node
    // tmp2 points the previous node
    while ( tmp -> next != NULL){
        if (tmp -> data == val){
            tmp2 -> next = tmp-> next;
            cout << "delete " << tmp -> data << endl;
            delete tmp;
            return;
        }
        tmp2 = tmp;
        tmp = tmp ->next;
    }

    // after the loop, tmp points the last node of linked list
    // you do not have to worry about tmp2 at this point.
    // becuase tmp already checked it.
    if (tmp -> data == val){
        cout << "delete "  << tmp -> data << endl;
        delete tmp;
        return;
    }

    else{
        cout << "there is no such val, cannot delete the request val" << endl;
    }

}


int main()
{
    // If node is empty, you cannot print the linked list ( you will get the error)
    // other than that, feel free to play with it

    Node * head = new Node();
    initNode( head, 10);
    addNode( head,  6);
    addNode( head, 3);
    addNode( head, 67);
    addNodeAtFirst (head, 99);
    printNode( head );
    deleteAllNode( head );

    cout << "new start" << endl;
    head = new Node();
    initNode( head, 5 );
    addNode ( head, 65);
    addNode ( head, 75);
    printNode( head );

    cout << "search 6. Since there is no 6 in the linked list, the following funtion return 0" << endl;
    cout << searchNode( head, 6) << endl;
    cout << "search 5. the following function return 1" << endl;
    cout << searchNode( head, 5) << endl;

    deleteNode( head, 65);
    deleteNode( head, 75);
    deleteNode( head, 5);

    printNode( head );
  

}

c++ vector

c++ vector

Vector is like array.
In array, you cannot change the length, but you can do that in vector.
It has index like array. syntax like "vector[3]= 3" is totally fine in vector

Format

std :: vector
     -> if you use "using namespace std", you do tno need to add "std ::"

constructor
     vector <type> name
     vector <type> name (length, val)
     vector <type> name (array , size of array)
         - type can be anything(string, int, char and other )

    .size()
        - return size of vector

    .insert( "interator", "val" )
        - add new element to vector. The element would be added at index. The elements in the vector shift one to right
        - you need iterator vector<int>::iterator 

    .push_back( "val" )
        - add new element to vector. The element will be stored at the end of vector. 

    .erase( "iterator" )
       - delete element of vector
       - if your vector is called input3, treat input3.begin() as index 0
                -> if you want to delete third element of vector, it would be input3.begin() +2
       - once the element is deleted, elements after deleted elements would shift one to left

    .clear()
       - delete all element of vector

------------------------------------------------------------------------------------------------------------------------

The following is practice code. If you have suggestion or correction, please feel free to leave comment.

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

using namespace std;

int main(int argc, char** argv) {

    int array[] = {1,2,3,4};
   
    //1
    //constructors of vector
    vector <int> input (3,100); //length = 3 val = 100
    vector <int> input2 (array, array + sizeof(array) / sizeof(int));// constructor with array
    vector <int> input3;// empty vector
   
    //2
    //print element of vector. it is like array
    for(int i=0; i< input.size(); i++){
        cout << input[i] << endl;
    }
    cout << "----------------------------" << endl;
   
    //3
    //print element of vector. it is like array
    for(int i=0; i< input2.size(); i++){
        cout << input2[i] << endl;
       
    }
    cout << "----------------------------" << endl;
   
    //3
    //insert elements to vector
    //if you use insert, the vector element is stored at the very first index. the rest
    //are shift to right by one
    //if you use push_back, the vector element is stored at the end of vector
    vector<int>::iterator it;
    it = input3.insert(it , 300);
    it = input3.insert(it , 400);
    it = input3.insert(it , 100);
    input3.push_back( 999 );
   
    for (int i=0; i<input3.size(); i++){
        cout << input3[i] << endl;
    }
   
    cout << "----------------------------" << endl;
    //4
    //delete 2 elements of input3 vector
    //index(int) wont work. you need to use either begin or iterator
    input3.erase (input3.begin()+1);
   
    for (int i=0; i<input3.size(); i++){
    cout << input3[i] << endl;
    }
   
    cout << "-----------------------------" << endl;
    //5
    //clear all contents of vector
    input.clear();
    if (input.size() == 0)
        cout << "there is nothing in input vector" << endl;
    return 0;
}

c++ i/o stream

c++ i/o stream

In order to use data in disk, monitor, keybord and other input/output devices, we need to use stream.

We can think the stream as a bridge that connect your c++ program with oother input device.
For example, I am going to demonstrate your " cout " command.

cout << "hello world" ;

your c++ program runs " cout " --> stream is created --> your c++ programs grabs "hello world" --> "hello world" is sent to monitor via stream --> "hello world" is displayed on your monitor.

files and other input/output devices have same behaviour

I am going to show you how I can read and write text file using ifstream and ofstream.
ifstream = reading from a file
ofstream = writing to a file
---------------------------------------------------------------------------------------------------------------------------

 The following is practice code. If you have suggestion or correction, please feel free to leave comment.


#include <iostream>
#include <fstream>
using namespace std;

int main() {
    //writing sth to " test.txt " file
    ofstream f;
    f.open("test.txt");
    f << "hello world" << endl;
    f.close();

    //read " text2.txt " file line by line
    ifstream ff ("text2.txt");
   
    //check whether text2.txt is usable file
    if( ff.is_open())
    {
         string line;

         //getline returns true until there is sth to read in the file
         //reading line is stored in string variable
         while ( getline( ff, line ))
        {
                cout << line << endl;
        }
    }

    ff.close()


}

c++ string

c++ string

String is like char * in C.
In my opinion, it is easier and safter to use string instead of  char *.
You do not have to worry about memory leak; in C, you need to make sure the length and delete.

Format

std :: string
     -> if you use "using namespace std", you do not need " std:: "

    .length()
        - return word length of string

    .at( "position" )
         - return a string at the postion

    .substring("start point" ,  "length")
        - return sub string of string

    .compare( "compare string")
        - compare two strings. If they are same, it returns 0
 
    + operator
         - add two strings

    .find( "wanted string" )
         - if "wanted string" is in the string, return the first position of the string
         - if there isn't "wanted string", it returns 18446744073709551615 (= string::npos )             

    .erase("start point", "length")
         - erase part of string from starting point until the length

    .replace("position", "length", "replacing string")
         - grab sub string starting at specified postion untill the lenth and repace with the "replacing
            string"
 -------------------------------------------------------------------------------------------------------------------------

The following is practice code. If you have suggestion or correction, please feel free to leave comment.

#include <iostream>
#include <string>

using namespace std;

int main(int argc, char** argv) {

    string input = "hello world";
    string input2 = "hello world";
    string input3 = "hello world2";
   
    //1
    //getting length of string
    int length = input.length();
   
    //2
    //grab a component of string
    for(int i=0; i< length; i++){
        cout << input.at(i) << endl;
    }
    cout << endl;
   
    //3
    //substring start position of 1 upto lenth 5
    string subString = input.substr(1,5);
    cout << subString << endl << endl;

    //4
    // compare two strings are equal, if they are, return 0
    cout << "compare same: " << input.compare(input2) << endl;
    cout << "compare different: " << input.compare(input3) << endl;
    cout << endl;
   
    //5
    // add two string
    cout << "add two strings : " << input + input2 << endl;
   
    //6
    // find string
    cout << "where is lo : " << input.find("lo") << endl << endl;
    cout << "where is z : " << input.find("z") << endl << endl << endl;
  
    //7
    // delete part of string
    input2.erase(0,5);
    cout << "delete position 0 upto length 5 : " << input2 << endl;
   
    //8
    // replace string
    input2.replace(0, 0, "hi");
    cout << "repalce : " << input2 << endl;
   
     return 0;
}

c++ set

c++ set

Set is very useful data structure in C++.
It is like an array but it has lots of useful tools.
Tools that I often use and introduce are..

Format
std :: set < type > setName
    -> if you use "using namesapace std", you do not need std ::
    -> type can be int, char, string and vice versa

    .insert( "item" )
        - insert value in a set

    .size(   )
        - check number of item in a set

    .find( "item")
    .find( "index")
       - find item by using element or index.
       - This function is really powerful because it find element in O(1).
             -> every element is in hash. when it search for item, what it needs to is looking the hash value
       - if find cannot find it returns .end ()

    .erase( "item" )
    .erase( "index" )
        - erase element by using element or index

If you want to grab a element from set,  use iterator
ex) 
  set < string > :: iterator checker
  checker = yourSet.find("item")
  cout << *checker << endl;
------------------------------------------------------------------------------------------------------------------------------

The following is practice code. If you have suggestion or correction, please feel free to leave comment

#include <iostream>
#include <set>
using namespace std;

int main(int argc, char** argv) {
   
    set <string> aSet;
    set <string>::iterator checker;
    set <string>::iterator element;
   
    string input1 = "one";
    string input2 = "two";
    string input3 = "three";
    string input4 = "four";
    string inputDummy = "one";
   
    aSet.insert( input1 );
    aSet.insert( input2 );
    aSet.insert( input3 );
    aSet.insert( input4 );
    aSet.insert( inputDummy );
   
    // 1
    //return three because input1 and inputDummy have same value
    cout << aSet.size() << endl;
   
    //2
    //return one because set has one
    checker = aSet.find("one");
    if( checker != aSet.end() )
        cout << "one" << endl;
   
    //3
    //return none because has one
    checker = aSet.find("five");
    if( checker == aSet.end() )
        cout << "five is not in the set" << endl << endl;
   
    //4
    //print every elements
    //print in alphabetical order
    for( element = aSet.begin(); element != aSet.end() ; element++ ){
        cout << *element << endl;
    }
   
    //5
    //erase element of set by value and index
    aSet.erase( "one" );
    aSet.erase( input2 );
    cout << endl;
   
    //6
    //print every elements
    for( element = aSet.begin(); element != aSet.end() ; element++ ){
        cout << *element << endl;
    }
   
   
    return 0;
}