DEV Community: dinhluanbmt

C++, about priority_queue(min max heap)

dinhluanbmt — Tue, 26 Dec 2023 03:16:20 +0000

priority_queue (min/max heap)
Building complexity: O(n) / priority_queue pq(iV.begin(),iV.end());
priority_queue s_pq;
for(auto i: iV) s_pq.push(i) //building time complexity O(n* log n)
pop : O(log n)
push : O(log n)
top : O(1)
default order: max heap( maximum item is on top) - descending order.
min heap (min item on top) - ascending order
priority_queue, std::greater> m_h(iV.begin(),iV.end());
Example code

 vector<int> iV = { 3,5,8,3,6,1,20,4,8,1};
    cout << "==========max heap=============" << endl;
    // building time complexity O(n)
    priority_queue<int> pq(iV.begin(), iV.end());// default order => max heap, descending order
    pq.push(24);//O(log n) time complexity
    while (!pq.empty()) {
        cout << " " << pq.top() << endl; // --> acces the maximum item : O(1)
        pq.pop();// O(log n) time complexity
    }
    //==========
    cout << "==========min heap==============" << endl;
    // min heap, O(n) building time complexity
    priority_queue<int,vector<int>, std::greater<int>> m_h(iV.begin(),iV.end());
    while (!m_h.empty()) {
        cout << " " << m_h.top() << endl;
        m_h.pop();
    }

    priority_queue<int, vector<int>, greater<int>> slow_bh; // O(1) building time
    for (auto i : iV) slow_bh.push(i); // building time O (n* log n)

Custom data type

struct City {
    int population;
    string name;
    City(int pop = 0, string s = "") {
        population = pop;
        name = s;
    }
    // for max heap
    bool operator< (const City& c) const
    {
        return population < c.population || (population == c.population && name < c.name);
    }
    //for min heap
    bool operator> (const City& c) const {
        return population > c.population || (population == c.population && name > c.name);
    }
    //bool operator== (const City& c) const / for other methods

};
void test_priority_queue() {
    vector<City> cV = { {100,"suwon"},{320,"incheon"},{40,"seoul"},{500,"kwangju"}};
    // max heap
    cout << "========== max heap =============" << endl;
    priority_queue<City> pq(cV.begin(), cV.end());
    while (!pq.empty()) {
        cout << " " << pq.top().population << " " << pq.top().name << endl;
        pq.pop();
    }
    cout << "========== min heap =============" << endl;
    //min heap
    priority_queue<City, vector<City>, std::greater<City>> mc_h(cV.begin(), cV.end());
    while (!mc_h.empty()) {
        cout << " " << mc_h.top().population << " " << mc_h.top().name << endl;
        mc_h.pop();
    }
}

C++, about map, set

dinhluanbmt — Thu, 21 Dec 2023 05:13:24 +0000

std::map and std::set ( std::unordered_map and std::unordered_set) share similar time complexity for their basic operations
Big O of map and set

Building : O(n* log n)
Find : O(log n)
Insert : O(log n)
Erase : O(log n) At default all items are sorted as ascending order.

Example of map

int main() {
    // default order (ascending)
    map<int, bool> m_map = { {5,true},{4,false},{8,true},{2,false} };
    // descending order
    map<int, bool, std::greater<int>> des_map = { {5,true},{4,false},{8,true},{2,false} }; 
    des_map.insert({ 10,true });// insert
    des_map.insert(pair<int, bool>(3, false));//insert pair
    des_map.insert(make_pair(9, true));// make_pair
    des_map.erase(5);// erase a key
    auto f_it = des_map.find(123);
    // just find item
    if (f_it != des_map.end()) {
        cout << "found in map" << endl;
    }
    else cout << "not found" << endl;

    if (des_map[123]) // create if not exist
    {
        cout << "found in map" << endl;
    }
    else cout << "not found" << endl;
    cout << "=========== items in map ========" << endl;
    for (auto it : des_map) {
        cout << " " << it.first << " " << std::boolalpha<<it.second << endl;
    }    
    return 0;
}

Custom key map

struct People {
    int age;
    string name;
    People(int a = 0, string s = "") {
        age = a;
        name = s;
    }
    // overload operator to compare
    bool operator< (const People& p) const {
        return age < p.age || (age == p.age && name < p.name);
    }
    // need for std::greater<People>
    bool operator> (const People& p) const //  use People with other STL function
    {
        return age > p.age || (age == p.age && name > p.name);
    }
    bool operator== (const People& p) const // use People with other STL function
    {
        return (age == p.age && name == p.name);
    }
};
void custom_key_map() {
    // Creating a map with People as keys and string as values
    std::map<People, std::string, greater<People>> peopleMap;
    // Create instances of People
    People person1{ 25, "Alice" };
    People person2{ 30, "Bob" };
    People person3{ 21, "Charlie" };
    // Inserting values into the map
    peopleMap[person1] = "Engineer";
    peopleMap[person2] = "Doctor";
    peopleMap[person3] = "Artist";
    // Iterating through the map
    for (const auto& pair : peopleMap) {
        std::cout << "Age: " << pair.first.age << ", Name: " << pair.first.name
            << ", Profession: " << pair.second << std::endl;
    }
    // Creating a People object for Bob
    People bob{ 30, "Bob" };
    // Using find to check if Bob exists in the map
    auto it = peopleMap.find(bob);
    if (it != peopleMap.end()) {
        std::cout << "Bob exists in the map. Profession: " << it->second << std::endl;
    }
    else {
        std::cout << "Bob doesn't exist in the map." << std::endl;
    }
}

Example of set

int main() {
    map<int, int> i_map;// ascending order
    map<int, int, std::greater<int>> des_map;//desending order
    unordered_map<int, int> u_map;// unordered_map
    vector<int> iV = { 5,2,8,4,3,5,8,16 };
    set<int> i_s(iV.begin(),iV.end());// ascending order
    if (i_s.insert(5).second == false) {
        cout << " already in set" << endl;
    }
    else cout << " inserted" << endl;

    auto fit =i_s.find(123);// find
    if (fit != i_s.end()) {
        cout << " in set" << endl;
    }
    else cout << " not found" << endl;
    i_s.erase(5);// erase 
    set<int, std::greater<int>> des_set(iV.begin(),iV.end());// descending order
    unordered_set<int> u_set;
    cout << "====== ascending set=====" << endl;
    for (auto i : i_s) cout << " " << i << endl;
    cout << "======= descending set=====" << endl;
    for (auto i : des_set) cout << " " << i << endl;        
    return 0;
}

C++ - Basic Tree Traversal(Recursive vs Queue)

dinhluanbmt — Mon, 07 Aug 2023 07:16:55 +0000

LeetCode question :
102. Binary Tree Level Order Traversal
Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level)

Definition for a binary tree node

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

Recursive Solution

class Solution {
public:
    void visit(TreeNode* root, vector<vector<int>>& ret, int level) {
        if (!root) return;
        while (ret.size() < level + 1) {
            vector<int> v;
            ret.push_back(v);
        }
        ret[level].push_back(root->val);
        visit(root->left, ret, level + 1);
        visit(root->right, ret, level + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> tree;
        visit(root, tree, 0);
        return tree;
    }
};

Using Queue

class Solution_non_recursive {
public:

    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> retVec;
        if (!root)
            return retVec;
        queue<TreeNode*> q;
        q.push(root);
        int i, size;
        TreeNode* tN;
        while (!q.empty())
        {
            vector<int> tv;
            size = q.size();
            for (i = 0; i < size; ++i)
            {
                tN = q.front();
                q.pop();
                tv.push_back(tN->val);
                if (tN->left) q.push(tN->left);
                if (tN->right) q.push(tN->right);
            }
            retVec.push_back(tv);
        }
        return retVec;
    }
};

Leetcode Question:
104. Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Recursive Solution:

class Solution_recursive {
public:
    int getmax(TreeNode* root, int cur){        
        if(!root) return cur;
        return max(getmax(root->left,cur+1),getmax(root->right,cur+1));
    }
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        return getmax(root,1) -1 ;
    }
};

Using queue

class Solution_queue {
public:    
    int maxDepth(TreeNode* root) {
        int depth = 0;
        if(!root) return depth;
        queue<TreeNode*> mq;
        mq.push(root);
        int size,i;
        TreeNode* tn;
        while(!mq.empty()){
            size = mq.size();
            depth++;
            for(i = 0; i<size;i++){
                tn = mq.front();
                mq.pop();
                if(tn->left) mq.push(tn->left);
                if(tn->right) mq.push(tn->right);
            }
        }     
       return depth;
    }
};

C++ - Basic Tree Traversal(Recursive vs Stack)

dinhluanbmt — Tue, 01 Aug 2023 02:05:30 +0000

Definition for a binary tree node

struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };

Main types of binary tree traversal:

Inorder (Traversal): left - root - right
Preorder(Traversal): root - left - right
Postorder(Traversal): left - right - root

leetcode question :
94. Binary Tree Inorder Traversal
Given the root of a binary tree, return the inorder traversal of its nodes' values.

Recursive Solution

class Recursive_Solution {
public:
    void travel(vector<int>& tree, TreeNode* root) {
        if (!root) return;
        travel(tree, root->left);
        tree.push_back(root->val);
        travel(tree, root->right);

    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        travel(ret, root);
        return ret;
    }
};

Non Recursive (using stack)

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> mst;
        vector<int> ret;
        TreeNode* tn = root;
        while (tn || !mst.empty()) {
            while (tn) {
                mst.push(tn);
                tn = tn->left;
            }
            tn = mst.top();
            ret.push_back(tn->val);
            mst.pop();
            tn = tn->right;
        }
        return ret;
    }
};

Leetcode question:
98. Validate Binary Search Tree
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Non Recursive (using Stack)

class Solution_stack {
public: 
    bool isValidBST(TreeNode* root) {       
        stack<TreeNode*> st;
        TreeNode* tn = root;
        TreeNode* prv = nullptr;
        while(tn || !st.empty()){            
            while(tn){
                st.push(tn);
                tn = tn->left;
            }
            tn = st.top();
            st.pop();
            if(prv){
                if(prv->val >= tn->val) return false;
            }
            prv = tn;
            tn = tn->right;
        }   
        return true;     
    }
};

Recursive solution

class Solution_recursive {
public:    
    bool g_ret = true;
    TreeNode* prv = nullptr;
    void check(TreeNode* root){
        if(!root) return;
        if(root->left) check(root->left);
        if(prv){
            if(prv->val >= root->val) {g_ret = false; return;}
        }
        prv = root;
        check(root->right);
    }    
    bool isValidBST(TreeNode* root) {       
        check(root);
        return g_ret;
    }
};

C++, Conditional (ternary) operator

dinhluanbmt — Thu, 13 Jul 2023 07:41:13 +0000

When the conditions and expressions are simple and concise, the conditional operator is extremely useful. It can reduce multiple lines of if-else conditions to a single line, making the code more compact and readable.
some examples:

void conditional_operator_example(int a, int b, string str1, string str2) {    
    //Ensure i >= 0    
    int i = (a - 2 > 0) ? a - 2 : 0;
    cout << "i : " << i << endl;

    //Grade base on mark
    int mark = b;
    string result = (mark >= 5) ? "Pass" : "Fail";
    cout << "Result : " << result << endl;

    // Get the longer string
    string& long_str = str1.length() > str2.length() ? str1 : str2;
    cout << " longer str : " << long_str << endl;

    //Check if the two numbers have the same sign (both positive or both negative)    
    bool is_sameSign = ((a >= 0) == (b >= 0)) ? true : false;
    cout << "Same Sign : " <<boolalpha<< is_sameSign << endl;
}

C++, Preprocessor directives: #define, #ifdef...

dinhluanbmt — Mon, 10 Jul 2023 02:12:48 +0000

Even though #define, #include, #ifdef, #ifndef, #endif.. are very common but when i try a hackerrank problem, the term "Preprocessor directives" sound unfamiliar to me. So i just summarize about it here.
Definition: Preprocessor directives are lines included in the code of programs preceded by a hash sign (#). These lines are not program statements but directives for the preprocessor. The preprocessor examines the code before actual compilation of code begins and resolves all these directives before any code is actually generated by regular statements
Some types of preprocessor directives that I frequently use :
Macro Definition

#define foreach(v,i) for(int i = 0; i< v.size();i++)
#define toStr(S) #S  // to string
#define getmax(a,b)  ((a) > (b)) ? (a): (b)
#define FUNCTION(name, operator) int name(int a, int b){if(a operator b)return a;else return b;}
FUNCTION(maximum, >)
FUNCTION(minimum, <)

void testFunc() {
    vector<int> iV = { 3,5,7,8,3,5,4 };
    foreach(iV, k) {
        cout << " " << iV[k];
    }
    cout << endl;
    int a = 9;
    int b = 52;
    int min_val = minimum(a, b);
    int max_val = getmax(a, b);
    cout << "Debug info : " << endl;
    cout << "  File : " << __FILE__ << endl;//predefined macro for debug
    cout<<"  Line : " << __LINE__ << endl;
    cout << endl;
    cout << toStr(Min Value = ) << min_val << endl;
    cout << toStr(Max Value = ) << max_val << endl;
}

File Inclusion : #include "header.h"

Conditional Compilation

#define DEBUG 
void test_define() {
#ifdef DEBUG
    cout << "Debug mode enabled." << std::endl;
#else
    cout << " not define DEBUG " << endl;
#endif
#ifndef RELEASE
        cout << "Not in release mode." << std::endl;
#endif
}

There are others directives like :

#undef
#pragma startup
#pragma exit
...

but i never use except #pragma once to prevent multiple inclusions of the file

C++, Forward declaration

dinhluanbmt — Fri, 07 Jul 2023 00:06:28 +0000

Forward declaration is a powerful technique that allows us to declare a type without needing its full definition. This reduces the number of dependencies and can improve compilation times. It is particularly useful in large projects or library development.

Ex: class A header file (A.h)

// we don't need to include the header file B.h here
// #include "B.h" in A.cpp  to instantiate B object
class B;// forward declaration 
class A {
private:
    B* pB;// ok
    B& rB;// ok
    //B ob;// error because compiler need to know the definition of class B
public:
    void method() {
        //pB->dosomething(); error        
    }
    void use_classB_method();

};

Class A definition (A.cpp)

#include "B.h"
void A::use_classB_method() {
    pB = new B();
    pB->dosomething();
}

C++, try catch , custom exception

dinhluanbmt — Wed, 05 Jul 2023 06:58:09 +0000

Due to performance considerations, I have rarely used try-catch in my works. However, I recently encountered an easy problem on HackerRank about try catch that I couldn't solve.
--> I think we still need some basic about try-cacth^^

//define my own exception class
class mException {
    int val;
public:
    mException(int n = 0) {
        val = n;
    }
    string what() {
        string str = "(mException) error at size = ";
        str.append(to_string(val));
        return str;
    }
};
// just thow some exceptions
bool isValid(string str) {
    size_t size = str.length();
    if (size == 1) throw invalid_argument("invalid argument...length = 1 ");
    if (size < 4) throw mException(size);// thow my custom exception
    if (str[0] == 'A') return true;
    else return false;
}
void test_try_catch(string str) {
    try {
        bool ret = isValid(str);
        if (ret) cout << "Valid..." << endl;
        else cout << "Invalid String" << endl;
    }
    catch (invalid_argument& ex) {
        cout << ex.what() << endl;
    }
    catch (mException& mex) {
        cout << mex.what() << endl;
    }
    catch (...) {
        cout << "other exception..." << endl;
    }
}

C++, Template and Template for a specific type

dinhluanbmt — Tue, 04 Jul 2023 00:25:06 +0000

We have many reasons to use templates, but it is important to remember that templates should be defined in header files. Because the code for specific types is generated when we instantiate them

// for Int, double, float
template <class T>
class AddElements {
    T val;
public:
    AddElements(T obj) {
        this->val = obj;
    }
    T add(T obj) {
        return (val + obj);
    }
};

Sometimes, we might need to define a template specialization for a specific type

//template for string and additional function concatenate
template <>
class AddElements<string> {
    string val;
public:
    AddElements(string str) {
        this->val = str;
    }
    string concatenate(string str) {
        this->val.append(str);
        return this->val;
    }
};

more than one template argument, default value for template argument

template<typename T, typename U = double>
class mPair {
public:
    T first;
    U second;
    mPair(T f, U s) : first(f), second(s) {}
    bool operator > (const mPair& obj) {
        return this->second > obj.second;
    }
};

use case :

int main()
{
    AddElements<int> ae(4); 
    int sum = ae.add(16); // 20

    AddElements<string> s_ae("hello ");
    string str = s_ae.concatenate("world...!"); // hello world...!  

    mPair <string> df_mp("default", 8.4);// second argument type name is as default -> double
    cout << " default first " << df_mp.first << " second: " << df_mp.second << endl;
    mPair<string, int> mp("str1", 40); // 
    cout << " first " << mp.first << " second " << mp.second << endl;
    mPair<string, int> mp1("str2", 8);

    mPair<string,int> mpmx = getMax<mPair<string,int>>(mp, mp1);
    mPair<string, int> mpmx1 = getMax(mp, mp1);// the compiler can deduce the template parameters from the type of mp
    return 0;   
}

C++, Static Object - Singleton pattern

dinhluanbmt — Thu, 29 Jun 2023 01:53:31 +0000

For many reasons, we may want only one instance of a class to exist throughout the lifetime of an application. This is where the Singleton pattern comes

class mSingleObj {
private:
    static shared_ptr<mSingleObj> instance;
    string description = "this is single instance object";
    // private constructor so that we can not create an instance
    mSingleObj(){}
    // private copy constructor and assignment operator
    //  previous version of c++
    mSingleObj(const mSingleObj&){}
    mSingleObj& operator=(const mSingleObj&) {}
    // move constructor and move assignment operator
    // >= c++11 we can delete
    mSingleObj(mSingleObj&& ) = delete;
    mSingleObj& operator=(mSingleObj&& ) = delete;
public:
    //the only one way to to get object
    static shared_ptr<mSingleObj> getInstance() {
        return instance;
    }
    void display() {
        cout << description << endl;
    }
    ~mSingleObj() { cout << "Destructor called only one..." << endl; }
};
//static object need to be initialized outside the class defination
shared_ptr<mSingleObj> mSingleObj::instance(new mSingleObj());

void testSingletonObj() {    
    shared_ptr<mSingleObj> sObj = mSingleObj::getInstance();
    sObj->display();
    shared_ptr<mSingleObj> other_sObj = mSingleObj::getInstance();
    other_sObj->display();
    //check whether objects are the same
    cout << "(sObj) Address of managed object: " << sObj.get() << std::endl;
    cout << "(other_sObj) Address of managed object: " << other_sObj.get() << std::endl;
}

Important things:

the private constructor
a way to get the object (because we cant not create an object of class with private constructor)
the private Copy constructor and Copy assignment operator

But in my experience, I really dislike the Singleton pattern when dealing with unit tests.

C++, Static Object - share data

dinhluanbmt — Wed, 28 Jun 2023 00:13:32 +0000

Static objects are created only once before the program starts and destroyed when the program terminates. So they can be used to share data between different functions or instances of a class

class CountObject {
    static int count; //declare share data
public:
    CountObject() {
        count++;
    }
//static method, can be used without instantiating an object of the CountObject class
    static int getCount() {
        return count;
    }
};
//need to define and initilize value
int CountObject::count = 0;

then we can use it like:

CountObject a, b, c;
cout<<"nums of created objects :"<<CountObject::getCount()<<endl;

Just remember to define and initialize the static object outside of the class to ensure that only one instance is created for the entire program.
int CountObject::count = 0;

C++, Pass function to algorithm vs Lambda expression

dinhluanbmt — Mon, 26 Jun 2023 00:47:02 +0000

If we need to use standard functions with custom objects (our defined struct or class) before C++11, we can only pass functions to algorithms.

struct City {
    string name;
    double population;
};
// compare City by population
bool cmpfnc(const City& a, const City& b) {
    return a.population < b.population;
}
// then we can use it
vector<City> vCity = { {"city 1", 140000}, {"city 2", 100000},{"city 3", 700000},{"city 4", 500000} };
sort(vCity.begin(), vCity.end(), cmpfnc); //pass cmpfnc function  to standard stl sort
for (auto c : vCity) {
     cout << "City name: " << c.name << " population: " << c.population << endl;
}

from C++11, Lambda expression makes it simple

vector<City> vCity = { {"city 1", 140000}, {"city 2", 100000},{"city 3", 700000},{"city 4", 500000} };
//lambda expression
sort(vCity.begin(), vCity.end(), [](const City& a, const City& b) {return a.population < b.population; });
for (auto c : vCity) {
   cout << "City name: " << c.name << " population: " << c.population << endl;
}

But sometimes, I also forget the ";" in the code of a lambda expression [](const City& a, const City& b) {return a.population < b.population;} so don't forget it.