C++ Grammar Knowledge

Posted on Edited on In ,

This post talks about the knowledge (grammar, concepts) of C++.

Data Types

Basic Data Types

There are several data type in C++ and each data type could be regarded as an “object”. The object has an area of memory and the address of the memory. The memory stores value of the data and its address could be get by adding a & in the left.

e.g. int a = 3; and &a is its address.

Pointer

There is also a kind of data type names pointer, which also has an area of memory and the address of the memory. Differently from the normal data type, the memory stores an address of another object. By adding a & could get the address of the pointer, and adding a * could get the object that the pointer pointing to.

e.g. int a = 3; int* b = &a; and &b is the address of pointer b, and b is the address of a, which is &a, and *b is the value in address &a, which is a = 3.

Reference

Reference is a special data type and it is another name of the object. The object could be normal data type of pointer. A reference shares the same address of the object itself.

e.g. int a = 3; int& b = a;. by changing the value of b will change the value of a and vice versa. &b is same as &a.

e.g. int a = 3; int* b = &a; int*& c = b;. *b is a, *c is a. &c is the same with &b, c is the same with &a.

The reference is mainly used when passing parameters to a function. It could saves time and space.

Function Parameter Passing and Return Modes

When passing parameters to functions, the passing has following two modes.

Passing by value Passing by reference
void function (typename a) {} void function (typename& a) {}
Typename could be two main categories
Normal type: int, bool, float, double, class, etc
Pointer: int*, bool*, float*, double*, int[], class*, etc		 Same with left
Copy the content of outer argument into parameter a. The parameter a only valid inside the function. Create another name of outer argument. The parameter a shares the same address of outer parameter. The parameter a only valid inside the function
Deep copy of outer argument, cost time and space if the typename is normal type with large memory. e.g. vector<int>, class NO copy of outer argument, save time and space
All modification to a itself won’t reflect outside the function.
If the typename is a pointer, the content copied is the address of another object. Using *a could also operate the object that outer argument points to. So the modification to the object a points to could reflect outside the function		 Any modification to a is the modification to outer argument. If the passing parameters shouldn’t be changed. Use void function (const typename& a) {}

When returning results from a function, we could announce the type of return type like int func() or int& func(). Inside the function, the return xx;

Return by value Return by reference
int function() { return xx; } int& function() { static int a = 0; return a; }
Caller will create a copy same as the returned object, cost lots of resource Caller will have direct access to the original object, save lots of resource
Suitable for built-in types or small structs Suitable for large structs or classes
Can return the local variables inside the function. Can also return unique_ptr / shared_ptr pointing to a new created class Can only return static variable, or class fields
Return result is a rvalue (only can be placed on the right of operator =) Return result is a lvalue (can be placed on the left of operator =)

Common usages of return by reference

  • Return a static variable
  • Return input reference
  • Return *this
  • Return some protected/private fields inside the class

See the Pointer and Smart Pointer section for more info.

const for Pointer

When const is used to describe a variable, that means the value of the variable cannot be changed. const could also be used to describe the pointer. （左定值，右定向）

1
2
3
4
5
6
7
8
9
10
int a = 8;
int b = 9;
int* const p = &a;  // const means p must points to the address of &a
p = &b              // error
*p = 9              // correct, the value in address of &a could be changed

const int* p2 = &a; // const means the value in address &a cannot be changed
p2 = &b;            // but the address which p2 points to could be changed

const int* const p3 = &a; // both the address p3 points to and the value in address &a cannot be changed

When the const is used to describe the member method of a class in the end, it means this method cannot change the variable inside the class. This method is a read-only method.

Pointer and Smart Pointer

Pointer type Description
raw pointer (*) Stores an address of the object, but not own the object, which means the object resource could be destroyed by others.
unique_ptr Smart pointer. Hold a pointer pointing to a memory and this memory cannot be pointed by other smart pointers. Destroying this unique_ptr will destroy the memory resource automatically. In other words, this unique_ptr owns the memory. Needs to use std::move() to transfer the ownership.
shared_ptr Smart pointer. A memory resource could be pointed to by several shared_ptr. Share_ptr counts how many share_ptr pointing to this memory. The memory resource will be destroyed once the all the shared_ptr are destroyed.
weak_ptr Points to a memory together with other shared_ptr, but weak_ptr doesn’t increase the count of how many shared_ptr points to the memory. Thus weak_ptr needs to check whether the object is still alive

Smart pointer means the object which is pointed to will be automatically deallocate when the object can no longer be referenced. In other words, the object resource will be destroyed when the pointer is destroyed.

Passing a shared_ptr to a function by value will increase the count the shared_ptr. Since the parameter only exist in the function. Once the function ends, the count decreases. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// unique_ptr
std::unique_ptr<int> myInt(new int(10));
std::unique_ptr<int[]> myIntArray(new int[5] {1, 2, 3, 4, 5});
std::unique_ptr<int> myInt2 = std::move(myInt);

// shared_ptr
std::shared_ptr<int> sp(new int(42));
std::shared_ptr<MyClass> myClassPtr(new MyClass());
std::shared_ptr<MyClass> myClassPtr2 = std::make_shared<MyClass>();

// weak_ptr
std::shared_ptr<int> sp(new int(42));
std::weak_ptr<int> wp(sp);
if (auto p = wp.lock()) {
    *p;
}

Shared Pointer implementation

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream> 
#include <memory> 

template<typename T> 

class SmartPointer { 

private: 
    T* _ptr; 
    size_t* _count; 

public: 

    // Initialize a shared pointer with count 1
    SmartPointer(T* ptr = nullptr) : _ptr(ptr) { 
        if (_ptr) { 
            _count = new size_t(1); 
        } else { 
            _count = new size_t(0); 
        } 
    } 

    // Copy from another shared pointer, increase the count
    SmartPointer(const SmartPointer& ptr) { 
        if (this != &ptr) { 
            this->_ptr = ptr._ptr; 
            this->_count = ptr._count; 
            (*this->_count)++; 
        } 
    } 

    // Assign the value and return this object itself
    // Return as reference type to  1) allow to be the right value, (e.g. support a = b = c)
    // 2) avoid extra resource allocation. The outer function don't need to copy this object again 
    SmartPointer& operator=(const SmartPointer& ptr) { 
        if (this->_ptr == ptr._ptr) { 
            return *this; 
        } 

        if (this->_ptr) { 
            (*this->_count)--; 
            if (this->_count == 0) { 
                delete this->_ptr; 
                delete this->_count; 
            } 
        } 

        this->_ptr = ptr._ptr; 
        this->_count = ptr._count; 
        (*this->_count)++; 
        return *this; 
    } 

    // Return the content
    // Use reference return type to avoid copy of content
    T& operator*() { 
        assert(this->_ptr == nullptr); 
        return *(this->_ptr); 
    } 

    // Return the raw pointer
    T* operator->() { 
        assert(this->_ptr == nullptr); 
        return this->_ptr; 
    }

    // Decrease the count
    ~SmartPointer() { 
        (*this->_count)--; 
        if (*this->_count == 0) { 
            delete this->_ptr; 
            delete this->_count; 
        } 
    } 

    size_t use_count(){ 
        return *this->_count; 
    } 
}; 

int main() { 
    SmartPointer<int> sp(new int(10)); 
    SmartPointer<int> sp2(sp); 
    SmartPointer<int> sp3(new int(20)); 

    sp2 = sp3; 

    std::cout << sp.use_count() << std::endl; 
    std::cout << sp3.use_count() << std::endl; 
    //delete operator 
}

Lock of Thread

When thread A and thread B needs to operate data in thread C. There will be problem since the data from thread C vary in random time. Therefore, a lock needs to be applied to the data in thread C. The lock could guarantees the data in thread C only be modified by one thread.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// In thread C
std::mutex data_mutex;
int a = 3;

void ChangeValueManualUnlock(int b)
{
    // Thread A and thread B tries to lock the data_mutex. If cannot lock, the thread will be stuck until it could lock the the data_mutex
    data_mutex.lock();  
    
    a = b;

    // Unlock the data_mutex, otherwise the thread A or thread B will be stuck forever 
    data_mutex.unlock();  
}

void ChangeValueAutoUnlock(int b)
{
    // lck tries to lock the data_mutex at beginning. When the lck is destruct, it automatically unlock data_mutex
    std::unique_lock<std::mutex> lck(data_mutex);  
    a = b;
}

// different types of lock
// simple lock, lock the mutex immediately
std::lock_guard lck(data_mutex);

// could defer lock the mutex, could also manually unblock and lock
std::unique_lock lck(data_mutex, std::defer_lock);
lck.lock();
lck.unblock;

// lock multi-mutexes in deadlock-free manner
std::scope_lock lck(data_mutex1, data_mutex2);

// shared_mutex
std::shared_mutex shared_mutex;
// unique_lock controls the write access. Once locked, others cannot lock it again
std::unique_lock lck(shared_mutex);
// several read lock could lock the shared_mutex at the same time, enabling concurrent reading
std::shared_lock lck1(shared_mutex);
std::shared_lock lck2(shared_mutex);

When a thread is a loop and it needs to hangout during the normal time and could be trigger by other thread. The std::condition_variable could be used together with std::unique_lock and std::mutex

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
std::mutex data_mutex
std::condition_variable update;

void ThreaLoop()
{
    while (true)
    {
        std::unique_lock<std::mutex> lck(data_mutex);

        // 1) When entering thins line, the data_mutex will be firstly unblock, so that other thread could try to lock it.
        // 2) Then this update conditional_variable will wait to be notified by others
        // 3) Once notified, it checks whether the lambda expression returns true
        // 4) If the lambda expression returns true, it tries to lock the data_mutex again and continue following logics
        update.wait(lck, [&]() { return XX; });   

        // Do something
    }
}

void Update()
{
    // since the update.wait temporarily release the data_mutex, this call could succeed
    std::unique_lock<std::mutex> lck(data_mutex);
    
    // notify_all to notify all waiting thread
    update.notify_all();

    // notify_one to only notify one of the waiting thread
    // update.notify_one();
}

Operators Override

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class A{
    // Support for chain assignment: a=b=c=1
    A& operator=(const A& rhs) {
        if (this == &rhs) {
            // ..
        }

        // `this` is the pointer, `*this` is this object
        return *this;
    }

    B* b;

    B* operator->() {
        // return a pointer pointing to type of B
        // `->` will finally be translated to `*().`  b->xx => *(b).xx
        return this->b;
    }

    B& operator*() {
        return *(this->b);
    }
}

a = b equals to a.operator=(b)

Virtual Functions & Polymorphism

Principles: Virtual Tables and Virtual Table Pointer

virtual keyword marks the function can be overrided or is overriding previous functions in base class. See more in here.

The deconstrucor function of base class should be marked as virtual.

override keyword is to make sure the override behaviour happens correctly. The compiler will throw warnings if the function in derivated class doesn’t happen the override behaviour towards functions in base class.

Memory Management

Memory categories (From high address to low address)

  • Stack
  • Heap
  • Static and const values (non-initialized)
  • Static and const values (initialized)
  • Code Segment

Object Storage

  • Static storage duration objects
    • Created before entering main
    • Static initialization
    • Dynamo initialization
  • Thread storage duration objects
    • Created before thread started, similar to static storage duration objects
  • Automatic storage duration objects
    • For variables inside function
    • Allocation on the stack
  • Dynamic storage duration objects
    • With a call to new/delete , or malloc/free
    • Return the address to the allocated memory from Head
    • Smart pointer

Common problems

  • Cannot create a space in heap
  • Forget to initialize the content in heap
  • Forget to free the heap space
1
2
3
4
5
6
7
8
9
10
11
12
13
// allocate n bytes
void* buffer = malloc(n);

if (buffer == NULL) {
    // check whether allocation succeed
}

// void* points to 4 bytes in 32-bit CPU, and points to 8 bytes in 64-bit CPU
// to move void* points to the next byte
void* nextByte = (void*)((char*)buffer + 1);
void* nextByte = (void*)((size_t)buffer + 1);

free(buffer);

Hash functions

1
2
3
4
5
6
7
8
9
// Define a hash function for std::vector<double>
auto vector_hash = [](const std::vector<double>& vec) {
    size_t seed = vec.size();
    for (auto& elem : vec) {
        // Use the bitwise XOR operator to combine the hash of each element
        seed ^= std::hash<double>{}(elem) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }
    return seed;
};

Grammar and common std types

  • initialization
  • length
  • traversal
  • functions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
// ===================================================
// rand
rand() % 10;        // get random integer of [0, 9]
// ===================================================


// ===================================================
// enum
enum Weekday {
    Monday = 0,     // 0
    Tuesday,        // 1
    Wednesday       // 2
};
enum class Color {  // avoid type collisions
    Blue,           // 0
    Red = 3,        // 3
    Yellow          // 4
};
Weekday day = Monday;
Color color = Color::Red;
int day_val = static_cast<int>(day);
int day2 = static_cast<Weekday>(1);
// ===================================================


// ===================================================
// std::string
std::string str = "abc";
str.size(); str.length();  // output 3
str.substr(1, 2);   // 1 is starting position, 2 is length, so output "bc"
std::cout << str << std::endl;
for (char c: str) {
    c;
}

// char*
chat* str = new char[10];
char* str = "Hello World";  // there is a '\0' char in the end
std::size_t len = std::strlen(str);
std::cout << str << std::endl;
for (int i = 0; str[i] != '\0', ++i) {
    str[i];
}

// char array
char str[] = {'H', 'e', 'l', 'l', 'o', '\0'};
char str[] = "Hello";
std::size_t len = std::strlen(str);
std::cout.write(str, length) << std::endl;
for (int i = 0; i < length; ++i) {
    str[i];
}

// str operations
strcopy(target, source);
strcat(s1, s2); s1 + s2;
strlen(s);
strcomp(s1, s2);    // <0 if s1<s2
strchr(s1, ch);     // return the pointer to the 1-st ch character in s1
strstr(s1, s2);     // return the pointer to the 1-st s2 in s1
s1.find('-', 0);    // find the idx of first '-' char starting from idx 0. If not found, std::string::npos will be returned
std::stoi(s1);      // string to integer
to_string(123);     // integer to string
string str(1, 'a');  // char to string
string a = b;       // deep copy
string a(b);        // deep copy         
// split by character
char delimiter;
std::string token;
std::stringstream ss(path);
while (std::getline(ss, token, delimiter)) {
    tokens.push_back(token);
}     
std::tolower(c);    // upper case to lower case
std::toupper(c);    // upper case to upper case
// ===================================================


// ===================================================
// 1-d array
// In stack. Size is fixed at compile time.
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
for (int val: arr) {
    val;
}
// this works because arr is an array, but this cannot work inside a function which takes int[] as argument, since the int[] decays to int* in that scenario.
std::fill(std::begin(arr), std::end(arr), 0);   // set to 0
// pass array to functions, actually pass the address of the first element
// so the size for the array is also needed
void myFunc(int arr[], int size) {

}
void myFunc(int* arr, int size) {

}

// int*
// In heap. Dynamic size
int* a = arr;
int* a = new int[10]{0};
delete[] a;
for (int i = 0; i < 10; ++i) {
    a[i];       // C++ 20 standard
    *(a + i);
}

// 2-d array
int a[2][3] {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};
a[0][0];

// int**
int n = 10;
int** grid = new int*[n];
for (int i = 0; i < n; ++i) {
    grid[i] = new int[n];
    std::fill(&grid[i][0], &grid[i][0] + n, 0);     // initialize the row to 0
}
gird[3][4];     // C++ 20 standard
*(*(grid+3) + 4)
// ===================================================


// ===================================================
// std::array
// In stack. more like the c-style array. size cannot be changed. 
// Comparing with int[] or int* array, this std::array provides the size, begin, end functions all the time. 
#include<array>
std::array<int, 5> myArray = {0};   // all initialize to 0
std::array<int, 3> myArray = {1, 2, 3};
std::array<int, 4> myArray {4, 3, 2, 1};
int len = myArray.size();
for (int i = 0; i < myArray.size(); ++i) {
    myArray[i];
}
for (const int& element: myArray) {
    element;
}
// for_each loop could apply the function (lambda function, function pointer, or function object) to each element of the container
std::for_each(myArray.begin(), myArray.end(), [](const auto& element) {
    element;
});

// std::vector
// In heap. Container controls allocation and deallocation. The size of vector could be changed. Is contiguous in memory
int n = 3;
std::vector<int> a (n, -1);  // all initialize to -1
std::vector<std::vector<int>> b(4, std::vector<int>(4, -1));  // 4*4, all initialize to -1
int a[] = {1, 2, 3};
std::vector<int> vec(a, a + n);
int size = vec.size();
b.push_back(2); b.pop_back();
b.insert(1, 23); b.erase(1);
b.resize(3, std::vector<int>(3, -1)) // 3*3, all initialize to -1
// traversal is same as std::array above
vector<int>::iterator v = a.begin();
while (v != a.end()) {
    *v;
    ++v;
}

// std::forward_list
// In heap. Implement as singly-linked list in memory.
// cannot support random accessing
std::forward_list<int> my_list = {1, 2, 3, 4, 5};
my_list.push_front(3);
my_list.insert_after(my_list.before_begin(), 1);
my_list.insert_after(my_list.begin(), 2);
for (int element: my_list) {
    element;
}
for (auto it = my_list.begin(); my_list.end(); ++it) {
    *it;
}

// vector operations
std::vector<int> a;
std::sort(a.begin(), a.end());
std::sort(a.begin(), a.end(), [](int a, int b) { return a < b});
std::reverse(a.begin(), a.end());
std::accumulate(a.begin(), a.end(), 0);         // return sum, initial value is 0
*(std::max_element(nums.begin(), nums.end()));    // return max value
a.insert(a.begin(), 3);                         // insert value to the beginning
// ===================================================


// ===================================================
// std::queue
std::queue<int> q;
q.front(); q.back(); q.size();
q.push(3); q.pop();
while (!q.empty()) {
    q.front();
    q.pop();
}

// std::deque
std::deque<int> q;
q.front(); q.back(); q.size();
q.push_back(3); q.pop_back();
q.push_front(3); q.pop_front();
for(std::deque<int>::iterator it = q.begin(); it != q.end(); ++it) {
    *it;
}

// std::stack
std::stack<int> st;
st.top(); st.size();
st.push(3); st.pop();
while (!st.empty()) {
    st.top();
    st.pop();
}

// priority queue
std::priority_queue<int> maxQueue;
maxQueue.top();     // get the maximum number
std::priority_queue<int, vector<int>, std::greater<int>> minQueue;  // sort larger value to front
minQueue.pop();     // get the minimum number
auto cmp = [](){};
std::priority_queue<int, vector<int>, decltype(cmp)> customQueue(cmp);  // a customized priority queue

// std::heap
int myints[] = {10,20,30,5,15};
std::vector<int> v(myints, myints+5);

std::make_heap (v.begin(),v.end());
std::cout << "initial max heap   : " << v.front() << '\n';

std::pop_heap (v.begin(),v.end()); 
v.pop_back();
std::cout << "max heap after pop : " << v.front() << '\n';

v.push_back(99); 
std::push_heap (v.begin(),v.end());
std::cout << "max heap after push: " << v.front() << '\n';

std::sort_heap (v.begin(),v.end());
// ===================================================


// ===================================================
// std::set
// red-black tree. O(log(n)) operation (search, insert, delete) time
std::set<int> visited = {1, 2, 3, 4, 5};
int v[] = {1, 2, 3, 4, 5}
std::set<int> visited(std::begin(v), std::end(v));
std::vector<int> v = {1, 2, 3, 4, 5};
std::set<int> visited(v.begin(), v.end());
visited.size();
visited.insert(2);
visited.count(2);       // return 1
visited.erase(2);
for (int i : visited) {
    i;
}
for(std::set<int>::iterator it = visited.begin(); it != visited.end(); ++it) {
    *it;
}
std::foreach(visited.begin(), visited.end(), [](int i) { i; });
// define customize comparator
auto my_comparator = [](const MyType& lhs, const MyType& rhs) {
    return lhs.id < rhs.id;
};
std::unordered_set<MyType, decltype(my_comparator)> my_set(my_comparator);



// std::unordered_set
// hash table. O(1) operation time. O(n) in worst case 
std::unordered_set<int> visited;

// std::map
// red-black tree. Key in order. O(log(n)) operation (search, insert, delete) time
std::map<int, int> keyToValue {
    {1, 2},
    {2, 4},
    {3, 6}
};
std::map<int, int, std::greater<int>> maxSortedMap; 

keyToValue[1] = 3;
keyToValue.size();
keyToValue.count(1) // return 1
keyToValue.count(0) // return 0
keyToValue.erase(1) // delete key 1
keyToValue.begin()->first;  // return the smallest key
for (const auto& [key, value]: keyToValue) {
    key;
    value;
}
for (auto it = keyToValue.begin(); it != keyToValue.end(); ++it) {
    it->first;
    it->second;
}

// define customize comparator
auto my_comparator = [](const MyType& lhs, const MyType& rhs) {
    return lhs.id < rhs.id;
};
std::unordered_set<MyType, int, decltype(my_comparator)> my_set(0, my_comparator);


// std::unordered_map
// implementation is hash map. Key not in order. O(1) operation time. O(n) in worst case 
std::unordered_map<int, int> keyToValue;
// ===================================================


// ===================================================
// std::multiset
// has several same keys stored in order. Implemented as red-black tree
std::multiset<int> m = {1, 2, 3, 2, 3, 3, 4};
// above contains keys: 1, 2, 2, 3, 3, 3, 4 
auto it = m.equal_range(2);
if (it.first != it.second) {

}

// std::unordered_multiset
// implement as hash table

// std::multimap
// Has several same keys stored in order. Implemented as red-black tree
std::multimap<std::string, int> mm = {
    {"apple", 4},
    {"banana", 3},
    {"apple", 5}
};
mm.insert(std::make_pair("abc", 3));
// range is std::pair
auto range = mm.equal_range("apple");
for (auto it = range.first; it != range.second; ++it) {
    it->first;  // key
    it->second; // value
}

// std::unordered_multimap
// implement as hash table
// ===================================================


// ===================================================
// static_cast 
// Casting is checked by the compiler and any errors will be caught at compile time.
Base* base_ptr = new Derived;
Derived* derived_ptr = static_cast<Derived*>(base_ptr);
int x = 42;
double y = static_cast<double>(x);  // same to c-style conversion (double)x

// dynamic_cast 
// For type conversions between polymorphic types that requires runtime type checking. 
// Could throw exception if cannot convert.
Derived* derived_ptr = dynamic_cast<Derived*>(base_ptr);

// reinterpret_cast
// For low-level programming. Only change the types, but not change the value in memory.
float* floatPtr = new float(3.14);
int* intPtr = reinterpret_cast<int*> floatPtr;
// ===================================================


// ===================================================
// template
template<typename T>
inline T Max(const T& a, const T& b)  {
    return a < b ? b : a;
}

// lambda expression
[](int x, int y) -> int { return x + y; };
// use other variables by reference
[&](int x, int y) -> int { return a[x] < a[y]; };

// function pointer
int add(int a, int b) {

}
int (*add_ptr)(int, int) = add;
add_ptr(1, 2);

std::function<int(int, int)> add_ptr2 = add;
add_ptr(1, 2);

// callback. The callback could also be a function pointer
void compute(int x, std::function<void(int)> callback) {
    // Do some computation
    int result = x * x;
    
    // Call the callback function with the result
    callback(result);
}

void caller() {
    int a;
    compute(1, [&](int result) {
        // do something using variable a and result
    });
}
// ===================================================


// ===================================================
// struct
// fields are public by default
struct Book {
    char title[50];
    char author[50];
    int  book_id;
};
Book book;
strcpy(book.title, "hello");

// class
class Box {
public:
    Box(): length(10), width(2), height(1) {

    }
    Box(double length, double width, double height): length(length), width(width), height(height) {

    }
    Box(const int boxId): boxId(boxId) {

    }
    ~Box() {
        delete[] arr;
    }
    static Box* CreateBox() {
        Box* p = new Box(staticBoxId++);
        return p;
    }

    Box(const Box& box) {

    }
    Box operator+(const Box& box) {

    }

    // If defining pure virtual function, virtual int volume() = 0
    // then this class cannot be instantiated. This class turns to an "interface"
    virtual int volume() {

    }

    // printInfo is a function outside class Box, but it can access all fields inside class Box.
    friend void printInfo(Box box);
private:
    static int staticBoxId;
    int boxId;
    double length;
    double width;
    double height;
    int* arr;
}
Box::staticBoxId = 0;
Box box(1, 2, 3);
Box* p = new Box(1, 2, 3);

class Base {
public:
    void func();
}
// the inheritance is private by default
class Derived: public Base {
public:
    void func() {
        // call parent function
        Base::func();
    }
}
// ===================================================


// ===================================================
// exception
throw std::out_of_range("Value cannot be negative");
// ===================================================


// ===================================================
// macro
#define PI 3.1415926
#define MIN(a, b) (a < b ? a: b)
#ifdef DEBUG
    //
#endif

// pre-defined macro
__LINE__
__FILE__
__DATE__
__TIME__
// ===================================================


// ===================================================
// thread
struct thread_data {
    int thread_id;
    char* message;
}

void* PrintHello(void* threadarg) {
    struct thread_data* my_data;
    my_data = (thread_data*)threadarg;

    pthread_exit(NULL);
}

pthread_t threads[NUM_THREADS]; 
thread_data td[NUM_THREADS];
for(int i = 0; i < NUM_THREADS; ++i) {
    td[i].thread_id = i;
    td[i].message = "This is message";
    rc = pthread_create(&threads[i], 
                        NULL, 
                        PrintHello, 
                        (void *)&td[i]);
}

// std::thread
// start from C++ 11
void foo(int z) {

}

class thread_obj {
public:
    void operator()(int z) {

    }
}

auto f = [](int z) {

};

// create a thread with function/class overriding ()/lambda expression
// once created, the thread will start to execute
std::thread th1(foo, 3);
std::thread th2(thread_obj(), 3);
std::thread th3(f, 3);

// once thread variables goes out of scope. the terminate() function will be called if the thread is joinable. To avoid the thread get terminated, one of following functions need to be called.

// block current thread and wait for th1 finishes
th1.join();
// th2 will run in backend, even if th2 variable is out of scope 
th2.detach();


// async threading
int add(int a, int b) {
    return a + b;
}

// this creates another thread to run
std::future<int> result = std::async(std::launch::async, add, 10, 20);
// continue to do other things
// main thread will block until the async finishes
int res = result.get();
// ===================================================

String implementation

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream> 
#include <cstring> 

using namespace std; 

class String{ 

public: 
    String(char *str = NULL); 
    String(String &str); 
    ~String(); 

    String operator+(const String & str); 
    String& operator=(const String &str); 
    bool operator==(const String &str); 

    int length(); 
    String substr(int start, int n); 

    friend ostream & operator<<(ostream &o,const String &str); 

private: 
    char* m_data; 
    int m_size; 
}; 

String::String(char *str = NULL){ 
    if(str == NULL){ 
        m_data = new char[1]; 
        m_data[0] = '\0'; 
        m_size = 0; 
    } else { 
        m_size = strlen(str); 
        m_data = new char[m_size + 1]; 
        strcpy(m_data,str); 
    } 
} 

String::String(const String &str){ 
    m_size = str.m_size; 
    m_data = new char[m_size + 1]; 
    strcpy(m_data, str.m_data); 
} 

String::~String(){ 
    delete[] m_data; 
} 

String String::operator+(const String &str){ 
    String newStr; 
    delete[] newStr.m_data; 
    newStr.m_size = m_size + str.m_size; 
    newStr.m_data = new char[newStr.m_size + 1]; 

    strcpy(newStr.m_data, m_data); 
    strcpy(newStr.m_data + m_size, str.m_data); 
    return newStr; 
} 

String& String::operation=(const char * str){ 
    if (m_data == str){ 
        return *this; 
    } 

    delete[] m_data; 
    m_size = strlen(str); 
    m_data = new char[m_size + 1]; 
    strcpy(m_data, str); 
    return *this; 
} 

bool String::operation==(const char *str){ 
    return strcmp(m_data, str.m_data) == 0; 
} 

int String::length(){ 
    return m_size; 
} 

String String::substr(int start, int n){ 
    String newStr; 
    delete[] newStr.m_data; 
    newStr.m_data = new char[n + 1]; 
    for (int i = 0; i < n; i++) { 
        newStr.m_data[i] = m_data[start + i];    
    } 
    newStr.m_data[n] = '\0'; 
    newStr.m_size = n; 
    return newStr; 
} 

ostream & operator<<(ostream &o, const String &str){ 
    o<<str.data; 
    return o;
}

Reference

  1. C++ const 关键字小结
  2. Passing smart pointers shared_ptr and unique_ptr