-
Notifications
You must be signed in to change notification settings - Fork 0
/
2023-databases-project0.html
845 lines (533 loc) · 41.2 KB
/
2023-databases-project0.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
<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=auto>
<head>
<meta charset="UTF-8">
<link rel="apple-touch-icon" sizes="76x76" href="/img/new_avatar.jpg">
<link rel="icon" href="/img/new_avatar.jpg">
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=5.0, shrink-to-fit=no">
<meta http-equiv="x-ua-compatible" content="ie=edge">
<meta http-equiv="Content-Security-Policy" content="upgrade-insecure-requests">
<meta name="theme-color" content="#2f4154">
<meta name="author" content="Ming Xu">
<meta name="keywords" content="技术, 感悟, 生活">
<meta name="description" content="1 介绍 Project 0， 也就是C++ Primer， 是 CMU15-445 2022-Fall 课程的入门项目，重点考察 Cpp11 (及以上版本) 的基础语法， 包括与面向对象、泛型编程相关的基本特性。这门课程的所有项目需要在 Bustub （一个专门为课程教学设计的 DBMS，也可见课程之用心…）中使用 Cpp 进行编写。 该项目要求为 Bustub 实现一个支持键值对存储的字典树（">
<meta property="og:type" content="article">
<meta property="og:title" content="踩坑实录之Project 0：C++ 实现字典树">
<meta property="og:url" content="https://xuming234.work/2023-databases-project0.html">
<meta property="og:site_name" content="胥铭的博客 - 不积硅步，无以至千里">
<meta property="og:description" content="1 介绍 Project 0， 也就是C++ Primer， 是 CMU15-445 2022-Fall 课程的入门项目，重点考察 Cpp11 (及以上版本) 的基础语法， 包括与面向对象、泛型编程相关的基本特性。这门课程的所有项目需要在 Bustub （一个专门为课程教学设计的 DBMS，也可见课程之用心…）中使用 Cpp 进行编写。 该项目要求为 Bustub 实现一个支持键值对存储的字典树（">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://xuming234.work/img/post_img/CMU15_445/cover.jpg">
<meta property="article:published_time" content="2023-07-28T02:31:33.000Z">
<meta property="article:modified_time" content="2023-07-28T17:41:00.869Z">
<meta property="article:author" content="Ming Xu">
<meta property="article:tag" content="数据库系统">
<meta property="article:tag" content="C++">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="https://xuming234.work/img/post_img/CMU15_445/cover.jpg">
<meta name="referrer" content="no-referrer-when-downgrade">
<title>踩坑实录之Project 0：C++ 实现字典树 - 胥铭的博客 - 不积硅步，无以至千里</title>
<link rel="stylesheet" href="https://lib.baomitu.com/twitter-bootstrap/4.6.1/css/bootstrap.min.css" />
<link rel="stylesheet" href="https://lib.baomitu.com/github-markdown-css/4.0.0/github-markdown.min.css" />
<link rel="stylesheet" href="https://lib.baomitu.com/hint.css/2.7.0/hint.min.css" />
<link rel="stylesheet" href="https://lib.baomitu.com/fancybox/3.5.7/jquery.fancybox.min.css" />
<!-- 主题依赖的图标库，不要自行修改 -->
<!-- Do not modify the link that theme dependent icons -->
<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_hj8rtnfg7um.css">
<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_lbnruvf0jn.css">
<link rel="stylesheet" href="/css/main.css" />
<link id="highlight-css" rel="stylesheet" href="/css/highlight.css" />
<link id="highlight-css-dark" rel="stylesheet" href="/css/highlight-dark.css" />
<script id="fluid-configs">
var Fluid = window.Fluid || {};
Fluid.ctx = Object.assign({}, Fluid.ctx)
var CONFIG = {"hostname":"xuming234.work","root":"/","version":"1.9.4","typing":{"enable":true,"typeSpeed":70,"cursorChar":"_","loop":false,"scope":[]},"anchorjs":{"enable":true,"element":"h1,h2,h3,h4,h5,h6","placement":"left","visible":"hover","icon":""},"progressbar":{"enable":true,"height_px":3,"color":"#29d","options":{"showSpinner":false,"trickleSpeed":100}},"code_language":{"enable":true,"default":"TEXT"},"copy_btn":true,"image_caption":{"enable":true},"image_zoom":{"enable":true,"img_url_replace":["",""]},"toc":{"enable":true,"placement":"right","headingSelector":"h1,h2,h3,h4,h5,h6","collapseDepth":0},"lazyload":{"enable":true,"loading_img":"/img/loading.gif","onlypost":false,"offset_factor":2},"web_analytics":{"enable":false,"follow_dnt":true,"baidu":null,"google":null,"gtag":null,"tencent":{"sid":null,"cid":null},"woyaola":null,"cnzz":null,"leancloud":{"app_id":null,"app_key":null,"server_url":null,"path":"window.location.pathname","ignore_local":false}},"search_path":"/local-search.xml"};
if (CONFIG.web_analytics.follow_dnt) {
var dntVal = navigator.doNotTrack || window.doNotTrack || navigator.msDoNotTrack;
Fluid.ctx.dnt = dntVal && (dntVal.startsWith('1') || dntVal.startsWith('yes') || dntVal.startsWith('on'));
}
</script>
<script src="/js/utils.js" ></script>
<script src="/js/color-schema.js" ></script>
<meta name="generator" content="Hexo 6.3.0"></head>
<body>
<header>
<div class="header-inner" style="height: 70vh;">
<nav id="navbar" class="navbar fixed-top navbar-expand-lg navbar-dark scrolling-navbar">
<div class="container">
<a class="navbar-brand" href="/">
<strong>EXTREME</strong>
</a>
<button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
data-target="#navbarSupportedContent"
aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
<div class="animated-icon"><span></span><span></span><span></span></div>
</button>
<!-- Collapsible content -->
<div class="collapse navbar-collapse" id="navbarSupportedContent">
<ul class="navbar-nav ml-auto text-center">
<li class="nav-item">
<a class="nav-link" href="/">
<i class="iconfont icon-home-fill"></i>
<span>首页</span>
</a>
</li>
<li class="nav-item">
<a class="nav-link" href="/archives/">
<i class="iconfont icon-archive-fill"></i>
<span>归档</span>
</a>
</li>
<li class="nav-item">
<a class="nav-link" href="/categories/">
<i class="iconfont icon-category-fill"></i>
<span>分类</span>
</a>
</li>
<li class="nav-item">
<a class="nav-link" href="/tags/">
<i class="iconfont icon-tags-fill"></i>
<span>标签</span>
</a>
</li>
<li class="nav-item">
<a class="nav-link" href="/about/">
<i class="iconfont icon-user-fill"></i>
<span>关于</span>
</a>
</li>
<li class="nav-item">
<a class="nav-link" href="/links/">
<i class="iconfont icon-link-fill"></i>
<span>友链</span>
</a>
</li>
<li class="nav-item" id="search-btn">
<a class="nav-link" target="_self" href="javascript:;" data-toggle="modal" data-target="#modalSearch" aria-label="Search">
<i class="iconfont icon-search"></i>
</a>
</li>
<li class="nav-item" id="color-toggle-btn">
<a class="nav-link" target="_self" href="javascript:;" aria-label="Color Toggle">
<i class="iconfont icon-dark" id="color-toggle-icon"></i>
</a>
</li>
</ul>
</div>
</div>
</nav>
<div id="banner" class="banner" parallax=true
style="background: url('/img/bg/data_break.jpg') no-repeat center center; background-size: cover;">
<div class="full-bg-img">
<div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
<div class="banner-text text-center fade-in-up">
<div class="h2">
<span id="subtitle" data-typed-text="踩坑实录之Project 0：C++ 实现字典树"></span>
</div>
<div class="mt-3">
<span class="post-meta">
<i class="iconfont icon-date-fill" aria-hidden="true"></i>
<time datetime="2023-07-28 10:31" pubdate>
2023年7月28日 上午
</time>
</span>
</div>
<div class="mt-1">
<span class="post-meta mr-2">
<i class="iconfont icon-chart"></i>
7.4k 字
</span>
<span class="post-meta mr-2">
<i class="iconfont icon-clock-fill"></i>
62 分钟
</span>
<span id="busuanzi_container_page_pv" style="display: none">
<i class="iconfont icon-eye" aria-hidden="true"></i>
<span id="busuanzi_value_page_pv"></span> 次
</span>
</div>
</div>
</div>
</div>
</div>
</div>
</header>
<main>
<div class="container-fluid nopadding-x">
<div class="row nomargin-x">
<div class="side-col d-none d-lg-block col-lg-2">
</div>
<div class="col-lg-8 nopadding-x-md">
<div class="container nopadding-x-md" id="board-ctn">
<div id="board">
<article class="post-content mx-auto">
<!-- SEO header -->
<h1 style="display: none">踩坑实录之Project 0：C++ 实现字典树</h1>
<p class="note note-info">
本文最后更新于：2023年7月29日 凌晨
</p>
<div class="markdown-body">
<h2 id="1-介绍">1 介绍</h2>
<p>Project 0， 也就是C++ Primer， 是 CMU15-445 2022-Fall 课程的入门项目，重点考察 Cpp11 (及以上版本) 的基础语法， 包括与面向对象、泛型编程相关的基本特性。这门课程的所有项目需要在 Bustub （一个专门为课程教学设计的 DBMS，也可见课程之用心…）中使用 Cpp 进行编写。</p>
<p>该项目要求为 Bustub 实现一个支持键值对存储的字典树（Trie树，如下图所示）。这里博主回忆起了之前在《数据结构与算法分析：C++语言描述》(第四版) 中看到的关于后缀树和后缀数组 (Suffix Array) 的内容。这两种数据结构 (前缀树和后缀树) 感觉非常相似，都可以支持在字符串中快速查找给定的模式。那本书中给出了后缀数组和最长公共前缀数组 (<strong>L</strong>ongest <strong>C</strong>ommon <strong>P</strong>refix, 二者合并可以唯一确定后缀树) 的一种 O(<em>N</em>) 实现，非常烧脑。博主在做这个项目之前也重温了一下这部分的内容，以为会有共同之处。幸运的是，项目中 Trie 树的实现基于 STL 提供的 HashMap， 还是比较容易理解的。<br>
<img src="/img/post_img/CMU15_445/trie_example.png" srcset="/img/loading.gif" lazyload alt=""></p>
<p><strong>值得注意的是</strong>，目前该数据库已经更新到支持 2023-Spring 的教学要求， 与 2022-Fall 的课程要求并不完全相同。 庆幸的是，课程团队提供了一个 2022-Fall 的发布版。如果需要完成 2022-Fall 的项目，<code>git clone</code> 时必须指定 branch (博主之前对着 2023-Spring 的代码和 2022-Fall 的项目说明，懵逼了半天…):</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><code class="hljs bash">git <span class="hljs-built_in">clone</span> -b v20221128-2022Fall [email protected]:cmu-db/bustub.git<br></code></pre></td></tr></table></figure>
<h3 id="Git-常用指令">Git 常用指令</h3>
<p>博主在开始项目之前，对 git 的常用指令以及维护 github 仓库也完全不熟练，踩了不少坑。简单来说，git 的主要功能是实现软件版本控制，同时辅助协同开发。git 指令提供了非常多的选项，简单使用的话只需要知道其中几个即可：<br>
<img src="/img/post_img/CMU15_445/git.png" srcset="/img/loading.gif" lazyload alt=""></p>
<ul>
<li><code>git init [<repo-name>]</code><br>
初始化 git 仓库。该命令默认当前路径下创建 .git 文件，其中包含了版本控制所需的元数据；可以提供文件夹名称，在指定文件夹中建立 git 仓库; 同时，该指令默认创建 main 分支。</li>
<li><code>git add .</code><br>
将所有改动的文件添加到暂缓区域(staging)，并跟踪其变化；可以具体指定文件名。</li>
<li><code>git commit -m 'descreption'</code><br>
将暂缓区内容提交到本地仓库。</li>
<li><code>git push <remote-repo> <local-branch>：<remote-branch></code><br>
将本地分支推送到远程仓库并合并; 若本地分支与远程分支名相同，可以不写冒号后的内容。</li>
<li><code>git pull <remote-repo> <remote-branch>: <local-branch></code><br>
拉取远程主机的 remote-branch 分支，合并到本地的 local-branch 分支；若与当前分支合并，可以省略 local-branch。</li>
</ul>
<p>以上四条指令， 加上 <code>git clone</code> 可以满足基本的本地代码开发要求。涉及远程仓库的指令常常对网络环境有要求，使用 SSH 进行连接可以避免一些问题（添加 SSH 密钥参考之前的 <a href="https://xuming234.work/2023-hexo-framework-deployment.html">Blog</a>）。以下再补充一些其它常用的指令：</p>
<ul>
<li><code>git remote add <alias-name> <remote-repo></code><br>
为远程主机添加一个别名，可以方便推送和拉取； <code>git remote rm <alias-name></code> 用于删除别名， <code>git remote rename <old> <new></code> 用于重命名别名。</li>
<li><code>git status</code><br>
查看当前仓库状态，显示有变更的文件。</li>
<li><code>git branch [<new-branch-name>]</code><br>
列出当前仓库的所有分支；提供分支名时，将创建该名称的新分支。</li>
<li><code>git checkout <branch-name></code><br>
切换至给定名称的分支；该命令会将当前工作区恢复到创建该分支时候的模样。</li>
</ul>
<p>这些指令基本满足了博主当前开发的所有需求，让我也对 git 的工作方式有了初步的了解，更详细的说明可以参考<a target="_blank" rel="noopener" href="https://www.runoob.com/git/git-tutorial.html">这里</a>。</p>
<h2 id="2-环境搭建">2 环境搭建</h2>
<p>工欲善其事，必先利其器。毫无疑问，一个高效、优雅的编码环境，将带来事半功倍的效果。</p>
<h3 id="2-1-项目编译">2.1 项目编译</h3>
<p>作者推荐在 Ubuntu 20.04 以上的版本或者 macOS 中编译、开发、测试 Bustub， 而其它开发环境不能保证正常工作。博主本人的开发机是 Windows 10, 测试机是 Ubuntu 18.04。博主一开始试图直接在测试机中安装项目所需的开发工具，意识到确实很难完整安装所有工具的推荐版本，也无法生成完整的项目文件。主要原因是，项目要求用 clang-12 进行编译，而 Ubuntu 18.04 最高只支持到 clang-6。</p>
<p>为了减少踩坑，决定采用作者提供的 Docker 容器对文件进行编译。编译过程很顺利，所有的编译工具都能被顺利安装。值得注意的是，为了方便 Debug， 作者建议在容器中安装 GDB 调试工具，同时任何时候 <code>cmake</code> 都指定为 Debug 模式，即</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><code class="hljs bash">cmake -D CMKAE_BUILD_TYPE=Debug ..<br></code></pre></td></tr></table></figure>
<p>这里有一个<strong>小坑</strong>，指定 Debug 模式的时候，会报 warning，提示CMake 并没有使用推荐的编译器。 这里可以修改 CMakeLists.txt， 手动指明使用的编译器：</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><code class="hljs bash"><span class="hljs-built_in">set</span>(CMAKE_C_COMPILER /usr/bin/clang-12)<br><span class="hljs-built_in">set</span>(CMAKE_CXX_COMPILER /usr/bin/clang++-12)<br></code></pre></td></tr></table></figure>
<h3 id="2-2-VSCode-远程开发">2.2 VSCode 远程开发</h3>
<p>由于测试机并没有提供 GUI，直接将 Vim 配置成 C++ 的开发环境对博主来说难度颇大，使用也不顺手，于时考虑在本地开发机中利用 VSCode 进行远程开发。值得注意的是，这里的远程主机是运行中的 docker 容器。</p>
<p>为了在外部能访问容器, 首先在创建、运行容器时，需要指定端口映射：</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><code class="hljs bash">docker run -it -p 10008:10008 -v $(<span class="hljs-built_in">pwd</span>):/bustub [bustub-image] bash<br></code></pre></td></tr></table></figure>
<p>其中 <code>-t</code> 为容器分配伪终端；<code>-i</code>让容器的标准输入保持打开；<code>-p</code> 指定端口映射，这里将本地主机的 10008 端口映射到容器的 10008 端口; <code>-v</code> 将本地文件挂载到容器的指定文件目录下， 这里是在 bustub 根目录下运行的 <code>docker run</code> 指令； 后续再指定运行的 bustub 镜像 (通过 <code>docker build</code> 指令建立) 和需要运行的指令(<code>bash</code> 进入容器的 bash 命令行)。</p>
<p>然后，在Docker 容器中安装 SSH 所需的依赖:</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><code class="hljs bash">apt-get update<br>apt-get install openssh-server openssh-clients openssl<br></code></pre></td></tr></table></figure>
<p>配置容器中的 /etc/ssh/sshd_config 文件， 开放指定的 10008 端口 （如果没有该文件，则表明 SSH 服务所需的依赖没有被正确安装）:</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><code class="hljs bash">Port=10008<br>PermitRootLogin <span class="hljs-built_in">yes</span><br>PubkeyAuthentication <span class="hljs-built_in">yes</span><br></code></pre></td></tr></table></figure>
<p>重启 docker 的 SSH 服务:</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><code class="hljs bash">service ssh restart<br></code></pre></td></tr></table></figure>
<p>尝试在本地连接运行中的 docker 容器:</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><code class="hljs bash">ssh -p 10008 [email protected]<br></code></pre></td></tr></table></figure>
<p>如果能成功进入该容器，则表明配置正确。接下来需要在 VSCode 中安装远程开发套件 Remote Development。 安装完成后，即可连接远程主机中的容器。如果远程主机配置了免密登录，则需要将私钥保存到本地用户路径下的 .ssh 文件中。顺利连接的情况下，VSCode 会自动在容器中安装一部分依赖， 而我们也可以在本地对开发环境进行一些个性化设置。</p>
<p>这里推荐在 VSCode 中配置 clang-format 插件， 并在 setting.json 中开启 formatOnSave 功能， 以提高编码过程中的代码可读性。当然，项目作者本身提供了 formatting 和代码逻辑/风格的检查工具，在需要进行其它修改时， 也可以在 json 文件中很方便的关闭 formatOnSave 功能。</p>
<p>OK， 环境配置完毕，接下来，就可以开始快乐的 Coding 了~</p>
<h2 id="3-项目开发过程">3 项目开发过程</h2>
<p>课程团队提供了关于该项目的非常详细的说明。简单来说，我们只需要在在 /src/include/primer/p0_trie.h 中完成 TrieNode 类， TrieNodeWithValue 类和 Trie 类的接口实现。</p>
<h3 id="3-1-关于-unique-ptr-的使用">3.1 关于 unique_ptr 的使用</h3>
<p>TrieNode 类提供单一节点的操作接口。由于使用了 STL 的 unordered_map 来管理与子节点的连接，因此实现还是相对简单的。 其中最大的坑在于处理 unique_ptr 的使用问题。</p>
<p>unique_ptr 是一种智能指针类。C++ 中所有智能指针的设计目标都是通过类析构函数的自动调用机制，来帮助内存管理， 使用时都应该遵循 RAII（<strong>R</strong>esource <strong>A</strong>cquision <strong>I</strong>s <strong>I</strong>nitialization） 的原则，且一定要避免和普通指针混合使用。 其中 unique_ptr 是为了防止多个指针指向同一个对象时，对象删除后出现空悬指针的问题。除了一般化的使用原则外，该智能指针不允许拷贝 (一个例外是允许函数返回unique_ptr, 此时会执行特殊的复制) 和赋值 (对应的拷贝构造和拷贝赋值都被声明为 =delete)， 以保证任何时刻都只有一个 unique_ptr 指向给定对象。该智能指针仅支持所有权的转移，即利用 <code>std::move()</code> 将对象的所有权从一个 unique_ptr 转移到另一个 unique_ptr。 除了重载了 -> 和 * 运算符外，该智能指针还支持以下常用接口：</p>
<ul>
<li><code>get()</code>: 返回对象的普通指针， 主要用于匹配函数形参；</li>
<li><code>release()</code>: 放弃对象的所有权，将该智能指针置为空；</li>
<li><code>reset([ptr])</code>: 释放 unique_ptr 所管理的资源, 并置空；或将其指向 ptr；</li>
</ul>
<p>此外，在 C++14 及以后的版本中，还提供了 <code>make_unique</code> 用于构造unique_ptr。这也是后面利用 clang-tidy 进行检查时所建议的做法。</p>
<p><strong>TrieNode 类的移动构造函数</strong></p>
<p>由于 unique_ptr 的种种限制，资源转移时需要格外小心。博主踩的第一个<strong>坑</strong>是 TrieNode 类的移动构造函数。 在这里，需要将 TrieNode 类中的 children_ 私有成员移动到新对象中。</p>
<p>博主原本认为, 可以直接将 other_trie_node.children_ 传递给 <code>unordered_map<char, std::unique_ptr<TrieNode>></code> 的构造函数， 编译器能够通过模板产生正确的移动构造函数。 然而事与愿违, 此时调用的仍然是复制构造函数。由于 unique_ptr 不支持复制构造， <code>unordered_map<char, std::unique_ptr<TrieNode>></code> 的复制构造函数也被声明为 <code>=delete</code>，导致编译失败。</p>
<p>这里应该涉及到引用参数的模板匹配机制 (这部分个人感觉很复杂)。之所以调用复制构造函数，博主认为是直接使用参数名时，传递的依然是左值表达式 (参考《C++ Primer》(第5版) 613页)。这里需要传递右值表达式，最直接的解决办法是使用 <code>std::move()</code>；稍微复杂一点的是使用转发, 即:</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><code class="hljs cpp">std::forward<<span class="hljs-built_in">deceltype</span>(children_)>(other_trie_node.children_);<br></code></pre></td></tr></table></figure>
<p>值得注意的是， <code>deceltype()</code>用于右值时得到原本的类型。 另外，在移动构造函数体内进行 <code>swap</code> 也是一种可行的方法, 因为 children_ 应该默认是空的：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><code class="hljs cpp">children_.<span class="hljs-built_in">swap</span>(other_trie_node.children_);<br></code></pre></td></tr></table></figure>
<p>另一个涉及到相似问题的地方是 TrieNode 类中的插入操作。由于需要在 children_ 中建立新的不存在的 key， 推荐使用 unordered_map 的 insert 方法 (使用 [] 的方式，会增加一次对 unique_ptr 对象默认构造的调用，参考《Effective STL》条款24)。 如果使用 insert 则难以避免调用 make_pair 来构造 pair 对象，此时会再次面对 unique_ptr 对象的传递问题。</p>
<p>总之，任何时候都要避免对 unique_ptr 以及包含 unique_ptr 的类的复制和赋值操作。</p>
<p><strong>访问 unique_ptr 所管理的对象</strong><br>
Unique_ptr 对资源所有权的严格限制带来了一个很重要的问题——不能直接通过对象的指针去访问对象了。因为这种方式混用了普通指针和智能指针，破坏了智能指针的设计初衷； 而使用其它智能指针去引用 unique_ptr 所管理的资源也是不好的习惯(参考《C++ Primer》（第5版）417页)。</p>
<p>项目作者使用 unique_ptr<T>* 来访问 unqiue_ptr 所管理的对象，有效规避了上面提到的两个问题。这是一种值得借鉴的做法（暂时没有考证是不是标准做法）。</p>
<h3 id="3-2-Trie-中实现-Insert">3.2 Trie 中实现 Insert</h3>
<p>字典树的插入逻辑是比较清晰的，作者也给出了各种情况下插入操作的细节。其中有一点很值得注意。当遍历插入的字符串到尾字符时，当前节点并不是终止节点，此时需要进行将 TrieNode 类转化为 TrieNodeWithValue 类。</p>
<p>博主一开始使用 TrieNodeWithValue 类构造函数的 key-value 版本构造新的对象，然后替换原来的 TrieNode 类。 结果也能通过 starter_trie_test 的测试。 后来自己再补充了一些随机字符串的插入和删除，却总是出现神秘 Fail。通过打印日志，博主发现插入都是成功的，但有的查询和删除会出现失败。这意味着插入操作虽然返回了 true, 但实际上改变了插入的内容。</p>
<p>经过一番检查后，发现原因就在于 TrieNodeWithValue 类的构造方式。 如果构造新的对象去替换原来的 TrieNode 节点，会丢失该节点所有子节点的连接。因此，必须从原来的 TrieNode 对象构造 TrieNodeWithValue 对象。</p>
<h3 id="3-3-基类指针访问派生类对象的成员">3.3 基类指针访问派生类对象的成员</h3>
<p>Trie 类的 GetValue 接口需要访问 TrieNodeWithValue 类的 Value_ 成员。 这里涉及到需要用基类指针访问派生类对象成员的问题。博主其实首先想到的是考虑将 GetValue 声明为 virtual 函数(在基类中添加一个空函数版本)，但是作者显然没有这样考虑。有点意外，作者要求使用 dynamic_cast。</p>
<p>运行期类型识别 （<strong>R</strong>un<strong>t</strong>ime <strong>T</strong>ype <strong>I</strong>dentification, RTTI）在 <a target="_blank" rel="noopener" href="https://zh-google-styleguide.readthedocs.io/en/latest/google-cpp-styleguide/others/#section-7">Google 开源项目风格指南</a> 中是不推荐的做法，意味着存在设计问题 (建议是使用虚函数或者访问者模式来替换 RTTI)。博主本人在这方面有些过于教条了，后来发现 dynamic_cast 仍然是一个相当有用的工具。 尤其是在基类指针无法被转换时，会返回 nullptr，提供了安全保证 (但是一定要避免滥用)。这里也算是弥补了知识盲区。</p>
<h3 id="3-4-并发控制">3.4 并发控制</h3>
<p>并发控制对博主来讲是完全陌生的领域。只是在学习过程中，了解过大概的思路。不过完成 Project 0 也确实不需要其它更复杂的手段，只需要简单地在进入读/写函数时上锁，离开前解锁就可以了。</p>
<p>有些意外的是，博主以为项目设计的 ReaderWriterLatch 也应该支持 RAII， 结果并非如此。总的来说，对于并发控制这一部分，还需要更深入的学习。</p>
<h3 id="3-5-Debug-过程">3.5 Debug 过程</h3>
<p>项目开发过程中主要使用 GDB 进行调试， 基本能解决大部分代码逻辑的问题，包括无意识的混淆了父节点和子节点，忘记 while-loop 中的变量更新等各种迷之错误。更隐晦的逻辑错误是通过编写测试案例和打日志来解决的。不得不承认，测试和日志记录也是技术活。</p>
<p>项目所使用的 GTest 框架再次触及博主只是的盲区…</p>
<p>值得注意的是，由于整个项目大量使用智能指针，博主在整个调试过程中都没有发现有内存管理方面的问题。很意外也很庆幸，可以说以鲜活生动的实例，向博主本人充分证实了使用智能指针进行资源管理的有效性和安全性。</p>
<h3 id="3-6-格式修改">3.6 格式修改</h3>
<p>课程团队对项目的代码规范有相当严格的要求，并提供了静态代码分析工具。基本的排版规范是参考 Google 的风格指南，通过 clang-format 进行自动排版。 这也是博主开发环境的默认选项。</p>
<p>同时，还提供了 clang-tidy 进行其它检查。给出了几条很有意思的建议：</p>
<ul>
<li>if-else 逻辑冗余： 避免在 return 后接 else<br>
博主一开始在很多需要控制流中止的地方，选择立刻 return。经验上讲，博主认为这样可以避免一些不必要的问题，比如流程没有完全退出。因此，导致很多 else 出现在了 return 之后。不过确实，这个问题基本可以通过删除不必要的 else 语句进行调整，极大减少了不必要的逻辑分支。</li>
<li>另一种 if-else 逻辑冗余的形式： 在 if 语句块中只返回 bool 值确实。这完全可以去掉 if， 让代码更精简。</li>
<li>要求所有的 if-else 语句中都加大括号<br>
也无可厚非吧，比较看个人喜好。</li>
<li>未使用 make_unique<br>
这是 C++14 的新特性，之前确实忽略了。推荐使用 make_unique 应该有深层次的原因。</li>
</ul>
<h2 id="4-总结">4 总结</h2>
<p>第一个项目从开始编码到最后提交通过大概花了 1.5 天，加上环境配置的话应该有 2 天了。 总的来说，虽然是该课程最简单的项目，但也令我收获满满。首先，项目本身的代码质量很高，完成项目本身也是在吸收优秀的设计经验。其次，完成项目需要利用各种工具，除了必要的编译工具，还需要掌握测试工具，尤其是使用 GDB 进行调试和利用 GTest 进行单元测试（不过博主本身并没有在命令行中进行 GDB 调试，而是配置到了 VSCode 中）。最值得称道的是，项目的反馈感相当的足。虽然 Project 0，只要求实现很小的部分，但依然能让整个项目成功编译且产生输出；而且也向非 CMU 的学生开放了 Gradescope 评分，能进一步帮助检查代码 bug。再次为课程团队点赞！！！</p>
<p>另外，博主本人其实对这种大中型 (maybe？) 项目的编译过程也很感兴趣，尤其是如何组织源码文件和编写对应的 CMakeList， 毕竟为一个很小的项目编写 CMakeList 对博主来讲都有不小的挑战。 总的来说，还有很多地方需要学习。希望自己能坚持下去。</p>
</div>
<hr/>
<div>
<div class="post-metas my-3">
<div class="post-meta mr-3 d-flex align-items-center">
<i class="iconfont icon-category"></i>
<span class="category-chains">
<span class="category-chain">
<a href="/categories/%E9%A1%B9%E7%9B%AE%E5%AE%9E%E8%B7%B5/" class="category-chain-item">项目实践</a>
</span>
</span>
</div>
<div class="post-meta">
<i class="iconfont icon-tags"></i>
<a href="/tags/%E6%95%B0%E6%8D%AE%E5%BA%93%E7%B3%BB%E7%BB%9F/">#数据库系统</a>
<a href="/tags/C/">#C++</a>
</div>
</div>
<div class="license-box my-3">
<div class="license-title">
<div>踩坑实录之Project 0：C++ 实现字典树</div>
<div>https://xuming234.work/2023-databases-project0.html</div>
</div>
<div class="license-meta">
<div class="license-meta-item">
<div>作者</div>
<div>Ming Xu</div>
</div>
<div class="license-meta-item license-meta-date">
<div>发布于</div>
<div>2023年7月28日</div>
</div>
<div class="license-meta-item">
<div>许可协议</div>
<div>
<a target="_blank" href="https://creativecommons.org/licenses/by/4.0/">
<span class="hint--top hint--rounded" aria-label="BY - 署名">
<i class="iconfont icon-by"></i>
</span>
</a>
</div>
</div>
</div>
<div class="license-icon iconfont"></div>
</div>
<div class="post-prevnext my-3">
<article class="post-prev col-6">
</article>
<article class="post-next col-6">
<a href="/2023-databases-start.html" title="CMU15-445 学习笔记 (一)">
<span class="hidden-mobile">CMU15-445 学习笔记 (一)</span>
<span class="visible-mobile">下一篇</span>
<i class="iconfont icon-arrowright"></i>
</a>
</article>
</div>
</div>
<article id="comments" lazyload>
<script type="text/javascript">
Fluid.utils.loadComments('#comments', function() {
var light = 'github-light';
var dark = 'github-dark';
var schema = document.documentElement.getAttribute('data-user-color-scheme');
if (schema === 'dark') {
schema = dark;
} else {
schema = light;
}
window.UtterancesThemeLight = light;
window.UtterancesThemeDark = dark;
var s = document.createElement('script');
s.setAttribute('src', 'https://utteranc.es/client.js');
s.setAttribute('repo', 'michael-mxu/blog-comments');
s.setAttribute('issue-term', 'pathname');
s.setAttribute('theme', schema);
s.setAttribute('crossorigin', 'anonymous');
document.getElementById('comments').appendChild(s);
})
</script>
<noscript>Please enable JavaScript to view the comments</noscript>
</article>
</article>
</div>
</div>
</div>
<div class="side-col d-none d-lg-block col-lg-2">
<aside class="sidebar" style="margin-left: -1rem">
<div id="toc">
<p class="toc-header">
<i class="iconfont icon-list"></i>
<span>目录</span>
</p>
<div class="toc-body" id="toc-body"></div>
</div>
</aside>
</div>
</div>
</div>
<a id="scroll-top-button" aria-label="TOP" href="#" role="button">
<i class="iconfont icon-arrowup" aria-hidden="true"></i>
</a>
<div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
aria-hidden="true">
<div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
<div class="modal-content">
<div class="modal-header text-center">
<h4 class="modal-title w-100 font-weight-bold">搜索</h4>
<button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
<span aria-hidden="true">×</span>
</button>
</div>
<div class="modal-body mx-3">
<div class="md-form mb-5">
<input type="text" id="local-search-input" class="form-control validate">
<label data-error="x" data-success="v" for="local-search-input">关键词</label>
</div>
<div class="list-group" id="local-search-result"></div>
</div>
</div>
</div>
</div>
</main>
<footer>
<div class="footer-inner">
<div class="footer-content">
<a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a> <i class="iconfont icon-love"></i> <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener"><span>Fluid</span></a>
</div>
<div class="statistics">
<span id="busuanzi_container_site_pv" style="display: none">
总访问量
<span id="busuanzi_value_site_pv"></span>
次
</span>
<span id="busuanzi_container_site_uv" style="display: none">
总访客数
<span id="busuanzi_value_site_uv"></span>
人
</span>
</div>
</div>
</footer>
<!-- Scripts -->
<script src="https://lib.baomitu.com/nprogress/0.2.0/nprogress.min.js" ></script>
<link rel="stylesheet" href="https://lib.baomitu.com/nprogress/0.2.0/nprogress.min.css" />
<script>
NProgress.configure({"showSpinner":false,"trickleSpeed":100})
NProgress.start()
window.addEventListener('load', function() {
NProgress.done();
})
</script>
<script src="https://lib.baomitu.com/jquery/3.6.0/jquery.min.js" ></script>
<script src="https://lib.baomitu.com/twitter-bootstrap/4.6.1/js/bootstrap.min.js" ></script>
<script src="/js/events.js" ></script>
<script src="/js/plugins.js" ></script>
<script src="https://lib.baomitu.com/typed.js/2.0.12/typed.min.js" ></script>
<script>
(function (window, document) {
var typing = Fluid.plugins.typing;
var subtitle = document.getElementById('subtitle');
if (!subtitle || !typing) {
return;
}
var text = subtitle.getAttribute('data-typed-text');
typing(text);
})(window, document);
</script>
<script src="/js/img-lazyload.js" ></script>
<script>
Fluid.utils.createScript('https://lib.baomitu.com/tocbot/4.18.2/tocbot.min.js', function() {
var toc = jQuery('#toc');
if (toc.length === 0 || !window.tocbot) { return; }
var boardCtn = jQuery('#board-ctn');
var boardTop = boardCtn.offset().top;
window.tocbot.init(Object.assign({
tocSelector : '#toc-body',
contentSelector : '.markdown-body',
linkClass : 'tocbot-link',
activeLinkClass : 'tocbot-active-link',
listClass : 'tocbot-list',
isCollapsedClass: 'tocbot-is-collapsed',
collapsibleClass: 'tocbot-is-collapsible',
scrollSmooth : true,
includeTitleTags: true,
headingsOffset : -boardTop,
}, CONFIG.toc));
if (toc.find('.toc-list-item').length > 0) {
toc.css('visibility', 'visible');
}
Fluid.events.registerRefreshCallback(function() {
if ('tocbot' in window) {
tocbot.refresh();
var toc = jQuery('#toc');
if (toc.length === 0 || !tocbot) {
return;
}
if (toc.find('.toc-list-item').length > 0) {
toc.css('visibility', 'visible');
}
}
});
});
</script>
<script src=https://lib.baomitu.com/clipboard.js/2.0.11/clipboard.min.js></script>
<script>Fluid.plugins.codeWidget();</script>
<script>
Fluid.utils.createScript('https://lib.baomitu.com/anchor-js/4.3.1/anchor.min.js', function() {
window.anchors.options = {
placement: CONFIG.anchorjs.placement,
visible : CONFIG.anchorjs.visible
};
if (CONFIG.anchorjs.icon) {
window.anchors.options.icon = CONFIG.anchorjs.icon;
}
var el = (CONFIG.anchorjs.element || 'h1,h2,h3,h4,h5,h6').split(',');
var res = [];
for (var item of el) {
res.push('.markdown-body > ' + item.trim());
}
if (CONFIG.anchorjs.placement === 'left') {
window.anchors.options.class = 'anchorjs-link-left';
}
window.anchors.add(res.join(', '));
Fluid.events.registerRefreshCallback(function() {
if ('anchors' in window) {
anchors.removeAll();
var el = (CONFIG.anchorjs.element || 'h1,h2,h3,h4,h5,h6').split(',');
var res = [];
for (var item of el) {
res.push('.markdown-body > ' + item.trim());
}
if (CONFIG.anchorjs.placement === 'left') {
anchors.options.class = 'anchorjs-link-left';
}
anchors.add(res.join(', '));
}
});
});
</script>
<script>
Fluid.utils.createScript('https://lib.baomitu.com/fancybox/3.5.7/jquery.fancybox.min.js', function() {
Fluid.plugins.fancyBox();
});
</script>
<script>Fluid.plugins.imageCaption();</script>
<script src="/js/local-search.js" ></script>
<script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>
<!-- 主题的启动项，将它保持在最底部 -->
<!-- the boot of the theme, keep it at the bottom -->
<script src="/js/boot.js" ></script>
<noscript>
<div class="noscript-warning">博客在允许 JavaScript 运行的环境下浏览效果更佳</div>
</noscript>
</body>
</html>