-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathpriority_queue20220504.html
388 lines (280 loc) · 39.4 KB
/
priority_queue20220504.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
<!DOCTYPE html>
<html lang=en>
<head>
<!-- so meta -->
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="HandheldFriendly" content="True">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=5" />
<meta name="description" content="在 Leetcode 的 373.查找和最小的 K 对数字 题目中为了保证每次的迭代我们都能得到和最小的元素,我们需要借助 STL 中的优先队列按照比较标准(Compare)将优先级最高的元素总是放在队列首部的特点来取得和最小的 K 个元素.在 STL 中 priority_queue 并不是一种容器,其是一种 container adapter.其通过将其他容器提供的接口和堆(heap)算法结合">
<meta property="og:type" content="article">
<meta property="og:title" content="priority_queue 乱象">
<meta property="og:url" content="https://tblgsn.github.io/priority_queue20220504.html">
<meta property="og:site_name" content="tblgsn的个人博客">
<meta property="og:description" content="在 Leetcode 的 373.查找和最小的 K 对数字 题目中为了保证每次的迭代我们都能得到和最小的元素,我们需要借助 STL 中的优先队列按照比较标准(Compare)将优先级最高的元素总是放在队列首部的特点来取得和最小的 K 个元素.在 STL 中 priority_queue 并不是一种容器,其是一种 container adapter.其通过将其他容器提供的接口和堆(heap)算法结合">
<meta property="og:locale" content="en_US">
<meta property="article:published_time" content="2022-05-04T00:00:00.000Z">
<meta property="article:modified_time" content="2025-01-22T09:14:47.022Z">
<meta property="article:author" content="tblgsn">
<meta property="article:tag" content="C++">
<meta property="article:tag" content="priority_queue">
<meta name="twitter:card" content="summary">
<link rel="shortcut icon" href="/images/favicon.ico">
<link rel="icon" type="image/png" href="/images/favicon-192x192.png" sizes="192x192">
<link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon.png">
<!-- title -->
<title>priority_queue 乱象</title>
<!-- async scripts -->
<!-- Google Analytics -->
<!-- Umami Analytics -->
<!-- styles -->
<link rel="stylesheet" href="/css/style.css">
<!-- persian styles -->
<!-- rss -->
<link rel="alternate" href="/true" title="tblgsn的个人博客" type="application/atom+xml" />
<!-- mathjax -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {
skipTags: ['script', 'noscript', 'style', 'textarea', 'pre'],
inlineMath: [['$','$']]
}
});
</script>
<script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/latest.js?config=TeX-MML-AM_CHTML' async></script>
<meta name="generator" content="Hexo 7.0.0"></head>
<body class="max-width mx-auto px3 ltr">
<div id="header-post">
<a id="menu-icon" href="#" aria-label="Menu"><i class="fa-solid fa-bars fa-lg"></i></a>
<a id="menu-icon-tablet" href="#" aria-label="Menu"><i class="fa-solid fa-bars fa-lg"></i></a>
<a id="top-icon-tablet" href="#" aria-label="Top" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');" style="display:none;"><i class="fa-solid fa-chevron-up fa-lg"></i></a>
<span id="menu">
<span id="nav">
<ul>
<!--
--><li><a href="/">Home</a></li><!--
--><!--
--><li><a href="/archives/">Writing</a></li><!--
--><!--
--><li><a target="_blank" rel="noopener" href="http://github.com/tblgsn">Projects</a></li><!--
--><!--
--><li><a href="/about/">About</a></li><!--
-->
</ul>
</span>
<br/>
<span id="actions">
<ul>
<li><a class="icon" aria-label="Previous post" href="/history20231201.html"><i class="fa-solid fa-chevron-left" aria-hidden="true" onmouseover="$('#i-prev').toggle();" onmouseout="$('#i-prev').toggle();"></i></a></li>
<li><a class="icon" aria-label="Next post" href="/linuxbgtask20220403.html"><i class="fa-solid fa-chevron-right" aria-hidden="true" onmouseover="$('#i-next').toggle();" onmouseout="$('#i-next').toggle();"></i></a></li>
<li><a class="icon" aria-label="Back to top" href="#" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');"><i class="fa-solid fa-chevron-up" aria-hidden="true" onmouseover="$('#i-top').toggle();" onmouseout="$('#i-top').toggle();"></i></a></li>
<li><a class="icon" aria-label="Share post" href="#"><i class="fa-solid fa-share-alt" aria-hidden="true" onmouseover="$('#i-share').toggle();" onmouseout="$('#i-share').toggle();" onclick="$('#share').toggle();return false;"></i></a></li>
</ul>
<span id="i-prev" class="info" style="display:none;">Previous post</span>
<span id="i-next" class="info" style="display:none;">Next post</span>
<span id="i-top" class="info" style="display:none;">Back to top</span>
<span id="i-share" class="info" style="display:none;">Share post</span>
</span>
<br/>
<div id="share" style="display: none">
<ul>
<li><a class="icon" target="_blank" rel="noopener" href="http://www.facebook.com/sharer.php?u=https://tblgsn.github.io/priority_queue20220504.html"><i class="fab fa-facebook " aria-hidden="true"></i></a></li>
<li><a class="icon" target="_blank" rel="noopener" href="https://twitter.com/share?url=https://tblgsn.github.io/priority_queue20220504.html&text=priority_queue 乱象"><i class="fab fa-twitter " aria-hidden="true"></i></a></li>
<li><a class="icon" target="_blank" rel="noopener" href="http://www.linkedin.com/shareArticle?url=https://tblgsn.github.io/priority_queue20220504.html&title=priority_queue 乱象"><i class="fab fa-linkedin " aria-hidden="true"></i></a></li>
<li><a class="icon" target="_blank" rel="noopener" href="https://pinterest.com/pin/create/bookmarklet/?url=https://tblgsn.github.io/priority_queue20220504.html&is_video=false&description=priority_queue 乱象"><i class="fab fa-pinterest " aria-hidden="true"></i></a></li>
<li><a class="icon" href="mailto:?subject=priority_queue 乱象&body=Check out this article: https://tblgsn.github.io/priority_queue20220504.html"><i class="fa-solid fa-envelope " aria-hidden="true"></i></a></li>
<li><a class="icon" target="_blank" rel="noopener" href="https://getpocket.com/save?url=https://tblgsn.github.io/priority_queue20220504.html&title=priority_queue 乱象"><i class="fab fa-get-pocket " aria-hidden="true"></i></a></li>
<li><a class="icon" target="_blank" rel="noopener" href="http://reddit.com/submit?url=https://tblgsn.github.io/priority_queue20220504.html&title=priority_queue 乱象"><i class="fab fa-reddit " aria-hidden="true"></i></a></li>
<li><a class="icon" target="_blank" rel="noopener" href="http://www.stumbleupon.com/submit?url=https://tblgsn.github.io/priority_queue20220504.html&title=priority_queue 乱象"><i class="fab fa-stumbleupon " aria-hidden="true"></i></a></li>
<li><a class="icon" target="_blank" rel="noopener" href="http://digg.com/submit?url=https://tblgsn.github.io/priority_queue20220504.html&title=priority_queue 乱象"><i class="fab fa-digg " aria-hidden="true"></i></a></li>
<li><a class="icon" target="_blank" rel="noopener" href="http://www.tumblr.com/share/link?url=https://tblgsn.github.io/priority_queue20220504.html&name=priority_queue 乱象&description="><i class="fab fa-tumblr " aria-hidden="true"></i></a></li>
<li><a class="icon" target="_blank" rel="noopener" href="https://news.ycombinator.com/submitlink?u=https://tblgsn.github.io/priority_queue20220504.html&t=priority_queue 乱象"><i class="fab fa-hacker-news " aria-hidden="true"></i></a></li>
</ul>
</div>
<div id="toc">
<ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%81%87%E8%A7%81%E7%9A%84%E2%80%9C%E4%B9%B1%E8%B1%A1%E2%80%9D"><span class="toc-number">1.</span> <span class="toc-text">遇见的“乱象”</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#priority-queue-%E8%A7%A3%E6%9E%90"><span class="toc-number">2.</span> <span class="toc-text">priority_queue 解析</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B9%B1%E8%B1%A1%E7%9A%84%E6%A0%B9%E6%BA%90"><span class="toc-number">3.</span> <span class="toc-text">乱象的根源</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%BB%93%E5%B0%BE"><span class="toc-number">4.</span> <span class="toc-text">结尾</span></a></li></ol>
</div>
</span>
</div>
<div class="content index py4 ">
<article class="post h-entry" itemscope itemtype="http://schema.org/BlogPosting">
<header>
<h1 class="posttitle p-name" itemprop="name headline">
priority_queue 乱象
</h1>
<div class="meta">
<span class="author p-author h-card" itemprop="author" itemscope itemtype="http://schema.org/Person">
<span class="p-name" itemprop="name">@TBLGSn</span>
</span>
<div class="postdate">
<time datetime="2022-05-04T00:00:00.000Z" class="dt-published" itemprop="datePublished">2022-05-04</time>
</div>
<div class="article-tag">
<i class="fa-solid fa-tag"></i>
<a class="p-category" href="/tags/C/" rel="tag">C++</a>, <a class="p-category" href="/tags/priority-queue/" rel="tag">priority_queue</a>
</div>
</div>
</header>
<div class="content e-content" itemprop="articleBody">
<p>在 Leetcode 的 <a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/">373.查找和最小的 K 对数字</a> 题目中为了保证每次的迭代我们都能得到和最小的元素,我们需要借助 STL 中的优先队列按照比较标准(Compare)将优先级最高的元素总是放在队列首部的特点来取得和最小的 K 个元素.<br>在 STL 中 priority_queue 并不是一种容器,其是一种 container adapter.其通过将其他容器提供的接口和堆(heap)算法结合,将原有的接口改变为优先队列特有的接口.</p>
<p>在默认的实现中,通常优先队列的默认底层容器都是 vector,这一点可以通过 priority_queue 类的模板定义就能确定.<br>同时模板定义还指定了作为元素比较的方式 Compare.默认情况下,C++ 通过作用域运算符访问的名字看作是变量而不是一个类型,我们需要使用 typename 关键字显式的告诉编译器这是一个类型. 然后通过底层容器 Sequence 中定义的 value_type 得到容器中的元素类型</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">template</span> <<span class="keyword">class</span> <span class="title class_">T</span>, <span class="keyword">class</span> <span class="title class_">Sequence</span> = vector<T>, <span class="keyword">class</span> Compare = less<<span class="keyword">typename</span> Sequence::value_type> ></span><br></pre></td></tr></table></figure>
<blockquote>
<p>更多关于优先队列的源码可以在<a target="_blank" rel="noopener" href="https://github.com/TBLGSn/SGI-STL/blob/master/Annotation/container/other_container/queue%2Bpriority_queue/stl_queue.h">这里</a>查看.</p>
</blockquote>
<h2 id="遇见的“乱象”"><a href="#遇见的“乱象”" class="headerlink" title="遇见的“乱象”"></a>遇见的“乱象”</h2><p>由于我们在优先队列中需要储存 nums1 和 nums2 的下标,所以我们需要将 模板参数 T 指定为 pair<int, int>.底层的数据结构依旧是vector,不过 vector 中存储的元素类型是pair<int, int>.对于比较函数 Compare,由于我们需要构建的是“最小堆”,所以我们需要指定更改 less 为 自定义的比较函数 cmp.我们选择使用 lambda 函数来完成任务,同时使用隐式引用捕获来让编译器根据函数体中的代码来推断需要捕获哪些变量.</p>
<figure class="highlight plaintext"><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><span class="line">auto cmp = [&](value_type &a, value_type &b){</span><br><span class="line"> return nums1[a.first] + nums2[b.second] > nums1[a.second] + nums2[a.first];</span><br><span class="line"> };</span><br></pre></td></tr></table></figure>
<p>这些并没有什么难以理解的,但是难以理解的是对优先队列的实例化方式.</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">priority_queue<pair<<span class="type">int</span>, <span class="type">int</span>>, vector<pair<<span class="type">int</span>, <span class="type">int</span>>>, <span class="keyword">decltype</span>(cmp)> <span class="built_in">pq</span>(cmp);</span><br></pre></td></tr></table></figure>
<blockquote>
<p>decltype,在C++中,作为操作符,用于查询表达式的数据类型</p>
</blockquote>
<p>这样的代码相当的“啰嗦”,但是如果你尝试删掉“多余的无效声明”时,你会发现这实际上十分的困难.每一个部分都是必可不少的,你甚至不能删除对于 cmp 的两次“重复”的使用(一处是 decltype(cmp), 一处是作为构造函数参数传入的 cmp).</p>
<h2 id="priority-queue-解析"><a href="#priority-queue-解析" class="headerlink" title="priority_queue 解析"></a>priority_queue 解析</h2><p>priority_queue 采用模板的方式进行定义,因此我们很容易使用内置的数据类型作为优先队列的元素类型.</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">priority_queue<<span class="type">int</span>> pq1;</span><br><span class="line">priority_queue<<span class="type">double</span>> pq2;</span><br><span class="line">priority_queue<string> pq3;</span><br><span class="line">......</span><br><span class="line">> 在声明优先队列时如果仅仅指定元素的类型,那么我们得到的默认底层实现为 vector 的“元素优先最小队列”</span><br></pre></td></tr></table></figure>
<p>对于任何重写了’<’运算符的内置数据类型,我们可以以很简单的形式定义优先队列.对于用户自定义的数据类型,我们也仅仅需要给出元素之间的比较规则即可.例如你可以定义一个结构体然后重写运算符’<’来指出对于结构体元素的比较方法.</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">struct</span> <span class="title class_">mytype</span></span><br><span class="line">{</span><br><span class="line"> <span class="type">int</span> x, y;</span><br><span class="line"> <span class="built_in">mytype</span>(<span class="type">int</span> x_, <span class="type">int</span> y_):<span class="built_in">x</span>(x_),<span class="built_in">y</span>(y_) {}</span><br><span class="line"> <span class="comment">// 尾部的 const 是必须的</span></span><br><span class="line"> <span class="type">bool</span> <span class="keyword">operator</span><(<span class="type">const</span> mytype &a) <span class="type">const</span>{</span><br><span class="line"> <span class="keyword">return</span> a.x + a.y < x + y;</span><br><span class="line"> }</span><br><span class="line">};</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> priority_queue<mytype> pq;</span><br><span class="line"> pq.<span class="built_in">push</span>(<span class="built_in">mytype</span>(<span class="number">-1</span>,<span class="number">0</span>));</span><br><span class="line"> pq.<span class="built_in">push</span>(<span class="built_in">mytype</span>(<span class="number">1</span>,<span class="number">0</span>));</span><br><span class="line"> std::cout <<pq.<span class="built_in">top</span>().x;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>一切似乎都很完美,直到我们使用系统内置的数据类型但是需要单独指定的 Compare 函数时,一切就不是这么美好了.文章开头的例子就是这样,使用 pair<int, int> 作为优先队列中元素,我们需要的不是“最小堆”而是“最大堆”,我们需要按照下面的格式声明优先队列.</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// STL 提供了如下的优先队列构造函数</span></span><br><span class="line"><span class="function"><span class="keyword">explicit</span> <span class="title">priority_queue</span><span class="params">(<span class="type">const</span> Compare& x)</span> : c(), comp(x) {</span>}</span><br><span class="line"><span class="comment">//我们指明优先队列元素类型,同时使用上面的构造函数形式来实例化优先队列</span></span><br><span class="line"><span class="function">priority_queue<<span class="type">int</span>> <span class="title">pq1</span><span class="params">(cmp)</span></span>;</span><br><span class="line">priority_queue<<span class="type">int</span>, vector<<span class="type">int</span>>> <span class="built_in">pq2</span>(cmp);</span><br><span class="line">priority_queue<<span class="type">int</span>, cmp> pq3;</span><br><span class="line">priority_queue<<span class="type">int</span>, vector<<span class="type">int</span>>,<span class="keyword">decltype</span>(cmp)> pq4;</span><br></pre></td></tr></table></figure>
<p>让人吃惊的是,上面的几种实例化方式连编译环节也通不过.<br>让我们回忆一下 priority_queue 的声明:</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">template</span> <<span class="keyword">class</span> <span class="title class_">T</span>, <span class="keyword">class</span> <span class="title class_">Sequence</span> = vector<T>, <span class="keyword">class</span> Compare = less<<span class="keyword">typename</span> Sequence::value_type> ></span><br><span class="line">priority_queue {</span><br><span class="line"> <span class="comment">//...</span></span><br><span class="line"><span class="keyword">protected</span>:</span><br><span class="line"> Sequence c; <span class="comment">// 底层容器</span></span><br><span class="line"> Compare comp;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line"> <span class="built_in">priority_queue</span>() : <span class="built_in">c</span>() {}</span><br><span class="line"> <span class="function"><span class="keyword">explicit</span> <span class="title">priority_queue</span><span class="params">(<span class="type">const</span> Compare& x)</span> : c(), comp(x) {</span>}</span><br><span class="line"> <span class="comment">//...</span></span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>对于第一种实例化形式,我们通过传递自定义的lambda cmp 给 priority_queue 的构造函数,通过初始化列表的方式进行初始化(其中底层容器 c 使用默认构造函数,而 comp 调用复制构造函数进行构造.这一切似乎都合情合理,但是这里有一个麻烦的地方 —— comp 的类型是什么?<br>第二种实例化形式指明模板参数 T 为 int、 Sequence 为 vector<int>,但是并没有明确的指出 Compare 的类型. 我们试图通过调用构造函数来改变 模板参数中对于Compare 的默认实现,并“猜测”编译器会根据构造函数自行推导出模板声明中 Compare 的数据类型.遗憾的是这样想法只能是幻想.<br>priority_queue 的构造函数中行参 x 的类型是 Compare, 然而 Compare 的数据类型是由模板参数指定的,然而我们在实例化优先队列 pq2 时没有指明 Compare 的类型,编译器并不会根据复制构造函数的类型推导出 Compare 的类型. </p>
<p>如果你不想使用模板参数中默认的数据类型,唯一的做法是在实例化时明确的指出每一个模板参数的数据类型.因此更改 Compare 类型的唯一做法是在实例化变量时指明 Compare 的类型.</p>
<p>pq3 的实例化方式也是错误的, C++ 也并未为我们提供单独指定模板参数列表中某一个参数的方式,因此我们如果要指定 Compare,就一定要指出 Sequence 的数据类型.</p>
<p>总结了上面三种实例化参数“失败”的原因,在 pq4 的实例化中我们使用了 decltype 说明符检查 cmp 的声明类型.终于直接或间接的指明了优先队列所有模板参数,但这行代码依旧不能通过顺利的运行.</p>
<h2 id="乱象的根源"><a href="#乱象的根源" class="headerlink" title="乱象的根源"></a>乱象的根源</h2><p><strong>上面第四个实例化示例失败的缘由是: 缺少对应的默认构造函数.</strong><br>此时 pq 的类别是 std::priority_queue<int, std::vector<int, std::allocator<int>>, lambda []bool (const int &a, const int &b)->bool>,<br>因此某一个构造函数才能正确的完成实例化.</p>
<p>如果我们不使用 lambda 表达式,而是将 cmp 定义为 struct ,那么代码就能顺利的运行,而此时调用的是 priority_queue 的默认构造函数.</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">template</span> <<span class="keyword">typename</span> T></span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">cmp</span> {</span><br><span class="line"> <span class="function"><span class="type">bool</span> <span class="title">operator</span><span class="params">()</span><span class="params">(<span class="type">const</span> T &a, <span class="type">const</span> T &b)</span> </span>{</span><br><span class="line"> <span class="keyword">return</span> a < b;</span><br><span class="line"> }</span><br><span class="line">};</span><br><span class="line">priority_queue<<span class="type">int</span>, vector<<span class="type">int</span>>, cmp<<span class="type">int</span>> > pq; <span class="comment">//调用默认构造函数完成实例化</span></span><br></pre></td></tr></table></figure>
<p>使用 decltype 说明符指定 Compare 与使用模板 struct 指定 Compare 是有区别的. 使用 decltype 时, Compare 的类型是: lambda []bool (const int &a, const int &b,而使用模板结构体时 Compare 的类型是: cmp<int> (构体名称<T>)<br>最重要的是, <strong>lambda没有默认构造函数和析构函数</strong>. 但是结构体有默认的构造函数和析构函数. 因此使用 delctype得到 lambda 类型来定义 Compare 类型的优先队列不能调用默认的构造函数完成实例化.而使用结构体模板方式实例化优先队列可以调用默认的构造函数.</p>
<blockquote>
<p>在 《Effective C++》一书中指出: 如果你没有声明，C++ 会为你声明(编译器版本)一个cop构造函数、copy assignment 操作符、和一个析构函数.如果你没有声明任何的构造函数，编译器也会为你声明一个 default 构造函数。</p>
</blockquote>
<p>对于 lambda 而言,虽然没有默认的构造函数,但是却规定了 operator= 运算符.因此我们借助 delctype 说明符直接或者间接的指明模板参数类型之后,调用另一个 copy 构造函数完成对象的构造.</p>
<blockquote>
<p>更多关于 lambda 的信息可以在<a target="_blank" rel="noopener" href="https://en.cppreference.com/w/cpp/language/lambda">这里</a>查看.</p>
</blockquote>
<p>C++ 确实提供了类模板参数推导的机制,但是假定类模板参数的推导是“万能的”是不现实的,很显然参数的推导需要遵守一定的规则 —— <a target="_blank" rel="noopener" href="https://en.cppreference.com/w/cpp/language/class_template_argument_deduction">1.类模板参数推导</a>,<a target="_blank" rel="noopener" href="https://en.cppreference.com/w/cpp/language/template_parameters">2.模板形参与模板实参</a></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">template</span> <<span class="keyword">class</span> <span class="title class_">T1</span>, <span class="keyword">class</span> <span class="title class_">T2</span>></span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">pair</span> {</span><br><span class="line"> <span class="keyword">typedef</span> T1 first_type;</span><br><span class="line"> <span class="keyword">typedef</span> T2 second_type;</span><br><span class="line"> T1 first;</span><br><span class="line"> T2 second;</span><br><span class="line"> <span class="built_in">pair</span>() : <span class="built_in">first</span>(<span class="built_in">T1</span>()), <span class="built_in">second</span>(<span class="built_in">T2</span>()) {}</span><br><span class="line"> <span class="built_in">pair</span>(<span class="type">const</span> T1& a, <span class="type">const</span> T2& b) : <span class="built_in">first</span>(a), <span class="built_in">second</span>(b) {}</span><br><span class="line"> <span class="comment">//...</span></span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>对于 pair 我们并不陌生, pair 同样被实现为模板,下面的代码能够顺利的运行.</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">std::pair <span class="title">p</span><span class="params">(<span class="number">2</span>, <span class="number">4.5</span>)</span></span>;</span><br></pre></td></tr></table></figure>
<p>然而下面的代码不能通过编译,因为 k 和 nums.size() 的类型并不相同.</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">vector<<span class="type">int</span>> nums {<span class="number">0</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>};</span><br><span class="line"><span class="type">int</span> k = <span class="number">10</span>;</span><br><span class="line"><span class="comment">// min 的 模板声明为 template<typename T> ,因此 min 的两个实参的类型要相同.</span></span><br><span class="line"><span class="type">int</span> res = <span class="built_in">min</span>(k, nums.<span class="built_in">size</span>());</span><br></pre></td></tr></table></figure>
<p>有趣的是,对于指定模板参数默认值的情况,如果我们不指出模板参数类型模板推导更倾向于默认的实现(double类型 2.1 可以转型为 int 类型)</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">template</span> <<span class="keyword">typename</span> T1, <span class="keyword">typename</span> T2 = <span class="type">int</span>></span><br><span class="line"><span class="keyword">class</span> Mytype</span><br><span class="line">{</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line"> T1 x;</span><br><span class="line"> T2 y;</span><br><span class="line"> <span class="built_in">Mytype</span>(T1 x_, T2 y_):<span class="built_in">x</span>(x_),<span class="built_in">y</span>(y_) {}</span><br><span class="line">};</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="function">Mytype<<span class="type">int</span>> <span class="title">m</span><span class="params">(<span class="number">1</span>, <span class="number">2.1</span>)</span></span>;</span><br><span class="line"> <span class="comment">// 结果是 2 和 int,而 m.x 编译器推导出类型为 int</span></span><br><span class="line"> std::cout << m.y << std::endl; </span><br><span class="line"> std::cout << <span class="built_in">typeid</span>(m.y).<span class="built_in">name</span>() << std::endl;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h2 id="结尾"><a href="#结尾" class="headerlink" title="结尾"></a>结尾</h2><p>对于 priority_queue ,如果我们想避免出现文章开头“冗余”的实例化代码,最好的办法是使用 struct. 但这样我们就放弃了 lambda 的便利性。为了使用 lambda ,我们又必须指出要使用 copy 构造函数。 lambda 和 模板结构体有着完全不一样的特点.使用 lambda 和 decltype 说明符的组合与使用 struct 是有区别的. 同时,在实例化模板类时,指出所有的模板参数类型是至关重要的.指明类模板参数在一定情况下是必须的,比如上面的 min 函数,编译器可以推导出两个参数的类型,却可能在两个类型的犹豫不决. 最后,我要指出的是类模板参数推导并不是万能的,只有特定情况才能完成类的参数类型推导.事实上,只有在 C++17 起编译器才会从初始化器的类型推导缺失的模板实参. 除此之外,编译器更倾向于指定的默认的参数声明,并不能通过构造函数的方式促使它重新推导模板参数.</p>
</div>
</article>
<div class="blog-post-comments">
<div id="utterances_thread">
<noscript>Please enable JavaScript to view the comments.</noscript>
</div>
</div>
<div id="footer-post-container">
<div id="footer-post">
<div id="nav-footer" style="display: none">
<ul>
<li><a href="/">Home</a></li>
<li><a href="/archives/">Writing</a></li>
<li><a target="_blank" rel="noopener" href="http://github.com/tblgsn">Projects</a></li>
<li><a href="/about/">About</a></li>
</ul>
</div>
<div id="toc-footer" style="display: none">
<ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%81%87%E8%A7%81%E7%9A%84%E2%80%9C%E4%B9%B1%E8%B1%A1%E2%80%9D"><span class="toc-number">1.</span> <span class="toc-text">遇见的“乱象”</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#priority-queue-%E8%A7%A3%E6%9E%90"><span class="toc-number">2.</span> <span class="toc-text">priority_queue 解析</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B9%B1%E8%B1%A1%E7%9A%84%E6%A0%B9%E6%BA%90"><span class="toc-number">3.</span> <span class="toc-text">乱象的根源</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%BB%93%E5%B0%BE"><span class="toc-number">4.</span> <span class="toc-text">结尾</span></a></li></ol>
</div>
<div id="share-footer" style="display: none">
<ul>
<li><a class="icon" target="_blank" rel="noopener" href="http://www.facebook.com/sharer.php?u=https://tblgsn.github.io/priority_queue20220504.html"><i class="fab fa-facebook fa-lg" aria-hidden="true"></i></a></li>
<li><a class="icon" target="_blank" rel="noopener" href="https://twitter.com/share?url=https://tblgsn.github.io/priority_queue20220504.html&text=priority_queue 乱象"><i class="fab fa-twitter fa-lg" aria-hidden="true"></i></a></li>
<li><a class="icon" target="_blank" rel="noopener" href="http://www.linkedin.com/shareArticle?url=https://tblgsn.github.io/priority_queue20220504.html&title=priority_queue 乱象"><i class="fab fa-linkedin fa-lg" aria-hidden="true"></i></a></li>
<li><a class="icon" target="_blank" rel="noopener" href="https://pinterest.com/pin/create/bookmarklet/?url=https://tblgsn.github.io/priority_queue20220504.html&is_video=false&description=priority_queue 乱象"><i class="fab fa-pinterest fa-lg" aria-hidden="true"></i></a></li>
<li><a class="icon" href="mailto:?subject=priority_queue 乱象&body=Check out this article: https://tblgsn.github.io/priority_queue20220504.html"><i class="fa-solid fa-envelope fa-lg" aria-hidden="true"></i></a></li>
<li><a class="icon" target="_blank" rel="noopener" href="https://getpocket.com/save?url=https://tblgsn.github.io/priority_queue20220504.html&title=priority_queue 乱象"><i class="fab fa-get-pocket fa-lg" aria-hidden="true"></i></a></li>
<li><a class="icon" target="_blank" rel="noopener" href="http://reddit.com/submit?url=https://tblgsn.github.io/priority_queue20220504.html&title=priority_queue 乱象"><i class="fab fa-reddit fa-lg" aria-hidden="true"></i></a></li>
<li><a class="icon" target="_blank" rel="noopener" href="http://www.stumbleupon.com/submit?url=https://tblgsn.github.io/priority_queue20220504.html&title=priority_queue 乱象"><i class="fab fa-stumbleupon fa-lg" aria-hidden="true"></i></a></li>
<li><a class="icon" target="_blank" rel="noopener" href="http://digg.com/submit?url=https://tblgsn.github.io/priority_queue20220504.html&title=priority_queue 乱象"><i class="fab fa-digg fa-lg" aria-hidden="true"></i></a></li>
<li><a class="icon" target="_blank" rel="noopener" href="http://www.tumblr.com/share/link?url=https://tblgsn.github.io/priority_queue20220504.html&name=priority_queue 乱象&description="><i class="fab fa-tumblr fa-lg" aria-hidden="true"></i></a></li>
<li><a class="icon" target="_blank" rel="noopener" href="https://news.ycombinator.com/submitlink?u=https://tblgsn.github.io/priority_queue20220504.html&t=priority_queue 乱象"><i class="fab fa-hacker-news fa-lg" aria-hidden="true"></i></a></li>
</ul>
</div>
<div id="actions-footer">
<a id="menu" class="icon" href="#" onclick="$('#nav-footer').toggle();return false;"><i class="fa-solid fa-bars fa-lg" aria-hidden="true"></i> Menu</a>
<a id="toc" class="icon" href="#" onclick="$('#toc-footer').toggle();return false;"><i class="fa-solid fa-list fa-lg" aria-hidden="true"></i> TOC</a>
<a id="share" class="icon" href="#" onclick="$('#share-footer').toggle();return false;"><i class="fa-solid fa-share-alt fa-lg" aria-hidden="true"></i> Share</a>
<a id="top" style="display:none" class="icon" href="#" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');"><i class="fa-solid fa-chevron-up fa-lg" aria-hidden="true"></i> Top</a>
</div>
</div>
</div>
<footer id="footer">
<div class="footer-left">
Copyright ©
2019-2025
tblgsn
</div>
<div class="footer-right">
<nav>
<ul>
<!--
--><li><a href="/">Home</a></li><!--
--><!--
--><li><a href="/archives/">Writing</a></li><!--
--><!--
--><li><a target="_blank" rel="noopener" href="http://github.com/tblgsn">Projects</a></li><!--
--><!--
--><li><a href="/about/">About</a></li><!--
-->
</ul>
</nav>
</div>
</footer>
</div>
<!-- styles -->
<link rel="preload" as="style" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.4.0/css/all.min.css" crossorigin="anonymous" onload="this.onload=null;this.rel='stylesheet'"/>
<!-- jquery -->
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.6.0/jquery.min.js" crossorigin="anonymous"></script>
<!-- clipboard -->
<script src="https://cdnjs.cloudflare.com/ajax/libs/clipboard.js/2.0.7/clipboard.min.js" crossorigin="anonymous"></script>
<script type="text/javascript">
$(function() {
// copy-btn HTML
var btn = "<span class=\"btn-copy tooltipped tooltipped-sw\" aria-label=\"Copy to clipboard!\">";
btn += '<i class="fa-regular fa-clone"></i>';
btn += '</span>';
// mount it!
$(".highlight table").before(btn);
var clip = new ClipboardJS('.btn-copy', {
text: function(trigger) {
return Array.from(trigger.nextElementSibling.querySelectorAll('.code')).reduce((str,it)=>str+it.innerText+'\n','')
}
});
clip.on('success', function(e) {
e.trigger.setAttribute('aria-label', "Copied!");
e.clearSelection();
})
})
</script>
<script src="/js/main.js"></script>
<!-- search -->
<!-- Baidu Analytics -->
<!-- Cloudflare Analytics -->
<!-- Disqus Comments -->
<!-- utterances Comments -->
<script type="text/javascript">
var utterances_repo = 'TBLGSn/tblgsn.github.io';
var utterances_issue_term = 'url';
var utterances_label = 'Comment';
var utterances_theme = 'github-dark';
(function(){
var script = document.createElement('script');
script.src = 'https://utteranc.es/client.js';
script.setAttribute('repo', utterances_repo);
script.setAttribute('issue-term', 'pathname');
script.setAttribute('label', utterances_label);
script.setAttribute('theme', utterances_theme);
script.setAttribute('crossorigin', 'anonymous');
script.async = true;
(document.getElementById('utterances_thread')).appendChild(script);
}());
</script>
</body>
</html>