C++ Tips

This article is recording the problems that I encountered during my learning process. I will put links for relative problems. I will try to organize them in a better way when I have more content.

Static Keyword in C++

Perfect forwarding and universal references

RAII

memset

memset works byte by byte. The code and problem can be found in this post.

class Solution {
    int a[15],f[32768],o[32768];
public:
    int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {
        memset(a,0,sizeof(a));//set a to all 0s
        int i,j,l;
        for(auto e:dependencies)a[e[1]-1]|=1<<e[0]-1;
        for(i=1;i<1<<n;i++)o[i]=o[i>>1]+(i&1);
        memset(f,127,sizeof(f));// This is not setting all 1s. It is setting each byte as 01111111. Do not clear about the reason and will figure it out later.
        for(i=f[0]=0;i<1<<n;i++)if(f[i]<=n)
        {
            for(j=l=0;j<n;j++)if(!(i>>j&1)&&(a[j]&i)==a[j])l|=1<<j;
            for(j=l;j;j=j-1&l)if(o[j]<=k)f[i|j]=min(f[i|j],f[i]+1);
        }
        return f[(1<<n)-1];
    }
};

Why does "memset(arr, -1, sizeof(arr)/sizeof(int))" not clear an integer array to -1?

How to set 2d int array to -1.

“

Just change to memset (arr, -1, sizeof(arr));

Note that for other values than 0 and -1 this would not work since memset sets the byte values for the block of memory that starts at the variable indicated by *ptr for the following num bytes.

void * memset ( void * ptr, int value, size_t num );

And since int is represented on more than one byte, you will not get the desired value for the integers in your array.

Exceptions:

• 0 is an exception since, if you set all the bytes to 0, the value will be zero
• -1 is another exception since, as Patrick highlighted -1 is 0xff (=255) in int8_t and 0xffffffff in int32_t

”

__builtin_popcount

An example of using this can be found in this post.

Leetcode 461. Hamming Distance

class Solution {
public:
    int hammingDistance(int x, int y) {
        return __builtin_popcount(x^y);   
    }
};

2^n overflow

1498. Number of Subsequences That Satisfy the Given Sum Condition

// pow(2,idx-1) will get overflow
unsigned long long MOD = 1e9+7;
class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        sort (nums.begin(), nums.end());
       int64_t  res = 0;
        for(int i=0;i<nums.size();++i){
            auto num = nums[i];
            if ((num+num)>target)break;
            auto idx = upper_bound(nums.begin(), nums.end(), target-num)-nums.begin();
            idx -= i;
            if (idx<=0)continue;
            int64_t this_res = pow(2,idx-1);
            this_res %= MOD;
             res += this_res;
            if (res>=MOD)res %= MOD;
            
        }
        return res;
    }
};

By precalculate the res, we can get AC

unsigned long long MOD = 1e9+7;
class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
       auto  n = nums.size();
        vector<int> p2(n+1, 1);
        for(int i=1;i<n+1;++i)p2[i] = (p2[i-1]<<1)%MOD;
        
        sort (nums.begin(), nums.end());
       int64_t  res = 0;
        for(int i=0;i<nums.size();++i){
            auto num = nums[i];
            if ((num+num)>target)break;
            auto idx = upper_bound(nums.begin(), nums.end(), target-num)-nums.begin();
            idx -= i;
            if (idx<=0)continue;
            int64_t this_res = p2[idx-1];
            this_res %= MOD;
             res += this_res;
            if (res>=MOD)res %= MOD;
            
        }
        return res;
    }
};

Flip a binary string

#include<iostream>
#include<string>
using namespace std;
int main()
{
    string s = "0011";
    for (auto& c : s) c = '0' + '1' - c;
    cout<<s<<endl;
    return 0;
}

C++11 move

See this post

A = std::move(B);

A related problem

119. Pascal’s Triangle II

Before

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ret, new_ret;
        ret.push_back(1);
        for (int i = 1; i <= rowIndex; ++i)
        {
            new_ret.push_back(1);
            for (int j = 1; j < ret.size(); ++j)
            {
                new_ret.push_back(ret[j-1] + ret[j]);
            }
            new_ret.push_back(1);
            ret = new_ret;
            new_ret.clear();
        }
        return ret;
    }
};

after

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ret, new_ret;
        ret.push_back(1);
        for (int i = 1; i <= rowIndex; ++i)
        {
            new_ret.push_back(1);
            for (int j = 1; j < ret.size(); ++j)
            {
                new_ret.push_back(ret[j-1] + ret[j]);
            }
            new_ret.push_back(1);
            ret = move(new_ret);
        }
        return ret;
    }
};

An improved version

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ret;
        ret.push_back(1);
        for (int i = 1; i <= rowIndex; ++i)
        {
            ret.push_back(1);
            for (int j = ret.size()-2; j >= 1; --j)
                ret[j] += ret[j-1];
        }
        return ret;
    }
};

C++11 new features

https://www.bilibili.com/video/BV1Cs411a7Le?from=search&seid=7134922932340859775