]> git.proxmox.com Git - ceph.git/blame - ceph/src/boost/libs/sort/doc/doxygen/html/namespaceboost_1_1sort.html
projects / ceph.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
bump version to 12.2.2-pve1
[ceph.git] / ceph / src / boost / libs / sort / doc / doxygen / html / namespaceboost_1_1sort.html
CommitLineData
7c673cae
FG		 1<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
2<html xmlns="http://www.w3.org/1999/xhtml">
3<head>
4<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
5<meta http-equiv="X-UA-Compatible" content="IE=9"/>
6<meta name="generator" content="Doxygen 1.8.9.1"/>
7<title>Boost.Sort: boost::sort Namespace Reference</title>
8<link href="tabs.css" rel="stylesheet" type="text/css"/>
9<script type="text/javascript" src="jquery.js"></script>
10<script type="text/javascript" src="dynsections.js"></script>
11<link href="search/search.css" rel="stylesheet" type="text/css"/>
12<script type="text/javascript" src="search/searchdata.js"></script>
13<script type="text/javascript" src="search/search.js"></script>
14<script type="text/javascript">
15 $(document).ready(function() { init_search(); });
16</script>
17<link href="doxygen.css" rel="stylesheet" type="text/css" />
18</head>
19<body>
20<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
21<div id="titlearea">
22<table cellspacing="0" cellpadding="0">
23 <tbody>
24 <tr style="height: 56px;">
25 <td style="padding-left: 0.5em;">
26 <div id="projectname">Boost.Sort
27 </div>
28 </td>
29 </tr>
30 </tbody>
31</table>
32</div>
33<!-- end header part -->
34<!-- Generated by Doxygen 1.8.9.1 -->
35<script type="text/javascript">
36var searchBox = new SearchBox("searchBox", "search",false,'Search');
37</script>
38 <div id="navrow1" class="tabs">
39 <ul class="tablist">
40 <li><a href="index.html"><span>Main&#160;Page</span></a></li>
41 <li class="current"><a href="namespaces.html"><span>Namespaces</span></a></li>
42 <li><a href="annotated.html"><span>Classes</span></a></li>
43 <li><a href="files.html"><span>Files</span></a></li>
44 <li>
45 <div id="MSearchBox" class="MSearchBoxInactive">
46 <span class="left">
47 <img id="MSearchSelect" src="search/mag_sel.png"
48 onmouseover="return searchBox.OnSearchSelectShow()"
49 onmouseout="return searchBox.OnSearchSelectHide()"
50 alt=""/>
51 <input type="text" id="MSearchField" value="Search" accesskey="S"
52 onfocus="searchBox.OnSearchFieldFocus(true)"
53 onblur="searchBox.OnSearchFieldFocus(false)"
54 onkeyup="searchBox.OnSearchFieldChange(event)"/>
55 </span><span class="right">
56 <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
57 </span>
58 </div>
59 </li>
60 </ul>
61 </div>
62 <div id="navrow2" class="tabs2">
63 <ul class="tablist">
64 <li><a href="namespaces.html"><span>Namespace&#160;List</span></a></li>
65 <li><a href="namespacemembers.html"><span>Namespace&#160;Members</span></a></li>
66 </ul>
67 </div>
68<!-- window showing the filter options -->
69<div id="MSearchSelectWindow"
70 onmouseover="return searchBox.OnSearchSelectShow()"
71 onmouseout="return searchBox.OnSearchSelectHide()"
72 onkeydown="return searchBox.OnSearchSelectKey(event)">
73</div>
74
75<!-- iframe showing the search results (closed by default) -->
76<div id="MSearchResultsWindow">
77<iframe src="javascript:void(0)" frameborder="0"
78 name="MSearchResults" id="MSearchResults">
79</iframe>
80</div>
81
82<div id="nav-path" class="navpath">
83 <ul>
84<li class="navelem"><a class="el" href="namespaceboost.html">boost</a></li><li class="navelem"><a class="el" href="namespaceboost_1_1sort.html">sort</a></li> </ul>
85</div>
86</div><!-- top -->
87<div class="header">
88 <div class="summary">
89<a href="#func-members">Functions</a> </div>
90 <div class="headertitle">
91<div class="title">boost::sort Namespace Reference</div> </div>
92</div><!--header-->
93<div class="contents">
94<table class="memberdecls">
95<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="func-members"></a>
96Functions</h2></td></tr>
97<tr class="memitem:ac3a946e197df6cfc4968c6371ace319b"><td class="memTemplParams" colspan="2">template&lt;class Data_type , class Cast_type &gt; </td></tr>
98<tr class="memitem:ac3a946e197df6cfc4968c6371ace319b"><td class="memTemplItemLeft" align="right" valign="top">Cast_type&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespaceboost_1_1sort.html#ac3a946e197df6cfc4968c6371ace319b">float_mem_cast</a> (const Data_type &amp;data)</td></tr>
99<tr class="memdesc:ac3a946e197df6cfc4968c6371ace319b"><td class="mdescLeft">&#160;</td><td class="mdescRight">Casts a float to the specified integer type. <a href="#ac3a946e197df6cfc4968c6371ace319b">More...</a><br /></td></tr>
100<tr class="separator:ac3a946e197df6cfc4968c6371ace319b"><td class="memSeparator" colspan="2">&#160;</td></tr>
101<tr class="memitem:acbcfc139de18c5c35c0ff1744c56e211"><td class="memTemplParams" colspan="2">template&lt;class RandomAccessIter &gt; </td></tr>
102<tr class="memitem:acbcfc139de18c5c35c0ff1744c56e211"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespaceboost_1_1sort.html#acbcfc139de18c5c35c0ff1744c56e211">float_sort</a> (RandomAccessIter first, RandomAccessIter last)</td></tr>
103<tr class="memdesc:acbcfc139de18c5c35c0ff1744c56e211"><td class="mdescLeft">&#160;</td><td class="mdescRight"><code>float_sort</code> with casting to the appropriate size. <a href="#acbcfc139de18c5c35c0ff1744c56e211">More...</a><br /></td></tr>
104<tr class="separator:acbcfc139de18c5c35c0ff1744c56e211"><td class="memSeparator" colspan="2">&#160;</td></tr>
105<tr class="memitem:ad65f9ec25686acfbd2a59683cc99be12"><td class="memTemplParams" colspan="2">template&lt;class RandomAccessIter , class Right_shift &gt; </td></tr>
106<tr class="memitem:ad65f9ec25686acfbd2a59683cc99be12"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespaceboost_1_1sort.html#ad65f9ec25686acfbd2a59683cc99be12">float_sort</a> (RandomAccessIter first, RandomAccessIter last, Right_shift rshift)</td></tr>
107<tr class="memdesc:ad65f9ec25686acfbd2a59683cc99be12"><td class="mdescLeft">&#160;</td><td class="mdescRight">Floating-point sort algorithm using random access iterators with just right-shift functor. <a href="#ad65f9ec25686acfbd2a59683cc99be12">More...</a><br /></td></tr>
108<tr class="separator:ad65f9ec25686acfbd2a59683cc99be12"><td class="memSeparator" colspan="2">&#160;</td></tr>
109<tr class="memitem:a941746cb1461c5f4971c2cf1efb9301e"><td class="memTemplParams" colspan="2">template&lt;class RandomAccessIter , class Right_shift , class Compare &gt; </td></tr>
110<tr class="memitem:a941746cb1461c5f4971c2cf1efb9301e"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespaceboost_1_1sort.html#a941746cb1461c5f4971c2cf1efb9301e">float_sort</a> (RandomAccessIter first, RandomAccessIter last, Right_shift rshift, Compare comp)</td></tr>
111<tr class="memdesc:a941746cb1461c5f4971c2cf1efb9301e"><td class="mdescLeft">&#160;</td><td class="mdescRight">Float sort algorithm using random access iterators with both right-shift and user-defined comparison operator. <a href="#a941746cb1461c5f4971c2cf1efb9301e">More...</a><br /></td></tr>
112<tr class="separator:a941746cb1461c5f4971c2cf1efb9301e"><td class="memSeparator" colspan="2">&#160;</td></tr>
113<tr class="memitem:ae6ffbcf932699589fd2b93879f209013"><td class="memTemplParams" colspan="2">template&lt;class RandomAccessIter &gt; </td></tr>
114<tr class="memitem:ae6ffbcf932699589fd2b93879f209013"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespaceboost_1_1sort.html#ae6ffbcf932699589fd2b93879f209013">integer_sort</a> (RandomAccessIter first, RandomAccessIter last)</td></tr>
115<tr class="memdesc:ae6ffbcf932699589fd2b93879f209013"><td class="mdescLeft">&#160;</td><td class="mdescRight">Integer sort algorithm using random access iterators. (All variants fall back to <code>std::sort</code> if the data size is too small, &lt; <code>detail::min_sort_size</code>). <a href="#ae6ffbcf932699589fd2b93879f209013">More...</a><br /></td></tr>
116<tr class="separator:ae6ffbcf932699589fd2b93879f209013"><td class="memSeparator" colspan="2">&#160;</td></tr>
117<tr class="memitem:aa4ebb2541be58f9f0fecd8d7c108b817"><td class="memTemplParams" colspan="2">template&lt;class RandomAccessIter , class Right_shift , class Compare &gt; </td></tr>
118<tr class="memitem:aa4ebb2541be58f9f0fecd8d7c108b817"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespaceboost_1_1sort.html#aa4ebb2541be58f9f0fecd8d7c108b817">integer_sort</a> (RandomAccessIter first, RandomAccessIter last, Right_shift shift, Compare comp)</td></tr>
119<tr class="memdesc:aa4ebb2541be58f9f0fecd8d7c108b817"><td class="mdescLeft">&#160;</td><td class="mdescRight">Integer sort algorithm using random access iterators with both right-shift and user-defined comparison operator. (All variants fall back to <code>std::sort</code> if the data size is too small, &lt; <code>detail::min_sort_size</code>). <a href="#aa4ebb2541be58f9f0fecd8d7c108b817">More...</a><br /></td></tr>
120<tr class="separator:aa4ebb2541be58f9f0fecd8d7c108b817"><td class="memSeparator" colspan="2">&#160;</td></tr>
121<tr class="memitem:ae50349854aad811f67a540d9b3aa4d4a"><td class="memTemplParams" colspan="2">template&lt;class RandomAccessIter , class Right_shift &gt; </td></tr>
122<tr class="memitem:ae50349854aad811f67a540d9b3aa4d4a"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespaceboost_1_1sort.html#ae50349854aad811f67a540d9b3aa4d4a">integer_sort</a> (RandomAccessIter first, RandomAccessIter last, Right_shift shift)</td></tr>
123<tr class="memdesc:ae50349854aad811f67a540d9b3aa4d4a"><td class="mdescLeft">&#160;</td><td class="mdescRight">Integer sort algorithm using random access iterators with just right-shift functor. (All variants fall back to <code>std::sort</code> if the data size is too small, &lt; <code>detail::min_sort_size</code>). <a href="#ae50349854aad811f67a540d9b3aa4d4a">More...</a><br /></td></tr>
124<tr class="separator:ae50349854aad811f67a540d9b3aa4d4a"><td class="memSeparator" colspan="2">&#160;</td></tr>
125<tr class="memitem:a4bc25fdacd4c948f631f08a3f9aa38eb"><td class="memTemplParams" colspan="2">template&lt;class RandomAccessIter &gt; </td></tr>
126<tr class="memitem:a4bc25fdacd4c948f631f08a3f9aa38eb"><td class="memTemplItemLeft" align="right" valign="top">boost::enable_if_c&lt; std::numeric_limits&lt; typename std::iterator_traits&lt; RandomAccessIter &gt;::value_type &gt;::is_integer, void &gt;::type&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespaceboost_1_1sort.html#a4bc25fdacd4c948f631f08a3f9aa38eb">spreadsort</a> (RandomAccessIter first, RandomAccessIter last)</td></tr>
127<tr class="memdesc:a4bc25fdacd4c948f631f08a3f9aa38eb"><td class="mdescLeft">&#160;</td><td class="mdescRight">Generic <code>spreadsort</code> variant detecting integer-type elements so call to <code>integer_sort</code>. <a href="#a4bc25fdacd4c948f631f08a3f9aa38eb">More...</a><br /></td></tr>
128<tr class="separator:a4bc25fdacd4c948f631f08a3f9aa38eb"><td class="memSeparator" colspan="2">&#160;</td></tr>
129<tr class="memitem:a94a736da091bd5d3b525818399f1b272"><td class="memTemplParams" colspan="2">template&lt;class RandomAccessIter &gt; </td></tr>
130<tr class="memitem:a94a736da091bd5d3b525818399f1b272"><td class="memTemplItemLeft" align="right" valign="top">boost::enable_if_c&lt; !std::numeric_limits&lt; typename std::iterator_traits&lt; RandomAccessIter &gt;::value_type &gt;::is_integer &amp;&amp;std::numeric_limits&lt; typename std::iterator_traits&lt; RandomAccessIter &gt;::value_type &gt;::is_iec559, void &gt;::type&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespaceboost_1_1sort.html#a94a736da091bd5d3b525818399f1b272">spreadsort</a> (RandomAccessIter first, RandomAccessIter last)</td></tr>
131<tr class="memdesc:a94a736da091bd5d3b525818399f1b272"><td class="mdescLeft">&#160;</td><td class="mdescRight">Generic <code>spreadsort</code> variant detecting float element type so call to <code>float_sort</code>. <a href="#a94a736da091bd5d3b525818399f1b272">More...</a><br /></td></tr>
132<tr class="separator:a94a736da091bd5d3b525818399f1b272"><td class="memSeparator" colspan="2">&#160;</td></tr>
133<tr class="memitem:aafdea66d9b4a7faef5604b3079b525fa"><td class="memTemplParams" colspan="2">template&lt;class RandomAccessIter &gt; </td></tr>
134<tr class="memitem:aafdea66d9b4a7faef5604b3079b525fa"><td class="memTemplItemLeft" align="right" valign="top">boost::enable_if_c&lt; is_same&lt; typename std::iterator_traits&lt; RandomAccessIter &gt;::value_type, typename std::string &gt;::value||is_same&lt; typename std::iterator_traits&lt; RandomAccessIter &gt;::value_type, typename std::wstring &gt;::value, void &gt;::type&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespaceboost_1_1sort.html#aafdea66d9b4a7faef5604b3079b525fa">spreadsort</a> (RandomAccessIter first, RandomAccessIter last)</td></tr>
135<tr class="memdesc:aafdea66d9b4a7faef5604b3079b525fa"><td class="mdescLeft">&#160;</td><td class="mdescRight">Generic <code>spreadsort</code> variant detecting string element type so call to <code>string_sort</code> for <code>std::strings</code> and <code>std::wstrings</code>. <a href="#aafdea66d9b4a7faef5604b3079b525fa">More...</a><br /></td></tr>
136<tr class="separator:aafdea66d9b4a7faef5604b3079b525fa"><td class="memSeparator" colspan="2">&#160;</td></tr>
137<tr class="memitem:a950a2dbbe75f048a0b343dbf7c532dc0"><td class="memTemplParams" colspan="2">template&lt;class RandomAccessIter , class Unsigned_char_type &gt; </td></tr>
138<tr class="memitem:a950a2dbbe75f048a0b343dbf7c532dc0"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespaceboost_1_1sort.html#a950a2dbbe75f048a0b343dbf7c532dc0">string_sort</a> (RandomAccessIter first, RandomAccessIter last, Unsigned_char_type unused)</td></tr>
139<tr class="memdesc:a950a2dbbe75f048a0b343dbf7c532dc0"><td class="mdescLeft">&#160;</td><td class="mdescRight">String sort algorithm using random access iterators, allowing character-type overloads.<br />
140 (All variants fall back to <code>std::sort</code> if the data size is too small, &lt; <code>detail::min_sort_size</code>). <a href="#a950a2dbbe75f048a0b343dbf7c532dc0">More...</a><br /></td></tr>
141<tr class="separator:a950a2dbbe75f048a0b343dbf7c532dc0"><td class="memSeparator" colspan="2">&#160;</td></tr>
142<tr class="memitem:a6acd5fc94521b0a5cb47dc491b6d862f"><td class="memTemplParams" colspan="2">template&lt;class RandomAccessIter &gt; </td></tr>
143<tr class="memitem:a6acd5fc94521b0a5cb47dc491b6d862f"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespaceboost_1_1sort.html#a6acd5fc94521b0a5cb47dc491b6d862f">string_sort</a> (RandomAccessIter first, RandomAccessIter last)</td></tr>
144<tr class="memdesc:a6acd5fc94521b0a5cb47dc491b6d862f"><td class="mdescLeft">&#160;</td><td class="mdescRight">String sort algorithm using random access iterators, wraps using default of unsigned char. (All variants fall back to <code>std::sort</code> if the data size is too small, &lt; <code>detail::min_sort_size</code>). <a href="#a6acd5fc94521b0a5cb47dc491b6d862f">More...</a><br /></td></tr>
145<tr class="separator:a6acd5fc94521b0a5cb47dc491b6d862f"><td class="memSeparator" colspan="2">&#160;</td></tr>
146<tr class="memitem:a4ad4785d90f47d51ff1d2fac8c21bb48"><td class="memTemplParams" colspan="2">template&lt;class RandomAccessIter , class Compare , class Unsigned_char_type &gt; </td></tr>
147<tr class="memitem:a4ad4785d90f47d51ff1d2fac8c21bb48"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespaceboost_1_1sort.html#a4ad4785d90f47d51ff1d2fac8c21bb48">reverse_string_sort</a> (RandomAccessIter first, RandomAccessIter last, Compare comp, Unsigned_char_type unused)</td></tr>
148<tr class="memdesc:a4ad4785d90f47d51ff1d2fac8c21bb48"><td class="mdescLeft">&#160;</td><td class="mdescRight">String sort algorithm using random access iterators, allowing character-type overloads. <a href="#a4ad4785d90f47d51ff1d2fac8c21bb48">More...</a><br /></td></tr>
149<tr class="separator:a4ad4785d90f47d51ff1d2fac8c21bb48"><td class="memSeparator" colspan="2">&#160;</td></tr>
150<tr class="memitem:afd4938835fd03aab9c42bd0653e5dbe5"><td class="memTemplParams" colspan="2">template&lt;class RandomAccessIter , class Compare &gt; </td></tr>
151<tr class="memitem:afd4938835fd03aab9c42bd0653e5dbe5"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespaceboost_1_1sort.html#afd4938835fd03aab9c42bd0653e5dbe5">reverse_string_sort</a> (RandomAccessIter first, RandomAccessIter last, Compare comp)</td></tr>
152<tr class="memdesc:afd4938835fd03aab9c42bd0653e5dbe5"><td class="mdescLeft">&#160;</td><td class="mdescRight">String sort algorithm using random access iterators, wraps using default of <code>unsigned</code> char. <a href="#afd4938835fd03aab9c42bd0653e5dbe5">More...</a><br /></td></tr>
153<tr class="separator:afd4938835fd03aab9c42bd0653e5dbe5"><td class="memSeparator" colspan="2">&#160;</td></tr>
154<tr class="memitem:a5143ec4f58cfe13eca2a0d6b6f6a6680"><td class="memTemplParams" colspan="2">template&lt;class RandomAccessIter , class Get_char , class Get_length &gt; </td></tr>
155<tr class="memitem:a5143ec4f58cfe13eca2a0d6b6f6a6680"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespaceboost_1_1sort.html#a5143ec4f58cfe13eca2a0d6b6f6a6680">string_sort</a> (RandomAccessIter first, RandomAccessIter last, Get_char getchar, Get_length length)</td></tr>
156<tr class="memdesc:a5143ec4f58cfe13eca2a0d6b6f6a6680"><td class="mdescLeft">&#160;</td><td class="mdescRight">String sort algorithm using random access iterators, wraps using default of <code>unsigned</code> char. <a href="#a5143ec4f58cfe13eca2a0d6b6f6a6680">More...</a><br /></td></tr>
157<tr class="separator:a5143ec4f58cfe13eca2a0d6b6f6a6680"><td class="memSeparator" colspan="2">&#160;</td></tr>
158<tr class="memitem:a82c4c0d7ba9873ecce7c674631dceae2"><td class="memTemplParams" colspan="2">template&lt;class RandomAccessIter , class Get_char , class Get_length , class Compare &gt; </td></tr>
159<tr class="memitem:a82c4c0d7ba9873ecce7c674631dceae2"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespaceboost_1_1sort.html#a82c4c0d7ba9873ecce7c674631dceae2">string_sort</a> (RandomAccessIter first, RandomAccessIter last, Get_char getchar, Get_length length, Compare comp)</td></tr>
160<tr class="memdesc:a82c4c0d7ba9873ecce7c674631dceae2"><td class="mdescLeft">&#160;</td><td class="mdescRight">String sort algorithm using random access iterators, wraps using default of <code>unsigned</code> char. <a href="#a82c4c0d7ba9873ecce7c674631dceae2">More...</a><br /></td></tr>
161<tr class="separator:a82c4c0d7ba9873ecce7c674631dceae2"><td class="memSeparator" colspan="2">&#160;</td></tr>
162<tr class="memitem:a7940f1b2a7746c083a12a4e26077096b"><td class="memTemplParams" colspan="2">template&lt;class RandomAccessIter , class Get_char , class Get_length , class Compare &gt; </td></tr>
163<tr class="memitem:a7940f1b2a7746c083a12a4e26077096b"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespaceboost_1_1sort.html#a7940f1b2a7746c083a12a4e26077096b">reverse_string_sort</a> (RandomAccessIter first, RandomAccessIter last, Get_char getchar, Get_length length, Compare comp)</td></tr>
164<tr class="memdesc:a7940f1b2a7746c083a12a4e26077096b"><td class="mdescLeft">&#160;</td><td class="mdescRight">Reverse String sort algorithm using random access iterators. <a href="#a7940f1b2a7746c083a12a4e26077096b">More...</a><br /></td></tr>
165<tr class="separator:a7940f1b2a7746c083a12a4e26077096b"><td class="memSeparator" colspan="2">&#160;</td></tr>
166</table>
167<a name="details" id="details"></a><h2 class="groupheader">Detailed Description</h2>
168<div class="textblock"><p>Namespace for spreadsort sort variants for different data types. </p><dl class="section note"><dt>Note</dt><dd>Use hyperlinks (coloured) to get detailed information about functions. </dd></dl>
169</div><h2 class="groupheader">Function Documentation</h2>
170<a class="anchor" id="ac3a946e197df6cfc4968c6371ace319b"></a>
171<div class="memitem">
172<div class="memproto">
173<div class="memtemplate">
174template&lt;class Data_type , class Cast_type &gt; </div>
175<table class="mlabels">
176 <tr>
177 <td class="mlabels-left">
178 <table class="memname">
179 <tr>
180 <td class="memname">Cast_type boost::sort::float_mem_cast </td>
181 <td>(</td>
182 <td class="paramtype">const Data_type &amp;&#160;</td>
183 <td class="paramname"><em>data</em></td><td>)</td>
184 <td></td>
185 </tr>
186 </table>
187 </td>
188 <td class="mlabels-right">
189<span class="mlabels"><span class="mlabel">inline</span></span> </td>
190 </tr>
191</table>
192</div><div class="memdoc">
193
194<p>Casts a float to the specified integer type. </p>
195<dl class="tparams"><dt>Template Parameters</dt><dd>
196 <table class="tparams">
197 <tr><td class="paramname">Data_type</td><td>Floating-point IEEE 754/IEC559 type. </td></tr>
198 <tr><td class="paramname">Cast_type</td><td>Integer type (same size) to which to cast.</td></tr>
199 </table>
200 </dd>
201</dl>
202<dl class="section user"><dt>Example:</dt><dd><div class="fragment"><div class="line"><span class="keyword">struct </span><a class="code" href="structrightshift.html">rightshift</a> {</div>
203<div class="line"> <span class="keywordtype">int</span> operator()(<span class="keyword">const</span> <a class="code" href="struct_d_a_t_a___t_y_p_e.html">DATA_TYPE</a> &amp;x, <span class="keyword">const</span> <span class="keywordtype">unsigned</span> offset)<span class="keyword"> const </span>{</div>
204<div class="line"> <span class="keywordflow">return</span> <a class="code" href="namespaceboost_1_1sort.html#ac3a946e197df6cfc4968c6371ace319b">float_mem_cast</a>&lt;<a class="code" href="floatfunctorsample_8cpp.html#ae35c40bc2f912c11f0e36ac66cba4489">KEY_TYPE</a>, <a class="code" href="double_8cpp.html#a38779bfd63dd113c9f7602664546a58c">CAST_TYPE</a>&gt;(x.<a class="code" href="struct_d_a_t_a___t_y_p_e.html#aa28561fc8e223d84187ccfaf99953bae">key</a>) &gt;&gt; offset;</div>
205<div class="line"> }</div>
206<div class="line">};</div>
207</div><!-- fragment --> </dd></dl>
208
209</div>
210</div>
211<a class="anchor" id="acbcfc139de18c5c35c0ff1744c56e211"></a>
212<div class="memitem">
213<div class="memproto">
214<div class="memtemplate">
215template&lt;class RandomAccessIter &gt; </div>
216<table class="mlabels">
217 <tr>
218 <td class="mlabels-left">
219 <table class="memname">
220 <tr>
221 <td class="memname">void boost::sort::float_sort </td>
222 <td>(</td>
223 <td class="paramtype">RandomAccessIter&#160;</td>
224 <td class="paramname"><em>first</em>, </td>
225 </tr>
226 <tr>
227 <td class="paramkey"></td>
228 <td></td>
229 <td class="paramtype">RandomAccessIter&#160;</td>
230 <td class="paramname"><em>last</em>&#160;</td>
231 </tr>
232 <tr>
233 <td></td>
234 <td>)</td>
235 <td></td><td></td>
236 </tr>
237 </table>
238 </td>
239 <td class="mlabels-right">
240<span class="mlabels"><span class="mlabel">inline</span></span> </td>
241 </tr>
242</table>
243</div><div class="memdoc">
244
245<p><code>float_sort</code> with casting to the appropriate size. </p>
246<dl class="tparams"><dt>Template Parameters</dt><dd>
247 <table class="tparams">
248 <tr><td class="paramname">RandomAccessIter</td><td><a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a></td></tr>
249 </table>
250 </dd>
251</dl>
252<dl class="params"><dt>Parameters</dt><dd>
253 <table class="params">
254 <tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>Iterator pointer to first element. </td></tr>
255 <tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>Iterator pointing to one beyond the end of data.</td></tr>
256 </table>
257 </dd>
258</dl>
259<p>Some performance plots of runtime vs. n and log(range) are provided:<br />
260 <a href="../../doc/graph/windows_float_sort.htm">windows_float_sort</a> <br />
261 <a href="../../doc/graph/osx_float_sort.htm">osx_float_sort</a></p>
262<dl class="section user"><dt>A simple example of sorting some floating-point is:</dt><dd><div class="fragment"><div class="line">vector&lt;float&gt; vec;</div>
263<div class="line">vec.push_back(1.0);</div>
264<div class="line">vec.push_back(2.3);</div>
265<div class="line">vec.push_back(1.3);</div>
266<div class="line"><a class="code" href="namespaceboost_1_1sort.html#a4bc25fdacd4c948f631f08a3f9aa38eb">spreadsort</a>(vec.begin(), vec.end());</div>
267</div><!-- fragment --> </dd></dl>
268<dl class="section user"><dt>The sorted vector contains ascending values "1.0 1.3 2.3".</dt><dd></dd></dl>
269
270</div>
271</div>
272<a class="anchor" id="ad65f9ec25686acfbd2a59683cc99be12"></a>
273<div class="memitem">
274<div class="memproto">
275<div class="memtemplate">
276template&lt;class RandomAccessIter , class Right_shift &gt; </div>
277<table class="mlabels">
278 <tr>
279 <td class="mlabels-left">
280 <table class="memname">
281 <tr>
282 <td class="memname">void boost::sort::float_sort </td>
283 <td>(</td>
284 <td class="paramtype">RandomAccessIter&#160;</td>
285 <td class="paramname"><em>first</em>, </td>
286 </tr>
287 <tr>
288 <td class="paramkey"></td>
289 <td></td>
290 <td class="paramtype">RandomAccessIter&#160;</td>
291 <td class="paramname"><em>last</em>, </td>
292 </tr>
293 <tr>
294 <td class="paramkey"></td>
295 <td></td>
296 <td class="paramtype">Right_shift&#160;</td>
297 <td class="paramname"><em>rshift</em>&#160;</td>
298 </tr>
299 <tr>
300 <td></td>
301 <td>)</td>
302 <td></td><td></td>
303 </tr>
304 </table>
305 </td>
306 <td class="mlabels-right">
307<span class="mlabels"><span class="mlabel">inline</span></span> </td>
308 </tr>
309</table>
310</div><div class="memdoc">
311
312<p>Floating-point sort algorithm using random access iterators with just right-shift functor. </p>
313<dl class="tparams"><dt>Template Parameters</dt><dd>
314 <table class="tparams">
315 <tr><td class="paramname">RandomAccessIter</td><td><a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a> </td></tr>
316 <tr><td class="paramname">Right_shift</td><td>Functor for right-shift by parameter <code>shift</code> bits.</td></tr>
317 </table>
318 </dd>
319</dl>
320<dl class="params"><dt>Parameters</dt><dd>
321 <table class="params">
322 <tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>Iterator pointer to first element. </td></tr>
323 <tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>Iterator pointing to one beyond the end of data. </td></tr>
324 <tr><td class="paramdir">[in]</td><td class="paramname">rshift</td><td>Number of bits to right-shift (using functor). </td></tr>
325 </table>
326 </dd>
327</dl>
328
329</div>
330</div>
331<a class="anchor" id="a941746cb1461c5f4971c2cf1efb9301e"></a>
332<div class="memitem">
333<div class="memproto">
334<div class="memtemplate">
335template&lt;class RandomAccessIter , class Right_shift , class Compare &gt; </div>
336<table class="mlabels">
337 <tr>
338 <td class="mlabels-left">
339 <table class="memname">
340 <tr>
341 <td class="memname">void boost::sort::float_sort </td>
342 <td>(</td>
343 <td class="paramtype">RandomAccessIter&#160;</td>
344 <td class="paramname"><em>first</em>, </td>
345 </tr>
346 <tr>
347 <td class="paramkey"></td>
348 <td></td>
349 <td class="paramtype">RandomAccessIter&#160;</td>
350 <td class="paramname"><em>last</em>, </td>
351 </tr>
352 <tr>
353 <td class="paramkey"></td>
354 <td></td>
355 <td class="paramtype">Right_shift&#160;</td>
356 <td class="paramname"><em>rshift</em>, </td>
357 </tr>
358 <tr>
359 <td class="paramkey"></td>
360 <td></td>
361 <td class="paramtype">Compare&#160;</td>
362 <td class="paramname"><em>comp</em>&#160;</td>
363 </tr>
364 <tr>
365 <td></td>
366 <td>)</td>
367 <td></td><td></td>
368 </tr>
369 </table>
370 </td>
371 <td class="mlabels-right">
372<span class="mlabels"><span class="mlabel">inline</span></span> </td>
373 </tr>
374</table>
375</div><div class="memdoc">
376
377<p>Float sort algorithm using random access iterators with both right-shift and user-defined comparison operator. </p>
378<dl class="tparams"><dt>Template Parameters</dt><dd>
379 <table class="tparams">
380 <tr><td class="paramname">RandomAccessIter</td><td><a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a> </td></tr>
381 <tr><td class="paramname">Right_shift</td><td>functor for right-shift by parameter <code>shift</code> bits. </td></tr>
382 <tr><td class="paramname">Comp</td><td>To provide <code>operator&lt;</code> for user-defined comparison.</td></tr>
383 </table>
384 </dd>
385</dl>
386<dl class="params"><dt>Parameters</dt><dd>
387 <table class="params">
388 <tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>Iterator pointer to first element. </td></tr>
389 <tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>Iterator pointing to one beyond the end of data. </td></tr>
390 <tr><td class="paramdir">[in]</td><td class="paramname">rshift</td><td>Number of bits to right-shift (using functor). </td></tr>
391 <tr><td class="paramdir">[in]</td><td class="paramname">comp</td><td>comparison functor. </td></tr>
392 </table>
393 </dd>
394</dl>
395
396</div>
397</div>
398<a class="anchor" id="ae6ffbcf932699589fd2b93879f209013"></a>
399<div class="memitem">
400<div class="memproto">
401<div class="memtemplate">
402template&lt;class RandomAccessIter &gt; </div>
403<table class="mlabels">
404 <tr>
405 <td class="mlabels-left">
406 <table class="memname">
407 <tr>
408 <td class="memname">void boost::sort::integer_sort </td>
409 <td>(</td>
410 <td class="paramtype">RandomAccessIter&#160;</td>
411 <td class="paramname"><em>first</em>, </td>
412 </tr>
413 <tr>
414 <td class="paramkey"></td>
415 <td></td>
416 <td class="paramtype">RandomAccessIter&#160;</td>
417 <td class="paramname"><em>last</em>&#160;</td>
418 </tr>
419 <tr>
420 <td></td>
421 <td>)</td>
422 <td></td><td></td>
423 </tr>
424 </table>
425 </td>
426 <td class="mlabels-right">
427<span class="mlabels"><span class="mlabel">inline</span></span> </td>
428 </tr>
429</table>
430</div><div class="memdoc">
431
432<p>Integer sort algorithm using random access iterators. (All variants fall back to <code>std::sort</code> if the data size is too small, &lt; <code>detail::min_sort_size</code>). </p>
433<p><code>integer_sort</code> is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than <code>std::sort</code> for large tests (&gt;=100kB).<br />
434Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, so <code>integer_sort</code> is asymptotically faster than pure comparison-based algorithms. <code>s</code> is <code>max_splits</code>, which defaults to 11, so its worst-case with default settings for 32-bit integers is <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).<br />
435<br />
436Some performance plots of runtime vs. n and log(range) are provided:<br />
437 <a href="../../doc/graph/windows_integer_sort.htm">windows_integer_sort</a> <br />
438 <a href="../../doc/graph/osx_integer_sort.htm">osx_integer_sort</a></p>
439<dl class="tparams"><dt>Template Parameters</dt><dd>
440 <table class="tparams">
441 <tr><td class="paramname">RandomAccessIter</td><td><a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a> </td></tr>
442 </table>
443 </dd>
444</dl>
445<dl class="params"><dt>Parameters</dt><dd>
446 <table class="params">
447 <tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>Iterator pointer to first element. </td></tr>
448 <tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>Iterator pointing to one beyond the end of data.</td></tr>
449 </table>
450 </dd>
451</dl>
452<dl class="section pre"><dt>Precondition</dt><dd>[<code>first</code>, <code>last</code>) is a valid range. </dd>
453<dd>
454<code>RandomAccessIter</code> <code>value_type</code> is mutable. </dd>
455<dd>
456<code>RandomAccessIter</code> <code>value_type</code> is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> </dd>
457<dd>
458<code>RandomAccessIter</code> <code>value_type</code> supports the <code>operator&gt;&gt;</code>, which returns an integer-type right-shifted a specified number of bits. </dd></dl>
459<dl class="section post"><dt>Postcondition</dt><dd>The elements in the range [<code>first</code>, <code>last</code>) are sorted in ascending order.</dd></dl>
460<dl class="exception"><dt>Exceptions</dt><dd>
461 <table class="exception">
462 <tr><td class="paramname">std::exception</td><td>Propagates exceptions if any of the element comparisons, the element swaps (or moves), the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw.</td></tr>
463 </table>
464 </dd>
465</dl>
466<dl class="section warning"><dt>Warning</dt><dd>Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. </dd>
467<dd>
468Invalid arguments cause undefined behaviour. </dd></dl>
469<dl class="section note"><dt>Note</dt><dd><code>spreadsort</code> function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.</dd></dl>
470<dl class="section remark"><dt>Remarks</dt><dd>The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: </dd>
471<dd>
472* N is <code>last</code> - <code>first</code>, </dd>
473<dd>
474* K is the log of the range in bits (32 for 32-bit integers using their full range), </dd>
475<dd>
476* S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). </dd></dl>
477
478</div>
479</div>
480<a class="anchor" id="aa4ebb2541be58f9f0fecd8d7c108b817"></a>
481<div class="memitem">
482<div class="memproto">
483<div class="memtemplate">
484template&lt;class RandomAccessIter , class Right_shift , class Compare &gt; </div>
485<table class="mlabels">
486 <tr>
487 <td class="mlabels-left">
488 <table class="memname">
489 <tr>
490 <td class="memname">void boost::sort::integer_sort </td>
491 <td>(</td>
492 <td class="paramtype">RandomAccessIter&#160;</td>
493 <td class="paramname"><em>first</em>, </td>
494 </tr>
495 <tr>
496 <td class="paramkey"></td>
497 <td></td>
498 <td class="paramtype">RandomAccessIter&#160;</td>
499 <td class="paramname"><em>last</em>, </td>
500 </tr>
501 <tr>
502 <td class="paramkey"></td>
503 <td></td>
504 <td class="paramtype">Right_shift&#160;</td>
505 <td class="paramname"><em>shift</em>, </td>
506 </tr>
507 <tr>
508 <td class="paramkey"></td>
509 <td></td>
510 <td class="paramtype">Compare&#160;</td>
511 <td class="paramname"><em>comp</em>&#160;</td>
512 </tr>
513 <tr>
514 <td></td>
515 <td>)</td>
516 <td></td><td></td>
517 </tr>
518 </table>
519 </td>
520 <td class="mlabels-right">
521<span class="mlabels"><span class="mlabel">inline</span></span> </td>
522 </tr>
523</table>
524</div><div class="memdoc">
525
526<p>Integer sort algorithm using random access iterators with both right-shift and user-defined comparison operator. (All variants fall back to <code>std::sort</code> if the data size is too small, &lt; <code>detail::min_sort_size</code>). </p>
527<p><code>integer_sort</code> is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than <code>std::sort</code> for large tests (&gt;=100kB).<br />
528Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, so <code>integer_sort</code> is asymptotically faster than pure comparison-based algorithms. <code>s</code> is <code>max_splits</code>, which defaults to 11, so its worst-case with default settings for 32-bit integers is <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).<br />
529<br />
530Some performance plots of runtime vs. n and log(range) are provided:<br />
531 <a href="../../doc/graph/windows_integer_sort.htm">windows_integer_sort</a> <br />
532 <a href="../../doc/graph/osx_integer_sort.htm">osx_integer_sort</a></p>
533<dl class="tparams"><dt>Template Parameters</dt><dd>
534 <table class="tparams">
535 <tr><td class="paramname">RandomAccessIter</td><td><a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a> </td></tr>
536 <tr><td class="paramname">Right_shift</td><td>functor for right-shift by parameter <code>shift</code> bits. </td></tr>
537 <tr><td class="paramname">Comp</td><td>To provide <code>operator&lt;</code> for user-defined comparison.</td></tr>
538 </table>
539 </dd>
540</dl>
541<dl class="params"><dt>Parameters</dt><dd>
542 <table class="params">
543 <tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>Iterator pointer to first element. </td></tr>
544 <tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>Iterator pointing to one beyond the end of data. </td></tr>
545 <tr><td class="paramdir">[in]</td><td class="paramname">shift</td><td>Number of bits to right-shift (using functor). </td></tr>
546 <tr><td class="paramdir">[in]</td><td class="paramname">comp</td><td>comparison functor.</td></tr>
547 </table>
548 </dd>
549</dl>
550<dl class="section pre"><dt>Precondition</dt><dd>[<code>first</code>, <code>last</code>) is a valid range. </dd>
551<dd>
552<code>RandomAccessIter</code> <code>value_type</code> is mutable. </dd>
553<dd>
554<code>RandomAccessIter</code> <code>value_type</code> is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> </dd>
555<dd>
556<code>RandomAccessIter</code> <code>value_type</code> supports the <code>operator&gt;&gt;</code>, which returns an integer-type right-shifted a specified number of bits. </dd></dl>
557<dl class="section post"><dt>Postcondition</dt><dd>The elements in the range [<code>first</code>, <code>last</code>) are sorted in ascending order.</dd></dl>
558<dl class="section return"><dt>Returns</dt><dd><code>void</code>.</dd></dl>
559<dl class="exception"><dt>Exceptions</dt><dd>
560 <table class="exception">
561 <tr><td class="paramname">std::exception</td><td>Propagates exceptions if any of the element comparisons, the element swaps (or moves), the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw.</td></tr>
562 </table>
563 </dd>
564</dl>
565<dl class="section warning"><dt>Warning</dt><dd>Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. </dd>
566<dd>
567Invalid arguments cause undefined behaviour. </dd></dl>
568<dl class="section note"><dt>Note</dt><dd><code>spreadsort</code> function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.</dd></dl>
569<dl class="section remark"><dt>Remarks</dt><dd>The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: </dd>
570<dd>
571* N is <code>last</code> - <code>first</code>, </dd>
572<dd>
573* K is the log of the range in bits (32 for 32-bit integers using their full range), </dd>
574<dd>
575* S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). </dd></dl>
576
577</div>
578</div>
579<a class="anchor" id="ae50349854aad811f67a540d9b3aa4d4a"></a>
580<div class="memitem">
581<div class="memproto">
582<div class="memtemplate">
583template&lt;class RandomAccessIter , class Right_shift &gt; </div>
584<table class="mlabels">
585 <tr>
586 <td class="mlabels-left">
587 <table class="memname">
588 <tr>
589 <td class="memname">void boost::sort::integer_sort </td>
590 <td>(</td>
591 <td class="paramtype">RandomAccessIter&#160;</td>
592 <td class="paramname"><em>first</em>, </td>
593 </tr>
594 <tr>
595 <td class="paramkey"></td>
596 <td></td>
597 <td class="paramtype">RandomAccessIter&#160;</td>
598 <td class="paramname"><em>last</em>, </td>
599 </tr>
600 <tr>
601 <td class="paramkey"></td>
602 <td></td>
603 <td class="paramtype">Right_shift&#160;</td>
604 <td class="paramname"><em>shift</em>&#160;</td>
605 </tr>
606 <tr>
607 <td></td>
608 <td>)</td>
609 <td></td><td></td>
610 </tr>
611 </table>
612 </td>
613 <td class="mlabels-right">
614<span class="mlabels"><span class="mlabel">inline</span></span> </td>
615 </tr>
616</table>
617</div><div class="memdoc">
618
619<p>Integer sort algorithm using random access iterators with just right-shift functor. (All variants fall back to <code>std::sort</code> if the data size is too small, &lt; <code>detail::min_sort_size</code>). </p>
620<p><code>integer_sort</code> is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than <code>std::sort</code> for large tests (&gt;=100kB).<br />
621 </p><dl class="section user"><dt>Performance:</dt><dd>Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, so <code>integer_sort</code> is asymptotically faster than pure comparison-based algorithms. <code>s</code> is <code>max_splits</code>, which defaults to 11, so its worst-case with default settings for 32-bit integers is <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).<br />
622<br />
623Some performance plots of runtime vs. n and log(range) are provided:<br />
624 <a href="../../doc/graph/windows_integer_sort.htm">windows_integer_sort</a><br />
625 <a href="../../doc/graph/osx_integer_sort.htm">osx_integer_sort</a></dd></dl>
626<dl class="tparams"><dt>Template Parameters</dt><dd>
627 <table class="tparams">
628 <tr><td class="paramname">RandomAccessIter</td><td><a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a> </td></tr>
629 <tr><td class="paramname">Right_shift</td><td>functor for right-shift by parameter <code>shift</code> bits.</td></tr>
630 </table>
631 </dd>
632</dl>
633<dl class="params"><dt>Parameters</dt><dd>
634 <table class="params">
635 <tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>Iterator pointer to first element. </td></tr>
636 <tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>Iterator pointing to one beyond the end of data. </td></tr>
637 <tr><td class="paramdir">[in]</td><td class="paramname">shift</td><td>Number of bits to right-shift (using functor).</td></tr>
638 </table>
639 </dd>
640</dl>
641<dl class="section pre"><dt>Precondition</dt><dd>[<code>first</code>, <code>last</code>) is a valid range. </dd>
642<dd>
643<code>RandomAccessIter</code> <code>value_type</code> is mutable. </dd>
644<dd>
645<code>RandomAccessIter</code> <code>value_type</code> is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> </dd>
646<dd>
647<code>RandomAccessIter</code> <code>value_type</code> supports the <code>operator&gt;&gt;</code>, which returns an integer-type right-shifted a specified number of bits. </dd></dl>
648<dl class="section post"><dt>Postcondition</dt><dd>The elements in the range [<code>first</code>, <code>last</code>) are sorted in ascending order.</dd></dl>
649<dl class="exception"><dt>Exceptions</dt><dd>
650 <table class="exception">
651 <tr><td class="paramname">std::exception</td><td>Propagates exceptions if any of the element comparisons, the element swaps (or moves), the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw.</td></tr>
652 </table>
653 </dd>
654</dl>
655<dl class="section warning"><dt>Warning</dt><dd>Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. </dd>
656<dd>
657Invalid arguments cause undefined behaviour. </dd></dl>
658<dl class="section note"><dt>Note</dt><dd><code>spreadsort</code> function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.</dd></dl>
659<dl class="section remark"><dt>Remarks</dt><dd>The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: </dd>
660<dd>
661* N is <code>last</code> - <code>first</code>, </dd>
662<dd>
663* K is the log of the range in bits (32 for 32-bit integers using their full range), </dd>
664<dd>
665* S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). </dd></dl>
666
667</div>
668</div>
669<a class="anchor" id="a4ad4785d90f47d51ff1d2fac8c21bb48"></a>
670<div class="memitem">
671<div class="memproto">
672<div class="memtemplate">
673template&lt;class RandomAccessIter , class Compare , class Unsigned_char_type &gt; </div>
674<table class="mlabels">
675 <tr>
676 <td class="mlabels-left">
677 <table class="memname">
678 <tr>
679 <td class="memname">void boost::sort::reverse_string_sort </td>
680 <td>(</td>
681 <td class="paramtype">RandomAccessIter&#160;</td>
682 <td class="paramname"><em>first</em>, </td>
683 </tr>
684 <tr>
685 <td class="paramkey"></td>
686 <td></td>
687 <td class="paramtype">RandomAccessIter&#160;</td>
688 <td class="paramname"><em>last</em>, </td>
689 </tr>
690 <tr>
691 <td class="paramkey"></td>
692 <td></td>
693 <td class="paramtype">Compare&#160;</td>
694 <td class="paramname"><em>comp</em>, </td>
695 </tr>
696 <tr>
697 <td class="paramkey"></td>
698 <td></td>
699 <td class="paramtype">Unsigned_char_type&#160;</td>
700 <td class="paramname"><em>unused</em>&#160;</td>
701 </tr>
702 <tr>
703 <td></td>
704 <td>)</td>
705 <td></td><td></td>
706 </tr>
707 </table>
708 </td>
709 <td class="mlabels-right">
710<span class="mlabels"><span class="mlabel">inline</span></span> </td>
711 </tr>
712</table>
713</div><div class="memdoc">
714
715<p>String sort algorithm using random access iterators, allowing character-type overloads. </p>
716<p>(All variants fall back to <code>std::sort</code> if the data size is too small, &lt; detail::min_sort_size).</p>
717<p><code>integer_sort</code> is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than <code>std::sort</code> for large tests (&gt;=100kB).<br />
718Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, so <code>integer_sort</code> is asymptotically faster than pure comparison-based algorithms. <code>s</code> is <code>max_splits</code>, which defaults to 11, so its worst-case with default settings for 32-bit integers is <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).<br />
719<br />
720Some performance plots of runtime vs. n and log(range) are provided:<br />
721 <a href="../../doc/graph/windows_integer_sort.htm">windows_integer_sort</a> <br />
722 <a href="../../doc/graph/osx_integer_sort.htm">osx_integer_sort</a></p>
723<dl class="tparams"><dt>Template Parameters</dt><dd>
724 <table class="tparams">
725 <tr><td class="paramname">RandomAccessIter</td><td><a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a> </td></tr>
726 <tr><td class="paramname">Comp</td><td>To provide <code>operator&lt;</code> for user-defined comparison. </td></tr>
727 <tr><td class="paramname">Unsigned_char_type</td><td>Unsigned character type used for string.</td></tr>
728 </table>
729 </dd>
730</dl>
731<dl class="params"><dt>Parameters</dt><dd>
732 <table class="params">
733 <tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>Iterator pointer to first element. </td></tr>
734 <tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>Iterator pointing to one beyond the end of data. </td></tr>
735 <tr><td class="paramdir">[in]</td><td class="paramname">comp</td><td>comparison functor. </td></tr>
736 <tr><td class="paramdir">[in]</td><td class="paramname">unused</td><td>Unused ???</td></tr>
737 </table>
738 </dd>
739</dl>
740<dl class="section pre"><dt>Precondition</dt><dd>[<code>first</code>, <code>last</code>) is a valid range. </dd>
741<dd>
742<code>RandomAccessIter</code> <code>value_type</code> is mutable. </dd>
743<dd>
744<code>RandomAccessIter</code> <code>value_type</code> is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> </dd>
745<dd>
746<code>RandomAccessIter</code> <code>value_type</code> supports the <code>operator&gt;&gt;</code>, which returns an integer-type right-shifted a specified number of bits. </dd></dl>
747<dl class="section post"><dt>Postcondition</dt><dd>The elements in the range [<code>first</code>, <code>last</code>) are sorted in ascending order.</dd></dl>
748<dl class="section return"><dt>Returns</dt><dd><code>void</code>.</dd></dl>
749<dl class="exception"><dt>Exceptions</dt><dd>
750 <table class="exception">
751 <tr><td class="paramname">std::exception</td><td>Propagates exceptions if any of the element comparisons, the element swaps (or moves), the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw.</td></tr>
752 </table>
753 </dd>
754</dl>
755<dl class="section warning"><dt>Warning</dt><dd>Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. </dd>
756<dd>
757Invalid arguments cause undefined behaviour. </dd></dl>
758<dl class="section note"><dt>Note</dt><dd><code>spreadsort</code> function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.</dd></dl>
759<dl class="section remark"><dt>Remarks</dt><dd>The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: </dd>
760<dd>
761* N is <code>last</code> - <code>first</code>, </dd>
762<dd>
763* K is the log of the range in bits (32 for 32-bit integers using their full range), </dd>
764<dd>
765* S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). </dd></dl>
766
767</div>
768</div>
769<a class="anchor" id="afd4938835fd03aab9c42bd0653e5dbe5"></a>
770<div class="memitem">
771<div class="memproto">
772<div class="memtemplate">
773template&lt;class RandomAccessIter , class Compare &gt; </div>
774<table class="mlabels">
775 <tr>
776 <td class="mlabels-left">
777 <table class="memname">
778 <tr>
779 <td class="memname">void boost::sort::reverse_string_sort </td>
780 <td>(</td>
781 <td class="paramtype">RandomAccessIter&#160;</td>
782 <td class="paramname"><em>first</em>, </td>
783 </tr>
784 <tr>
785 <td class="paramkey"></td>
786 <td></td>
787 <td class="paramtype">RandomAccessIter&#160;</td>
788 <td class="paramname"><em>last</em>, </td>
789 </tr>
790 <tr>
791 <td class="paramkey"></td>
792 <td></td>
793 <td class="paramtype">Compare&#160;</td>
794 <td class="paramname"><em>comp</em>&#160;</td>
795 </tr>
796 <tr>
797 <td></td>
798 <td>)</td>
799 <td></td><td></td>
800 </tr>
801 </table>
802 </td>
803 <td class="mlabels-right">
804<span class="mlabels"><span class="mlabel">inline</span></span> </td>
805 </tr>
806</table>
807</div><div class="memdoc">
808
809<p>String sort algorithm using random access iterators, wraps using default of <code>unsigned</code> char. </p>
810<p>(All variants fall back to <code>std::sort</code> if the data size is too small, &lt; <code>detail::min_sort_size</code>).</p>
811<p><code>integer_sort</code> is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than <code>std::sort</code> for large tests (&gt;=100kB).<br />
812Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, so <code>integer_sort</code> is asymptotically faster than pure comparison-based algorithms. <code>s</code> is <code>max_splits</code>, which defaults to 11, so its worst-case with default settings for 32-bit integers is <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).<br />
813<br />
814Some performance plots of runtime vs. n and log(range) are provided:<br />
815 <a href="../../doc/graph/windows_integer_sort.htm">windows_integer_sort</a> <br />
816 <a href="../../doc/graph/osx_integer_sort.htm">osx_integer_sort</a></p>
817<dl class="tparams"><dt>Template Parameters</dt><dd>
818 <table class="tparams">
819 <tr><td class="paramname">RandomAccessIter</td><td><a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a> </td></tr>
820 <tr><td class="paramname">Comp</td><td>To provide <code>operator&lt;</code> for user-defined comparison.</td></tr>
821 </table>
822 </dd>
823</dl>
824<dl class="params"><dt>Parameters</dt><dd>
825 <table class="params">
826 <tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>Iterator pointer to first element. </td></tr>
827 <tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>Iterator pointing to one beyond the end of data. </td></tr>
828 <tr><td class="paramdir">[in]</td><td class="paramname">comp</td><td>Comparison functor.</td></tr>
829 </table>
830 </dd>
831</dl>
832<dl class="section pre"><dt>Precondition</dt><dd>[<code>first</code>, <code>last</code>) is a valid range. </dd>
833<dd>
834<code>RandomAccessIter</code> <code>value_type</code> is mutable. </dd>
835<dd>
836<code>RandomAccessIter</code> <code>value_type</code> is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> </dd>
837<dd>
838<code>RandomAccessIter</code> <code>value_type</code> supports the <code>operator&gt;&gt;</code>, which returns an integer-type right-shifted a specified number of bits. </dd></dl>
839<dl class="section post"><dt>Postcondition</dt><dd>The elements in the range [<code>first</code>, <code>last</code>) are sorted in ascending order.</dd></dl>
840<dl class="section return"><dt>Returns</dt><dd><code>void</code>.</dd></dl>
841<dl class="exception"><dt>Exceptions</dt><dd>
842 <table class="exception">
843 <tr><td class="paramname">std::exception</td><td>Propagates exceptions if any of the element comparisons, the element swaps (or moves), the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw.</td></tr>
844 </table>
845 </dd>
846</dl>
847<dl class="section warning"><dt>Warning</dt><dd>Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. </dd>
848<dd>
849Invalid arguments cause undefined behaviour. </dd></dl>
850<dl class="section note"><dt>Note</dt><dd><code>spreadsort</code> function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.</dd></dl>
851<dl class="section remark"><dt>Remarks</dt><dd>The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: </dd>
852<dd>
853* N is <code>last</code> - <code>first</code>, </dd>
854<dd>
855* K is the log of the range in bits (32 for 32-bit integers using their full range), </dd>
856<dd>
857* S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). </dd></dl>
858
859</div>
860</div>
861<a class="anchor" id="a7940f1b2a7746c083a12a4e26077096b"></a>
862<div class="memitem">
863<div class="memproto">
864<div class="memtemplate">
865template&lt;class RandomAccessIter , class Get_char , class Get_length , class Compare &gt; </div>
866<table class="mlabels">
867 <tr>
868 <td class="mlabels-left">
869 <table class="memname">
870 <tr>
871 <td class="memname">void boost::sort::reverse_string_sort </td>
872 <td>(</td>
873 <td class="paramtype">RandomAccessIter&#160;</td>
874 <td class="paramname"><em>first</em>, </td>
875 </tr>
876 <tr>
877 <td class="paramkey"></td>
878 <td></td>
879 <td class="paramtype">RandomAccessIter&#160;</td>
880 <td class="paramname"><em>last</em>, </td>
881 </tr>
882 <tr>
883 <td class="paramkey"></td>
884 <td></td>
885 <td class="paramtype">Get_char&#160;</td>
886 <td class="paramname"><em>getchar</em>, </td>
887 </tr>
888 <tr>
889 <td class="paramkey"></td>
890 <td></td>
891 <td class="paramtype">Get_length&#160;</td>
892 <td class="paramname"><em>length</em>, </td>
893 </tr>
894 <tr>
895 <td class="paramkey"></td>
896 <td></td>
897 <td class="paramtype">Compare&#160;</td>
898 <td class="paramname"><em>comp</em>&#160;</td>
899 </tr>
900 <tr>
901 <td></td>
902 <td>)</td>
903 <td></td><td></td>
904 </tr>
905 </table>
906 </td>
907 <td class="mlabels-right">
908<span class="mlabels"><span class="mlabel">inline</span></span> </td>
909 </tr>
910</table>
911</div><div class="memdoc">
912
913<p>Reverse String sort algorithm using random access iterators. </p>
914<p>(All variants fall back to <code>std::sort</code> if the data size is too small, &lt; <code>detail::min_sort_size</code>).</p>
915<p><code>integer_sort</code> is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than <code>std::sort</code> for large tests (&gt;=100kB).<br />
916Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, so <code>integer_sort</code> is asymptotically faster than pure comparison-based algorithms. <code>s</code> is <code>max_splits</code>, which defaults to 11, so its worst-case with default settings for 32-bit integers is <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).<br />
917<br />
918Some performance plots of runtime vs. n and log(range) are provided:<br />
919 <a href="../../doc/graph/windows_integer_sort.htm">windows_integer_sort</a> <br />
920 <a href="../../doc/graph/osx_integer_sort.htm">osx_integer_sort</a></p>
921<dl class="tparams"><dt>Template Parameters</dt><dd>
922 <table class="tparams">
923 <tr><td class="paramname">RandomAccessIter</td><td><a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a> </td></tr>
924 <tr><td class="paramname">Get_char</td><td>???. </td></tr>
925 <tr><td class="paramname">Get_length</td><td>??? TODO </td></tr>
926 <tr><td class="paramname">Comp</td><td>To provide <code>operator&lt;</code> for user-defined comparison.</td></tr>
927 </table>
928 </dd>
929</dl>
930<dl class="params"><dt>Parameters</dt><dd>
931 <table class="params">
932 <tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>Iterator pointer to first element. </td></tr>
933 <tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>Iterator pointing to one beyond the end of data. </td></tr>
934 <tr><td class="paramdir">[in]</td><td class="paramname">comp</td><td>comparison functor. </td></tr>
935 <tr><td class="paramdir">[in]</td><td class="paramname">getchar</td><td>??? </td></tr>
936 <tr><td class="paramdir">[in]</td><td class="paramname">length</td><td>???</td></tr>
937 </table>
938 </dd>
939</dl>
940<dl class="section pre"><dt>Precondition</dt><dd>[<code>first</code>, <code>last</code>) is a valid range. </dd>
941<dd>
942<code>RandomAccessIter</code> <code>value_type</code> is mutable. </dd>
943<dd>
944<code>RandomAccessIter</code> <code>value_type</code> is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> </dd></dl>
945<dl class="section post"><dt>Postcondition</dt><dd>The elements in the range [<code>first</code>, <code>last</code>) are sorted in ascending order.</dd></dl>
946<dl class="section return"><dt>Returns</dt><dd><code>void</code>.</dd></dl>
947<dl class="exception"><dt>Exceptions</dt><dd>
948 <table class="exception">
949 <tr><td class="paramname">std::exception</td><td>Propagates exceptions if any of the element comparisons, the element swaps (or moves), the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw.</td></tr>
950 </table>
951 </dd>
952</dl>
953<dl class="section warning"><dt>Warning</dt><dd>Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. </dd>
954<dd>
955Invalid arguments cause undefined behaviour. </dd></dl>
956<dl class="section note"><dt>Note</dt><dd><code>spreadsort</code> function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.</dd></dl>
957<dl class="section remark"><dt>Remarks</dt><dd>The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: </dd>
958<dd>
959* N is <code>last</code> - <code>first</code>, </dd>
960<dd>
961* K is the log of the range in bits (32 for 32-bit integers using their full range), </dd>
962<dd>
963* S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). </dd></dl>
964
965</div>
966</div>
967<a class="anchor" id="a4bc25fdacd4c948f631f08a3f9aa38eb"></a>
968<div class="memitem">
969<div class="memproto">
970<div class="memtemplate">
971template&lt;class RandomAccessIter &gt; </div>
972<table class="mlabels">
973 <tr>
974 <td class="mlabels-left">
975 <table class="memname">
976 <tr>
977 <td class="memname">boost::enable_if_c&lt; std::numeric_limits&lt; typename std::iterator_traits&lt;RandomAccessIter&gt;::value_type &gt;::is_integer, void &gt;::type boost::sort::spreadsort </td>
978 <td>(</td>
979 <td class="paramtype">RandomAccessIter&#160;</td>
980 <td class="paramname"><em>first</em>, </td>
981 </tr>
982 <tr>
983 <td class="paramkey"></td>
984 <td></td>
985 <td class="paramtype">RandomAccessIter&#160;</td>
986 <td class="paramname"><em>last</em>&#160;</td>
987 </tr>
988 <tr>
989 <td></td>
990 <td>)</td>
991 <td></td><td></td>
992 </tr>
993 </table>
994 </td>
995 <td class="mlabels-right">
996<span class="mlabels"><span class="mlabel">inline</span></span> </td>
997 </tr>
998</table>
999</div><div class="memdoc">
1000
1001<p>Generic <code>spreadsort</code> variant detecting integer-type elements so call to <code>integer_sort</code>. </p>
1002<p>If the data type provided is an integer, <code>integer_sort</code> is used. </p><dl class="section note"><dt>Note</dt><dd>Sorting other data types requires picking between <code>integer_sort</code>, <code>float_sort</code> and <code>string_sort</code> directly, as <code>spreadsort</code> won't accept types that don't have the appropriate <code>type_traits</code>. </dd></dl>
1003<dl class="tparams"><dt>Template Parameters</dt><dd>
1004 <table class="tparams">
1005 <tr><td class="paramname">RandomAccessIter</td><td><a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a> </td></tr>
1006 </table>
1007 </dd>
1008</dl>
1009<dl class="params"><dt>Parameters</dt><dd>
1010 <table class="params">
1011 <tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>Iterator pointer to first element. </td></tr>
1012 <tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>Iterator pointing to one beyond the end of data.</td></tr>
1013 </table>
1014 </dd>
1015</dl>
1016<dl class="section pre"><dt>Precondition</dt><dd>[<code>first</code>, <code>last</code>) is a valid range. </dd>
1017<dd>
1018<code>RandomAccessIter</code> <code>value_type</code> is mutable. </dd>
1019<dd>
1020<code>RandomAccessIter</code> <code>value_type</code> is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> </dd>
1021<dd>
1022<code>RandomAccessIter</code> <code>value_type</code> supports the <code>operator&gt;&gt;</code>, which returns an integer-type right-shifted a specified number of bits. </dd></dl>
1023<dl class="section post"><dt>Postcondition</dt><dd>The elements in the range [<code>first</code>, <code>last</code>) are sorted in ascending order. </dd></dl>
1024
1025</div>
1026</div>
1027<a class="anchor" id="a94a736da091bd5d3b525818399f1b272"></a>
1028<div class="memitem">
1029<div class="memproto">
1030<div class="memtemplate">
1031template&lt;class RandomAccessIter &gt; </div>
1032<table class="mlabels">
1033 <tr>
1034 <td class="mlabels-left">
1035 <table class="memname">
1036 <tr>
1037 <td class="memname">boost::enable_if_c&lt; !std::numeric_limits&lt; typename std::iterator_traits&lt;RandomAccessIter&gt;::value_type &gt;::is_integer &amp;&amp; std::numeric_limits&lt; typename std::iterator_traits&lt;RandomAccessIter&gt;::value_type &gt;::is_iec559, void &gt;::type boost::sort::spreadsort </td>
1038 <td>(</td>
1039 <td class="paramtype">RandomAccessIter&#160;</td>
1040 <td class="paramname"><em>first</em>, </td>
1041 </tr>
1042 <tr>
1043 <td class="paramkey"></td>
1044 <td></td>
1045 <td class="paramtype">RandomAccessIter&#160;</td>
1046 <td class="paramname"><em>last</em>&#160;</td>
1047 </tr>
1048 <tr>
1049 <td></td>
1050 <td>)</td>
1051 <td></td><td></td>
1052 </tr>
1053 </table>
1054 </td>
1055 <td class="mlabels-right">
1056<span class="mlabels"><span class="mlabel">inline</span></span> </td>
1057 </tr>
1058</table>
1059</div><div class="memdoc">
1060
1061<p>Generic <code>spreadsort</code> variant detecting float element type so call to <code>float_sort</code>. </p>
1062<p>If the data type provided is a float or castable-float, <code>float_sort</code> is used. </p><dl class="section note"><dt>Note</dt><dd>Sorting other data types requires picking between <code>integer_sort</code>, <code>float_sort</code> and <code>string_sort</code> directly, as <code>spreadsort</code> won't accept types that don't have the appropriate <code>type_traits</code>.</dd></dl>
1063<dl class="tparams"><dt>Template Parameters</dt><dd>
1064 <table class="tparams">
1065 <tr><td class="paramname">RandomAccessIter</td><td><a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a> </td></tr>
1066 </table>
1067 </dd>
1068</dl>
1069<dl class="params"><dt>Parameters</dt><dd>
1070 <table class="params">
1071 <tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>Iterator pointer to first element. </td></tr>
1072 <tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>Iterator pointing to one beyond the end of data.</td></tr>
1073 </table>
1074 </dd>
1075</dl>
1076<dl class="section pre"><dt>Precondition</dt><dd>[<code>first</code>, <code>last</code>) is a valid range. </dd>
1077<dd>
1078<code>RandomAccessIter</code> <code>value_type</code> is mutable. </dd>
1079<dd>
1080<code>RandomAccessIter</code> <code>value_type</code> is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> </dd>
1081<dd>
1082<code>RandomAccessIter</code> <code>value_type</code> supports the <code>operator&gt;&gt;</code>, which returns an integer-type right-shifted a specified number of bits. </dd></dl>
1083<dl class="section post"><dt>Postcondition</dt><dd>The elements in the range [<code>first</code>, <code>last</code>) are sorted in ascending order. </dd></dl>
1084
1085</div>
1086</div>
1087<a class="anchor" id="aafdea66d9b4a7faef5604b3079b525fa"></a>
1088<div class="memitem">
1089<div class="memproto">
1090<div class="memtemplate">
1091template&lt;class RandomAccessIter &gt; </div>
1092<table class="mlabels">
1093 <tr>
1094 <td class="mlabels-left">
1095 <table class="memname">
1096 <tr>
1097 <td class="memname">boost::enable_if_c&lt; is_same&lt;typename std::iterator_traits&lt;RandomAccessIter&gt;::value_type, typename std::string&gt;::value || is_same&lt;typename std::iterator_traits&lt;RandomAccessIter&gt;::value_type, typename std::wstring&gt;::value, void &gt;::type boost::sort::spreadsort </td>
1098 <td>(</td>
1099 <td class="paramtype">RandomAccessIter&#160;</td>
1100 <td class="paramname"><em>first</em>, </td>
1101 </tr>
1102 <tr>
1103 <td class="paramkey"></td>
1104 <td></td>
1105 <td class="paramtype">RandomAccessIter&#160;</td>
1106 <td class="paramname"><em>last</em>&#160;</td>
1107 </tr>
1108 <tr>
1109 <td></td>
1110 <td>)</td>
1111 <td></td><td></td>
1112 </tr>
1113 </table>
1114 </td>
1115 <td class="mlabels-right">
1116<span class="mlabels"><span class="mlabel">inline</span></span> </td>
1117 </tr>
1118</table>
1119</div><div class="memdoc">
1120
1121<p>Generic <code>spreadsort</code> variant detecting string element type so call to <code>string_sort</code> for <code>std::strings</code> and <code>std::wstrings</code>. </p>
1122<p>If the data type provided is a string or wstring, <code>string_sort</code> is used. </p><dl class="section note"><dt>Note</dt><dd>Sorting other data types requires picking between <code>integer_sort</code>, <code>float_sort</code> and <code>string_sort</code> directly, as <code>spreadsort</code> won't accept types that don't have the appropriate <code>type_traits</code>.</dd></dl>
1123<dl class="tparams"><dt>Template Parameters</dt><dd>
1124 <table class="tparams">
1125 <tr><td class="paramname">RandomAccessIter</td><td><a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a> </td></tr>
1126 </table>
1127 </dd>
1128</dl>
1129<dl class="params"><dt>Parameters</dt><dd>
1130 <table class="params">
1131 <tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>Iterator pointer to first element. </td></tr>
1132 <tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>Iterator pointing to one beyond the end of data.</td></tr>
1133 </table>
1134 </dd>
1135</dl>
1136<dl class="section pre"><dt>Precondition</dt><dd>[<code>first</code>, <code>last</code>) is a valid range. </dd>
1137<dd>
1138<code>RandomAccessIter</code> <code>value_type</code> is mutable. </dd>
1139<dd>
1140<code>RandomAccessIter</code> <code>value_type</code> is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> </dd>
1141<dd>
1142<code>RandomAccessIter</code> <code>value_type</code> supports the <code>operator&gt;&gt;</code>, which returns an integer-type right-shifted a specified number of bits. </dd></dl>
1143<dl class="section post"><dt>Postcondition</dt><dd>The elements in the range [<code>first</code>, <code>last</code>) are sorted in ascending order. </dd></dl>
1144
1145</div>
1146</div>
1147<a class="anchor" id="a950a2dbbe75f048a0b343dbf7c532dc0"></a>
1148<div class="memitem">
1149<div class="memproto">
1150<div class="memtemplate">
1151template&lt;class RandomAccessIter , class Unsigned_char_type &gt; </div>
1152<table class="mlabels">
1153 <tr>
1154 <td class="mlabels-left">
1155 <table class="memname">
1156 <tr>
1157 <td class="memname">void boost::sort::string_sort </td>
1158 <td>(</td>
1159 <td class="paramtype">RandomAccessIter&#160;</td>
1160 <td class="paramname"><em>first</em>, </td>
1161 </tr>
1162 <tr>
1163 <td class="paramkey"></td>
1164 <td></td>
1165 <td class="paramtype">RandomAccessIter&#160;</td>
1166 <td class="paramname"><em>last</em>, </td>
1167 </tr>
1168 <tr>
1169 <td class="paramkey"></td>
1170 <td></td>
1171 <td class="paramtype">Unsigned_char_type&#160;</td>
1172 <td class="paramname"><em>unused</em>&#160;</td>
1173 </tr>
1174 <tr>
1175 <td></td>
1176 <td>)</td>
1177 <td></td><td></td>
1178 </tr>
1179 </table>
1180 </td>
1181 <td class="mlabels-right">
1182<span class="mlabels"><span class="mlabel">inline</span></span> </td>
1183 </tr>
1184</table>
1185</div><div class="memdoc">
1186
1187<p>String sort algorithm using random access iterators, allowing character-type overloads.<br />
1188 (All variants fall back to <code>std::sort</code> if the data size is too small, &lt; <code>detail::min_sort_size</code>). </p>
1189<p><code>string_sort</code> is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than <code>std::sort</code> for large tests (&gt;=100kB).<br />
1190</p><dl class="section user"><dt></dt><dd>Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, so <code>integer_sort</code> is asymptotically faster than pure comparison-based algorithms. <code>s</code> is <code>max_splits</code>, which defaults to 11, so its worst-case with default settings for 32-bit integers is <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).<br />
1191<br />
1192Some performance plots of runtime vs. n and log(range) are provided:<br />
1193<a href="../../doc/graph/windows_string_sort.htm">windows_string_sort</a><br />
1194<a href="../../doc/graph/osx_string_sort.htm">osx_string_sort</a></dd></dl>
1195<dl class="tparams"><dt>Template Parameters</dt><dd>
1196 <table class="tparams">
1197 <tr><td class="paramname">RandomAccessIter</td><td><a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a> </td></tr>
1198 <tr><td class="paramname">Unsigned_char_type</td><td>Unsigned character type used for string. </td></tr>
1199 </table>
1200 </dd>
1201</dl>
1202<dl class="params"><dt>Parameters</dt><dd>
1203 <table class="params">
1204 <tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>Iterator pointer to first element. </td></tr>
1205 <tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>Iterator pointing to one beyond the end of data. </td></tr>
1206 <tr><td class="paramdir">[in]</td><td class="paramname">unused</td><td>Unused ???</td></tr>
1207 </table>
1208 </dd>
1209</dl>
1210<dl class="section pre"><dt>Precondition</dt><dd>[<code>first</code>, <code>last</code>) is a valid range. </dd>
1211<dd>
1212<code>RandomAccessIter</code> <code>value_type</code> is mutable. </dd>
1213<dd>
1214<code>RandomAccessIter</code> <code>value_type</code> is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> </dd>
1215<dd>
1216<code>RandomAccessIter</code> <code>value_type</code> supports the <code>operator&gt;&gt;</code>, which returns an integer-type right-shifted a specified number of bits. </dd></dl>
1217<dl class="section post"><dt>Postcondition</dt><dd>The elements in the range [<code>first</code>, <code>last</code>) are sorted in ascending order.</dd></dl>
1218<dl class="exception"><dt>Exceptions</dt><dd>
1219 <table class="exception">
1220 <tr><td class="paramname">std::exception</td><td>Propagates exceptions if any of the element comparisons, the element swaps (or moves), the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw.</td></tr>
1221 </table>
1222 </dd>
1223</dl>
1224<dl class="section warning"><dt>Warning</dt><dd>Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. </dd>
1225<dd>
1226Invalid arguments cause undefined behaviour. </dd></dl>
1227<dl class="section note"><dt>Note</dt><dd><code>spreadsort</code> function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.</dd></dl>
1228<dl class="section remark"><dt>Remarks</dt><dd>The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: </dd>
1229<dd>
1230* N is <code>last</code> - <code>first</code>, </dd>
1231<dd>
1232* K is the log of the range in bits (32 for 32-bit integers using their full range), </dd>
1233<dd>
1234* S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). </dd></dl>
1235
1236</div>
1237</div>
1238<a class="anchor" id="a6acd5fc94521b0a5cb47dc491b6d862f"></a>
1239<div class="memitem">
1240<div class="memproto">
1241<div class="memtemplate">
1242template&lt;class RandomAccessIter &gt; </div>
1243<table class="mlabels">
1244 <tr>
1245 <td class="mlabels-left">
1246 <table class="memname">
1247 <tr>
1248 <td class="memname">void boost::sort::string_sort </td>
1249 <td>(</td>
1250 <td class="paramtype">RandomAccessIter&#160;</td>
1251 <td class="paramname"><em>first</em>, </td>
1252 </tr>
1253 <tr>
1254 <td class="paramkey"></td>
1255 <td></td>
1256 <td class="paramtype">RandomAccessIter&#160;</td>
1257 <td class="paramname"><em>last</em>&#160;</td>
1258 </tr>
1259 <tr>
1260 <td></td>
1261 <td>)</td>
1262 <td></td><td></td>
1263 </tr>
1264 </table>
1265 </td>
1266 <td class="mlabels-right">
1267<span class="mlabels"><span class="mlabel">inline</span></span> </td>
1268 </tr>
1269</table>
1270</div><div class="memdoc">
1271
1272<p>String sort algorithm using random access iterators, wraps using default of unsigned char. (All variants fall back to <code>std::sort</code> if the data size is too small, &lt; <code>detail::min_sort_size</code>). </p>
1273<p><code>string_sort</code> is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than <code>std::sort</code> for large tests (&gt;=100kB).<br />
1274Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, so <code>integer_sort</code> is asymptotically faster than pure comparison-based algorithms. <code>s</code> is <code>max_splits</code>, which defaults to 11, so its worst-case with default settings for 32-bit integers is <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).<br />
1275<br />
1276Some performance plots of runtime vs. n and log(range) are provided:<br />
1277 <a href="../../doc/graph/windows_string_sort.htm">windows_string_sort</a> <br />
1278 <a href="../../doc/graph/osx_string_sort.htm">osx_string_sort</a></p>
1279<dl class="tparams"><dt>Template Parameters</dt><dd>
1280 <table class="tparams">
1281 <tr><td class="paramname">RandomAccessIter</td><td><a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a> </td></tr>
1282 </table>
1283 </dd>
1284</dl>
1285<dl class="params"><dt>Parameters</dt><dd>
1286 <table class="params">
1287 <tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>Iterator pointer to first element. </td></tr>
1288 <tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>Iterator pointing to one beyond the end of data.</td></tr>
1289 </table>
1290 </dd>
1291</dl>
1292<dl class="section pre"><dt>Precondition</dt><dd>[<code>first</code>, <code>last</code>) is a valid range. </dd>
1293<dd>
1294<code>RandomAccessIter</code> <code>value_type</code> is mutable. </dd>
1295<dd>
1296<code>RandomAccessIter</code> <code>value_type</code> is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> </dd>
1297<dd>
1298<code>RandomAccessIter</code> <code>value_type</code> supports the <code>operator&gt;&gt;</code>, which returns an integer-type right-shifted a specified number of bits. </dd></dl>
1299<dl class="section post"><dt>Postcondition</dt><dd>The elements in the range [<code>first</code>, <code>last</code>) are sorted in ascending order.</dd></dl>
1300<dl class="exception"><dt>Exceptions</dt><dd>
1301 <table class="exception">
1302 <tr><td class="paramname">std::exception</td><td>Propagates exceptions if any of the element comparisons, the element swaps (or moves), the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw.</td></tr>
1303 </table>
1304 </dd>
1305</dl>
1306<dl class="section warning"><dt>Warning</dt><dd>Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. </dd>
1307<dd>
1308Invalid arguments cause undefined behaviour. </dd></dl>
1309<dl class="section note"><dt>Note</dt><dd><code>spreadsort</code> function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.</dd></dl>
1310<dl class="section remark"><dt>Remarks</dt><dd>The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: </dd>
1311<dd>
1312* N is <code>last</code> - <code>first</code>, </dd>
1313<dd>
1314* K is the log of the range in bits (32 for 32-bit integers using their full range), </dd>
1315<dd>
1316* S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). </dd></dl>
1317
1318</div>
1319</div>
1320<a class="anchor" id="a5143ec4f58cfe13eca2a0d6b6f6a6680"></a>
1321<div class="memitem">
1322<div class="memproto">
1323<div class="memtemplate">
1324template&lt;class RandomAccessIter , class Get_char , class Get_length &gt; </div>
1325<table class="mlabels">
1326 <tr>
1327 <td class="mlabels-left">
1328 <table class="memname">
1329 <tr>
1330 <td class="memname">void boost::sort::string_sort </td>
1331 <td>(</td>
1332 <td class="paramtype">RandomAccessIter&#160;</td>
1333 <td class="paramname"><em>first</em>, </td>
1334 </tr>
1335 <tr>
1336 <td class="paramkey"></td>
1337 <td></td>
1338 <td class="paramtype">RandomAccessIter&#160;</td>
1339 <td class="paramname"><em>last</em>, </td>
1340 </tr>
1341 <tr>
1342 <td class="paramkey"></td>
1343 <td></td>
1344 <td class="paramtype">Get_char&#160;</td>
1345 <td class="paramname"><em>getchar</em>, </td>
1346 </tr>
1347 <tr>
1348 <td class="paramkey"></td>
1349 <td></td>
1350 <td class="paramtype">Get_length&#160;</td>
1351 <td class="paramname"><em>length</em>&#160;</td>
1352 </tr>
1353 <tr>
1354 <td></td>
1355 <td>)</td>
1356 <td></td><td></td>
1357 </tr>
1358 </table>
1359 </td>
1360 <td class="mlabels-right">
1361<span class="mlabels"><span class="mlabel">inline</span></span> </td>
1362 </tr>
1363</table>
1364</div><div class="memdoc">
1365
1366<p>String sort algorithm using random access iterators, wraps using default of <code>unsigned</code> char. </p>
1367<p>(All variants fall back to <code>std::sort</code> if the data size is too small, &lt; <code>detail::min_sort_size</code>).</p>
1368<p><code>integer_sort</code> is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than <code>std::sort</code> for large tests (&gt;=100kB).<br />
1369Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, so <code>integer_sort</code> is asymptotically faster than pure comparison-based algorithms. <code>s</code> is <code>max_splits</code>, which defaults to 11, so its worst-case with default settings for 32-bit integers is <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).<br />
1370<br />
1371Some performance plots of runtime vs. n and log(range) are provided:<br />
1372 <a href="../../doc/graph/windows_integer_sort.htm">windows_integer_sort</a> <br />
1373 <a href="../../doc/graph/osx_integer_sort.htm">osx_integer_sort</a></p>
1374<dl class="tparams"><dt>Template Parameters</dt><dd>
1375 <table class="tparams">
1376 <tr><td class="paramname">RandomAccessIter</td><td><a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a> </td></tr>
1377 <tr><td class="paramname">Get_char</td><td>Bracket functor equivalent to <code>operator</code>[], taking a number corresponding to the character offset.. </td></tr>
1378 <tr><td class="paramname">Get_length</td><td>Functor to get the length of the string in characters. TODO Check this and below and other places!!!</td></tr>
1379 </table>
1380 </dd>
1381</dl>
1382<dl class="params"><dt>Parameters</dt><dd>
1383 <table class="params">
1384 <tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>Iterator pointer to first element. </td></tr>
1385 <tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>Iterator pointing to one beyond the end of data. </td></tr>
1386 <tr><td class="paramdir">[in]</td><td class="paramname">getchar</td><td>Number corresponding to the character offset from bracket functor equivalent to <code>operator</code>[]. </td></tr>
1387 <tr><td class="paramdir">[in]</td><td class="paramname">length</td><td>Functor to get the length of the string in characters.</td></tr>
1388 </table>
1389 </dd>
1390</dl>
1391<dl class="section pre"><dt>Precondition</dt><dd>[<code>first</code>, <code>last</code>) is a valid range. </dd>
1392<dd>
1393<code>RandomAccessIter</code> <code>value_type</code> is mutable. </dd>
1394<dd>
1395<code>RandomAccessIter</code> <code>value_type</code> is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> </dd>
1396<dd>
1397<code>RandomAccessIter</code> <code>value_type</code> supports the <code>operator&gt;&gt;</code>, which returns an integer-type right-shifted a specified number of bits. </dd></dl>
1398<dl class="section post"><dt>Postcondition</dt><dd>The elements in the range [<code>first</code>, <code>last</code>) are sorted in ascending order.</dd></dl>
1399<dl class="section return"><dt>Returns</dt><dd><code>void</code>.</dd></dl>
1400<dl class="exception"><dt>Exceptions</dt><dd>
1401 <table class="exception">
1402 <tr><td class="paramname">std::exception</td><td>Propagates exceptions if any of the element comparisons, the element swaps (or moves), the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw.</td></tr>
1403 </table>
1404 </dd>
1405</dl>
1406<dl class="section warning"><dt>Warning</dt><dd>Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. </dd>
1407<dd>
1408Invalid arguments cause undefined behaviour. </dd></dl>
1409<dl class="section note"><dt>Note</dt><dd><code>spreadsort</code> function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.</dd></dl>
1410<dl class="section remark"><dt>Remarks</dt><dd>The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: </dd>
1411<dd>
1412* N is <code>last</code> - <code>first</code>, </dd>
1413<dd>
1414* K is the log of the range in bits (32 for 32-bit integers using their full range), </dd>
1415<dd>
1416* S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). </dd></dl>
1417
1418</div>
1419</div>
1420<a class="anchor" id="a82c4c0d7ba9873ecce7c674631dceae2"></a>
1421<div class="memitem">
1422<div class="memproto">
1423<div class="memtemplate">
1424template&lt;class RandomAccessIter , class Get_char , class Get_length , class Compare &gt; </div>
1425<table class="mlabels">
1426 <tr>
1427 <td class="mlabels-left">
1428 <table class="memname">
1429 <tr>
1430 <td class="memname">void boost::sort::string_sort </td>
1431 <td>(</td>
1432 <td class="paramtype">RandomAccessIter&#160;</td>
1433 <td class="paramname"><em>first</em>, </td>
1434 </tr>
1435 <tr>
1436 <td class="paramkey"></td>
1437 <td></td>
1438 <td class="paramtype">RandomAccessIter&#160;</td>
1439 <td class="paramname"><em>last</em>, </td>
1440 </tr>
1441 <tr>
1442 <td class="paramkey"></td>
1443 <td></td>
1444 <td class="paramtype">Get_char&#160;</td>
1445 <td class="paramname"><em>getchar</em>, </td>
1446 </tr>
1447 <tr>
1448 <td class="paramkey"></td>
1449 <td></td>
1450 <td class="paramtype">Get_length&#160;</td>
1451 <td class="paramname"><em>length</em>, </td>
1452 </tr>
1453 <tr>
1454 <td class="paramkey"></td>
1455 <td></td>
1456 <td class="paramtype">Compare&#160;</td>
1457 <td class="paramname"><em>comp</em>&#160;</td>
1458 </tr>
1459 <tr>
1460 <td></td>
1461 <td>)</td>
1462 <td></td><td></td>
1463 </tr>
1464 </table>
1465 </td>
1466 <td class="mlabels-right">
1467<span class="mlabels"><span class="mlabel">inline</span></span> </td>
1468 </tr>
1469</table>
1470</div><div class="memdoc">
1471
1472<p>String sort algorithm using random access iterators, wraps using default of <code>unsigned</code> char. </p>
1473<p>(All variants fall back to <code>std::sort</code> if the data size is too small, &lt; <code>detail::min_sort_size</code>).</p>
1474<p><code>integer_sort</code> is a fast templated in-place hybrid radix/comparison algorithm, which in testing tends to be roughly 50% to 2X faster than <code>std::sort</code> for large tests (&gt;=100kB).<br />
1475Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, so <code>integer_sort</code> is asymptotically faster than pure comparison-based algorithms. <code>s</code> is <code>max_splits</code>, which defaults to 11, so its worst-case with default settings for 32-bit integers is <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).<br />
1476<br />
1477Some performance plots of runtime vs. n and log(range) are provided:<br />
1478 <a href="../../doc/graph/windows_integer_sort.htm">windows_integer_sort</a> <br />
1479 <a href="../../doc/graph/osx_integer_sort.htm">osx_integer_sort</a></p>
1480<dl class="tparams"><dt>Template Parameters</dt><dd>
1481 <table class="tparams">
1482 <tr><td class="paramname">RandomAccessIter</td><td><a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a> </td></tr>
1483 <tr><td class="paramname">Get_char</td><td>???. </td></tr>
1484 <tr><td class="paramname">Get_length</td><td>??? TODO </td></tr>
1485 <tr><td class="paramname">Comp</td><td>To provide <code>operator&lt;</code> for user-defined comparison.</td></tr>
1486 </table>
1487 </dd>
1488</dl>
1489<dl class="params"><dt>Parameters</dt><dd>
1490 <table class="params">
1491 <tr><td class="paramdir">[in]</td><td class="paramname">first</td><td>Iterator pointer to first element. </td></tr>
1492 <tr><td class="paramdir">[in]</td><td class="paramname">last</td><td>Iterator pointing to one beyond the end of data. </td></tr>
1493 <tr><td class="paramdir">[in]</td><td class="paramname">comp</td><td>comparison functor. </td></tr>
1494 <tr><td class="paramdir">[in]</td><td class="paramname">getchar</td><td>??? </td></tr>
1495 <tr><td class="paramdir">[in]</td><td class="paramname">length</td><td>???</td></tr>
1496 </table>
1497 </dd>
1498</dl>
1499<dl class="section pre"><dt>Precondition</dt><dd>[<code>first</code>, <code>last</code>) is a valid range. </dd>
1500<dd>
1501<code>RandomAccessIter</code> <code>value_type</code> is mutable. </dd>
1502<dd>
1503<code>RandomAccessIter</code> <code>value_type</code> is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> </dd></dl>
1504<dl class="section post"><dt>Postcondition</dt><dd>The elements in the range [<code>first</code>, <code>last</code>) are sorted in ascending order.</dd></dl>
1505<dl class="section return"><dt>Returns</dt><dd><code>void</code>.</dd></dl>
1506<dl class="exception"><dt>Exceptions</dt><dd>
1507 <table class="exception">
1508 <tr><td class="paramname">std::exception</td><td>Propagates exceptions if any of the element comparisons, the element swaps (or moves), the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw.</td></tr>
1509 </table>
1510 </dd>
1511</dl>
1512<dl class="section warning"><dt>Warning</dt><dd>Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. </dd>
1513<dd>
1514Invalid arguments cause undefined behaviour. </dd></dl>
1515<dl class="section note"><dt>Note</dt><dd><code>spreadsort</code> function provides a wrapper that calls the fastest sorting algorithm available for a data type, enabling faster generic-programming.</dd></dl>
1516<dl class="section remark"><dt>Remarks</dt><dd>The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: </dd>
1517<dd>
1518* N is <code>last</code> - <code>first</code>, </dd>
1519<dd>
1520* K is the log of the range in bits (32 for 32-bit integers using their full range), </dd>
1521<dd>
1522* S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). </dd></dl>
1523
1524</div>
1525</div>
1526</div><!-- contents -->
1527<!-- start footer part -->
1528<hr class="footer"/><address class="footer"><small>
1529Generated on Fri Jan 9 2015 14:20:24 for Boost.Sort by &#160;<a href="http://www.doxygen.org/index.html">
1530<img class="footer" src="doxygen.png" alt="doxygen"/>
1531</a> 1.8.9.1
1532</small></address>
1533</body>
1534</html>
Ceph