-
Notifications
You must be signed in to change notification settings - Fork 1
/
tag-cmu.html
2547 lines (2458 loc) · 154 KB
/
tag-cmu.html
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
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<link rel="alternate"
type="application/rss+xml"
href="https://chenyo.me/rss.xml"
title="RSS feed for https://chenyo.me">
<title>Chenyo's Blog</title>
<script type="text/javascript"
src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'],['\\(','\\)']]}});
</script>
<meta name="author" content="chenyo">
<meta name="referrer" content="no-referrer">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="stylesheet" href="assets/style.css" type="text/css"/>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.4.0/css/all.min.css"/>
<link rel="favicon" type="image/x-icon" href="favicon.ico">
<script src="assets/search.js"></script></head>
<body>
<div id="preamble" class="status">
<header>
<h1><a href="https://chenyo.me">Chenyo's org-static-blog</a></h1>
<nav>
<a href="https://chenyo.me">Home</a>
<a href="archive.html">Archive</a>
<a href="tags.html">Tags</a>
<div id="search-container">
<input type="text" id="search-input" placeholder="Search anywhere...">
<i class="fas fa-search search-icon"></i>
</div>
</nav>
</header></div>
<div id="content">
<h1 class="title">Posts tagged "cmu":</h1>
<div class="post-date">24 Sep 2024</div><h1 class="post-title"><a href="https://chenyo.me/2024-09-24-cpp-feature-introduction.html">C++ feature introduction</a></h1>
<nav id="table-of-contents" role="doc-toc">
<h2>Table of Contents</h2>
<div id="text-table-of-contents" role="doc-toc">
<ul>
<li><a href="#orgf153467">1. Namespace</a></li>
<li><a href="#org40232d3">2. Wrapper class</a></li>
<li><a href="#orgc9d8f4f">3. Iterator</a>
<ul>
<li><a href="#org94cb86d">3.1. A doubly linked list (DLL) iterator</a></li>
</ul>
</li>
<li><a href="#org4c18899">4. STL containers</a>
<ul>
<li><a href="#org6dcfbeb">4.1. Vector</a></li>
<li><a href="#orgfc95fbf">4.2. Set</a></li>
<li><a href="#org5038e7e">4.3. Unordered maps</a></li>
</ul>
</li>
<li><a href="#org644b019">5. <code>auto</code></a></li>
<li><a href="#org6876e1c">6. Smart pointers</a>
<ul>
<li><a href="#org03a407c">6.1. <code>std::unique_ptr</code></a></li>
<li><a href="#orga17c160">6.2. <code>std::shared_ptr</code></a></li>
</ul>
</li>
<li><a href="#orgff9d615">7. Synchronization</a>
<ul>
<li><a href="#org720a20f">7.1. <code>std::mutex</code></a></li>
<li><a href="#org972445b">7.2. <code>std::scoped_lock</code></a></li>
<li><a href="#org9630937">7.3. <code>std::condition_variable</code></a></li>
<li><a href="#org45ff32d">7.4. Reader-writer lock</a></li>
</ul>
</li>
</ul>
</div>
</nav>
<p>
This is a personal not for the <a href="https://github.com/cmu-db/15445-bootcamp">CMU 15-445 C++ bootcamp</a> along with some explanation from Claude.ai.
</p>
<div id="outline-container-orgf153467" class="outline-2">
<h2 id="orgf153467"><span class="section-number-2">1.</span> Namespace</h2>
<div class="outline-text-2" id="text-1">
<ul class="org-ul">
<li>Provides scopes to identifiers with <code>::</code>.</li>
<li><p>
Namespaces can be nested.
</p>
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><iostream></span>
<span style="color: #51afef;">namespace</span> <span style="color: #a9a1e1;">ABC</span> {
<span style="color: #ECBE7B;">void</span> <span style="color: #c678dd;">spam</span>(<span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">a</span>) { <span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"Hello from ABC::spam"</span> << <span style="color: #a9a1e1;">std</span>::endl; }
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">declare a nested namespace</span>
<span style="color: #51afef;">namespace</span> <span style="color: #a9a1e1;">DEF</span> {
<span style="color: #ECBE7B;">void</span> <span style="color: #c678dd;">bar</span>(<span style="color: #ECBE7B;">float</span> <span style="color: #dcaeea;">a</span>) { <span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"Hello from ABC::DEF::bar"</span> << <span style="color: #a9a1e1;">std</span>::endl; }
<span style="color: #ECBE7B;">void</span> <span style="color: #c678dd;">use_spam</span>(<span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">a</span>) {
<span style="color: #a9a1e1;">ABC</span>::spam(a);
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">no difference with ABC::spam(a) if DEF</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">does not have a spam function</span>
spam(a);
}
} <span style="color: #5B6268;">// </span><span style="color: #5B6268;">namespace DEF</span>
<span style="color: #ECBE7B;">void</span> <span style="color: #c678dd;">use_DEF_bar</span>(<span style="color: #ECBE7B;">float</span> <span style="color: #dcaeea;">a</span>) {
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">if a namespace outside of DEF wants to use DEF::bar</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">it must use the full namespace path ABC::DEF::bar</span>
<span style="color: #a9a1e1;">DEF</span>::bar(a);
}
} <span style="color: #5B6268;">// </span><span style="color: #5B6268;">namespace ABC</span>
</pre>
</div></li>
<li>Two namespaces can define functions with the same name and signatures.</li>
<li>Name resolution rules: first check in the current scope, then enclosing scopes, finally going outward until it reaches the global scope.</li>
<li>Can use <code>using namespace B</code> to use identifiers in <code>B</code> in the current scope without specifying <code>B::</code>, this is not a good practice.</li>
<li>Can also only bring certain members of a namespace into the current scope, e.g., <code>using C::eggs</code>.</li>
</ul>
</div>
</div>
<div id="outline-container-org40232d3" class="outline-2">
<h2 id="org40232d3"><span class="section-number-2">2.</span> Wrapper class</h2>
<div class="outline-text-2" id="text-2">
<ul class="org-ul">
<li><p>
Used to manage a resource, e.g., memory, file sockets, network connections.
</p>
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef;">class</span> <span style="color: #ECBE7B;">IntPtrManager</span> {
<span style="color: #51afef;">private</span>:
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">manages an int* to access the dynamic memory</span>
<span style="color: #ECBE7B;">int</span> *<span style="color: #dcaeea;">ptr_</span>;
};
</pre>
</div></li>
<li>Use the RAII (Resource Acquisition is Initialization) idea: tie the lifetime of a resource to the lifetime of an object.
<ul class="org-ul">
<li>Goal: ensure resources are released even if an exception occurs.</li>
<li><p>
Acquisition: resources are acquired in the constructor.
</p>
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef;">class</span> <span style="color: #ECBE7B;">IntPtrManager</span> {
<span style="color: #51afef;">public</span>:
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">the constructor initializes a resource</span>
<span style="color: #c678dd;">IntPtrManager</span>() {
ptr_ = <span style="color: #51afef;">new</span> <span style="color: #ECBE7B;">int</span>; <span style="color: #5B6268;">// </span><span style="color: #5B6268;">allocate the memory</span>
*ptr_ = <span style="color: #da8548; font-weight: bold;">0</span>; <span style="color: #5B6268;">// </span><span style="color: #5B6268;">set the default value</span>
}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">the second constructor takes an initial value</span>
<span style="color: #c678dd;">IntPtrManager</span>(<span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">val</span>) {
ptr_ = <span style="color: #51afef;">new</span> <span style="color: #ECBE7B;">int</span>;
*ptr_ = val;
}
};
</pre>
</div></li>
<li><p>
Release: resources are released in the destructor.
</p>
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef;">class</span> <span style="color: #ECBE7B;">IntPtrManager</span> {
<span style="color: #51afef;">public</span>:
~<span style="color: #c678dd;">IntPtrManager</span>() {
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">ptr_ may be null after the move</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">don't delete a null pointer</span>
<span style="color: #51afef;">if</span> (ptr_) {
<span style="color: #51afef;">delete</span> ptr_;
}
}
};
</pre>
</div></li>
</ul></li>
<li><p>
A wrapper class should not be copyable to avoid double deletion of the same resource in two destructors.
</p>
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef;">class</span> <span style="color: #ECBE7B;">IntPtrManager</span> {
<span style="color: #51afef;">public</span>:
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">delete copy constructor</span>
<span style="color: #c678dd;">IntPtrManager</span>(<span style="color: #51afef;">const</span> <span style="color: #ECBE7B;">IntPtrManager</span> &) = <span style="color: #51afef;">delete</span>;
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">delete copy assignment operator</span>
<span style="color: #ECBE7B;">IntPtrManager</span> &<span style="color: #51afef;">operator</span><span style="color: #c678dd;">=</span>(<span style="color: #51afef;">const</span> <span style="color: #ECBE7B;">IntPtrManager</span> &) = <span style="color: #51afef;">delete</span>;
};
</pre>
</div></li>
<li><p>
A wrapper class is still moveable from different lvalues/owners.
</p>
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef;">class</span> <span style="color: #ECBE7B;">IntPtrManager</span> {
<span style="color: #51afef;">public</span>:
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">a move constructor</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">called by IntPtrManager b(std::move(a))</span>
<span style="color: #c678dd;">IntPtrManager</span>(<span style="color: #ECBE7B;">IntPtrManager</span> &&<span style="color: #dcaeea;">other</span>) {
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">while other is a rvalue reference, other.ptr_ is a lvalue</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">therefore a copy happens here, not a move</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">in the constructor this.ptr_ has not pointed to anything</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">so no need to delete ptr_</span>
ptr = other.ptr_;
other.ptr_ = <span style="color: #a9a1e1;">nullptr</span>; <span style="color: #5B6268;">// </span><span style="color: #5B6268;">other.ptr_ becomes invalud</span>
}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">move assignment operator</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">this function is used by c = std::move(b) operation</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">note that calling std::move() does not require implementing this operator</span>
<span style="color: #ECBE7B;">IntPtrManager</span> &<span style="color: #51afef;">operator</span><span style="color: #c678dd;">=</span>(<span style="color: #ECBE7B;">IntPtrManager</span> &&<span style="color: #dcaeea;">other</span>) {
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">a self assignment should not delete its ptr_</span>
<span style="color: #51afef;">if</span> (ptr_ == other.ptr_) {
<span style="color: #51afef;">return</span> *<span style="color: #51afef;">this</span>;
}
<span style="color: #51afef;">if</span> (ptr_) {
<span style="color: #51afef;">delete</span> ptr_; <span style="color: #5B6268;">// </span><span style="color: #5B6268;">release old resource to avoid leak</span>
}
ptr_ = other.ptr_;
other.ptr_ = <span style="color: #a9a1e1;">nullptr</span>; <span style="color: #5B6268;">// </span><span style="color: #5B6268;">invalidate other.ptr_</span>
<span style="color: #51afef;">return</span> *<span style="color: #51afef;">this</span>;
}
};
</pre>
</div></li>
</ul>
</div>
</div>
<div id="outline-container-orgc9d8f4f" class="outline-2">
<h2 id="orgc9d8f4f"><span class="section-number-2">3.</span> Iterator</h2>
<div class="outline-text-2" id="text-3">
<ul class="org-ul">
<li><p>
Iterators, e.g., pointers, are objects that point to an element inside a container.
</p>
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #ECBE7B;">int</span> *<span style="color: #dcaeea;">array</span> = malloc(<span style="color: #51afef;">sizeof</span>(<span style="color: #ECBE7B;">int</span>) * <span style="color: #da8548; font-weight: bold;">10</span>);
<span style="color: #ECBE7B;">int</span> *<span style="color: #dcaeea;">iter</span> = array;
<span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">zero_elem</span> = *iter;
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">use ++ to iterate through the C style array</span>
iter++;
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">deference the operator to return the value at the iterator</span>
<span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">first_elem</span> = *iter;
</pre>
</div></li>
<li>Two main components of an iterator:
<ul class="org-ul">
<li>Dereference operator <code>*</code>: return the value of the element of the current iterator position.</li>
<li>Increment <code>++</code>: increment the iterator’s position by 1
<ul class="org-ul">
<li>Postfix <code>iter++</code>: return the iterator <b><b>before</b></b> the increment (<code>Iterator</code>).</li>
<li>Prefix <code>++iter</code>: return the result of the increment (<code>Iterator&</code>).</li>
<li><code>++iter</code> is more efficient.</li>
</ul></li>
</ul></li>
<li>Often used to access and modify elements in C++ STL containers.</li>
</ul>
</div>
<div id="outline-container-org94cb86d" class="outline-3">
<h3 id="org94cb86d"><span class="section-number-3">3.1.</span> A doubly linked list (DLL) iterator</h3>
<div class="outline-text-3" id="text-3-1">
<ul class="org-ul">
<li><p>
Define a link node:
</p>
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef;">struct</span> <span style="color: #ECBE7B;">Node</span> {
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">member initializer list, e.g., next_(nullptr) equals to next_ = nullptr</span>
<span style="color: #c678dd;">Node</span>(<span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">val</span>) : next_(<span style="color: #a9a1e1;">nullptr</span>), prev_(<span style="color: #a9a1e1;">nullptr</span>), value_(val) {}
<span style="color: #ECBE7B;">Node</span> *<span style="color: #dcaeea;">next_</span>;
<span style="color: #ECBE7B;">Node</span> *<span style="color: #dcaeea;">prev_</span>;
<span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">value_</span>;
};
</pre>
</div></li>
<li><p>
Define the iterator for the DLL:
</p>
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef;">class</span> <span style="color: #ECBE7B;">DLLIterator</span> {
<span style="color: #51afef;">public</span>:
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">takes in a node to mark the start of the iteration</span>
<span style="color: #c678dd;">DLLIterator</span>(<span style="color: #ECBE7B;">Node</span> *<span style="color: #dcaeea;">head</span>) : curr_(head) {}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">prefix increment operator (++iter)</span>
<span style="color: #ECBE7B;">DLLIterator</span> &<span style="color: #51afef;">operator</span><span style="color: #c678dd;">++</span>() {
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">must use -> to access the member of a pointer!</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">use . if accessing the object itself</span>
curr_ = curr_->next_;
<span style="color: #51afef;">return</span> *<span style="color: #51afef;">this</span>;
}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">postfix increment operator (iter++)</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">the (int) is a dummy parameter to differentiate</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">the prefix and postfix increment</span>
<span style="color: #ECBE7B;">DLLIterator</span> <span style="color: #51afef;">operator</span><span style="color: #c678dd;">++</span>(<span style="color: #ECBE7B;">int</span>) {
<span style="color: #ECBE7B;">DLLIterator</span> <span style="color: #dcaeea;">temp</span> = *<span style="color: #51afef;">this</span>;
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">this is a pointer to the current object</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">*this returns the iterator object</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">++*this calls the prefix increment operator,</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">which equals to `this->operator++()`</span>
++*<span style="color: #51afef;">this</span>;
<span style="color: #51afef;">return</span> temp;
}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">implement the equality operator</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">an lvalue reference argument avoids the copy</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">the const in the parameter means this function</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">cannot modify the argument</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">the `const` outside the parameter list means</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">the function cannot modify `this`</span>
<span style="color: #ECBE7B;">bool</span> <span style="color: #51afef;">operator</span><span style="color: #c678dd;">==</span>(<span style="color: #51afef;">const</span> <span style="color: #ECBE7B;">DLLIterator</span> &<span style="color: #dcaeea;">str</span>) <span style="color: #51afef;">const</span> {
<span style="color: #51afef;">return</span> itr.curr_ == <span style="color: #51afef;">this</span>->curr_;
}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">implement the dereference operator to return the value</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">at the current iterator position</span>
<span style="color: #ECBE7B;">int</span> <span style="color: #51afef;">operator</span><span style="color: #c678dd;">*</span>() { <span style="color: #51afef;">return</span> curr_->value_; }
<span style="color: #51afef;">private</span>:
<span style="color: #ECBE7B;">Node</span> *<span style="color: #dcaeea;">curr_</span>;
};
</pre>
</div></li>
<li><p>
Define DLL:
</p>
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef;">class</span> <span style="color: #ECBE7B;">DLL</span> {
<span style="color: #51afef;">public</span>:
<span style="color: #c678dd;">DLL</span>() : head_(<span style="color: #a9a1e1;">nullptr</span>), size_(<span style="color: #da8548; font-weight: bold;">0</span>) {}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">the destructor deletes nodes one by one</span>
~<span style="color: #c678dd;">DLL</span>() {
<span style="color: #ECBE7B;">Node</span> *<span style="color: #dcaeea;">current</span> = head_;
<span style="color: #51afef;">while</span> (current != <span style="color: #a9a1e1;">nullptr</span>) {
<span style="color: #ECBE7B;">Node</span> *<span style="color: #dcaeea;">next</span> = current->next_;
<span style="color: #51afef;">delete</span> current;
current = next;
}
head_ = <span style="color: #a9a1e1;">nullptr</span>;
}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">after the insertion `new_node` becomes the new head</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">`head` is just a pointer to the node</span>
<span style="color: #ECBE7B;">void</span> <span style="color: #c678dd;">InsertAtHead</span>(<span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">val</span>) {
<span style="color: #ECBE7B;">Node</span> *<span style="color: #dcaeea;">new_node</span> = <span style="color: #51afef;">new</span> <span style="color: #ECBE7B;">Node</span>(val);
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">new_node->next points to the object pointed by head_</span>
new_node->next_ = head_;
<span style="color: #51afef;">if</span> (head_ != <span style="color: #a9a1e1;">nullptr</span>) {
head_->prev_ = new_node;
}
head_ = new_node;
size_ += <span style="color: #da8548; font-weight: bold;">1</span>;
}
<span style="color: #ECBE7B;">DLLIterator</span> <span style="color: #c678dd;">Begin</span>() { <span style="color: #51afef;">return</span> DLLIterator(head_); }
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">returns the pointer pointing one after the last element</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">used in the loop to determine whether the iteration ends</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">e.g., `for (DLLIterator iter = dll.Begin(); iter != dll.End(); ++iter)`</span>
<span style="color: #ECBE7B;">DLLIterator</span> <span style="color: #c678dd;">End</span>() { <span style="color: #51afef;">return</span> DLLIterator(<span style="color: #a9a1e1;">nullptr</span>); }
<span style="color: #ECBE7B;">Node</span> *<span style="color: #dcaeea;">head_</span>{<span style="color: #a9a1e1;">nullptr</span>}; <span style="color: #5B6268;">// </span><span style="color: #5B6268;">in-class initializers</span>
<span style="color: #ECBE7B;">size_t</span> <span style="color: #dcaeea;">size_</span>;
};
</pre>
</div></li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org4c18899" class="outline-2">
<h2 id="org4c18899"><span class="section-number-2">4.</span> STL containers</h2>
<div class="outline-text-2" id="text-4">
<ul class="org-ul">
<li>The C++ STL (standard library) is a generic collection of data structure and algorithm implementations, e.g., stacks, queues, hash tables.</li>
<li>Each container has own header, e.g., <code>std::vector</code>.</li>
<li>The <code>std::set</code> is implemented as a red-black tree.</li>
</ul>
</div>
<div id="outline-container-org6dcfbeb" class="outline-3">
<h3 id="org6dcfbeb"><span class="section-number-3">4.1.</span> Vector</h3>
<div class="outline-text-3" id="text-4-1">
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><algorithm></span> <span style="color: #5B6268;">// </span><span style="color: #5B6268;">to use std::remove_if</span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><iostream></span> <span style="color: #5B6268;">// </span><span style="color: #5B6268;">to use std::cout</span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><vector></span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">A helper class used for vector</span>
<span style="color: #51afef;">class</span> <span style="color: #ECBE7B;">Point</span> {
<span style="color: #51afef;">public</span>:
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">constructors</span>
<span style="color: #c678dd;">Point</span>() : x_(<span style="color: #da8548; font-weight: bold;">0</span>), y_(<span style="color: #da8548; font-weight: bold;">0</span>) {}
<span style="color: #c678dd;">Point</span>(<span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">x</span>, <span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">y</span>) : x_(x), y_(y) {}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">inline asks the compiler to substitute the function</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">directly at the calling location instead of performing</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">a normal function call, to improve performance for small functions</span>
<span style="color: #51afef;">inline</span> <span style="color: #ECBE7B;">int</span> <span style="color: #c678dd;">GetX</span>() <span style="color: #51afef;">const</span> { <span style="color: #51afef;">return</span> x_; }
<span style="color: #51afef;">inline</span> <span style="color: #ECBE7B;">void</span> <span style="color: #c678dd;">SetX</span>(<span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">x</span>) { x_ = x; }
<span style="color: #ECBE7B;">void</span> <span style="color: #c678dd;">PrintPoint</span>() <span style="color: #51afef;">const</span> {
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"Point: ("</span> << x_ << <span style="color: #98be65;">", "</span> << <span style="color: #98be65;">"y_"</span> << <span style="color: #98be65;">")\n"</span>;
}
<span style="color: #51afef;">private</span>:
<span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">x_</span>;
<span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">y_</span>;
};
<span style="color: #ECBE7B;">int</span> <span style="color: #c678dd;">main</span>() {
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">vector</span><<span style="color: #ECBE7B;">Point</span>> <span style="color: #dcaeea;">point_vector</span>;
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">approach 1 to append to a vector</span>
point_vector.push_back(Point(<span style="color: #da8548; font-weight: bold;">35</span>, <span style="color: #da8548; font-weight: bold;">36</span>));
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">approach 2, pass the argument to Point(x,y) constructor</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">slightly faster than push_back</span>
point_vector.emplace_back(<span style="color: #da8548; font-weight: bold;">37</span>, <span style="color: #da8548; font-weight: bold;">38</span>);
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">iterate through index</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">size_t: unsigned integers specifially used in loop or counting</span>
<span style="color: #51afef;">for</span> (<span style="color: #ECBE7B;">size_t</span> <span style="color: #dcaeea;">i</span> = <span style="color: #da8548; font-weight: bold;">0</span>; i < point_vector.size(); ++i) {
point_vector[i].PrintPoint();
}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">iterate through mutable reference</span>
<span style="color: #51afef;">for</span> (<span style="color: #ECBE7B;">Point</span> &<span style="color: #dcaeea;">item</span> : point_vector) {
item.SetX(<span style="color: #da8548; font-weight: bold;">10</span>);
}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">iterate through immutable reference</span>
<span style="color: #51afef;">for</span> (<span style="color: #51afef;">const</span> <span style="color: #ECBE7B;">Point</span> &<span style="color: #dcaeea;">item</span> : point_vector) {
item.GetX();
}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">initialize the vector with an initializer list</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">vector</span><<span style="color: #ECBE7B;">int</span>> <span style="color: #dcaeea;">int_vector</span> = {<span style="color: #da8548; font-weight: bold;">0</span>, <span style="color: #da8548; font-weight: bold;">1</span>, <span style="color: #da8548; font-weight: bold;">2</span>, <span style="color: #da8548; font-weight: bold;">3</span>};
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">erase element given its index</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">int_vector.begin() returns a std::vector<int>::iterator</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">pointing to the first elemnt in the vector</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">the vector iterator has a plus iterator</span>
int_vector.erase(int_vector.begin() + <span style="color: #da8548; font-weight: bold;">2</span>); <span style="color: #5B6268;">// </span><span style="color: #5B6268;">{0, 1, 3}</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">erase a range of elements</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">int_vector.end() points to the end of a vector (not the last element)</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">and cannot be accessed.</span>
int_vector.erase(int_vector.begin() + <span style="color: #da8548; font-weight: bold;">1</span>, int_vector.end()); <span style="color: #5B6268;">// </span><span style="color: #5B6268;">{0}</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">erase elements via filtering</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">std::remove_if(range_begin, range_end, condition) returns an iterator</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">pointing to the first element to be erased</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">remove_if() also partitions point_vector so that unsatisfied elements are</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">moved before the point_vector.begin(), i.e., the vector is reordered</span>
point_vector.erase(
<span style="color: #a9a1e1;">std</span>::remove_if(point_vector.begin(), point_vector.end(),
[](<span style="color: #51afef;">const</span> <span style="color: #ECBE7B;">Point</span> &<span style="color: #dcaeea;">point</span>) { <span style="color: #51afef;">return</span> point.GetX() == <span style="color: #da8548; font-weight: bold;">10</span>; }),
point_vector.end());
<span style="color: #51afef;">return</span> <span style="color: #da8548; font-weight: bold;">0</span>;
}
</pre>
</div>
</div>
</div>
<div id="outline-container-orgfc95fbf" class="outline-3">
<h3 id="orgfc95fbf"><span class="section-number-3">4.2.</span> Set</h3>
<div class="outline-text-3" id="text-4-2">
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><iostream></span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><set></span>
<span style="color: #ECBE7B;">int</span> <span style="color: #c678dd;">main</span>() {
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">set</span><<span style="color: #ECBE7B;">int</span>> <span style="color: #dcaeea;">int_set</span>;
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">can insert element with .insert() or .emplace()</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">.emplace() allows to construct the object in place</span>
<span style="color: #51afef;">for</span> (<span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">i</span> = <span style="color: #da8548; font-weight: bold;">1</span>; i <= <span style="color: #da8548; font-weight: bold;">5</span>; ++i) {
int_set.insert(i);
}
<span style="color: #51afef;">for</span> (<span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">i</span> = <span style="color: #da8548; font-weight: bold;">6</span>; i <= <span style="color: #da8548; font-weight: bold;">10</span>; ++i) {
int_set.emplace(i);
}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">iterate the set</span>
<span style="color: #51afef;">for</span> (<span style="color: #a9a1e1;">std</span>::<span style="color: #a9a1e1;">set</span><<span style="color: #ECBE7B;">int</span>>::<span style="color: #ECBE7B;">iterator</span> <span style="color: #dcaeea;">it</span> = int_set.begin(); it != int_set.end();
++it) {
<span style="color: #a9a1e1;">std</span>::cout << *it << <span style="color: #98be65;">" "</span>;
}
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"\n"</span>;
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">.find(key) returns an iterator pointing to the key</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">if it is in the set, otherwise returns .end()</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #a9a1e1;">set</span><<span style="color: #ECBE7B;">int</span>>::<span style="color: #ECBE7B;">iterator</span> <span style="color: #dcaeea;">search</span> = int_set.find(<span style="color: #da8548; font-weight: bold;">2</span>);
<span style="color: #51afef;">if</span> (search != int_set.end()) {
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"2 is not found\n"</span>;
}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">check whether the set contains a key with .count()</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">it returns either 0 or 1 as each key is unique</span>
<span style="color: #51afef;">if</span> (int_set.count(<span style="color: #da8548; font-weight: bold;">11</span>) == <span style="color: #da8548; font-weight: bold;">0</span>) {
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"11 is not in the set.\n"</span>;
}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">erase a key, returns the count of removed elements 0 or 1</span>
int_set.erase(<span style="color: #da8548; font-weight: bold;">4</span>);
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">erase a key given its position, returns the iterator to the next element</span>
int_set.erase(int_set.begin());
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">erase a range of elements</span>
int_set.erase(int_set.find(<span style="color: #da8548; font-weight: bold;">9</span>), int_set.end());
}
</pre>
</div>
</div>
</div>
<div id="outline-container-org5038e7e" class="outline-3">
<h3 id="org5038e7e"><span class="section-number-3">4.3.</span> Unordered maps</h3>
<div class="outline-text-3" id="text-4-3">
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><iostream></span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><string></span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><unordered_map></span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><utility></span> <span style="color: #5B6268;">// </span><span style="color: #5B6268;">to use std::make_pair</span>
<span style="color: #ECBE7B;">int</span> <span style="color: #c678dd;">main</span>() {
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">unordered_map</span><<span style="color: #a9a1e1;">std</span>::string, <span style="color: #ECBE7B;">int</span>> <span style="color: #dcaeea;">map</span>;
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">insert items</span>
map.insert({<span style="color: #98be65;">"foo"</span>, <span style="color: #da8548; font-weight: bold;">2</span>});
map.insert({{<span style="color: #98be65;">"bar"</span>, <span style="color: #da8548; font-weight: bold;">1</span>}, {<span style="color: #98be65;">"eggs"</span>, <span style="color: #da8548; font-weight: bold;">2</span>}});
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">insert items via pairs</span>
map.insert(<span style="color: #a9a1e1;">std</span>::make_pair(<span style="color: #98be65;">"hello"</span>, <span style="color: #da8548; font-weight: bold;">10</span>));
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">insert items in an array-style</span>
<span style="color: #ECBE7B;">map</span>[<span style="color: #98be65;">"world"</span>] = <span style="color: #da8548; font-weight: bold;">3</span>;
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">update the value</span>
<span style="color: #ECBE7B;">map</span>[<span style="color: #98be65;">"foo"</span>] = <span style="color: #da8548; font-weight: bold;">9</span>;
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">.find() returns an iterator pointing to the item</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">or the end</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #a9a1e1;">unordered_map</span><<span style="color: #a9a1e1;">std</span>::string, <span style="color: #ECBE7B;">int</span>>::<span style="color: #ECBE7B;">iterator</span> <span style="color: #dcaeea;">result</span> = map.find(<span style="color: #98be65;">"bar"</span>);
<span style="color: #51afef;">if</span> (result != map.end()) {
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">one way to access the item</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">both '\n' and std::endl prints newliine, but std::endl</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">also flushes the output buffer, so use '\n' is better</span>
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"key: "</span> << result->first << <span style="color: #98be65;">" value: "</span> << result->second
<< <span style="color: #a9a1e1;">std</span>::endl;
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">another way is dereferencing</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">pair</span><<span style="color: #a9a1e1;">std</span>::string, <span style="color: #ECBE7B;">int</span>> <span style="color: #dcaeea;">pair</span> = *result;
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"key: "</span> << pair.first << <span style="color: #98be65;">" value: "</span> << pair.second
<< <span style="color: #a9a1e1;">std</span>::endl;
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">check whether a key exists with .count()</span>
<span style="color: #51afef;">if</span> (map.count(<span style="color: #98be65;">"foo"</span>) == <span style="color: #da8548; font-weight: bold;">0</span>) {
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"foo does not exist\n"</span>;
}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">erase an item via a key</span>
map.erase(<span style="color: #98be65;">"world"</span>);
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">or via an iterator</span>
map.erase(map.find(<span style="color: #98be65;">"bar"</span>));
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">can iterate the map via iterator or via for-each</span>
<span style="color: #51afef;">for</span> (<span style="color: #a9a1e1;">std</span>::<span style="color: #a9a1e1;">unordered_map</span><<span style="color: #a9a1e1;">std</span>::string, <span style="color: #ECBE7B;">int</span>>::<span style="color: #ECBE7B;">iterator</span> <span style="color: #dcaeea;">it</span> = map.begin();
it != map.end(); ++it) {
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"("</span> << it->first << <span style="color: #98be65;">", "</span> << it->second << <span style="color: #98be65;">"), "</span>;
}
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"\n"</span>;
}
}
</pre>
</div>
</div>
</div>
</div>
<div id="outline-container-org644b019" class="outline-2">
<h2 id="org644b019"><span class="section-number-2">5.</span> <code>auto</code></h2>
<div class="outline-text-2" id="text-5">
<ul class="org-ul">
<li><code>auto</code> keyword tells the compiler to infer the type via its initialization expression.</li>
</ul>
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><vector></span>
<span style="color: #51afef; font-weight: bold;">#include</span><span style="color: #98be65;"><unordered_map></span>
<span style="color: #51afef; font-weight: bold;">#include</span><span style="color: #98be65;"><string></span>
<span style="color: #51afef; font-weight: bold;">#include</span><span style="color: #98be65;"><iostream></span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">create very long class and function</span>
<span style="color: #51afef;">template</span> <<span style="color: #51afef;">typename</span> <span style="color: #ECBE7B;">T</span>, <span style="color: #51afef;">typename</span> <span style="color: #ECBE7B;">U</span>> <span style="color: #51afef;">class</span> <span style="color: #ECBE7B;">VeryLongTemplateClass</span> {
<span style="color: #51afef;">public</span>:
<span style="color: #c678dd;">VeryLongTemplateClass</span>(<span style="color: #ECBE7B;">T</span> <span style="color: #dcaeea;">instance1</span>, <span style="color: #ECBE7B;">U</span> <span style="color: #dcaeea;">instance2</span>)
: instance1_(instance1), instance2_(instance2) {}
<span style="color: #51afef;">private</span>:
<span style="color: #ECBE7B;">T</span> <span style="color: #dcaeea;">instance1_</span>;
<span style="color: #ECBE7B;">U</span> <span style="color: #dcaeea;">instance2_</span>;
};
<span style="color: #51afef;">template</span> <<span style="color: #51afef;">typename</span> <span style="color: #ECBE7B;">T</span>> <span style="color: #ECBE7B;">VeryLongTemplateClass</span><<span style="color: #ECBE7B;">T</span>, <span style="color: #ECBE7B;">T</span>> <span style="color: #c678dd;">construct_obj</span>(<span style="color: #ECBE7B;">T</span> <span style="color: #dcaeea;">instance</span>) {
<span style="color: #51afef;">return</span> VeryLongTemplateClass<<span style="color: #ECBE7B;">T</span>, <span style="color: #ECBE7B;">T</span>>(instance, instance);
}
<span style="color: #ECBE7B;">int</span> <span style="color: #c678dd;">main</span>() {
<span style="color: #51afef;">auto</span> <span style="color: #dcaeea;">a</span> = <span style="color: #da8548; font-weight: bold;">1</span>; <span style="color: #5B6268;">// </span><span style="color: #5B6268;">a is int</span>
<span style="color: #51afef;">auto</span> <span style="color: #dcaeea;">obj1</span> = construct_obj<<span style="color: #ECBE7B;">int</span>>(<span style="color: #da8548; font-weight: bold;">2</span>); <span style="color: #5B6268;">// </span><span style="color: #5B6268;">can infer</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">auto defaults to copy objects rather than taking the reference</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">vector</span><<span style="color: #ECBE7B;">int</span>> <span style="color: #dcaeea;">int_values</span> = {<span style="color: #da8548; font-weight: bold;">1</span>, <span style="color: #da8548; font-weight: bold;">2</span>, <span style="color: #da8548; font-weight: bold;">3</span>, <span style="color: #da8548; font-weight: bold;">4</span>};
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">a deep-copy happens</span>
<span style="color: #51afef;">auto</span> <span style="color: #dcaeea;">copy_int_values</span> = int_values;
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">this creates a reference</span>
<span style="color: #51afef;">auto</span> &<span style="color: #dcaeea;">ref_int_values</span> = int_values;
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">use auto in the for loop is very common</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">unordered_map</span><<span style="color: #a9a1e1;">std</span>::string, <span style="color: #ECBE7B;">int</span>> <span style="color: #dcaeea;">map</span>;
<span style="color: #51afef;">for</span> (<span style="color: #51afef;">auto</span> <span style="color: #dcaeea;">it</span> = map.begin(); it != map.end(); ++it) {
}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">another exmaple</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">vector</span><<span style="color: #ECBE7B;">int</span>> <span style="color: #dcaeea;">vec</span> = {<span style="color: #da8548; font-weight: bold;">1</span>, <span style="color: #da8548; font-weight: bold;">2</span>, <span style="color: #da8548; font-weight: bold;">3</span>, <span style="color: #da8548; font-weight: bold;">4</span>};
<span style="color: #51afef;">for</span> (<span style="color: #51afef;">const</span> <span style="color: #51afef;">auto</span> &<span style="color: #dcaeea;">elem</span> : vec) {
<span style="color: #a9a1e1;">std</span>::cout << elem << <span style="color: #98be65;">" "</span>;
}
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #a9a1e1;">std</span>::endl;
}
</pre>
</div>
</div>
</div>
<div id="outline-container-org6876e1c" class="outline-2">
<h2 id="org6876e1c"><span class="section-number-2">6.</span> Smart pointers</h2>
<div class="outline-text-2" id="text-6">
<ul class="org-ul">
<li>A smart pointer is a data structure used in languages that do not have built-in memory management (e.g., with garbage collection, e.g., Python, Java) to handle memory allocation and deallocation.</li>
<li><code>std::unique_ptr</code> and <code>std::shared_ptr</code> are two C++ standard library smart pointers, they are wrapper classes over raw pointers.</li>
<li><code>std::unique_ptr</code> retains sole ownership of an object, i.e., no two instances of <code>unique_ptr</code> can manage the same object, a <code>unique_ptr</code> cannot be copied.</li>
<li><code>std::shared_ptr</code> retains shared ownership of an object, i.e., multiple shared pointers can own the same object and can be copied.</li>
</ul>
</div>
<div id="outline-container-org03a407c" class="outline-3">
<h3 id="org03a407c"><span class="section-number-3">6.1.</span> <code>std::unique_ptr</code></h3>
<div class="outline-text-3" id="text-6-1">
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><iostream></span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><memory></span> <span style="color: #5B6268;">// </span><span style="color: #5B6268;">to use std::unique_ptr</span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><utility></span> <span style="color: #5B6268;">// </span><span style="color: #5B6268;">to use std::move</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">class Point is the same as before</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">takes in a unique point reference and changes its x value</span>
<span style="color: #ECBE7B;">void</span> <span style="color: #c678dd;">SetXTo10</span>(<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">unique_ptr</span><Point> &<span style="color: #dcaeea;">ptr</span>) { ptr->SetX(<span style="color: #da8548; font-weight: bold;">10</span>); }
<span style="color: #ECBE7B;">int</span> <span style="color: #c678dd;">main</span>() {
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">initialize an empty unique pointer</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">unique_ptr</span><Point> <span style="color: #dcaeea;">u1</span>;
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">initialize a unique pointer with constructors</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">unique_ptr</span><Point> <span style="color: #dcaeea;">u2</span> = <span style="color: #a9a1e1;">std</span>::make_unique<Point>();
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">unique_ptr</span><Point> <span style="color: #dcaeea;">u3</span> = <span style="color: #a9a1e1;">std</span>::make_unique<Point>(<span style="color: #da8548; font-weight: bold;">2</span>, <span style="color: #da8548; font-weight: bold;">3</span>);
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">can treat a unique pointer as a boolean to determine whether</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">the pointer contains data</span>
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"Pointer u1 is "</span> << (u1 ? <span style="color: #98be65;">"not empty"</span> : <span style="color: #98be65;">"empty"</span>) << <span style="color: #a9a1e1;">std</span>::endl;
<span style="color: #51afef;">if</span> (u2) {
<span style="color: #a9a1e1;">std</span>::cout << u2->GetX() << <span style="color: #a9a1e1;">std</span>::endl;
}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">unique_ptr has no copy constructor!</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">unique_ptr</span><Point> <span style="color: #dcaeea;">u4</span> = u3; <span style="color: #5B6268;">// </span><span style="color: #5B6268;">won't compile!</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">can transfer ownership with std::move</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">unique_ptr</span><Point> <span style="color: #dcaeea;">u5</span> = <span style="color: #a9a1e1;">std</span>::move(u3); <span style="color: #5B6268;">// </span><span style="color: #5B6268;">then u3 becomes empty!</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">pass the pointer as a reference so the ownership does not change</span>
SetXTo10(u5); <span style="color: #5B6268;">// </span><span style="color: #5B6268;">can still access u5 afterwards</span>
<span style="color: #51afef;">return</span> <span style="color: #da8548; font-weight: bold;">0</span>;
}
</pre>
</div>
<ul class="org-ul">
<li>Note that the compiler does not prevent 2 unique pointers from pointing to the same object.</li>
</ul>
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #5B6268;">// </span><span style="color: #5B6268;">the following code can compile</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">but it causes a double deletion!</span>
<span style="color: #ECBE7B;">MyClass</span> *<span style="color: #dcaeea;">obj</span> = <span style="color: #51afef;">new</span> <span style="color: #ECBE7B;">MyClass</span>();
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">unique_ptr</span><<span style="color: #ECBE7B;">MyClass</span>> <span style="color: #c678dd;">ptr1</span>(obj);
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">unique_ptr</span><<span style="color: #ECBE7B;">MyClass</span>> <span style="color: #c678dd;">ptr2</span>(obj);
</pre>
</div>
</div>
</div>
<div id="outline-container-orga17c160" class="outline-3">
<h3 id="orga17c160"><span class="section-number-3">6.2.</span> <code>std::shared_ptr</code></h3>
<div class="outline-text-3" id="text-6-2">
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><iostream></span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><memory></span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><utility></span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">class Point is the same as before</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">modify a Point inside a shared_ptr by passing the reference</span>
<span style="color: #ECBE7B;">void</span> <span style="color: #c678dd;">modify_ptr_via_ref</span>(<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">shared_ptr</span><Point> &<span style="color: #dcaeea;">point</span>) { point->SetX(<span style="color: #da8548; font-weight: bold;">10</span>); }
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">modify a Point inside a shared_ptr by passing the rvalue reference</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">If an object is passed by rvalue reference, one should assume the ownership</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">is moved after the function call, so the original object cannot be used</span>
<span style="color: #ECBE7B;">void</span> <span style="color: #c678dd;">modify_ptr_via_rvalue_ref</span>(<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">shared_ptr</span><Point> &&<span style="color: #dcaeea;">point</span>) {
point->SetY(<span style="color: #da8548; font-weight: bold;">11</span>);
}
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">copy a shared_pointer with the default constructor</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">so one should define own copy constructor and assignment when an object</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">contains pointers</span>
<span style="color: #ECBE7B;">void</span> <span style="color: #c678dd;">copy_shard_ptr_in_function</span>(<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">shared_ptr</span><Point> <span style="color: #dcaeea;">point</span>) {
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"Use count of the shared pointer: "</span> << point.use_count()
<< <span style="color: #a9a1e1;">std</span>::endl; <span style="color: #5B6268;">// </span><span style="color: #5B6268;">add by 1</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">the copy is destroyed at the end, so the count is decremented</span>
}
<span style="color: #ECBE7B;">int</span> <span style="color: #c678dd;">main</span>() {
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">the pointer constructors are the same as unique_ptr</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">shared_ptr</span><Point> <span style="color: #dcaeea;">s1</span>;
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">shared_ptr</span><Point> <span style="color: #dcaeea;">s2</span> = <span style="color: #a9a1e1;">std</span>::make_shared<Point>();
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">shared_ptr</span><Point> <span style="color: #dcaeea;">s3</span> = <span style="color: #a9a1e1;">std</span>::make_shared<Point>(<span style="color: #da8548; font-weight: bold;">2</span>, <span style="color: #da8548; font-weight: bold;">3</span>);
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">copy a shared pointer via copy assignment or copy constructor</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">increment the reference count, which can be tracked by .use_count</span>
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"Use count of s3"</span> << s3.use_count() << <span style="color: #a9a1e1;">std</span>::endl; <span style="color: #5B6268;">// </span><span style="color: #5B6268;">1</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">shared_ptr</span><Point> <span style="color: #dcaeea;">s4</span> = s3; <span style="color: #5B6268;">// </span><span style="color: #5B6268;">copy assignment</span>
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"Use count of s3"</span> << s3.use_count() << <span style="color: #a9a1e1;">std</span>::endl; <span style="color: #5B6268;">// </span><span style="color: #5B6268;">2</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">shared_ptr</span><Point> <span style="color: #dcaeea;">s5</span>(s4);
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"Use count of s3"</span> << s3.use_count() << <span style="color: #a9a1e1;">std</span>::endl; <span style="color: #5B6268;">// </span><span style="color: #5B6268;">3</span>
s3->SetX(<span style="color: #da8548; font-weight: bold;">100</span>); <span style="color: #5B6268;">// </span><span style="color: #5B6268;">also changes the data in s4 and s5</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">shared_ptr</span><Point> <span style="color: #dcaeea;">s6</span> = <span style="color: #a9a1e1;">std</span>::move(s5); <span style="color: #5B6268;">// </span><span style="color: #5B6268;">s5 transfer the ownership to s6</span>
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"Use count of s3"</span> << s3.use_count()
<< <span style="color: #a9a1e1;">std</span>::endl; <span style="color: #5B6268;">// </span><span style="color: #5B6268;">still 3: s3, s4, s6</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">as unique_ptr, shared_ptr can be passed by references and rvalue references</span>
modify_ptr_via_ref(s2); <span style="color: #5B6268;">// </span><span style="color: #5B6268;">setX(11)</span>
modify_ptr_via_rvalue_ref(<span style="color: #a9a1e1;">std</span>::move(s2)); <span style="color: #5B6268;">// </span><span style="color: #5B6268;">setY(12)</span>
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"s2.x = "</span> << s2->GetX()
<< <span style="color: #98be65;">" , s2.y = "</span> << s2->GetY(); <span style="color: #5B6268;">// </span><span style="color: #5B6268;">(11, 12)</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">shared_ptr can also be passed by value/copy</span>
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"Use count of s2"</span> << s2.use_count() << <span style="color: #a9a1e1;">std</span>::endl; <span style="color: #5B6268;">// </span><span style="color: #5B6268;">1</span>
copy_shared_ptr_in_function(s2); <span style="color: #5B6268;">// </span><span style="color: #5B6268;">inside the function, the use count is 2</span>
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"Use count of s2"</span> << s2.use_count()
<< <span style="color: #a9a1e1;">std</span>::endl; <span style="color: #5B6268;">// </span><span style="color: #5B6268;">1 again as the copy is detroyed</span>
<span style="color: #51afef;">return</span> <span style="color: #da8548; font-weight: bold;">0</span>;
}
</pre>
</div>
</div>
</div>
</div>
<div id="outline-container-orgff9d615" class="outline-2">
<h2 id="orgff9d615"><span class="section-number-2">7.</span> Synchronization</h2>
<div class="outline-text-2" id="text-7">
</div>
<div id="outline-container-org720a20f" class="outline-3">
<h3 id="org720a20f"><span class="section-number-3">7.1.</span> <code>std::mutex</code></h3>
<div class="outline-text-3" id="text-7-1">
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><iostream></span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><mutex></span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><thread></span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">define a global variable to be modified</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">by multiple threads</span>
<span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">count</span> = <span style="color: #da8548; font-weight: bold;">0</span>;
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">declare a mutex</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">mutex</span> <span style="color: #dcaeea;">m</span>;
<span style="color: #ECBE7B;">void</span> <span style="color: #c678dd;">add_count</span>() {
m.lock(); <span style="color: #5B6268;">// </span><span style="color: #5B6268;">acquire the lock</span>
count += <span style="color: #da8548; font-weight: bold;">1</span>;
m.unlock(); <span style="color: #5B6268;">// </span><span style="color: #5B6268;">release the lock</span>
}
<span style="color: #ECBE7B;">int</span> <span style="color: #c678dd;">main</span>() {
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">thread</span> <span style="color: #dcaeea;">t1</span>(add_count);
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">thread</span> <span style="color: #dcaeea;">t2</span>(add_count);
t1.join();
t2.join();
<span style="color: #a9a1e1;">std</span>::cout << count << <span style="color: #a9a1e1;">std</span>::endl; <span style="color: #5B6268;">// </span><span style="color: #5B6268;">always 2</span>
<span style="color: #51afef;">return</span> <span style="color: #da8548; font-weight: bold;">0</span>;
}
</pre>
</div>
</div>
</div>
<div id="outline-container-org972445b" class="outline-3">
<h3 id="org972445b"><span class="section-number-3">7.2.</span> <code>std::scoped_lock</code></h3>
<div class="outline-text-3" id="text-7-2">
<ul class="org-ul">
<li>A mutex wrapper that provides a RAII-style of obtaining and releasing the lock.</li>
<li>When the object is constructed, the locks are acquired; when the object is destructured, the locks are released.</li>
<li>Better than <code>std::mutex</code> since it provides exception safety.</li>
</ul>
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><iostream></span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><mutex></span>
<span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">count</span> = <span style="color: #da8548; font-weight: bold;">0</span>;
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">mutex</span> <span style="color: #dcaeea;">m</span>;
<span style="color: #ECBE7B;">void</span> <span style="color: #c678dd;">add_count</span>() {
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">the scoped_lock constructor allows for the thread</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">to acquire the mutex m</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">scoped_lock</span> <span style="color: #dcaeea;">slk</span>(m);
count += <span style="color: #da8548; font-weight: bold;">1</span>;
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">once the function finishes, slk is destructurd and</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">m is released</span>
}
</pre>
</div>
</div>
</div>
<div id="outline-container-org9630937" class="outline-3">
<h3 id="org9630937"><span class="section-number-3">7.3.</span> <code>std::condition_variable</code></h3>
<div class="outline-text-3" id="text-7-3">
<ul class="org-ul">
<li>Allow threads to wait until a particular condition before acquiring a mutex.</li>
<li>Allow other threads to signal waiting threads to alert them that the condition may be true.
<code>notify_one</code></li>
</ul>
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><condition_variable></span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><iostream></span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><mutex></span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><thread></span>
<span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">count</span> = <span style="color: #da8548; font-weight: bold;">0</span>;
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">mutex</span> <span style="color: #dcaeea;">m</span>;
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">declare a condition variable</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">condition_variable</span> <span style="color: #dcaeea;">cv</span>;
<span style="color: #ECBE7B;">void</span> <span style="color: #c678dd;">add_count_and_notify</span>() {
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">scoped_lock</span> <span style="color: #dcaeea;">slk</span>(m);
count += <span style="color: #da8548; font-weight: bold;">1</span>;
<span style="color: #51afef;">if</span> (count == <span style="color: #da8548; font-weight: bold;">2</span>) {
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">notidy one waiting thread</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">otherwise the waiter thread hangs forever</span>
cv.notify_one();
}
}
<span style="color: #ECBE7B;">void</span> <span style="color: #c678dd;">waiter_thread</span>() {
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">a unique_lock is movable but not copiable</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">more flexible than scoped_lock as it can unlock</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">and relock manually, while scoped_lock can only be</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">unlocked automatically.</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">scoped_lock cannot be used with condition variables</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">unique_lock</span> <span style="color: #dcaeea;">lk</span>(m);
cv.wait(lk, [] { <span style="color: #51afef;">return</span> count == <span style="color: #da8548; font-weight: bold;">2</span>; });
<span style="color: #a9a1e1;">std</span>::cout << count << <span style="color: #a9a1e1;">std</span>::endl;
}
<span style="color: #ECBE7B;">int</span> <span style="color: #c678dd;">main</span>() {
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">thread</span> <span style="color: #dcaeea;">t1</span>(waiter_thread);
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">make t1 really waits</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #a9a1e1;">this_thread</span>::sleep_for(<span style="color: #a9a1e1;">std</span>::<span style="color: #a9a1e1;">chrono</span>::milliseconds(<span style="color: #da8548; font-weight: bold;">100</span>));
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">thread</span> <span style="color: #dcaeea;">t2</span>(add_count_and_notify);
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">thread</span> <span style="color: #dcaeea;">t3</span>(add_count_and_notify);
t1.join();
t2.join();
t3.join();
<span style="color: #51afef;">return</span> <span style="color: #da8548; font-weight: bold;">0</span>;
}
</pre>
</div>
</div>
</div>
<div id="outline-container-org45ff32d" class="outline-3">
<h3 id="org45ff32d"><span class="section-number-3">7.4.</span> Reader-writer lock</h3>
<div class="outline-text-3" id="text-7-4">
<ul class="org-ul">
<li>A reader-writer lock allows multiple threads to have shared read access (no writers are allowed during read operations) and exclusive write access, i.e., no other readers or writers are allowed during the write.</li>
<li>C++ does not have a specific reader-writer’s lock library, but can be emulated with <code>std::shared_mutex</code>, <code>std::shared_lock</code> and <code>std::unique_lock</code>.</li>
<li><code>std::shared_mutex</code> is a mutex that allows for both shared read-only locking and exclusive write-only locking.</li>
<li><code>std::shared_lock</code> can be used as an RAII-style read lock.</li>
<li><p>
<code>std::unique_lock</code> can be used a RAII-style exclusive write lock.
</p>
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><iostream></span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><mutex></span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><shared_mutex></span>
<span style="color: #51afef; font-weight: bold;">#include</span> <span style="color: #98be65;"><thread></span>
<span style="color: #ECBE7B;">int</span> <span style="color: #dcaeea;">count</span> = <span style="color: #da8548; font-weight: bold;">0</span>; <span style="color: #5B6268;">// </span><span style="color: #5B6268;">resource</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">shared_mutex</span> <span style="color: #dcaeea;">m</span>;
<span style="color: #ECBE7B;">void</span> <span style="color: #c678dd;">read_value</span>() {
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">use shared_lock to gain read-only, shared access</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">shared_lock</span> <span style="color: #dcaeea;">lk</span>(m);
<span style="color: #a9a1e1;">std</span>::cout << <span style="color: #98be65;">"Reading "</span> + <span style="color: #a9a1e1;">std</span>::to_string(count) << <span style="color: #a9a1e1;">std</span>::endl;
}
<span style="color: #ECBE7B;">void</span> <span style="color: #c678dd;">write_value</span>() {
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">use unique_lock to gain exclusive access</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">unique_lock</span> <span style="color: #dcaeea;">lk</span>(m);
count += <span style="color: #da8548; font-weight: bold;">3</span>;
}
<span style="color: #ECBE7B;">int</span> <span style="color: #c678dd;">main</span>() {
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">since all 3 threads run in parallel,</span>
<span style="color: #5B6268;">// </span><span style="color: #5B6268;">the output is not deterministic</span>
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">thread</span> <span style="color: #dcaeea;">t1</span>(read_value);
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">thread</span> <span style="color: #dcaeea;">t2</span>(write_value);
<span style="color: #a9a1e1;">std</span>::<span style="color: #ECBE7B;">thread</span> <span style="color: #dcaeea;">t3</span>(read_value);
t1.join();
t2.join();
t3.join();
<span style="color: #51afef;">return</span> <span style="color: #da8548; font-weight: bold;">0</span>;
}
</pre>
</div></li>
</ul>
</div>
</div>
</div>
<div class="taglist"><a href="https://chenyo.me/tags.html">Tags</a>: <a href="https://chenyo.me/tag-c++.html">c++</a> <a href="https://chenyo.me/tag-study.html">study</a> <a href="https://chenyo.me/tag-cmu.html">cmu</a> </div>
<div class="post-date">05 Sep 2024</div><h1 class="post-title"><a href="https://chenyo.me/2024-09-05-db-notes:-hash-tables.html">CMU 15-445 notes: Hash Tables</a></h1>
<nav id="table-of-contents" role="doc-toc">
<h2>Table of Contents</h2>
<div id="text-table-of-contents" role="doc-toc">
<ul>
<li><a href="#orgb243d96">1. DBMS data structure application</a>
<ul>
<li><a href="#org3270460">1.1. Design decisions</a></li>
</ul>
</li>
<li><a href="#org8280e10">2. Hash tables</a>
<ul>
<li><a href="#org870ca3d">2.1. Where are hash tables used</a></li>
</ul>
</li>
<li><a href="#org323981e">3. Hash function</a></li>
<li><a href="#org9437813">4. Hashing scheme</a></li>
<li><a href="#org9be269e">5. Static hashing scheme</a>
<ul>
<li><a href="#org48b0827">5.1. Linear probe hashing</a>
<ul>
<li><a href="#org50cbcae">5.1.1. Non-unique keys</a></li>
<li><a href="#org5fedae3">5.1.2. Optimization</a></li>
</ul>
</li>
<li><a href="#orgfd5341b">5.2. Cuckoo hashing</a></li>
</ul>
</li>
<li><a href="#orgdb356c3">6. Dynamic hashing schemes</a>
<ul>
<li><a href="#orgcd53bbd">6.1. Chained Hashing</a></li>
<li><a href="#org3235a4c">6.2. Extendible hashing</a></li>
<li><a href="#org912057c">6.3. Linear hashing</a></li>
</ul>
</li>
</ul>
</div>
</nav>
<p>
This is a personal note for the <a href="https://15445.courses.cs.cmu.edu/fall2023/notes/07-hashtables.pdf">CMU 15-445 L7 notes</a> as well as some explanation from Claude.ai.
</p>
<div id="outline-container-orgb243d96" class="outline-2">
<h2 id="orgb243d96"><span class="section-number-2">1.</span> DBMS data structure application</h2>
<div class="outline-text-2" id="text-1">
<ul class="org-ul">
<li>Internal meta-data: <a href="https://chenyo.me/2024-08-13-db-notes:-memory-management.html#org7a44495">page tables</a>, <a href="https://chenyo.me/2024-07-31-db-notes:-database-storage.html#org66626ef">page directories</a>.</li>
<li>Tuple storage on disk.</li>
<li>Table indices: easy to find specific tuples.</li>
</ul>
</div>
<div id="outline-container-org3270460" class="outline-3">
<h3 id="org3270460"><span class="section-number-3">1.1.</span> Design decisions</h3>
<div class="outline-text-3" id="text-1-1">
<ul class="org-ul">
<li>Data layout for efficient access.</li>
<li>Concurrent access to data structures.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org8280e10" class="outline-2">
<h2 id="org8280e10"><span class="section-number-2">2.</span> Hash tables</h2>
<div class="outline-text-2" id="text-2">
<ul class="org-ul">
<li>Implements an associative array that maps keys to values.</li>
<li>On average \(O(1)\) operation complexity with the worst case \(O(n)\); \(O(n)\) storage complexity.
<ul class="org-ul">
<li>Optimization for constant complexity is important in real world.</li>
</ul></li>
</ul>
</div>
<div id="outline-container-org870ca3d" class="outline-3">
<h3 id="org870ca3d"><span class="section-number-3">2.1.</span> Where are hash tables used</h3>
<div class="outline-text-3" id="text-2-1">
<ul class="org-ul">
<li>For tuple indexing. While tuples are stored on pages with NSM or DSM, during the <b><b>query</b></b> the DBMS needs to quickly locate the page that stores specific tuples. It can achieve this with separately-stored hash tables, where each key can be a hash of a tuple id, and the value points the location.</li>
</ul>
</div>
</div>
</div>
<div id="outline-container-org323981e" class="outline-2">
<h2 id="org323981e"><span class="section-number-2">3.</span> Hash function</h2>
<div class="outline-text-2" id="text-3">
<ul class="org-ul">
<li>Maps a large key space into a smaller domain.</li>
<li>Takes in any key as input, and returns a deterministic integer representation.</li>
<li>Needs to consider the trade-off between fast execution and collision rate.
<ul class="org-ul">
<li>Does not need to be cryptographically.</li>
<li>The state-of-art (Fall 2023) hash function is XXHash3.</li>
</ul></li>
</ul>
</div>
</div>
<div id="outline-container-org9437813" class="outline-2">
<h2 id="org9437813"><span class="section-number-2">4.</span> Hashing scheme</h2>
<div class="outline-text-2" id="text-4">
<ul class="org-ul">
<li>Handles key collision after hashing.</li>
<li>Needs to consider the trade-off between large table allocation (to avoid collision) and additional instruction execution when a collision occurs.</li>
</ul>
</div>
</div>
<div id="outline-container-org9be269e" class="outline-2">
<h2 id="org9be269e"><span class="section-number-2">5.</span> Static hashing scheme</h2>
<div class="outline-text-2" id="text-5">
<ul class="org-ul">
<li>The hash table size is fixed; the DBMS has to rebuild a larger hash table (e.g., twice the size) from scratch when it runs out of space.</li>
</ul>
</div>
<div id="outline-container-org48b0827" class="outline-3">
<h3 id="org48b0827"><span class="section-number-3">5.1.</span> Linear probe hashing</h3>
<div class="outline-text-3" id="text-5-1">