C++ basics

Description

There are lots of funny techniques, so now here we are to collect them all once they are used.

  1. Remove all the occurrences of a char in a C++ string: str.erase(std::remove(str.begin(), str.end(), 'a'), str.end());
  2. Both vectors and deques provide a very similar interface and can be used for similar purposes, but internally both work in quite different ways: While vectors use a single array that needs to be occasionally reallocated for growth, the elements of a deque can be scattered in different chunks of storage, with the container keeping the necessary information internally to provide direct access to any of its elements in constant time and with a uniform sequential interface (through iterators). Therefore, deques are a little more complex internally than vectors, but this allows them to grow more efficiently under certain circumstances, especially with very long sequences, where reallocations become more expensive.

Recursion: some prerequisites like sentinel can be used before coming into the recursive function which will ease some burden. Almost all recursion can be converted to iterative using stack or queue
map: map<int, string, std::greater<int>>// descending key
comparing two arrays directly: array<int, 26> t_array{0}, s_array{0}; return s_array==t_array;
set.insert: return a pair to indicate conflict -> if(!window.insert(nums[i]).second) return true;
function unique

1
2
nums.erase(unique(nums.begin(),nums.end()),nums.end()); //return value: An iterator to the element that follows the last element not removed.
myvector.resize(distance(myvector.begin(),unique(myvector.begin(),myvector.end()))); //The number of elements between first and last.

lambda function

1
sort(newNums.begin(), newNums.end(), [](pair<int, int>&l, pair<int, int>&r){ return l.first < r.first; }); // p.s. The value returned indicates whether the element passed as first argument is considered to go before the second.

std::map will sort its elements by keys. It doesn’t care about the values when sorting.
stable_sort unlike sort will guarantee the equivalent elements are placed in their original relative order

find between two iterators

1
find_if( sortList.begin(), sortList.end(), [](const pair<string, int>& element){ return element.first == User.name } );//Returns an iterator to the first element in the range \[first,last) for which pred returns true. If no such element is found, the function returns last.

vector<pair<string, int>>insert a pair: revenue.push_back(std::make_pair(“string”,1)); revenue.emplace_back(“string”, 1);
use reference to pointer to modify pointer instead of pointer to pointer
priority_queue: priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap; //its default behavior is just like a maxHeap; Top K Frequent Elements
fill_n: fill_n(children, 26, nullptr); //Assigns val to the first n elements of the sequence pointed by first.
GrayCode: n^(n>>1)
deep copy vector whenever you copying vector
array is always more efficient compared to map, so try to use it instead of map whenever you can.
Roman Numeral: any of the letters representing numbers in the Roman numerical system: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1,000. In this system a letter placed after another of greater value adds (thus XVI or xvi is 16), whereas a letter placed before another of greater value subtracts (thus XC is 90).
In mathematics, the greatest common divisor (gcd) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4. The greatest common divisor is also known as the greatest common factor (gcf), highest common factor (hcf), greatest common measure (gcm), or highest common divisor.

  • Euclid’s algorithm
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int gcd(int a, int b)
    {
    while(b)
    {
    int t = b;
    b = a % b;
    a = t;
    }
    return a;
    }

use div to get quotient and remainder:

1
2
3
4
5
6
7
int main ()
{
div_t divresult;
divresult = div (38,5);
printf ("38 div 5 => %d, remainder %d.\n", divresult.quot, divresult.rem);
return 0;
}

  • partial_sum: partial_sum(nums.begin(), nums.end(), sums.begin() + 1);

    1
    2
    3
    4
    5
    y0 = x0
    y1 = x0 + x1
    y2 = x0 + x1 + x2
    y3 = x0 + x1 + x2 + x3
    y4 = x0 + x1 + x2 + x3 + x4
  • assign zeros for vector:

    1
    2
    3
    fill(v.begin(), v.end(), 0);
    memset(&v[0], 0, sizeof(v[0])*v.size());
    v.assgin(v.size(), 0);
  • split a string into vector:

    1
    2
    3
    4
    5
    6
    7
    vector<string> &split(const string &s, char delim, vector<string> &elems) {
    stringstream ss(s); //can be changed to fit integer;
    string item;
    while (getline(ss, item, delim))
    elems.push_back(item);
    return elems;
    }
  • remove leading and trailing white spaces;

    1
    2
    3
    4
    string delimiters = " \f\n\r\t\v";
    s.erase(s.find_last_not_of(delimiters)+1); //removing trailing white spaces;
    s.erase(0, s.find_first_not_of(delimiters)); //removing leading white spaces;
    find_last_not_of if nothing found, return string:npos which is normally -1;
  • lower_bound: Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val. std::lower_bound(collector.begin(), collector.end(), nums[i]);
    upper_bound: Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.

  • assign consecutive values to vector

    1
    2
    3
    4
    std::iota:
    std::vector<int> v(100) ; // vector with 100 ints.
    std::iota (std::begin(v), std::end(v), 0); // Fill with 0, 1, ..., 99.
    Assigns to every element in the range [first,last) successive values of val, as if incremented with ++val after each element is written.

declare first and then initialize

1
2
vector<int> sums; //you can just declare it first and then assign a value.
sums = vector<int>(size, 0);

reverse(v.begin(), v.end()) //neglecting the v.end(), so reverse(v.begin(), v.begin()+k) will reverse elements [0…k-1]

  • Control the digits of float number:
    1
    2
    3
    cout<<setprecision(5)<<f<<endl; //only control the valid digits 4-out-5-in rule;
    cout<<fixed<<setprecision(5)<<f<<endl; //control the valid digits after decimal point even there are trailing zeros;
    cout<<scientific<<setprecision(5)<<f<<endl; //just exactly as the previous fixed;

To insert another vector into the current, using insert: vv.insert(vv.end(), vv0.begin(), vv0.end());

  • 1
    2
    int numbers[] = {10,20,30};
    std::accumulate (numbers, numbers+3, init, std::minus<int>()); //the init will be the first operand always and the result will be stored into it too - init ?= for(element in range);

header <functional> contains lots of built-in function objects (Function objects are objects specifically designed to be used with a syntax similar to that of functions.).

  • When sizeof is applied to the name of an array, the result is the size in bytes of the whole array. This is one of the few exceptions to the rule that the name of an array is converted to a pointer to the first element of the array, and is possible just because the actual array size is fixed and known at compile time, when the sizeof operator is evaluated.

    1
    2
    int a[1000][1000];
    memset(a,0,sizeof a);
  • inplace_merge(v.begin(), v.begin()+m, v.end())

  • multiset to measure the distance among differnt keys, use distance(a, b) even there are duplicates, the distance will also be correct considering the duplicates.
    multiset will keep all the inserted values in strict weak ordering; besides the relative ordering of equivalent elements is preserved, and newly inserted elements follow their equivalents already in the container.

Always welcome new ideas and practical tricks, just leave them in the comments!