--001a11c31f70b16a380502d7ceaa
Content-Type: text/plain; charset=UTF-8

stable_sort and stable_partition allocate additional memory, if available,
to reduce algorithmic complexity. You can use these specifications as a
template for your own.

On Thu, Sep 11, 2014 at 5:49 PM, <germinolegrand@gmail.com> wrote:

> Hello everyone,
> I am currently writting new algorithms that I'd like to propose into the
> STL in a near future.
>
> But, I've just encountered a problem : the last algorithm I wrote relies
> on allocating/deallocating memory for internal computation.
>
> The maximum size of memory allocation needed is perfectly deductible from
> the arguments. But this is of course dependant of the choice of
> implementation.
>
> Currently I use a basic std::vector.
>
> What should I use ? Take a buffer as an argument ? Have an Allocator
> template argument ? Leave it as it is ?
>
> I found no examples in current STL algorithms, nor in library design
> guidelines <https://isocpp.org/std/library-design-guidelines>.
>
>
> template<class iterator_S, class iterator_T>
> int levenshtein_distance(iterator_S it_S_begin, iterator_S it_S_end,
> iterator_T it_T_begin, iterator_T it_T_end)
> {
>     #if __cplusplus >= 201402L
>     auto pair_it = std::mismatch(it_S_begin, it_S_end, it_T_begin,
> it_T_end);
>
>     it_S_begin = pair_it.first;
>     it_T_begin = pair_it.second;
>     #else
>     if(std::distance(it_S_begin, it_S_end) <= std::distance(it_T_begin,
> it_T_end))
>     {
>         auto pair_it = std::mismatch(it_S_begin, it_S_end, it_T_begin);
>
>         it_S_begin = pair_it.first;
>         it_T_begin = pair_it.second;
>     }
>     else
>     {
>         auto pair_it = std::mismatch(it_T_begin, it_T_end, it_S_begin);
>
>         it_T_begin = pair_it.first;
>         it_S_begin = pair_it.second;
>     }
>     #endif // __cplusplus
>
>     size_t size_S = std::distance(it_S_begin, it_S_end);
>     size_t size_T = std::distance(it_T_begin, it_T_end);
>
>     if(size_S == 0)
>         return size_T;
>     if(size_T == 0)
>         return size_S;
>
>     std::vector<int> costs(size_T + 1);
>
>     for(size_t i = 0; i < costs.size(); ++i)
>         costs[i] = i;
>
>     for(size_t i = 0; i < size_S; ++i)
>     {
>         costs[0] = i + 1;
>         int corner = i;
>
>         for(size_t j = 0; j < size_T; ++j)
>         {
>             int upper = costs[j + 1];
>
>             if(*std::next(it_S_begin, i) == *std::next(it_T_begin, j))
>                 costs[j + 1] = corner;
>             else
>                 costs[j + 1] = std::min(costs[j], std::min(upper, corner))
> + 1;
>
>             corner = upper;
>         }
>     }
>
>     return costs.back();
> }
>
>
>  --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> Visit this group at
> http://groups.google.com/a/isocpp.org/group/std-proposals/.
>

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

--001a11c31f70b16a380502d7ceaa
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">stable_sort and stable_partition allocate additional memor=
y, if available, to reduce algorithmic complexity. You can use these specif=
ications as a template for your own.</div><div class=3D"gmail_extra"><br><d=
iv class=3D"gmail_quote">On Thu, Sep 11, 2014 at 5:49 PM,  <span dir=3D"ltr=
">&lt;<a href=3D"mailto:germinolegrand@gmail.com" target=3D"_blank">germino=
legrand@gmail.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote=
" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><=
div dir=3D"ltr">Hello everyone,<br>I am currently writting new algorithms t=
hat I&#39;d like to propose into the STL in a near future.<br><br>But, I&#3=
9;ve just encountered a problem : the last algorithm I wrote relies on allo=
cating/deallocating memory for internal computation.<br><br>The maximum siz=
e of memory allocation needed is perfectly deductible from the arguments. B=
ut this is of course dependant of the choice of implementation.<br><br>Curr=
ently I use a basic std::vector.<br><br>What should I use ? Take a buffer a=
s an argument ? Have an Allocator template argument ? Leave it as it is ?<b=
r><br>I found no examples in current STL algorithms, nor in <a href=3D"http=
s://isocpp.org/std/library-design-guidelines" target=3D"_blank">library des=
ign guidelines</a>.<br><br><div style=3D"background-color:rgb(250,250,250);=
border-color:rgb(187,187,187);border-style:solid;border-width:1px;word-wrap=
:break-word"><code><div><span style=3D"color:#000"><br></span><span style=
=3D"color:#008">template</span><span style=3D"color:#660">&lt;</span><span =
style=3D"color:#008">class</span><span style=3D"color:#000"> iterator_S</sp=
an><span style=3D"color:#660">,</span><span style=3D"color:#000"> </span><s=
pan style=3D"color:#008">class</span><span style=3D"color:#000"> iterator_T=
</span><span style=3D"color:#660">&gt;</span><span style=3D"color:#000"><br=
></span><span style=3D"color:#008">int</span><span style=3D"color:#000"> le=
venshtein_distance</span><span style=3D"color:#660">(</span><span style=3D"=
color:#000">iterator_S it_S_begin</span><span style=3D"color:#660">,</span>=
<span style=3D"color:#000"> iterator_S it_S_end</span><span style=3D"color:=
#660">,</span><span style=3D"color:#000"> iterator_T it_T_begin</span><span=
 style=3D"color:#660">,</span><span style=3D"color:#000"> iterator_T it_T_e=
nd</span><span style=3D"color:#660">)</span><span style=3D"color:#000"><br>=
</span><span style=3D"color:#660">{</span><span style=3D"color:#000"><br>=
=C2=A0 =C2=A0 </span><span style=3D"color:#800">#if __cplusplus &gt;=3D 201=
402L</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 </span><span style=
=3D"color:#008">auto</span><span style=3D"color:#000"> pair_it </span><span=
 style=3D"color:#660">=3D</span><span style=3D"color:#000"> std</span><span=
 style=3D"color:#660">::</span><span style=3D"color:#000">mismatch</span><s=
pan style=3D"color:#660">(</span><span style=3D"color:#000">it_S_begin</spa=
n><span style=3D"color:#660">,</span><span style=3D"color:#000"> it_S_end</=
span><span style=3D"color:#660">,</span><span style=3D"color:#000"> it_T_be=
gin</span><span style=3D"color:#660">,</span><span style=3D"color:#000"> it=
_T_end</span><span style=3D"color:#660">);</span><span style=3D"color:#000"=
><br><br>=C2=A0 =C2=A0 it_S_begin </span><span style=3D"color:#660">=3D</sp=
an><span style=3D"color:#000"> pair_it</span><span style=3D"color:#660">.</=
span><span style=3D"color:#000">first</span><span style=3D"color:#660">;</s=
pan><span style=3D"color:#000"><br>=C2=A0 =C2=A0 it_T_begin </span><span st=
yle=3D"color:#660">=3D</span><span style=3D"color:#000"> pair_it</span><spa=
n style=3D"color:#660">.</span><span style=3D"color:#000">second</span><spa=
n style=3D"color:#660">;</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0=
 </span><span style=3D"color:#800">#else</span><span style=3D"color:#000"><=
br>=C2=A0 =C2=A0 </span><span style=3D"color:#008">if</span><span style=3D"=
color:#660">(</span><span style=3D"color:#000">std</span><span style=3D"col=
or:#660">::</span><span style=3D"color:#000">distance</span><span style=3D"=
color:#660">(</span><span style=3D"color:#000">it_S_begin</span><span style=
=3D"color:#660">,</span><span style=3D"color:#000"> it_S_end</span><span st=
yle=3D"color:#660">)</span><span style=3D"color:#000"> </span><span style=
=3D"color:#660">&lt;=3D</span><span style=3D"color:#000"> std</span><span s=
tyle=3D"color:#660">::</span><span style=3D"color:#000">distance</span><spa=
n style=3D"color:#660">(</span><span style=3D"color:#000">it_T_begin</span>=
<span style=3D"color:#660">,</span><span style=3D"color:#000"> it_T_end</sp=
an><span style=3D"color:#660">))</span><span style=3D"color:#000"><br>=C2=
=A0 =C2=A0 </span><span style=3D"color:#660">{</span><span style=3D"color:#=
000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"color:#008">auto=
</span><span style=3D"color:#000"> pair_it </span><span style=3D"color:#660=
">=3D</span><span style=3D"color:#000"> std</span><span style=3D"color:#660=
">::</span><span style=3D"color:#000">mismatch</span><span style=3D"color:#=
660">(</span><span style=3D"color:#000">it_S_begin</span><span style=3D"col=
or:#660">,</span><span style=3D"color:#000"> it_S_end</span><span style=3D"=
color:#660">,</span><span style=3D"color:#000"> it_T_begin</span><span styl=
e=3D"color:#660">);</span><span style=3D"color:#000"><br><br>=C2=A0 =C2=A0 =
=C2=A0 =C2=A0 it_S_begin </span><span style=3D"color:#660">=3D</span><span =
style=3D"color:#000"> pair_it</span><span style=3D"color:#660">.</span><spa=
n style=3D"color:#000">first</span><span style=3D"color:#660">;</span><span=
 style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 it_T_begin </span><sp=
an style=3D"color:#660">=3D</span><span style=3D"color:#000"> pair_it</span=
><span style=3D"color:#660">.</span><span style=3D"color:#000">second</span=
><span style=3D"color:#660">;</span><span style=3D"color:#000"><br>=C2=A0 =
=C2=A0 </span><span style=3D"color:#660">}</span><span style=3D"color:#000"=
><br>=C2=A0 =C2=A0 </span><span style=3D"color:#008">else</span><span style=
=3D"color:#000"><br>=C2=A0 =C2=A0 </span><span style=3D"color:#660">{</span=
><span style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span st=
yle=3D"color:#008">auto</span><span style=3D"color:#000"> pair_it </span><s=
pan style=3D"color:#660">=3D</span><span style=3D"color:#000"> std</span><s=
pan style=3D"color:#660">::</span><span style=3D"color:#000">mismatch</span=
><span style=3D"color:#660">(</span><span style=3D"color:#000">it_T_begin</=
span><span style=3D"color:#660">,</span><span style=3D"color:#000"> it_T_en=
d</span><span style=3D"color:#660">,</span><span style=3D"color:#000"> it_S=
_begin</span><span style=3D"color:#660">);</span><span style=3D"color:#000"=
><br><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 it_T_begin </span><span style=3D"color=
:#660">=3D</span><span style=3D"color:#000"> pair_it</span><span style=3D"c=
olor:#660">.</span><span style=3D"color:#000">first</span><span style=3D"co=
lor:#660">;</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=
=A0 it_S_begin </span><span style=3D"color:#660">=3D</span><span style=3D"c=
olor:#000"> pair_it</span><span style=3D"color:#660">.</span><span style=3D=
"color:#000">second</span><span style=3D"color:#660">;</span><span style=3D=
"color:#000"><br>=C2=A0 =C2=A0 </span><span style=3D"color:#660">}</span><s=
pan style=3D"color:#000"><br>=C2=A0 =C2=A0 </span><span style=3D"color:#800=
">#endif</span><span style=3D"color:#000"> </span><span style=3D"color:#800=
">// __cplusplus</span><span style=3D"color:#000"><br><br>=C2=A0 =C2=A0 siz=
e_t size_S </span><span style=3D"color:#660">=3D</span><span style=3D"color=
:#000"> std</span><span style=3D"color:#660">::</span><span style=3D"color:=
#000">distance</span><span style=3D"color:#660">(</span><span style=3D"colo=
r:#000">it_S_begin</span><span style=3D"color:#660">,</span><span style=3D"=
color:#000"> it_S_end</span><span style=3D"color:#660">);</span><span style=
=3D"color:#000"><br>=C2=A0 =C2=A0 size_t size_T </span><span style=3D"color=
:#660">=3D</span><span style=3D"color:#000"> std</span><span style=3D"color=
:#660">::</span><span style=3D"color:#000">distance</span><span style=3D"co=
lor:#660">(</span><span style=3D"color:#000">it_T_begin</span><span style=
=3D"color:#660">,</span><span style=3D"color:#000"> it_T_end</span><span st=
yle=3D"color:#660">);</span><span style=3D"color:#000"><br><br>=C2=A0 =C2=
=A0 </span><span style=3D"color:#008">if</span><span style=3D"color:#660">(=
</span><span style=3D"color:#000">size_S </span><span style=3D"color:#660">=
=3D=3D</span><span style=3D"color:#000"> </span><span style=3D"color:#066">=
0</span><span style=3D"color:#660">)</span><span style=3D"color:#000"><br>=
=C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"color:#008">return</span>=
<span style=3D"color:#000"> size_T</span><span style=3D"color:#660">;</span=
><span style=3D"color:#000"><br>=C2=A0 =C2=A0 </span><span style=3D"color:#=
008">if</span><span style=3D"color:#660">(</span><span style=3D"color:#000"=
>size_T </span><span style=3D"color:#660">=3D=3D</span><span style=3D"color=
:#000"> </span><span style=3D"color:#066">0</span><span style=3D"color:#660=
">)</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 </span=
><span style=3D"color:#008">return</span><span style=3D"color:#000"> size_S=
</span><span style=3D"color:#660">;</span><span style=3D"color:#000"><br><b=
r>=C2=A0 =C2=A0 std</span><span style=3D"color:#660">::</span><span style=
=3D"color:#000">vector</span><span style=3D"color:#080">&lt;int&gt;</span><=
span style=3D"color:#000"> costs</span><span style=3D"color:#660">(</span><=
span style=3D"color:#000">size_T </span><span style=3D"color:#660">+</span>=
<span style=3D"color:#000"> </span><span style=3D"color:#066">1</span><span=
 style=3D"color:#660">);</span><span style=3D"color:#000"><br><br>=C2=A0 =
=C2=A0 </span><span style=3D"color:#008">for</span><span style=3D"color:#66=
0">(</span><span style=3D"color:#000">size_t i </span><span style=3D"color:=
#660">=3D</span><span style=3D"color:#000"> </span><span style=3D"color:#06=
6">0</span><span style=3D"color:#660">;</span><span style=3D"color:#000"> i=
 </span><span style=3D"color:#660">&lt;</span><span style=3D"color:#000"> c=
osts</span><span style=3D"color:#660">.</span><span style=3D"color:#000">si=
ze</span><span style=3D"color:#660">();</span><span style=3D"color:#000"> <=
/span><span style=3D"color:#660">++</span><span style=3D"color:#000">i</spa=
n><span style=3D"color:#660">)</span><span style=3D"color:#000"><br>=C2=A0 =
=C2=A0 =C2=A0 =C2=A0 costs</span><span style=3D"color:#660">[</span><span s=
tyle=3D"color:#000">i</span><span style=3D"color:#660">]</span><span style=
=3D"color:#000"> </span><span style=3D"color:#660">=3D</span><span style=3D=
"color:#000"> i</span><span style=3D"color:#660">;</span><span style=3D"col=
or:#000"><br><br>=C2=A0 =C2=A0 </span><span style=3D"color:#008">for</span>=
<span style=3D"color:#660">(</span><span style=3D"color:#000">size_t i </sp=
an><span style=3D"color:#660">=3D</span><span style=3D"color:#000"> </span>=
<span style=3D"color:#066">0</span><span style=3D"color:#660">;</span><span=
 style=3D"color:#000"> i </span><span style=3D"color:#660">&lt;</span><span=
 style=3D"color:#000"> size_S</span><span style=3D"color:#660">;</span><spa=
n style=3D"color:#000"> </span><span style=3D"color:#660">++</span><span st=
yle=3D"color:#000">i</span><span style=3D"color:#660">)</span><span style=
=3D"color:#000"><br>=C2=A0 =C2=A0 </span><span style=3D"color:#660">{</span=
><span style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 costs</span><sp=
an style=3D"color:#660">[</span><span style=3D"color:#066">0</span><span st=
yle=3D"color:#660">]</span><span style=3D"color:#000"> </span><span style=
=3D"color:#660">=3D</span><span style=3D"color:#000"> i </span><span style=
=3D"color:#660">+</span><span style=3D"color:#000"> </span><span style=3D"c=
olor:#066">1</span><span style=3D"color:#660">;</span><span style=3D"color:=
#000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"color:#008">int=
</span><span style=3D"color:#000"> corner </span><span style=3D"color:#660"=
>=3D</span><span style=3D"color:#000"> i</span><span style=3D"color:#660">;=
</span><span style=3D"color:#000"><br><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 </spa=
n><span style=3D"color:#008">for</span><span style=3D"color:#660">(</span><=
span style=3D"color:#000">size_t j </span><span style=3D"color:#660">=3D</s=
pan><span style=3D"color:#000"> </span><span style=3D"color:#066">0</span><=
span style=3D"color:#660">;</span><span style=3D"color:#000"> j </span><spa=
n style=3D"color:#660">&lt;</span><span style=3D"color:#000"> size_T</span>=
<span style=3D"color:#660">;</span><span style=3D"color:#000"> </span><span=
 style=3D"color:#660">++</span><span style=3D"color:#000">j</span><span sty=
le=3D"color:#660">)</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=
=A0 =C2=A0 </span><span style=3D"color:#660">{</span><span style=3D"color:#=
000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"co=
lor:#008">int</span><span style=3D"color:#000"> upper </span><span style=3D=
"color:#660">=3D</span><span style=3D"color:#000"> costs</span><span style=
=3D"color:#660">[</span><span style=3D"color:#000">j </span><span style=3D"=
color:#660">+</span><span style=3D"color:#000"> </span><span style=3D"color=
:#066">1</span><span style=3D"color:#660">];</span><span style=3D"color:#00=
0"><br><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"=
color:#008">if</span><span style=3D"color:#660">(*</span><span style=3D"col=
or:#000">std</span><span style=3D"color:#660">::</span><span style=3D"color=
:#008">next</span><span style=3D"color:#660">(</span><span style=3D"color:#=
000">it_S_begin</span><span style=3D"color:#660">,</span><span style=3D"col=
or:#000"> i</span><span style=3D"color:#660">)</span><span style=3D"color:#=
000"> </span><span style=3D"color:#660">=3D=3D</span><span style=3D"color:#=
000"> </span><span style=3D"color:#660">*</span><span style=3D"color:#000">=
std</span><span style=3D"color:#660">::</span><span style=3D"color:#008">ne=
xt</span><span style=3D"color:#660">(</span><span style=3D"color:#000">it_T=
_begin</span><span style=3D"color:#660">,</span><span style=3D"color:#000">=
 j</span><span style=3D"color:#660">))</span><span style=3D"color:#000"><br=
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 costs</span><span =
style=3D"color:#660">[</span><span style=3D"color:#000">j </span><span styl=
e=3D"color:#660">+</span><span style=3D"color:#000"> </span><span style=3D"=
color:#066">1</span><span style=3D"color:#660">]</span><span style=3D"color=
:#000"> </span><span style=3D"color:#660">=3D</span><span style=3D"color:#0=
00"> corner</span><span style=3D"color:#660">;</span><span style=3D"color:#=
000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"co=
lor:#008">else</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 costs</span><span style=3D"color:#660">[=
</span><span style=3D"color:#000">j </span><span style=3D"color:#660">+</sp=
an><span style=3D"color:#000"> </span><span style=3D"color:#066">1</span><s=
pan style=3D"color:#660">]</span><span style=3D"color:#000"> </span><span s=
tyle=3D"color:#660">=3D</span><span style=3D"color:#000"> std</span><span s=
tyle=3D"color:#660">::</span><span style=3D"color:#000">min</span><span sty=
le=3D"color:#660">(</span><span style=3D"color:#000">costs</span><span styl=
e=3D"color:#660">[</span><span style=3D"color:#000">j</span><span style=3D"=
color:#660">],</span><span style=3D"color:#000"> std</span><span style=3D"c=
olor:#660">::</span><span style=3D"color:#000">min</span><span style=3D"col=
or:#660">(</span><span style=3D"color:#000">upper</span><span style=3D"colo=
r:#660">,</span><span style=3D"color:#000"> corner</span><span style=3D"col=
or:#660">))</span><span style=3D"color:#000"> </span><span style=3D"color:#=
660">+</span><span style=3D"color:#000"> </span><span style=3D"color:#066">=
1</span><span style=3D"color:#660">;</span><span style=3D"color:#000"><br><=
br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 corner </span><span style=3D"c=
olor:#660">=3D</span><span style=3D"color:#000"> upper</span><span style=3D=
"color:#660">;</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 =
=C2=A0 </span><span style=3D"color:#660">}</span><span style=3D"color:#000"=
><br>=C2=A0 =C2=A0 </span><span style=3D"color:#660">}</span><span style=3D=
"color:#000"><br><br>=C2=A0 =C2=A0 </span><span style=3D"color:#008">return=
</span><span style=3D"color:#000"> costs</span><span style=3D"color:#660">.=
</span><span style=3D"color:#000">back</span><span style=3D"color:#660">();=
</span><span style=3D"color:#000"><br></span><span style=3D"color:#660">}</=
span></div></code></div><span class=3D"HOEnZb"><font color=3D"#888888"><br>=
<br></font></span></div><span class=3D"HOEnZb"><font color=3D"#888888">

<p></p>

-- <br>
<br>
--- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org" target=3D"_=
blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" target=3D"_blank">http://groups.google.com/a/isocpp.org/gro=
up/std-proposals/</a>.<br>
</font></span></blockquote></div><br></div>

<p></p>

-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

--001a11c31f70b16a380502d7ceaa--

.

El 12/09/2014 0:49, germinolegrand@gmail.com escribi=C3=B3:
> Hello everyone,
> I am currently writting new algorithms that I'd like to propose into the
> STL in a near future.
>
> But, I've just encountered a problem : the last algorithm I wrote relies
> on allocating/deallocating memory for internal computation.
>
> The maximum size of memory allocation needed is perfectly deductible
> from the arguments. But this is of course dependant of the choice of
> implementation.
>
> Currently I use a basic std::vector.
>
> What should I use ? Take a buffer as an argument ? Have an Allocator
> template argument ? Leave it as it is ?

I think you're looking for "get_temporary_buffer/return_temporary_buffer"

http://www.cplusplus.com/reference/memory/get_temporary_buffer/

Many std implementations use it but AFAIK it's not mandatory. Usually=20
implementations try to allocate memory for the fastest algorithm, if=20
less memory is returned, then a slower algorithm is used.

Best,

Ion

--=20

---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

.

------=_Part_518_407218128.1410526367189
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

Thank you for your answers.

It leads me to two questions about=20
get_temporary_buffer/return_temporary_buffer :
1- How can the user control the temporary buffer ? What's the point in=20
using get_temporary_buffer/return_temporary_buffer if it can't ?
2- Oh my, this is really low level... Maybe some evolution is needed ?=20
Seems like two things are missing : a kind of smart pointer, and an=20
allocator for containers.

Regards,
germinolegrand

Le vendredi 12 septembre 2014 08:16:36 UTC+2, Ion Gazta=C3=B1aga a =C3=A9cr=
it :
>
> El 12/09/2014 0:49, germino...@gmail.com <javascript:> escribi=C3=B3:=20
> > Hello everyone,=20
> > I am currently writting new algorithms that I'd like to propose into th=
e=20
> > STL in a near future.=20
> >=20
> > But, I've just encountered a problem : the last algorithm I wrote relie=
s=20
> > on allocating/deallocating memory for internal computation.=20
> >=20
> > The maximum size of memory allocation needed is perfectly deductible=20
> > from the arguments. But this is of course dependant of the choice of=20
> > implementation.=20
> >=20
> > Currently I use a basic std::vector.=20
> >=20
> > What should I use ? Take a buffer as an argument ? Have an Allocator=20
> > template argument ? Leave it as it is ?=20
>
> I think you're looking for "get_temporary_buffer/return_temporary_buffer"=
=20
>
> http://www.cplusplus.com/reference/memory/get_temporary_buffer/=20
>
> Many std implementations use it but AFAIK it's not mandatory. Usually=20
> implementations try to allocate memory for the fastest algorithm, if=20
> less memory is returned, then a slower algorithm is used.=20
>
> Best,=20
>
> Ion=20
>

--=20

---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

------=_Part_518_407218128.1410526367189
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Thank you for your answers.<br><br>It leads me to two ques=
tions about get_temporary_buffer/return_temporary_buffer :<br>1- How can th=
e user control the temporary buffer ? What's the point in using get_tempora=
ry_buffer/return_temporary_buffer if it can't ?<br>2- Oh my, this is really=
 low level... Maybe some evolution is needed ? Seems like two things are mi=
ssing : a kind of smart pointer, and an allocator for containers.<br><br>Re=
gards,<br>germinolegrand<br><br>Le vendredi 12 septembre 2014 08:16:36 UTC+=
2, Ion Gazta=C3=B1aga a =C3=A9crit&nbsp;:<blockquote class=3D"gmail_quote" =
style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-l=
eft: 1ex;">El 12/09/2014 0:49, <a href=3D"javascript:" target=3D"_blank" gd=
f-obfuscated-mailto=3D"5UraV_HfspsJ" onmousedown=3D"this.href=3D'javascript=
:';return true;" onclick=3D"this.href=3D'javascript:';return true;">germino=
....@gmail.com</a> escribi=C3=B3:
<br>&gt; Hello everyone,
<br>&gt; I am currently writting new algorithms that I'd like to propose in=
to the
<br>&gt; STL in a near future.
<br>&gt;
<br>&gt; But, I've just encountered a problem : the last algorithm I wrote =
relies
<br>&gt; on allocating/deallocating memory for internal computation.
<br>&gt;
<br>&gt; The maximum size of memory allocation needed is perfectly deductib=
le
<br>&gt; from the arguments. But this is of course dependant of the choice =
of
<br>&gt; implementation.
<br>&gt;
<br>&gt; Currently I use a basic std::vector.
<br>&gt;
<br>&gt; What should I use ? Take a buffer as an argument ? Have an Allocat=
or
<br>&gt; template argument ? Leave it as it is ?
<br>
<br>I think you're looking for "get_temporary_buffer/return_<wbr>temporary_=
buffer"
<br>
<br><a href=3D"http://www.cplusplus.com/reference/memory/get_temporary_buff=
er/" target=3D"_blank" onmousedown=3D"this.href=3D'http://www.google.com/ur=
l?q\75http%3A%2F%2Fwww.cplusplus.com%2Freference%2Fmemory%2Fget_temporary_b=
uffer%2F\46sa\75D\46sntz\0751\46usg\75AFQjCNH9Q7uogbUSPINbyCUM24zCIy6VXw';r=
eturn true;" onclick=3D"this.href=3D'http://www.google.com/url?q\75http%3A%=
2F%2Fwww.cplusplus.com%2Freference%2Fmemory%2Fget_temporary_buffer%2F\46sa\=
75D\46sntz\0751\46usg\75AFQjCNH9Q7uogbUSPINbyCUM24zCIy6VXw';return true;">h=
ttp://www.cplusplus.com/<wbr>reference/memory/get_<wbr>temporary_buffer/</a=
>
<br>
<br>Many std implementations use it but AFAIK it's not mandatory. Usually=
=20
<br>implementations try to allocate memory for the fastest algorithm, if=20
<br>less memory is returned, then a slower algorithm is used.
<br>
<br>Best,
<br>
<br>Ion
<br></blockquote></div>

<p></p>

-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

------=_Part_518_407218128.1410526367189--

.

El 12/09/2014 14:52, germinolegrand@gmail.com escribi=C3=B3:
> Thank you for your answers.
>
> It leads me to two questions about
> get_temporary_buffer/return_temporary_buffer :
> 1- How can the user control the temporary buffer ? What's the point in
> using get_temporary_buffer/return_temporary_buffer if it can't ?
> 2- Oh my, this is really low level... Maybe some evolution is needed ?
> Seems like two things are missing : a kind of smart pointer, and an
> allocator for containers.

1) No idea. This implementation was in the SGI STL and it might be=20
inherited when the STL was standardized. Some call operator new=20
(replaceable), other implementations call "malloc". There is no way to=20
configure the memory source of "get_temporary_buffer" (although that=20
would be a good idea, IMHO, as it could be optimized for that pattern).=20
In any case, there is no guarantee algorithms will call=20
"get_temporary_buffer" (or at least I can't find any text in the=20
standard that says that).

2) SGI STL added temporary_buffer class=20
(https://www.sgi.com/tech/stl/temporary_buffer.html) as a smart ptr that=20
I think it's still used in GCC and some other STLs derived from the SGI=20
implementation. libc++ also implements its own mechanism (a unique_ptr=20
with a special deleter).

The hard part is to use that raw memory for objects (e.g. classes with=20
constructors) as you need to construct objects there before (move)=20
assigning and swapping elements. Each STL has its own strategy. I think=20
libstdc++ takes the first argument and constructs objects in the=20
temporary buffer move constructing from the first user-provided value=20
(*first) in a chain, reconstructing the first user objects with the last=20
temporary buffer objects. Libc++ constructs the objects in the temporary=20
buffer on-demand (or at least in stable_sort).

I would recommend reviewing the implementation of std::stable_sort in=20
both libc++ and libcstdc++ and take ideas from them.

Best,

Ion

--=20

---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

.

Am 12.09.2014 um 19:46 schrieb Ion Gazta=C3=B1aga:
> The hard part is to use that raw memory for objects (e.g. classes with=20
> constructors) as you need to construct objects there before (move)=20
> assigning and swapping elements. Each STL has its own strategy. I=20
> think libstdc++ takes the first argument and constructs objects in the=20
> temporary buffer move constructing from the first user-provided value=20
> (*first) in a chain, reconstructing the first user objects with the=20
> last temporary buffer objects. Libc++ constructs the objects in the=20
> temporary buffer on-demand (or at least in stable_sort).
uninitialized_copy, uninitialized_fill, raw_storage_iterator and friends=20
might be of help here. See http://en.cppreference.com/w/cpp/memory=20
section Uninitialized Storage.

--=20

---=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa=
ls/.

.