item_086.htm

C++程序编写规范,适合C++中级读者

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><b style='mso-bidi-font-weight:normal'><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>摘要</span></b></p>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>排序“不多不少”：要理解每个排序算法做什么，并选用能够完成任务且开销最小的算法。</span></p>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><b style='mso-bidi-font-weight:normal'><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>讨论</span><a name=ch75index09></a><a name=ch75index08></a><a
name=ch75lev1sec2></a><span lang=EN-US><o:p></o:p></span></b></p>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>你并不总是需要完全排序；你通常需要对较少的元素进行排序，在极少数情况下你需要对更多的元素进行排序。如果大致根据开销最低到开销最高的顺序来选择标准排序算法，那么应该是：</span><span
lang=EN-US>partition</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，</span><span
class=SpellE><span lang=EN-US>stable_partition</span></span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>，</span><span class=SpellE><span lang=EN-US>nth_element</span></span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>，</span><span class=SpellE><span lang=EN-US>partial_sort</span></span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>（及它的变体</span><span class=SpellE><span lang=EN-US>partial_sort_copy</span></span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>），</span><span lang=EN-US>sort</span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，以及</span><span
class=SpellE><span lang=EN-US>stable_sort</span></span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>。应该使用既能满足实际需要，又开销最低的算法；使用功能更强的算法就显得浪费了。</span></p>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span lang=EN-US>partition</span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，</span><span
class=SpellE><span lang=EN-US>stable_partition</span></span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>，以及</span><span class=SpellE><span lang=EN-US>nth_element</span></span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>可以在线性时间内完成，这已经不错了。</span></p>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span class=SpellE><span lang=EN-US>nth_element</span></span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>，</span><span class=SpellE><span lang=EN-US>partial_sort</span></span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>，</span><span lang=EN-US>sort</span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，以及</span><span
class=SpellE><span lang=EN-US>stable_sort</span></span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>需要随机存取迭代器。如果只有双向迭代器（例如：</span><span
lang=EN-US>list&lt;T&gt;::<span class=SpellE>iterator</span></span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>），那么就无法使用它们。如果需要使用这些算法，但却没有随机存取迭代器，那么可以考虑采用索引容器惯用法：创建一个支持随机存取迭代器的容器（例如：</span><span
lang=EN-US>vector</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>），用它来存放指向原容器区间内元素的迭代器，然后使用功能更强的算法对新容器排序，在排序时要用一个解引版的</span><span
lang=EN-US>predicate</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>（即在进行常规比较之前对迭代器进行解引）。</span></p>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>只有在需要保持相同元素的相对位置关系时才使用</span><span
lang=EN-US>stable_...</span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>版本。要注意</span><span
class=SpellE><span lang=EN-US>partial_sort</span></span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>和</span><span
class=SpellE><span lang=EN-US>nth_element</span></span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>并不稳定（这意味着它们不会保持等价元素在排序之前的相对位置关系不变），也没有符合标准的稳定版本。如果仍想用这些算法但需要稳定性，那么你可能要用</span><span
class=SpellE><span lang=EN-US>stable_sort</span></span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>。</span></p>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>当然，如果没有必要，就不要用排序算法：如果使用的是一个标准的关联型容器（</span><span
lang=EN-US>set/<span class=SpellE>multiset</span></span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>或</span><span
lang=EN-US>map/<span class=SpellE>multimap</span></span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>）或者</span><span
class=SpellE><span lang=EN-US>priority_queue</span></span><span lang=EN-US> adapter</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>，而且只需要一种次序，那么这些容器中的元素始终是有序的。</span></p>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><b style='mso-bidi-font-weight:normal'><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>示例</span></b></p>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><i style='mso-bidi-font-style:normal'><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>示例</span><span lang=EN-US>1</span></i><i style='mso-bidi-font-style:
normal'><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>：</span><span lang=EN-US>partition</span></i><i
style='mso-bidi-font-style:normal'><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>。</span></i><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>用</span><span lang=EN-US>partition</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>即可把一个区间划分成两部分：满足</span><span lang=EN-US>predicate</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>的所有元素在前，其后是不满足条件的所有元素。用它来回答类似下面的这些问题已经足够了：</span></p>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<ul style='margin-top:0cm' type=disc>
 <li class=MsoNormal style='mso-list:l2 level1 lfo5;tab-stops:list 36.0pt'><span
     lang=EN-US><span style='mso-spacerun:yes'>&nbsp;</span></span><span
     style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
     "Times New Roman"'>“哪些学生的成绩为</span><span lang=EN-US>B+</span><span
     style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
     "Times New Roman"'>或更好？”例如，</span><span lang=EN-US>partition( <span
     class=SpellE>students.begin</span>(), <span class=SpellE>students.end</span>(),
     <span class=SpellE>GradeAtLeast</span>(&quot;B+&quot;) );</span><span
     style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
     "Times New Roman"'>可以回答这个问题，它返回一个迭代器，指向成绩未达到</span><span lang=EN-US>B+</span><span
     style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
     "Times New Roman"'>的第一个学生。</span></li>
</ul>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<ul style='margin-top:0cm' type=disc>
 <li class=MsoNormal style='mso-list:l2 level1 lfo5;tab-stops:list 36.0pt'><span
     lang=EN-US><span style='mso-spacerun:yes'>&nbsp;</span></span><span
     style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
     "Times New Roman"'>“哪些产品的重量小于</span><span lang=EN-US>10kg</span><span
     style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
     "Times New Roman"'>？”例如，</span><span lang=EN-US>partition( <span
     class=SpellE>products.begin</span>(), <span class=SpellE>products.end</span>(),
     <span class=SpellE>WeightUnder</span>(10) );</span><span style='font-family:
     宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>可以回答这个问题，它返回一个迭代器，指向重量大于等于</span><span
     lang=EN-US>10kg</span><span style='font-family:宋体;mso-ascii-font-family:
     "Times New Roman";mso-hansi-font-family:"Times New Roman"'>的第一个产品。</span></li>
</ul>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><i style='mso-bidi-font-style:normal'><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>示例</span><span lang=EN-US>2</span></i><i style='mso-bidi-font-style:
normal'><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>：</span><span class=SpellE><span
lang=EN-US>nth_element</span></span></i><i style='mso-bidi-font-style:normal'><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>。</span></i><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>用</span><span
class=SpellE><span lang=EN-US>nth_element</span></span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>来把一个元素放在正确的第</span><span
lang=EN-US>n</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>个位置，这个位置正是区间经过完全排序后该元素应该占有的，同时所有其它元素也会正确地位于该第</span><span
lang=EN-US>n</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>个元素之前或之后。用它来回答类似下面的这些问题已经足够了：</span></p>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<ul style='margin-top:0cm' type=disc>
 <li class=MsoNormal style='mso-list:l5 level1 lfo6;tab-stops:list 36.0pt'><span
     lang=EN-US><span style='mso-spacerun:yes'>&nbsp;</span></span><span
     style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
     "Times New Roman"'>“最好的</span><span lang=EN-US>20</span><span
     style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
     "Times New Roman"'>个销售员是哪些？”例如，</span><span class=SpellE><span lang=EN-US>nth_element</span></span><span
     lang=EN-US>( <span class=SpellE>s.begin</span>(), <span class=SpellE>s.begin</span>()+19,
     <span class=SpellE>s.end</span>(), <span class=SpellE>SalesRating</span>
     );</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
     mso-hansi-font-family:"Times New Roman"'>可以把最好的</span><span lang=EN-US>20</span><span
     style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
     "Times New Roman"'>个元素放在最前面。</span></li>
</ul>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<ul style='margin-top:0cm' type=disc>
 <li class=MsoNormal style='mso-list:l5 level1 lfo6;tab-stops:list 36.0pt'><span
     lang=EN-US><span style='mso-spacerun:yes'>&nbsp;</span></span><span
     style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
     "Times New Roman"'>“在本次产品周期（</span><span lang=EN-US>production run</span><span
     style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
     "Times New Roman"'>）中质量等级位于中间的是哪件物品？”</span> <span style='font-family:
     宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>在一个经过排序的区间内该元素应该位于中间的位置。可以用</span><span
     class=SpellE><span lang=EN-US>nth_element</span></span><span lang=EN-US>( <span
     class=SpellE>run.begin</span>(), <span class=SpellE>run.begin</span>()+<span
     class=SpellE>run.size</span>()/2, <span class=SpellE>run.end</span>(), <span
     class=SpellE>ItemQuality</span> );</span><span style='font-family:宋体;
     mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>来找到该元素。</span></li>
</ul>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<ul style='margin-top:0cm' type=disc>
 <li class=MsoNormal style='mso-list:l5 level1 lfo6;tab-stops:list 36.0pt'><span
     lang=EN-US><span style='mso-spacerun:yes'>&nbsp;</span></span><span
     style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
     "Times New Roman"'>“哪件物品的品质位于第</span><span lang=EN-US>75</span><span
     style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
     "Times New Roman"'>百分位（</span><span lang=EN-US>at the 75th percentile</span><span
     style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
     "Times New Roman"'>）？”</span> <span style='font-family:宋体;mso-ascii-font-family:
     "Times New Roman";mso-hansi-font-family:"Times New Roman"'>在一个经过排序的区间内，该物品所在位置的前方有</span><span
     lang=EN-US>25%</span><span style='font-family:宋体;mso-ascii-font-family:
     "Times New Roman";mso-hansi-font-family:"Times New Roman"'>的元素。可以用</span><span
     class=SpellE><span lang=EN-US>nth_element</span></span><span lang=EN-US>( <span
     class=SpellE>run.begin</span>(), <span class=SpellE>run.begin</span>()+<span
     class=SpellE>run.size</span>()*.25, <span class=SpellE>run.end</span>(), <span
     class=SpellE>ItemQuality</span> );</span><span style='font-family:宋体;
     mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>来找到该元素。</span></li>
</ul>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><i style='mso-bidi-font-style:normal'><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>示例</span><span lang=EN-US>3</span></i><i style='mso-bidi-font-style:
normal'><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>：</span><span class=SpellE><span
lang=EN-US>partial_sort</span></span></i><i style='mso-bidi-font-style:normal'><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>。</span></i><span class=SpellE><span lang=EN-US>partial_sort</span></span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>可以完成</span><span class=SpellE><span lang=EN-US>nth_element</span></span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>的工作，除此之外，第</span><span lang=EN-US>n</span><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>个元素之前的那些元素也都经过了排序，位于正确的位置上。可以用</span><span class=SpellE><span
lang=EN-US>partial_sort</span></span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>来回答那些与</span><span
class=SpellE><span lang=EN-US>nth_element</span></span><span style='font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>类似，但同时需要对匹配的元素进行排序（而且无需对那些不匹配的元素进行排序）的问题。用它来回答此类问题已经足够了，“谁是第一名，第二名，以及第三名？”例如，</span><span
class=SpellE><span lang=EN-US>partial_sort</span></span><span lang=EN-US>( <span
class=SpellE>contestants.begin</span>(), <span class=SpellE>contestants.begin</span>()+3,
<span class=SpellE>contestants.end</span>(), <span class=SpellE>ScoreCompare</span>
);</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>会把前三名参赛者按顺序放在容器的最前面——就这么多。</span></p>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><b style='mso-bidi-font-weight:normal'><span
style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>例外</span></b></p>

<p class=MsoNormal><span lang=EN-US><o:p>&nbsp;</o:p></span></p>

<p class=MsoNormal><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>虽然</span><span class=SpellE><span
lang=EN-US>partial_sort</span></span><span style='font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"'>通常比完全排序要快，因为做的事情较少，但是如果要对区间内的大多数（或全部）元素进行排序的话，它可能会比完全排序慢。</span></p>

</div>

</body>

</html>