Concurrent Programming Course note 1

Haolin Yang published on 2019-08-28 included in Concurrent-Programming

What is concurrency

Systems of interacting computer programs which share resource and run concurrently.

parallelism and concurrency

Parallelism: Occurring physically at the same time.

Concurrency: Occurring logically at the same time.

synchronization

Process synchronization: Ensure the instructions are executed in certain order.

Synchronization is irrelevant if processes do not interact with each other.

Concurrency, and hence process synchronized, is useful only when processes interact with each other.

interaction

Share memory is kind of interact.

Algorithm feature in c++ STL

Haolin Yang published on 2019-08-25 included in STL-Study-Note

See all algorithm click here

Mutating and Non-mutating algorithms

Mutating algorithms

Mutating algorithms means this algorithm will change the content that iterator pointed to. Like copy, swap, replace, fill, remove, permutation, partition, random shuffling and sort.

If your give these algorithms a const iterator, only error will be returned.

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

int main(int argc, char const *argv[])
{
    std::vector<int> iv = {22,30,30,17,33,40,17,23,22,12,20};

    vector<int>::iterator ib = iv.begin();
    vector<int>::iterator ie = iv.end();

    sort(ib,ie); //works

    for (std::vector<int>::iterator i = iv.begin(); i != iv.end(); ++i)
    {
        cout << *i << ' ';
    }
    cout << endl;

    // vector<int>::const_iterator ib = iv.begin();
    // vector<int>::const_iterator ie = iv.end();

    // sort(ib,ie); // error
    return 0;
}

Non-mutating algorithm

Algorithm not change any element that iterator pointed to. Like: find, search, for_each, count, equal_mismatch, max, min.

Bit operation in C++

Haolin Yang published on 2019-08-18 included in STL-Study-Note

Bit operator

operator	function	example
«	left shift	0001 –> 0010
»	right shift	0010 –> 0001
&	and (bit by bit)	1100 & 1010 = 1000
\|	or (bit by bit)	1010 \| 0101 = 1111
~	reverse	~0000 = 1111
^	XOR	0110 ^ 1100 = 1010

Operator: &

x is a bit

x & 1 = x

x & 0 = 0

Usually use & as a filter. Suppose we have a number is X, X & 0011 will get the last two bits of X.

RB tree

Haolin Yang published on 2019-08-17 included in

2-3 tree & 2-4 tree

2-node: 1 key and 2 children 3-node: 2 keys and 3 children 4-node: 3 keys and 4 children

A (2,4) tree (also called 2-4 tree or 2-3-4 tree) is a multi-way search with the following properties:

Node-Size Property: every internal node has at most four children
Depth Property: all the external nodes have the same depth

insertion

Operator overwrite in c++

Haolin Yang published on 2019-08-13 included in STL-Study-Note

Example

increment and decrement operator

#include <iostream>
using namespace std;

class INT
{
private:
    int m_i;
public:
    INT(int i):m_i(i){};

    friend bool operator==(INT& test1, INT& test2){
        return test1.m_i == test2.m_i;
    }

    friend bool operator!=(INT& test1, INT& test2){
        return test1.m_i != test2.m_i;
    }

    friend INT operator+(INT& test1, INT& test2){
        int temp = test1.m_i + test2.m_i;
        INT res(temp);
        return res;
    }

    INT& operator=(INT& test){
        this->m_i = test.m_i;
        return *this;
    }

    int& operator*() const{
        return (int&)this->m_i;
    }
    // int a() const {}; This means a() cannot change any member in class.

    INT& operator++(){ //prefix. ++test;
        this->m_i += 1;
        return *this;
    }
    // Why prefix is not const. Because it always return original class and actually it support ++++test.

    const INT operator++(int){ //postfix. test++;
        INT temp = *this;
        // ++(*this);
        this->m_i += 1;
        return temp;
    }
    // Postfix must be const. Because it return a temporary variable and it not support test++++.
    // You can try int i = 1; i++++;
    // This is invalid.

    friend ostream& operator<<(ostream& s, const INT& i){
        s << '[' << i.m_i << ']';
        return s;
    }

};

int main(int argc, char const *argv[])
{
    INT test(1);
    INT test1(10);
    INT test2(3);
    cout << ++test << endl; //[2]
    cout << test++ << endl; //[2]
    cout << test << endl; //[3]
    cout << *test << endl; //3
    cout << (test + test2) << endl; //[6]
    cout << boolalpha << (test == test2) << endl; //true
    test = test1;
    cout << test << endl; //[10]
    return 0;
}

Second Example

convert operator

Container in c++

Haolin Yang published on 2019-07-31 included in STL-Study-Note

Classification

Sequence container
- array (build in)
- vector
- heap
- priority queue
- list
- slist (not standard)
- deque
- stack (adopter)
- queue (adopter)
Associative container
- RB-tree (not public)
- set
- map
- multiset
- multemap
- hashtable (not standard)
- hash_set (not standard)
- hash_map (not standard)
- hash_multimap (not standard)
- hash_multiset (not standard)

Associative container have a key-value pair. It do not have back and front so they never have push_back, pop_back.

Vector

This is similar with grow array. Vector use sequential space.

explicit and implicit in c++

Haolin Yang published on 2019-07-25 included in C++

explicit and implicit

In C++, constructor can be explicit and implicit.

The reserve word explicit affect constructor with only one parameter or only one parameter without given initial value.

#include <iostream>
using namespace std;

class test1
{
    int data;
public:
    test1(int t = 0):data(t){};
    ~test1(){};

    test1 operator + (const test1 &a) const{
        return test1(data + a.data);
    }

    test1& operator = (const test1 &a)
    {
        this->data = a.data;
        return *this;
    }

    int getData(){return data;};
};

class test2
{
    int data;
public:
    // explicit test2(int t):data(t){};
    explicit test2(int t, int a = 0):data(t){};
    ~test2(){};

    int getData(){return data;};
};

int main(int argc, char const *argv[])
{
    test1 t1(1); //explicit constructor
    cout << t1.getData() << endl; // 1

    test1 t2 = 1; //implicit constructor
    cout << t2.getData() << endl; // 1

    test1 t3 = 'a'; //implicit convert integer into char and call implicit constructor
    cout << t3.getData() << endl; // 97

    test1 t4;
    t4 = t2 + 3; // + operation will take 3 and call implicit constructor

    t4 = 3 + t2; // ERROR! + operater belongs the integer and it doesn't know how to convert t2

    test2 t5('a');// explicit constructor is OK
    cout << t5.getData() << endl; // 97

    test2 t6 = 'a'; //error. Must be explicit.
    return 0;
}

t1(1) -> explicit t1 = 1 -> implicit

Iterator in c++

Haolin Yang published on 2019-07-24 included in STL-Study-Note

Iterator 设计思维

STL 中 container 和 algorithm 是相对独立的，本身设计也是泛型化的。Iterator 就是用来将这两者联系在一起的。

Iterator 是一种 smart pointer

可以不用 delete

Iterator 属性

iterator_traits 是用来抽取 iterator 中的类型(特指 value type)的。

这是 iterator 中常见的五种属性。

template <class I>
struct iterator_traits
{
    typedef typename I::iterator_category iterator_category; //category
    typedef typename I::value_type value_type; // type
    typedef typename I::difference_type difference_type; //
    typedef typename I::pointer pointer; // T*
    typedef typename I::reference reference; // T&
};

#include <iostream>     // std::cout
#include <iterator>     // std::iterator_traits
#include <typeinfo>     // typeid
using namespace std;

int main() {
  typedef std::iterator_traits<double*> traits;
  cout << typeid(traits::iterator_category).name() << endl;
  cout << typeid(traits::value_type).name() << endl;
  cout << typeid(traits::difference_type).name() << endl;
  cout << typeid(traits::pointer).name() << endl;
  cout << typeid(traits::reference).name() << endl;
  return 0;
}

NSt3__126random_access_iterator_tagE
d
l
Pd
d
yanghaoli

iterator_category

Input iterator: Read only. Cannot be change.
Output iterator: Write only.
Forward iterator: Allow write and only one direction.(only operator++). Some algorithms use one direction enough.(like replace())
Bidirectional iterator: For some algorithm will move both direction. Support operator++ and operator–.
Random access iterator: Support more operator. p+n, p-n, p[n], p1-p2, p1 < p2.

iterator & const_iterator

const_iterator is read only.

Allocator in c++

Haolin Yang published on 2019-07-21 included in STL-Study-Note

Allocator is for memory

配置内存空间 -> 构建(constructor) -> 解构(destructor) -> 释放内存空间

construct() and destroy()

用于建构和解构

Memory allocate and release

双层配置器。第一级是区块大于 128 bytes 的，使用 malloc()和 free()。第二级是区块小于 128 bytes 的，使用 memory pool 和 freelist。

第一級配置器

第一級配置器以 malloc(), free(), realloc() 等 C 函式執行實際的記憶體配置、釋放、重配置動作，並實作出類似 C++ new-handler7 機制。是的，它不能直接運用 C++ new-handler 機制，因為它並非使用 ::operator new 來配置記憶體。

所謂 C++ new handler 機制是，你可以要求系統在記憶體配置需求無法被滿足時，喚起一個你所指定的函式。換句話說一旦 ::operator new 無法達成任務，在丟出 std::bad_alloc 異常狀態之前，會先呼叫由客端指定的處理常式。此處理常式通常即被稱為 new-handler。new-handler 解決記憶體不足的作法有特定的模式。

注意，SGI 以 malloc 而非 ::operator new 來配置記憶體(我所能夠想像的一個原因是歷史因素，另一個原因是 C++ 並未提供相應於 realloc() 的記憶體配置動作)，因此 SGI 不能直接使用 C++ 的 set_new_handler()，必須模擬一個類似的 set_malloc_handler()。

Functor in C++

Haolin Yang published on 2019-07-20 included in STL-Study-Note

Basically, Functor have same functionality with interface in java.

Think about this code. You want count all string whose length is less than 5.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

bool lenLessThanFive(const string& str){
    return str.size() < 5;
}

int main(int argc, char const *argv[])
{
    string ia[5] = {"a", "aa", "aaa", "aaaa", "aaaaa"};
    vector<string> iv(ia, ia+5);
    int res = count_if(iv.begin(), iv.end(), lenLessThanFive);
    cout << "res= " << res << endl;
    return 0;
}

lenLessThanFive is a function pointer here. It is work right, but it lack scalability. We cannot change the threshold in the function every time. Meanwhile, Function need to be unary(only one parameter). Therefore, we can consider the Functor.