------=_Part_42_1769367157.1422059200701
Content-Type: multipart/alternative;
 boundary="----=_Part_43_1547747690.1422059200701"

------=_Part_43_1547747690.1422059200701
Content-Type: text/plain; charset=UTF-8

All algorithms in the <algorithm> header that write data into an output
range currently take only a source iterator for the destination range and
assume that the range is large enough to hold the required output.

However, many algorithms in <algorithm> would benefit from having an
output-restricted variant, for at least two reasons:

   1. The programmer is only interested in the first n elements of the
   output.  I have personally encountered situations in which I wanted to use
   std::merge in this way.
   2. The programmer needs to operate on a given range of input data in
   batches.  For example, writing data into a memory-mapped file for
   communication with another process, or hardware.

As examples, consider restricted_copy and restricted_merge as defined below:

template<class ItA, class ItD>
std::tuple<ItA, ItD> restricted_copy(
    ItA a_src, ItA a_lim,
    ItD d_src, ItD d_lim
)
{
    while(a_src != a_lim && d_src != d_lim)
    {
        *d_src = *a_src;
        ++d_src;
        ++a_src;
    }

    return d_src;
}

template<class ItA, class ItB, class ItD>
std::tuple<ItA, ItB, ItD> restricted_merge(
    ItA a_src, ItA a_lim,
    ItB b_src, ItB b_lim,
    ItD d_src, ItD d_lim
) {
    while((a_src != a_lim) && (d_src != d_lim))
    {
        if(b_src == b_lim)
        {
            auto lim = restricted_copy(a_src, a_lim, d_src, d_lim);
            return make_tuple(
                std::get<0>(lim),
                b_src,
                std::get<1>(lim)
            );
        }

        if(*b_src < *a_src)
        {
            *d_src = *b_src;
            ++d_src;
            ++b_src;
        }
        else
        {
            *d_src = *a_src;
            ++d_src;
            ++a_src;
        }
    }

    auto lim = restricted_copy(b_src, b_lim, d_src, d_lim);
    return make_tuple(
        a_src,
        std::get<0>(lim),
        std::get<1>(lim)
    );
}

Both of these functions operate exactly like their <algorithm>
counterparts, with the exception that their behavior is well-defined when
the output range cannot hold the total result.  In addition, they are set
up to easily support resuming operation once the data in the output range
has been disposed of:

// ...

// [a_src, a_lim) defines a large source buffer.
// [d_src, d_lim) defines a smaller output buffer.
while(a_src != a_lim)
{
    auto d_cur_lim = d_lim;
    std::tie(a_src, d_cur_lim) = restricted_copy(
        a_src, a_lim,
        d_src, d_lim
    );

    // Do something with the range [d_src, d_cur_lim).
}


Functions from <algorithm> that could benefit from such forms include:

   - copy[_if]
   - copy_backward[_if]  [1]
   - move[_if]           [1]
   - move_backward[_if]  [1]
   - transform[_if]      [1]
   - remove_copy[_if]
   - replace_copy[_if]
   - reverse_copy[_if]   [1]
   - unique_copy[_if]    [1]
   - partition_copy[_if] [1,2]
   - partial_sort_copy   [3]
   - merge[_if]          [1]
   - set_difference
   - set_intersection
   - set_symmetric_difference
   - set_union


Notes:

  [1] These functions do not have an *_if variant in the standard, but
semantics of an *_if variant would be well defined and useful.

  [2] I am unsure whether partition_copy would benefit from an
output-restricted variant, but defining one would be straightforward.

  [3] partial_sort_copy is already an output-restricted variant.

--

---
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/.

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

<div dir=3D"ltr">All algorithms in the <span style=3D"font-family: courier =
new,monospace;">&lt;algorithm&gt;</span> header that write data into an out=
put range currently take only a source iterator for the destination range a=
nd assume that the range is large enough to hold the required output.<br><b=
r>However, many algorithms in <span style=3D"font-family: courier new,monos=
pace;">&lt;algorithm&gt; </span>would benefit from having an output-restric=
ted variant, for at least two reasons:<br><ol><li>The programmer is only in=
terested in the first n elements of the output.&nbsp; I have personally enc=
ountered situations in which I wanted to use <span style=3D"font-family: co=
urier new,monospace;">std::merge</span> in this way.</li><li>The programmer=
 needs to operate on a given range of input data in batches.&nbsp; For exam=
ple, writing data into a memory-mapped file for communication with another =
process, or hardware.</li></ol>As examples, consider <span style=3D"font-fa=
mily: courier new,monospace;">restricted_copy</span> and <span style=3D"fon=
t-family: courier new,monospace;">restricted_merge</span> as defined below:=
<br><br><div class=3D"prettyprint" 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 class=3D"prettyprint"><div class=3D"sub=
prettyprint"><span style=3D"color: #008;" class=3D"styled-by-prettify">temp=
late</span><span style=3D"color: #660;" class=3D"styled-by-prettify">&lt;</=
span><span style=3D"color: #008;" class=3D"styled-by-prettify">class</span>=
<span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span sty=
le=3D"color: #606;" class=3D"styled-by-prettify">ItA</span><span style=3D"c=
olor: #660;" class=3D"styled-by-prettify">,</span><span style=3D"color: #00=
0;" class=3D"styled-by-prettify"> </span><span style=3D"color: #008;" class=
=3D"styled-by-prettify">class</span><span style=3D"color: #000;" class=3D"s=
tyled-by-prettify"> </span><span style=3D"color: #606;" class=3D"styled-by-=
prettify">ItD</span><span style=3D"color: #660;" class=3D"styled-by-prettif=
y">&gt;</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br=
>std</span><span style=3D"color: #660;" class=3D"styled-by-prettify">::</sp=
an><span style=3D"color: #000;" class=3D"styled-by-prettify">tuple</span><s=
pan style=3D"color: #660;" class=3D"styled-by-prettify">&lt;</span><span st=
yle=3D"color: #606;" class=3D"styled-by-prettify">ItA</span><span style=3D"=
color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify"> </span><span style=3D"color: #606;" clas=
s=3D"styled-by-prettify">ItD</span><span style=3D"color: #660;" class=3D"st=
yled-by-prettify">&gt;</span><span style=3D"color: #000;" class=3D"styled-b=
y-prettify"> restricted_copy</span><span style=3D"color: #660;" class=3D"st=
yled-by-prettify">(</span><span style=3D"color: #000;" class=3D"styled-by-p=
rettify"><br>&nbsp; &nbsp; </span><span style=3D"color: #606;" class=3D"sty=
led-by-prettify">ItA</span><span style=3D"color: #000;" class=3D"styled-by-=
prettify"> a_src</span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">,</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </=
span><span style=3D"color: #606;" class=3D"styled-by-prettify">ItA</span><s=
pan style=3D"color: #000;" class=3D"styled-by-prettify"> a_lim</span><span =
style=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; </span><span s=
tyle=3D"color: #606;" class=3D"styled-by-prettify">ItD</span><span style=3D=
"color: #000;" class=3D"styled-by-prettify"> d_src</span><span style=3D"col=
or: #660;" class=3D"styled-by-prettify">,</span><span style=3D"color: #000;=
" class=3D"styled-by-prettify"> </span><span style=3D"color: #606;" class=
=3D"styled-by-prettify">ItD</span><span style=3D"color: #000;" class=3D"sty=
led-by-prettify"> d_lim<br></span><span style=3D"color: #660;" class=3D"sty=
led-by-prettify">)</span><span style=3D"color: #000;" class=3D"styled-by-pr=
ettify"><br></span><span style=3D"color: #660;" class=3D"styled-by-prettify=
">{</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nb=
sp; &nbsp; </span><span style=3D"color: #008;" class=3D"styled-by-prettify"=
>while</span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</s=
pan><span style=3D"color: #000;" class=3D"styled-by-prettify">a_src </span>=
<span style=3D"color: #660;" class=3D"styled-by-prettify">!=3D</span><span =
style=3D"color: #000;" class=3D"styled-by-prettify"> a_lim </span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">&amp;&amp;</span><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify"> d_src </span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">!=3D</span><span style=3D"co=
lor: #000;" class=3D"styled-by-prettify"> d_lim</span><span style=3D"color:=
 #660;" class=3D"styled-by-prettify">)</span><span style=3D"color: #000;" c=
lass=3D"styled-by-prettify"><br>&nbsp; &nbsp; </span><span style=3D"color: =
#660;" class=3D"styled-by-prettify">{</span><span style=3D"color: #000;" cl=
ass=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; </span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">*</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify">d_src </span><span style=3D"color: =
#660;" class=3D"styled-by-prettify">=3D</span><span style=3D"color: #000;" =
class=3D"styled-by-prettify"> </span><span style=3D"color: #660;" class=3D"=
styled-by-prettify">*</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify">a_src</span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">;</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br=
>&nbsp; &nbsp; &nbsp; &nbsp; </span><span style=3D"color: #660;" class=3D"s=
tyled-by-prettify">++</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify">d_src</span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">;</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br=
>&nbsp; &nbsp; &nbsp; &nbsp; </span><span style=3D"color: #660;" class=3D"s=
tyled-by-prettify">++</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify">a_src</span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">;</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br=
>&nbsp; &nbsp; </span><span style=3D"color: #660;" class=3D"styled-by-prett=
ify">}</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>=
<br>&nbsp; &nbsp; </span><span style=3D"color: #008;" class=3D"styled-by-pr=
ettify">return</span><span style=3D"color: #000;" class=3D"styled-by-pretti=
fy"> d_src</span><span style=3D"color: #660;" class=3D"styled-by-prettify">=
;</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br></spa=
n><span style=3D"color: #660;" class=3D"styled-by-prettify">}</span><span s=
tyle=3D"color: #000;" class=3D"styled-by-prettify"><br></span></div></code>=
</div><br><div class=3D"prettyprint" style=3D"background-color: rgb(250, 25=
0, 250); border-color: rgb(187, 187, 187); border-style: solid; border-widt=
h: 1px; word-wrap: break-word;"><code class=3D"prettyprint"><div class=3D"s=
ubprettyprint"><span style=3D"color: #008;" class=3D"styled-by-prettify">te=
mplate</span><span style=3D"color: #660;" class=3D"styled-by-prettify">&lt;=
</span><span style=3D"color: #008;" class=3D"styled-by-prettify">class</spa=
n><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span s=
tyle=3D"color: #606;" class=3D"styled-by-prettify">ItA</span><span style=3D=
"color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"color: #=
000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #008;" cla=
ss=3D"styled-by-prettify">class</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify"> </span><span style=3D"color: #606;" class=3D"styled-b=
y-prettify">ItB</span><span style=3D"color: #660;" class=3D"styled-by-prett=
ify">,</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </s=
pan><span style=3D"color: #008;" class=3D"styled-by-prettify">class</span><=
span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span styl=
e=3D"color: #606;" class=3D"styled-by-prettify">ItD</span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">&gt;</span><span style=3D"color: #=
000;" class=3D"styled-by-prettify"><br>std</span><span style=3D"color: #660=
;" class=3D"styled-by-prettify">::</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify">tuple</span><span style=3D"color: #660;" class=3D"s=
tyled-by-prettify">&lt;</span><span style=3D"color: #606;" class=3D"styled-=
by-prettify">ItA</span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">,</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </=
span><span style=3D"color: #606;" class=3D"styled-by-prettify">ItB</span><s=
pan style=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color=
: #606;" class=3D"styled-by-prettify">ItD</span><span style=3D"color: #660;=
" class=3D"styled-by-prettify">&gt;</span><span style=3D"color: #000;" clas=
s=3D"styled-by-prettify"> restricted_merge</span><span style=3D"color: #660=
;" class=3D"styled-by-prettify">(</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"><br>&nbsp; &nbsp; </span><span style=3D"color: #606=
;" class=3D"styled-by-prettify">ItA</span><span style=3D"color: #000;" clas=
s=3D"styled-by-prettify"> a_src</span><span style=3D"color: #660;" class=3D=
"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D"styled-b=
y-prettify"> </span><span style=3D"color: #606;" class=3D"styled-by-prettif=
y">ItA</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> a_l=
im</span><span style=3D"color: #660;" class=3D"styled-by-prettify">,</span>=
<span style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp;=
 </span><span style=3D"color: #606;" class=3D"styled-by-prettify">ItB</span=
><span style=3D"color: #000;" class=3D"styled-by-prettify"> b_src</span><sp=
an style=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color=
: #606;" class=3D"styled-by-prettify">ItB</span><span style=3D"color: #000;=
" class=3D"styled-by-prettify"> b_lim</span><span style=3D"color: #660;" cl=
ass=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D"st=
yled-by-prettify"><br>&nbsp; &nbsp; </span><span style=3D"color: #606;" cla=
ss=3D"styled-by-prettify">ItD</span><span style=3D"color: #000;" class=3D"s=
tyled-by-prettify"> d_src</span><span style=3D"color: #660;" class=3D"style=
d-by-prettify">,</span><span style=3D"color: #000;" class=3D"styled-by-pret=
tify"> </span><span style=3D"color: #606;" class=3D"styled-by-prettify">ItD=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> d_lim<br>=
</span><span style=3D"color: #660;" class=3D"styled-by-prettify">)</span><s=
pan style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">{</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; </span><span style=
=3D"color: #008;" class=3D"styled-by-prettify">while</span><span style=3D"c=
olor: #660;" class=3D"styled-by-prettify">((</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify">a_src </span><span style=3D"color: #660;"=
 class=3D"styled-by-prettify">!=3D</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"> a_lim</span><span style=3D"color: #660;" class=3D"=
styled-by-prettify">)</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify"> </span><span style=3D"color: #660;" class=3D"styled-by-prettify=
">&amp;&amp;</span><span style=3D"color: #000;" class=3D"styled-by-prettify=
"> </span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span=
><span style=3D"color: #000;" class=3D"styled-by-prettify">d_src </span><sp=
an style=3D"color: #660;" class=3D"styled-by-prettify">!=3D</span><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify"> d_lim</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">))</span><span style=3D"colo=
r: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; </span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">{</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; </spa=
n><span style=3D"color: #008;" class=3D"styled-by-prettify">if</span><span =
style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify">b_src </span><span style=3D"colo=
r: #660;" class=3D"styled-by-prettify">=3D=3D</span><span style=3D"color: #=
000;" class=3D"styled-by-prettify"> b_lim</span><span style=3D"color: #660;=
" class=3D"styled-by-prettify">)</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; </span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">{</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp=
; &nbsp; </span><span style=3D"color: #008;" class=3D"styled-by-prettify">a=
uto</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> lim </=
span><span style=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><s=
pan style=3D"color: #000;" class=3D"styled-by-prettify"> restricted_copy</s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span=
 style=3D"color: #000;" class=3D"styled-by-prettify">a_src</span><span styl=
e=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"colo=
r: #000;" class=3D"styled-by-prettify"> a_lim</span><span style=3D"color: #=
660;" class=3D"styled-by-prettify">,</span><span style=3D"color: #000;" cla=
ss=3D"styled-by-prettify"> d_src</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"> d_lim</span><span style=3D"color: #660;" class=3D"styled-by=
-prettify">);</span><span style=3D"color: #000;" class=3D"styled-by-prettif=
y"><br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </span><span style=3D"colo=
r: #008;" class=3D"styled-by-prettify">return</span><span style=3D"color: #=
000;" class=3D"styled-by-prettify"> make_tuple</span><span style=3D"color: =
#660;" class=3D"styled-by-prettify">(</span><span style=3D"color: #000;" cl=
ass=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &n=
bsp; &nbsp; std</span><span style=3D"color: #660;" class=3D"styled-by-prett=
ify">::</span><span style=3D"color: #008;" class=3D"styled-by-prettify">get=
</span><span style=3D"color: #660;" class=3D"styled-by-prettify">&lt;</span=
><span style=3D"color: #066;" class=3D"styled-by-prettify">0</span><span st=
yle=3D"color: #660;" class=3D"styled-by-prettify">&gt;(</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify">lim</span><span style=3D"col=
or: #660;" class=3D"styled-by-prettify">),</span><span style=3D"color: #000=
;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbs=
p; &nbsp; &nbsp; b_src</span><span style=3D"color: #660;" class=3D"styled-b=
y-prettify">,</span><span style=3D"color: #000;" class=3D"styled-by-prettif=
y"><br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; std</span><s=
pan style=3D"color: #660;" class=3D"styled-by-prettify">::</span><span styl=
e=3D"color: #008;" class=3D"styled-by-prettify">get</span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">&lt;</span><span style=3D"color: #=
066;" class=3D"styled-by-prettify">1</span><span style=3D"color: #660;" cla=
ss=3D"styled-by-prettify">&gt;(</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify">lim</span><span style=3D"color: #660;" class=3D"styled=
-by-prettify">)</span><span style=3D"color: #000;" class=3D"styled-by-prett=
ify"><br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">);</span><span style=3D"color: #00=
0;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; </span><sp=
an style=3D"color: #660;" class=3D"styled-by-prettify">}</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"><br><br>&nbsp; &nbsp; &nbsp;=
 &nbsp; </span><span style=3D"color: #008;" class=3D"styled-by-prettify">if=
</span><span style=3D"color: #660;" class=3D"styled-by-prettify">(*</span><=
span style=3D"color: #000;" class=3D"styled-by-prettify">b_src </span><span=
 style=3D"color: #660;" class=3D"styled-by-prettify">&lt;</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color=
: #660;" class=3D"styled-by-prettify">*</span><span style=3D"color: #000;" =
class=3D"styled-by-prettify">a_src</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">)</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; </span><span style=3D"color:=
 #660;" class=3D"styled-by-prettify">{</span><span style=3D"color: #000;" c=
lass=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <=
/span><span style=3D"color: #660;" class=3D"styled-by-prettify">*</span><sp=
an style=3D"color: #000;" class=3D"styled-by-prettify">d_src </span><span s=
tyle=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><span style=3D=
"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #=
660;" class=3D"styled-by-prettify">*</span><span style=3D"color: #000;" cla=
ss=3D"styled-by-prettify">b_src</span><span style=3D"color: #660;" class=3D=
"styled-by-prettify">;</span><span style=3D"color: #000;" class=3D"styled-b=
y-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </span><span styl=
e=3D"color: #660;" class=3D"styled-by-prettify">++</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify">d_src</span><span style=3D"color: #=
660;" class=3D"styled-by-prettify">;</span><span style=3D"color: #000;" cla=
ss=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">++</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify">b_src</span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">;</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; </s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">}</span><span=
 style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbs=
p; &nbsp; </span><span style=3D"color: #008;" class=3D"styled-by-prettify">=
else</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>&n=
bsp; &nbsp; &nbsp; &nbsp; </span><span style=3D"color: #660;" class=3D"styl=
ed-by-prettify">{</span><span style=3D"color: #000;" class=3D"styled-by-pre=
ttify"><br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </span><span style=3D"=
color: #660;" class=3D"styled-by-prettify">*</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify">d_src </span><span style=3D"color: #660;"=
 class=3D"styled-by-prettify">=3D</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"> </span><span style=3D"color: #660;" class=3D"style=
d-by-prettify">*</span><span style=3D"color: #000;" class=3D"styled-by-pret=
tify">a_src</span><span style=3D"color: #660;" class=3D"styled-by-prettify"=
>;</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbs=
p; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </span><span style=3D"color: #660;" c=
lass=3D"styled-by-prettify">++</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify">d_src</span><span style=3D"color: #660;" class=3D"style=
d-by-prettify">;</span><span style=3D"color: #000;" class=3D"styled-by-pret=
tify"><br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </span><span style=3D"c=
olor: #660;" class=3D"styled-by-prettify">++</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify">a_src</span><span style=3D"color: #660;" =
class=3D"styled-by-prettify">;</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; </span><span style=3D"c=
olor: #660;" class=3D"styled-by-prettify">}</span><span style=3D"color: #00=
0;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; </span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">}</span><span style=3D"color: #000=
;" class=3D"styled-by-prettify"><br><br>&nbsp; &nbsp; </span><span style=3D=
"color: #008;" class=3D"styled-by-prettify">auto</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"> lim </span><span style=3D"color: #66=
0;" class=3D"styled-by-prettify">=3D</span><span style=3D"color: #000;" cla=
ss=3D"styled-by-prettify"> restricted_copy</span><span style=3D"color: #660=
;" class=3D"styled-by-prettify">(</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify">b_src</span><span style=3D"color: #660;" class=3D"s=
tyled-by-prettify">,</span><span style=3D"color: #000;" class=3D"styled-by-=
prettify"> b_lim</span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">,</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> d_=
src</span><span style=3D"color: #660;" class=3D"styled-by-prettify">,</span=
><span style=3D"color: #000;" class=3D"styled-by-prettify"> d_lim</span><sp=
an style=3D"color: #660;" class=3D"styled-by-prettify">);</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; </span><sp=
an style=3D"color: #008;" class=3D"styled-by-prettify">return</span><span s=
tyle=3D"color: #000;" class=3D"styled-by-prettify"> make_tuple</span><span =
style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; =
a_src</span><span style=3D"color: #660;" class=3D"styled-by-prettify">,</sp=
an><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nb=
sp; &nbsp; &nbsp; std</span><span style=3D"color: #660;" class=3D"styled-by=
-prettify">::</span><span style=3D"color: #008;" class=3D"styled-by-prettif=
y">get</span><span style=3D"color: #660;" class=3D"styled-by-prettify">&lt;=
</span><span style=3D"color: #066;" class=3D"styled-by-prettify">0</span><s=
pan style=3D"color: #660;" class=3D"styled-by-prettify">&gt;(</span><span s=
tyle=3D"color: #000;" class=3D"styled-by-prettify">lim</span><span style=3D=
"color: #660;" class=3D"styled-by-prettify">),</span><span style=3D"color: =
#000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; std</sp=
an><span style=3D"color: #660;" class=3D"styled-by-prettify">::</span><span=
 style=3D"color: #008;" class=3D"styled-by-prettify">get</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">&lt;</span><span style=3D"co=
lor: #066;" class=3D"styled-by-prettify">1</span><span style=3D"color: #660=
;" class=3D"styled-by-prettify">&gt;(</span><span style=3D"color: #000;" cl=
ass=3D"styled-by-prettify">lim</span><span style=3D"color: #660;" class=3D"=
styled-by-prettify">)</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify"><br>&nbsp; &nbsp; </span><span style=3D"color: #660;" class=3D"s=
tyled-by-prettify">);</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify"><br></span><span style=3D"color: #660;" class=3D"styled-by-prett=
ify">}</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>=
</span></div></code></div><br>Both of these functions operate exactly like =
their <span style=3D"font-family: courier new,monospace;">&lt;algorithm&gt;=
</span> counterparts, with the exception that their behavior is well-define=
d when the output range cannot hold the total result.&nbsp; In addition, th=
ey are set up to easily support resuming operation once the data in the out=
put range has been disposed of:<br><br><div class=3D"prettyprint" style=3D"=
background-color: rgb(250, 250, 250); border-color: rgb(187, 187, 187); bor=
der-style: solid; border-width: 1px; word-wrap: break-word;"><code class=3D=
"prettyprint"><div class=3D"subprettyprint"><span style=3D"color: #800;" cl=
ass=3D"styled-by-prettify">// ...</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"><br><br></span><span style=3D"color: #800;" class=
=3D"styled-by-prettify">// [a_src, a_lim) defines a large source buffer.</s=
pan><span style=3D"color: #000;" class=3D"styled-by-prettify"><br></span><s=
pan style=3D"color: #800;" class=3D"styled-by-prettify">// [d_src, d_lim) d=
efines a smaller output buffer.</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify"><br></span><span style=3D"color: #008;" class=3D"style=
d-by-prettify">while</span><span style=3D"color: #660;" class=3D"styled-by-=
prettify">(</span><span style=3D"color: #000;" class=3D"styled-by-prettify"=
>a_src </span><span style=3D"color: #660;" class=3D"styled-by-prettify">!=
=3D</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> a_lim<=
/span><span style=3D"color: #660;" class=3D"styled-by-prettify">)</span><sp=
an style=3D"color: #000;" class=3D"styled-by-prettify"><br></span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">{</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; </span><span styl=
e=3D"color: #008;" class=3D"styled-by-prettify">auto</span><span style=3D"c=
olor: #000;" class=3D"styled-by-prettify"> d_cur_lim </span><span style=3D"=
color: #660;" class=3D"styled-by-prettify">=3D</span><span style=3D"color: =
#000;" class=3D"styled-by-prettify"> d_lim</span><span style=3D"color: #660=
;" class=3D"styled-by-prettify">;</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"><br>&nbsp; &nbsp; std</span><span style=3D"color: #=
660;" class=3D"styled-by-prettify">::</span><span style=3D"color: #000;" cl=
ass=3D"styled-by-prettify">tie</span><span style=3D"color: #660;" class=3D"=
styled-by-prettify">(</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify">a_src</span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">,</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> d_=
cur_lim</span><span style=3D"color: #660;" class=3D"styled-by-prettify">)</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><spa=
n style=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> restricted_copy</span><span=
 style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span style=3D=
"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp;=
 a_src</span><span style=3D"color: #660;" class=3D"styled-by-prettify">,</s=
pan><span style=3D"color: #000;" class=3D"styled-by-prettify"> a_lim</span>=
<span style=3D"color: #660;" class=3D"styled-by-prettify">,</span><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &=
nbsp; d_src</span><span style=3D"color: #660;" class=3D"styled-by-prettify"=
>,</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> d_lim<b=
r>&nbsp; &nbsp; </span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">);</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><b=
r><br>&nbsp; &nbsp; </span><span style=3D"color: #800;" class=3D"styled-by-=
prettify">// Do something with the range [d_src, d_cur_lim).</span><span st=
yle=3D"color: #000;" class=3D"styled-by-prettify"><br></span><span style=3D=
"color: #660;" class=3D"styled-by-prettify">}</span><span style=3D"color: #=
000;" class=3D"styled-by-prettify"><br></span></div></code></div><br><br>Fu=
nctions from <span style=3D"font-family: courier new,monospace;">&lt;algori=
thm&gt;</span> that could benefit from such forms include:<br><ul><li><span=
 style=3D"font-family: courier new,monospace;">copy[_if]</span></li><li><sp=
an style=3D"font-family: courier new,monospace;">copy_backward[_if]&nbsp; [=
1]</span></li><li><span style=3D"font-family: courier new,monospace;">move[=
_if]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; [1]</span>=
</li><li><span style=3D"font-family: courier new,monospace;">move_backward[=
_if]&nbsp; [1]</span></li><li><span style=3D"font-family: courier new,monos=
pace;">transform[_if]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; [1]</span></li><li><spa=
n style=3D"font-family: courier new,monospace;">remove_copy[_if]</span></li=
><li><span style=3D"font-family: courier new,monospace;">replace_copy[_if]<=
/span></li><li><span style=3D"font-family: courier new,monospace;">reverse_=
copy[_if]&nbsp;&nbsp; [1]</span></li><li><span style=3D"font-family: courie=
r new,monospace;">unique_copy[_if]&nbsp;&nbsp;&nbsp; [1]</span></li><li><sp=
an style=3D"font-family: courier new,monospace;">partition_copy[_if] [1,2]<=
/span></li><li><span style=3D"font-family: courier new,monospace;">partial_=
sort_copy&nbsp;&nbsp; [3]</span></li><li><span style=3D"font-family: courie=
r new,monospace;">merge[_if]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp=
;&nbsp; [1]</span></li><li><span style=3D"font-family: courier new,monospac=
e;">set_difference</span></li><li><span style=3D"font-family: courier new,m=
onospace;">set_intersection</span></li><li><span style=3D"font-family: cour=
ier new,monospace;">set_symmetric_difference</span></li><li><span style=3D"=
font-family: courier new,monospace;">set_union</span></li></ul><br>Notes:<b=
r><br>&nbsp; [1] These functions do not have an *_if variant in the standar=
d, but semantics of an *_if variant would be well defined and useful.<br><b=
r>&nbsp; [2] I am unsure whether partition_copy would benefit from an outpu=
t-restricted variant, but defining one would be straightforward.<br><br>&nb=
sp; [3] partial_sort_copy is already an output-restricted variant.<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 />

------=_Part_43_1547747690.1422059200701--
------=_Part_42_1769367157.1422059200701--

.

--Apple-Mail=_46DB59EB-6886-4FF2-ACBA-A0380EFE92E2
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset=UTF-8


> On 2015=E2=80=9301=E2=80=9324, at 8:26 AM, ahmed.taahir@gmail.com wrote:
>=20
> However, many algorithms in <algorithm> would benefit from having an outp=
ut-restricted variant, for at least two reasons:

Rather than rewrite all the algorithms, why not define an output-restricted=
 iterator category (perhaps together with an adaptor to generate one from a=
ny unrestricted output iterator, and perhaps adding non-output iterators in=
to the mix), and add constraints to the existing algorithms to ensure that =
the templates do the right thing?

There are several approaches to getting algorithms to terminate:

1. Advance the iterator to a singular value which is equal to the default-c=
onstructed value of the iterator type. IMHO this fits most elegantly with t=
he existing iterator scheme, but current ostream_iterator and ostreambuf_it=
erator don=E2=80=99t support default construction nor equality checks.

The algorithm would have to check against this value for every iteration of=
 the output iterator. A good implementation would only do so for restricted=
 iterators, but implementations would be free to treat all DefaultConstruct=
ible and EqualityComparable iterators the same.

2. Let restricted iterators have a failed() method, as ostreambuf_iterator =
does. The algorithm would have to check this function at every iteration. f=
ailed isn=E2=80=99t a bad name, it would add flexibility to existing ostrea=
mbuf_iterator code, and it avoids losing the state of the iterator into a s=
ingular value.

3. Throw an exception. Then the algorithm doesn=E2=80=99t need to add check=
s to the critical path. The iterator still has to do its own checking, so t=
he efficiency gain depends on whether the compiler in options (1) or (2) wo=
uld have leveraged inlining to identify the special case in the iterator co=
de with the algorithm=E2=80=99s it.failed() or it =3D=3D OutputIterator{} c=
heck. (If so, then there=E2=80=99s no performance loss for zero-overhead ex=
ceptions to save, so in the overall balance, they=E2=80=99re only adding bl=
oat and slowing down the early termination case.)

In any case, it would be nice if algorithms defined the state of iterator a=
dvancement upon exceptions, i.e. whether copy advances the InputIterator or=
 OutputIterator first. However, observing this state requires saving it out=
side the iterator object itself. Stream iterators do this, but most others =
don=E2=80=99t.

=3D=3D=3D

In the balance, I think I favor option (2). Pause-and-resume is orthogonal =
to existing generic iterator functionality. We already have serviceable I/O=
-oriented iterators in ostreambuf_iterator and that direction would encoura=
ge extension of current good (perhaps best) practices. Currently, anything =
done between batches needs to go into streambuf::underflow, but deriving st=
reambuf can be inconvenient.

And, (2) doesn=E2=80=99t preclude having (3) as well.

> The programmer is only interested in the first n elements of the output. =
 I have personally encountered situations in which I wanted to use std::mer=
ge in this way.
> The programmer needs to operate on a given range of input data in batches=
..  For example, writing data into a memory-mapped file for communication wi=
th another process, or hardware.

(1) is just a matter of adding an early exit condition, but (2) requires ef=
fectively turning the algorithm into a coroutine or =E2=80=9Cresumable func=
tion.=E2=80=9D This is a trivial problem for algorithms like copy and merge=
 which return all their internal state in a form allowing it to be passed b=
ack into another invocation. Most of the rest you=E2=80=99ve listed should =
be the same, but a closer look would help.

--=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/.

--Apple-Mail=_46DB59EB-6886-4FF2-ACBA-A0380EFE92E2
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html; charset=UTF-8

<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html charset=
=3Dutf-8"></head><body style=3D"word-wrap: break-word; -webkit-nbsp-mode: s=
pace; -webkit-line-break: after-white-space;" class=3D""><br class=3D""><di=
v><blockquote type=3D"cite" class=3D""><div class=3D"">On 2015=E2=80=9301=
=E2=80=9324, at 8:26 AM, <a href=3D"mailto:ahmed.taahir@gmail.com" class=3D=
"">ahmed.taahir@gmail.com</a> wrote:</div><br class=3D"Apple-interchange-ne=
wline"><div class=3D""><span style=3D"font-family: Helvetica; font-size: 12=
px; font-style: normal; font-variant: normal; font-weight: normal; letter-s=
pacing: normal; line-height: normal; orphans: auto; text-align: start; text=
-indent: 0px; text-transform: none; white-space: normal; widows: auto; word=
-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline=
 !important;" class=3D"">However, many algorithms in<span class=3D"Apple-co=
nverted-space">&nbsp;</span></span><span style=3D"font-size: 12px; font-sty=
le: normal; font-variant: normal; font-weight: normal; letter-spacing: norm=
al; line-height: normal; orphans: auto; text-align: start; text-indent: 0px=
; text-transform: none; white-space: normal; widows: auto; word-spacing: 0p=
x; -webkit-text-stroke-width: 0px; font-family: 'courier new', monospace;" =
class=3D"">&lt;algorithm&gt;<span class=3D"Apple-converted-space">&nbsp;</s=
pan></span><span style=3D"font-family: Helvetica; font-size: 12px; font-sty=
le: normal; font-variant: normal; font-weight: normal; letter-spacing: norm=
al; line-height: normal; orphans: auto; text-align: start; text-indent: 0px=
; text-transform: none; white-space: normal; widows: auto; word-spacing: 0p=
x; -webkit-text-stroke-width: 0px; float: none; display: inline !important;=
" class=3D"">would benefit from having an output-restricted variant, for at=
 least two reasons:</span><br style=3D"font-family: Helvetica; font-size: 1=
2px; font-style: normal; font-variant: normal; font-weight: normal; letter-=
spacing: normal; line-height: normal; orphans: auto; text-align: start; tex=
t-indent: 0px; text-transform: none; white-space: normal; widows: auto; wor=
d-spacing: 0px; -webkit-text-stroke-width: 0px;" class=3D""></div></blockqu=
ote><div><br class=3D""></div><div>Rather than rewrite all the algorithms, =
why not define an output-restricted iterator category (perhaps together wit=
h an adaptor to generate one from any unrestricted output iterator, and per=
haps adding non-output iterators into the mix), and add constraints to the =
existing algorithms to ensure that the templates do the right thing?</div><=
div><br class=3D""></div><div>There are several approaches to getting algor=
ithms to terminate:</div><div><br class=3D""></div><div>1. Advance the iter=
ator to a singular value which is equal to the default-constructed value of=
 the iterator type. IMHO this fits most elegantly with the existing iterato=
r scheme, but current <font face=3D"Courier" class=3D"">ostream_iterator</f=
ont> and <font face=3D"Courier" class=3D"">ostreambuf_iterator</font> don=
=E2=80=99t support default construction nor equality checks.</div><div><br =
class=3D""></div><div>The algorithm would have to check against this value =
for every iteration of the output iterator. A good implementation would onl=
y do so for restricted iterators, but implementations would be free to trea=
t all DefaultConstructible and EqualityComparable iterators the same.</div>=
<div><br class=3D"">2. Let restricted iterators have a <font face=3D"Courie=
r" class=3D"">failed()</font> method, as <font face=3D"Courier" class=3D"">=
ostreambuf_iterator</font> does. The algorithm would have to check this fun=
ction at every iteration. <font face=3D"Courier" class=3D"">failed</font> i=
sn=E2=80=99t a bad name, it would add flexibility to existing&nbsp;<span st=
yle=3D"font-family: Courier;" class=3D"">ostreambuf_iterator</span>&nbsp;co=
de, and it avoids losing the state of the iterator into a singular value.</=
div><div><br class=3D"">3. Throw an exception. Then the algorithm doesn=E2=
=80=99t need to add checks to the critical path. The iterator still has to =
do its own checking, so the efficiency gain depends on whether the compiler=
 in options (1) or (2) would have leveraged inlining to identify the specia=
l case in the iterator code with the algorithm=E2=80=99s <font face=3D"Cour=
ier" class=3D"">it.failed()</font> or <font face=3D"Courier" class=3D"">it =
=3D=3D OutputIterator{}</font> check. (If so, then there=E2=80=99s no perfo=
rmance loss for zero-overhead exceptions to save, so in the overall balance=
, they=E2=80=99re only adding bloat and slowing down the early termination =
case.)</div><div><br class=3D""></div><div>In any case, it would be nice if=
 algorithms defined the state of iterator advancement upon exceptions, i.e.=
 whether <font face=3D"Courier" class=3D"">copy</font> advances the <font f=
ace=3D"Courier" class=3D"">InputIterator</font> or <font face=3D"Courier" c=
lass=3D"">OutputIterator</font> first. However, observing this state requir=
es saving it outside the iterator object itself. Stream iterators do this, =
but most others don=E2=80=99t.</div><div><br class=3D""></div><div>=3D=3D=
=3D</div><div><br class=3D""></div><div>In the balance, I think I favor opt=
ion (2). Pause-and-resume is orthogonal to existing generic iterator functi=
onality. We already have serviceable I/O-oriented iterators in <font face=
=3D"Courier" class=3D"">ostreambuf_iterator</font>&nbsp;and that direction =
would encourage extension of current good (perhaps best) practices. Current=
ly, anything done between batches needs to go into <font face=3D"Courier" c=
lass=3D"">streambuf::underflow</font>, but deriving <font face=3D"Courier" =
class=3D"">streambuf</font> can be inconvenient.</div><div><br class=3D""><=
/div><div>And, (2) doesn=E2=80=99t preclude having (3) as well.</div><div><=
br class=3D""></div><blockquote type=3D"cite" class=3D""><div class=3D""><o=
l style=3D"font-family: Helvetica; font-size: 12px; font-style: normal; fon=
t-variant: normal; font-weight: normal; letter-spacing: normal; line-height=
: normal; orphans: auto; text-align: start; text-indent: 0px; text-transfor=
m: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text=
-stroke-width: 0px;" class=3D""><li class=3D"">The programmer is only inter=
ested in the first n elements of the output.&nbsp; I have personally encoun=
tered situations in which I wanted to use<span class=3D"Apple-converted-spa=
ce">&nbsp;</span><span style=3D"font-family: 'courier new', monospace;" cla=
ss=3D"">std::merge</span><span class=3D"Apple-converted-space">&nbsp;</span=
>in this way.</li><li class=3D"">The programmer needs to operate on a given=
 range of input data in batches.&nbsp; For example, writing data into a mem=
ory-mapped file for communication with another process, or hardware.</li></=
ol></div></blockquote></div><br class=3D""><div class=3D"">(1) is just a ma=
tter of adding an early exit condition, but (2) requires effectively turnin=
g the algorithm into a coroutine or =E2=80=9Cresumable function.=E2=80=9D T=
his is a trivial problem for algorithms like <font face=3D"Courier" class=
=3D"">copy</font> and <font face=3D"Courier" class=3D"">merge</font> which =
return all their internal state in a form allowing it to be passed back int=
o another invocation. Most of the rest you=E2=80=99ve listed should be the =
same, but a closer look would help.</div></body></html>

<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 />

--Apple-Mail=_46DB59EB-6886-4FF2-ACBA-A0380EFE92E2--

.

--nextPart5671826.A4aCVNUkvb
Content-Type: text/plain; charset=UTF-8

> ... why not define an output-restricted iterator category ...?

For three main reasons:

  1) It does not fit with current practice.

     Everywhere else in the STL, wherever a range is called for, it is
     represented in half-open form using a source iterator and limit
     iterator.

     In addition, partial_sort_copy is already output-restricted, and is
     implemented in this way.

  2) It does not fit with future practice.

     Explicit specification of the output range as a half-open range
     pair means that the algorithm can be used as the "4-legged" form
     mentioned in n4128 Section (the ranges proposal), Section 3.3.8
     [1].

     Thus, there would be a straightforward interoperation with ranges,
     when they are introduced.

  3) It seems Byzantine.

     To force iterators to do a range's job requires that the iterator
     be stateful, and seems to be a lot of effort to avoid defining some
     small functions.

     Many of the functions I propose will be nearly textually identical
     to their non-restricted counterparts.  For example, take
     restricted_copy and copy.  They can share a common implementation:

     ----%<-------------------------------------------------------------

     template<class ItA, class ItD>
     std::tuple<ItA, ItD> copy_base(
         ItA a_src, ItA a_lim,
         ItD d_src, ItD d_lim,
         bool restrict_output
     )
     {
         while(a_src != a_lim && (!restrict_output || (d_src != d_lim)))
         {
             *d_src = *a_src;
             ++d_src;
             ++a_src;
         }

         return make_tuple(a_src, d_src);
     }

     template<class ItA, class ItD>
     std::tuple<ItA, ItD> restricted_copy(
         ItA a_src, ItA a_lim,
         ItD d_src, ItD d_lim
     )
     {
         auto lims = copy_base(a_src, a_lim, d_src, d_lim, true);
         return std::get<1>(lims);
     }

     template<class ItA, class ItD>
     ItD copy(
         ItA a_src, ItA a_lim,
         ItD d_src
     )
     {
         // Here, the fourth argument to copy_base could be anything.
         auto lims = copy_base(a_src, a_lim, d_src, d_src, false);
         return std::get<0>(lims);
     }

     ----%<-------------------------------------------------------------

     Implemented like this, there isn't any repeated code, AND all the
     dirty tricks currently used by implementations of std::copy
     (std::memmove for appropriate iterator and data types) can placed
     into copy_base.


Taahir

[1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4128.html#additional-overloads-of-the-algorithms

--

---
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/.

--nextPart5671826.A4aCVNUkvb
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: This is a digitally signed message part.
Content-Transfer-Encoding: 7Bit

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQEcBAABAgAGBQJUwxipAAoJEP0dGB2mOaLG7loH/06VdeMn3O3A9nSEpsqricMf
EsA9N/FbcYbdYPhTrePGQ87Zo4YmYh+SzxQC8XOVaT2lAyJvQLWXuo94j4JNWmQn
kXYVDzrY3XsZ7fLFVtjX9QwC/ek3PM4cQkraKFP7ak+U/arA+Q85uSHGkbh/DKoK
ymtXmUabr+GMjwjZAmw2Rx+P02slR5bIcrg+5hILOobx7J89ejY/oEz+GARXGHTk
MJTPoLyjAdzVixZCP0ZTP5qXwIB/GhsBXXcI0c264QW0jL8ss/scgS781g+ZF9kc
z6vMPvMwsWreCrIvZ2myJUZg0BRKdmJhh3NeRfePosWj3rPvHIfzTiZMqx3OxDU=
=2+2C
-----END PGP SIGNATURE-----

--nextPart5671826.A4aCVNUkvb--


.

--Apple-Mail=_F0AF7771-9781-4319-8BAC-2EDF896F3FA7
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset=UTF-8


> On 2015=E2=80=9301=E2=80=9324, at 11:59 AM, Taahir Ahmed <ahmed.taahir@gm=
ail.com> wrote:
>=20
>> ... why not define an output-restricted iterator category ...?
>=20
> For three main reasons:

Fair points, although it=E2=80=99s not entirely black-and-white. My suggest=
ion jibes with the aspects of current practice that I mentioned, and it can=
 be mapped to ranges, just not in the way described in N4128. It also suppo=
rts things on the fringes of ranges, which aren=E2=80=99t possible by itera=
tor pairs, such as sentinels (e.g., interruption by a watchdog timer).

Also, partial_sort_copy doesn=E2=80=99t quite meet your constraints, becaus=
e you need it to accept a third output iterator argument, for the sake of r=
esuming in the middle. It needs to get an output range plus an extra iterat=
or.

>     Many of the functions I propose will be nearly textually identical
>     to their non-restricted counterparts.  For example, take
>     restricted_copy and copy.  They can share a common implementation:

Is it impossible to define your proposal in terms of four-legged overloads =
of the existing algorithms? If not, your proposal should explain why. There=
 might be a trade-off between introducing new names and having same-named o=
verloads return std::pairs. However, it=E2=80=99s still bound to be surpris=
ing to have the new algorithm to return an <Input,Output> pair even when it=
 does have a new name. Users are going to want to refactor between the diff=
erent versions.

--=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/.

--Apple-Mail=_F0AF7771-9781-4319-8BAC-2EDF896F3FA7
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html; charset=UTF-8

<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html charset=
=3Dutf-8"></head><body style=3D"word-wrap: break-word; -webkit-nbsp-mode: s=
pace; -webkit-line-break: after-white-space;" class=3D""><br class=3D""><di=
v><blockquote type=3D"cite" class=3D""><div class=3D"">On 2015=E2=80=9301=
=E2=80=9324, at 11:59 AM, Taahir Ahmed &lt;<a href=3D"mailto:ahmed.taahir@g=
mail.com" class=3D"">ahmed.taahir@gmail.com</a>&gt; wrote:</div><br class=
=3D"Apple-interchange-newline"><div class=3D""><blockquote type=3D"cite" cl=
ass=3D"">... why not define an output-restricted iterator category ...?<br =
class=3D""></blockquote><br class=3D"">For three main reasons:<br class=3D"=
"></div></blockquote><div><br class=3D""></div><div>Fair points, although i=
t=E2=80=99s not entirely black-and-white. My suggestion jibes with the aspe=
cts of current practice that I mentioned, and it can be mapped to ranges, j=
ust not in the way described in N4128. It also supports things on the fring=
es of ranges, which aren=E2=80=99t possible by iterator pairs, such as sent=
inels (e.g., interruption by a watchdog timer).</div><div><br class=3D""></=
div><div>Also, <font face=3D"Courier" class=3D"">partial_sort_copy</font> d=
oesn=E2=80=99t quite meet your constraints, because you need it to accept a=
 third output iterator argument, for the sake of resuming in the middle. It=
 needs to get an output range plus an extra iterator.</div><br class=3D""><=
blockquote type=3D"cite" class=3D""><div class=3D"">&nbsp; &nbsp; Many of t=
he functions I propose will be nearly textually identical<br class=3D""> &n=
bsp;&nbsp;&nbsp;&nbsp;to their non-restricted counterparts. &nbsp;For examp=
le, take<br class=3D""> &nbsp;&nbsp;&nbsp;&nbsp;restricted_copy and copy. &=
nbsp;They can share a common implementation:<br class=3D""></div></blockquo=
te><div><br class=3D""></div><div>Is it impossible to define your proposal =
in terms of four-legged overloads of the existing algorithms? If not, your =
proposal should explain why. There might be a trade-off between introducing=
 new names and having same-named overloads return <font face=3D"Courier" cl=
ass=3D"">std::pair</font>s. However, it=E2=80=99s still bound to be surpris=
ing to have the new algorithm to return an &lt;Input,Output&gt; pair even w=
hen it does have a new name. Users are going to want to refactor between th=
e different versions.</div></div></body></html>

<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 />

--Apple-Mail=_F0AF7771-9781-4319-8BAC-2EDF896F3FA7--

.

------=_Part_3822_1005245251.1422215760492
Content-Type: multipart/alternative;
 boundary="----=_Part_3823_903082608.1422215760492"

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



On Friday, January 23, 2015 at 9:16:25 PM UTC-5, David Krauss wrote:
>
>
> On 2015=E2=80=9301=E2=80=9324, at 8:26 AM, ahmed....@gmail.com <javascrip=
t:> wrote:
>
> However, many algorithms in <algorithm> would benefit from having an=20
> output-restricted variant, for at least two reasons:
>
>
> Rather than rewrite all the algorithms, why not define an=20
> output-restricted iterator category (perhaps together with an adaptor to=
=20
> generate one from any unrestricted output iterator, and perhaps adding=20
> non-output iterators into the mix), and add constraints to the existing=
=20
> algorithms to ensure that the templates do the right thing?
>

I actually had need of an output-restricted copy recently and ended up=20
writing it, but I tried this suggestion and it's pretty short, so I'll post=
=20
it here.

#include <algorithm>
#include <iostream>
#include <iterator>
=20
template<class Iterator>
struct flip_iterator
{
  using traits =3D std::iterator_traits<Iterator>;

  struct flip_assign {
    typename traits::reference ref;

    template<class T>
    flip_assign& operator =3D (T& t) { t =3D ref;
                                     return *this; }
  };

  using iterator_category =3D std::output_iterator_tag;

  using value_type =3D typename traits::value_type;
  using reference  =3D flip_assign;
  using pointer =3D typename traits::pointer;
  using difference_type =3D typename traits::difference_type;

  Iterator iter;

  flip_iterator(Iterator iter) : iter(iter) { }

  flip_iterator& operator ++ () { iter++; }

  flip_iterator operator ++ (int) { auto ret =3D *this;
                                    ++(*this);
                                    return ret; }

  reference operator * () { return flip_assign{*iter}; }
};


template<class Iterator>
flip_iterator<Iterator> flipped(Iterator iter) {
  return flip_iterator<Iterator>(iter);
}


int main() {
  int ys[3];
  std::copy(ys, ys+3, flipped(std::istream_iterator<int>(std::cin)));
  std::copy(ys, ys+3, std::ostream_iterator<int>(std::cout));
  return 0;
}

This lets me write certain algorithms very simply.

template<class ForwardIterator, class ForwardIterator, class Predicate,=20
class T>
void replace_if(ForwardIterator first, ForwardIterator last,
                Predicate pred, const T& new_value) {
  copy_if(first, last,
          flipped(filler(std::cref(new_value))),
          pred);
  // Note: filler returns pseudo iterator, it, where *it =3D new_val
}
template<class ForwardIterator, class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last,
              Generator gen)
{
  copy(first, last, flipped(generator(std::move(gen))));
  // Note: generator returns a pseudo iterator where *it =3D gen()
};

Although this solution feels a little hacky and I'm sure it has pitfalls.=
=20
Wouldn't an output-restricted algorithm be more idiomatic? Or do you mean=
=20
that some sort of iterator_traits property should dispatch between=20
"copy(from1, from2, to)" and "copy(to1, to2, from)"?
=20

>
> There are several approaches to getting algorithms to terminate:
>
> 1. Advance the iterator to a singular value which is equal to the=20
> default-constructed value of the iterator type. IMHO this fits most=20
> elegantly with the existing iterator scheme, but current ostream_iterator=
=20
> and ostreambuf_iterator don=E2=80=99t support default construction nor eq=
uality=20
> checks.
>
> The algorithm would have to check against this value for every iteration=
=20
> of the output iterator. A good implementation would only do so for=20
> restricted iterators, but implementations would be free to treat all=20
> DefaultConstructible and EqualityComparable iterators the same.
>
> 2. Let restricted iterators have a failed() method, as ostreambuf_iterato=
r=20
> does. The algorithm would have to check this function at every iteration.=
=20
> failed isn=E2=80=99t a bad name, it would add flexibility to existing=20
> ostreambuf_iterator code, and it avoids losing the state of the iterator=
=20
> into a singular value.
>
> 3. Throw an exception. Then the algorithm doesn=E2=80=99t need to add che=
cks to=20
> the critical path. The iterator still has to do its own checking, so the=
=20
> efficiency gain depends on whether the compiler in options (1) or (2) wou=
ld=20
> have leveraged inlining to identify the special case in the iterator code=
=20
> with the algorithm=E2=80=99s it.failed() or it =3D=3D OutputIterator{} ch=
eck. (If so,=20
> then there=E2=80=99s no performance loss for zero-overhead exceptions to =
save, so=20
> in the overall balance, they=E2=80=99re only adding bloat and slowing dow=
n the=20
> early termination case.)
>
> In any case, it would be nice if algorithms defined the state of iterator=
=20
> advancement upon exceptions, i.e. whether copy advances the InputIterator=
=20
> or OutputIterator first. However, observing this state requires saving it=
=20
> outside the iterator object itself. Stream iterators do this, but most=20
> others don=E2=80=99t.
>
> =3D=3D=3D
>
> In the balance, I think I favor option (2). Pause-and-resume is orthogona=
l=20
> to existing generic iterator functionality. We already have serviceable=
=20
> I/O-oriented iterators in ostreambuf_iterator and that direction would=20
> encourage extension of current good (perhaps best) practices. Currently,=
=20
> anything done between batches needs to go into streambuf::underflow, but=
=20
> deriving streambuf can be inconvenient.
>
> And, (2) doesn=E2=80=99t preclude having (3) as well.
>
>
>    1. The programmer is only interested in the first n elements of the=20
>    output.  I have personally encountered situations in which I wanted to=
 use
>     std::merge in this way.
>    2. The programmer needs to operate on a given range of input data in=
=20
>    batches.  For example, writing data into a memory-mapped file for=20
>    communication with another process, or hardware.
>
>
> (1) is just a matter of adding an early exit condition, but (2) requires=
=20
> effectively turning the algorithm into a coroutine or =E2=80=9Cresumable =
function.=E2=80=9D=20
> This is a trivial problem for algorithms like copy and merge which return=
=20
> all their internal state in a form allowing it to be passed back into=20
> another invocation. Most of the rest you=E2=80=99ve listed should be the =
same, but=20
> a closer look would help.
>

--=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_3823_903082608.1422215760492
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Friday, January 23, 2015 at 9:16:25 PM UTC-5, D=
avid Krauss wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;marg=
in-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div style=
=3D"word-wrap:break-word"><br><div><blockquote type=3D"cite"><div>On 2015=
=E2=80=9301=E2=80=9324, at 8:26 AM, <a href=3D"javascript:" target=3D"_blan=
k" gdf-obfuscated-mailto=3D"jVZ9oiWEorIJ" rel=3D"nofollow" onmousedown=3D"t=
his.href=3D'javascript:';return true;" onclick=3D"this.href=3D'javascript:'=
;return true;">ahmed....@gmail.com</a> wrote:</div><br><div><span style=3D"=
font-family:Helvetica;font-size:12px;font-style:normal;font-variant:normal;=
font-weight:normal;letter-spacing:normal;line-height:normal;text-align:star=
t;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;f=
loat:none;display:inline!important">However, many algorithms in<span>&nbsp;=
</span></span><span style=3D"font-size:12px;font-style:normal;font-variant:=
normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-ali=
gn:start;text-indent:0px;text-transform:none;white-space:normal;word-spacin=
g:0px;font-family:'courier new',monospace">&lt;algorithm&gt;<span>&nbsp;</s=
pan></span><span style=3D"font-family:Helvetica;font-size:12px;font-style:n=
ormal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-hei=
ght:normal;text-align:start;text-indent:0px;text-transform:none;white-space=
:normal;word-spacing:0px;float:none;display:inline!important">would benefit=
 from having an output-restricted variant, for at least two reasons:</span>=
<br style=3D"font-family:Helvetica;font-size:12px;font-style:normal;font-va=
riant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;te=
xt-align:start;text-indent:0px;text-transform:none;white-space:normal;word-=
spacing:0px"></div></blockquote><div><br></div><div>Rather than rewrite all=
 the algorithms, why not define an output-restricted iterator category (per=
haps together with an adaptor to generate one from any unrestricted output =
iterator, and perhaps adding non-output iterators into the mix), and add co=
nstraints to the existing algorithms to ensure that the templates do the ri=
ght thing?</div></div></div></blockquote><div><br></div><div>I actually had=
 need of an output-restricted copy recently and ended up writing it, but I =
tried this suggestion and it's pretty short, so I'll post it here.</div><di=
v><br></div><div><div class=3D"prettyprint" style=3D"border: 1px solid rgb(=
187, 187, 187); word-wrap: break-word; background-color: rgb(250, 250, 250)=
;"><code class=3D"prettyprint"><div class=3D"subprettyprint"><span style=3D=
"color: #800;" class=3D"styled-by-prettify">#include</span><span style=3D"c=
olor: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #08=
0;" class=3D"styled-by-prettify">&lt;algorithm&gt;</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"><br></span><span style=3D"color: #8=
00;" class=3D"styled-by-prettify">#include</span><span style=3D"color: #000=
;" class=3D"styled-by-prettify"> </span><span style=3D"color: #080;" class=
=3D"styled-by-prettify">&lt;iostream&gt;</span><span style=3D"color: #000;"=
 class=3D"styled-by-prettify"><br></span><span style=3D"color: #800;" class=
=3D"styled-by-prettify">#include</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"> </span><span style=3D"color: #080;" class=3D"style=
d-by-prettify">&lt;iterator&gt;</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify"><br>&nbsp;<br></span><span style=3D"color: #008;" clas=
s=3D"styled-by-prettify">template</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">&lt;</span><span style=3D"color: #008;" class=3D"st=
yled-by-prettify">class</span><span style=3D"color: #000;" class=3D"styled-=
by-prettify"> </span><span style=3D"color: #606;" class=3D"styled-by-pretti=
fy">Iterator</span><span style=3D"color: #660;" class=3D"styled-by-prettify=
">&gt;</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>=
</span><span style=3D"color: #008;" class=3D"styled-by-prettify">struct</sp=
an><span style=3D"color: #000;" class=3D"styled-by-prettify"> flip_iterator=
<br></span><span style=3D"color: #660;" class=3D"styled-by-prettify">{</spa=
n><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; </sp=
an><span style=3D"color: #008;" class=3D"styled-by-prettify">using</span><s=
pan style=3D"color: #000;" class=3D"styled-by-prettify"> traits </span><spa=
n style=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> std</span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">::</span><span style=3D"color: #00=
0;" class=3D"styled-by-prettify">iterator_traits</span><span style=3D"color=
: #660;" class=3D"styled-by-prettify">&lt;</span><span style=3D"color: #606=
;" class=3D"styled-by-prettify">Iterator</span><span style=3D"color: #660;"=
 class=3D"styled-by-prettify">&gt;;</span><span style=3D"color: #000;" clas=
s=3D"styled-by-prettify"><br><br>&nbsp; </span><span style=3D"color: #008;"=
 class=3D"styled-by-prettify">struct</span><span style=3D"color: #000;" cla=
ss=3D"styled-by-prettify"> flip_assign </span><span style=3D"color: #660;" =
class=3D"styled-by-prettify">{</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify"><br>&nbsp; &nbsp; </span><span style=3D"color: #008;" c=
lass=3D"styled-by-prettify">typename</span><span style=3D"color: #000;" cla=
ss=3D"styled-by-prettify"> traits</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">::</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify">reference </span><span style=3D"color: #008;" class=3D"styl=
ed-by-prettify">ref</span><span style=3D"color: #660;" class=3D"styled-by-p=
rettify">;</span><span style=3D"color: #000;" class=3D"styled-by-prettify">=
<br><br>&nbsp; &nbsp; </span><span style=3D"color: #008;" class=3D"styled-b=
y-prettify">template</span><span style=3D"color: #660;" class=3D"styled-by-=
prettify">&lt;</span><span style=3D"color: #008;" class=3D"styled-by-pretti=
fy">class</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> =
T</span><span style=3D"color: #660;" class=3D"styled-by-prettify">&gt;</spa=
n><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbs=
p; flip_assign</span><span style=3D"color: #660;" class=3D"styled-by-pretti=
fy">&amp;</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> =
</span><span style=3D"color: #008;" class=3D"styled-by-prettify">operator</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><spa=
n style=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color=
: #660;" class=3D"styled-by-prettify">(</span><span style=3D"color: #000;" =
class=3D"styled-by-prettify">T</span><span style=3D"color: #660;" class=3D"=
styled-by-prettify">&amp;</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"> t</span><span style=3D"color: #660;" class=3D"styled-by-pre=
ttify">)</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> <=
/span><span style=3D"color: #660;" class=3D"styled-by-prettify">{</span><sp=
an style=3D"color: #000;" class=3D"styled-by-prettify"> t </span><span styl=
e=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><span style=3D"co=
lor: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #008=
;" class=3D"styled-by-prettify">ref</span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">;</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;=
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbs=
p;</span><span style=3D"color: #008;" class=3D"styled-by-prettify">return</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><spa=
n style=3D"color: #660;" class=3D"styled-by-prettify">*</span><span style=
=3D"color: #008;" class=3D"styled-by-prettify">this</span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">;</span><span style=3D"color: #000=
;" class=3D"styled-by-prettify"> </span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">}</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"><br>&nbsp; </span><span style=3D"color: #660;" class=3D"styl=
ed-by-prettify">};</span><span style=3D"color: #000;" class=3D"styled-by-pr=
ettify"><br><br>&nbsp; </span><span style=3D"color: #008;" class=3D"styled-=
by-prettify">using</span><span style=3D"color: #000;" class=3D"styled-by-pr=
ettify"> iterator_category </span><span style=3D"color: #660;" class=3D"sty=
led-by-prettify">=3D</span><span style=3D"color: #000;" class=3D"styled-by-=
prettify"> std</span><span style=3D"color: #660;" class=3D"styled-by-pretti=
fy">::</span><span style=3D"color: #000;" class=3D"styled-by-prettify">outp=
ut_iterator_tag</span><span style=3D"color: #660;" class=3D"styled-by-prett=
ify">;</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>=
<br>&nbsp; </span><span style=3D"color: #008;" class=3D"styled-by-prettify"=
>using</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> val=
ue_type </span><span style=3D"color: #660;" class=3D"styled-by-prettify">=
=3D</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span=
><span style=3D"color: #008;" class=3D"styled-by-prettify">typename</span><=
span style=3D"color: #000;" class=3D"styled-by-prettify"> traits</span><spa=
n style=3D"color: #660;" class=3D"styled-by-prettify">::</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify">value_type</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">;</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"><br>&nbsp; </span><span style=3D"colo=
r: #008;" class=3D"styled-by-prettify">using</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify"> reference &nbsp;</span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">=3D</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify"> flip_assign</span><span style=3D"color: =
#660;" class=3D"styled-by-prettify">;</span><span style=3D"color: #000;" cl=
ass=3D"styled-by-prettify"><br>&nbsp; </span><span style=3D"color: #008;" c=
lass=3D"styled-by-prettify">using</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"> pointer </span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">=3D</span><span style=3D"color: #000;" class=3D"sty=
led-by-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by-pr=
ettify">typename</span><span style=3D"color: #000;" class=3D"styled-by-pret=
tify"> traits</span><span style=3D"color: #660;" class=3D"styled-by-prettif=
y">::</span><span style=3D"color: #000;" class=3D"styled-by-prettify">point=
er</span><span style=3D"color: #660;" class=3D"styled-by-prettify">;</span>=
<span style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; </span=
><span style=3D"color: #008;" class=3D"styled-by-prettify">using</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify"> difference_type </sp=
an><span style=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=
=3D"color: #008;" class=3D"styled-by-prettify">typename</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> traits</span><span style=3D=
"color: #660;" class=3D"styled-by-prettify">::</span><span style=3D"color: =
#000;" class=3D"styled-by-prettify">difference_type</span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">;</span><span style=3D"color: #000=
;" class=3D"styled-by-prettify"><br><br>&nbsp; </span><span style=3D"color:=
 #606;" class=3D"styled-by-prettify">Iterator</span><span style=3D"color: #=
000;" class=3D"styled-by-prettify"> iter</span><span style=3D"color: #660;"=
 class=3D"styled-by-prettify">;</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify"><br><br>&nbsp; flip_iterator</span><span style=3D"colo=
r: #660;" class=3D"styled-by-prettify">(</span><span style=3D"color: #606;"=
 class=3D"styled-by-prettify">Iterator</span><span style=3D"color: #000;" c=
lass=3D"styled-by-prettify"> iter</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">)</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"> </span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">:</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> it=
er</span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span>=
<span style=3D"color: #000;" class=3D"styled-by-prettify">iter</span><span =
style=3D"color: #660;" class=3D"styled-by-prettify">)</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #6=
60;" class=3D"styled-by-prettify">{</span><span style=3D"color: #000;" clas=
s=3D"styled-by-prettify"> </span><span style=3D"color: #660;" class=3D"styl=
ed-by-prettify">}</span><span style=3D"color: #000;" class=3D"styled-by-pre=
ttify"><br><br>&nbsp; flip_iterator</span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">&amp;</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by=
-prettify">operator</span><span style=3D"color: #000;" class=3D"styled-by-p=
rettify"> </span><span style=3D"color: #660;" class=3D"styled-by-prettify">=
++</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span>=
<span style=3D"color: #660;" class=3D"styled-by-prettify">()</span><span st=
yle=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">{</span><span style=3D"color: #000=
;" class=3D"styled-by-prettify"> iter</span><span style=3D"color: #660;" cl=
ass=3D"styled-by-prettify">++;</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify"> </span><span style=3D"color: #660;" class=3D"styled-by=
-prettify">}</span><span style=3D"color: #000;" class=3D"styled-by-prettify=
"><br><br>&nbsp; flip_iterator </span><span style=3D"color: #008;" class=3D=
"styled-by-prettify">operator</span><span style=3D"color: #000;" class=3D"s=
tyled-by-prettify"> </span><span style=3D"color: #660;" class=3D"styled-by-=
prettify">++</span><span style=3D"color: #000;" class=3D"styled-by-prettify=
"> </span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span=
><span style=3D"color: #008;" class=3D"styled-by-prettify">int</span><span =
style=3D"color: #660;" class=3D"styled-by-prettify">)</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #6=
60;" class=3D"styled-by-prettify">{</span><span style=3D"color: #000;" clas=
s=3D"styled-by-prettify"> </span><span style=3D"color: #008;" class=3D"styl=
ed-by-prettify">auto</span><span style=3D"color: #000;" class=3D"styled-by-=
prettify"> ret </span><span style=3D"color: #660;" class=3D"styled-by-prett=
ify">=3D</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> <=
/span><span style=3D"color: #660;" class=3D"styled-by-prettify">*</span><sp=
an style=3D"color: #008;" class=3D"styled-by-prettify">this</span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">;</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; &nb=
sp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &=
nbsp; &nbsp; &nbsp; </span><span style=3D"color: #660;" class=3D"styled-by-=
prettify">++(*</span><span style=3D"color: #008;" class=3D"styled-by-pretti=
fy">this</span><span style=3D"color: #660;" class=3D"styled-by-prettify">);=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp;=
 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbs=
p; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; </span><span style=3D"color: #=
008;" class=3D"styled-by-prettify">return</span><span style=3D"color: #000;=
" class=3D"styled-by-prettify"> ret</span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">;</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify"> </span><span style=3D"color: #660;" class=3D"styled-by-pre=
ttify">}</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><b=
r><br>&nbsp; reference </span><span style=3D"color: #008;" class=3D"styled-=
by-prettify">operator</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify"> </span><span style=3D"color: #660;" class=3D"styled-by-prettify=
">*</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span=
><span style=3D"color: #660;" class=3D"styled-by-prettify">()</span><span s=
tyle=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"c=
olor: #660;" class=3D"styled-by-prettify">{</span><span style=3D"color: #00=
0;" class=3D"styled-by-prettify"> </span><span style=3D"color: #008;" class=
=3D"styled-by-prettify">return</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify"> flip_assign</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">{*</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify">iter</span><span style=3D"color: #660;" class=3D"styled-by-=
prettify">};</span><span style=3D"color: #000;" class=3D"styled-by-prettify=
"> </span><span style=3D"color: #660;" class=3D"styled-by-prettify">}</span=
><span style=3D"color: #000;" class=3D"styled-by-prettify"><br></span><span=
 style=3D"color: #660;" class=3D"styled-by-prettify">};</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"><br><br><br></span><span sty=
le=3D"color: #008;" class=3D"styled-by-prettify">template</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">&lt;</span><span style=3D"co=
lor: #008;" class=3D"styled-by-prettify">class</span><span style=3D"color: =
#000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #606;" cl=
ass=3D"styled-by-prettify">Iterator</span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">&gt;</span><span style=3D"color: #000;" class=3D"s=
tyled-by-prettify"><br>flip_iterator</span><span style=3D"color: #660;" cla=
ss=3D"styled-by-prettify">&lt;</span><span style=3D"color: #606;" class=3D"=
styled-by-prettify">Iterator</span><span style=3D"color: #660;" class=3D"st=
yled-by-prettify">&gt;</span><span style=3D"color: #000;" class=3D"styled-b=
y-prettify"> flipped</span><span style=3D"color: #660;" class=3D"styled-by-=
prettify">(</span><span style=3D"color: #606;" class=3D"styled-by-prettify"=
>Iterator</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> =
iter</span><span style=3D"color: #660;" class=3D"styled-by-prettify">)</spa=
n><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span s=
tyle=3D"color: #660;" class=3D"styled-by-prettify">{</span><span style=3D"c=
olor: #000;" class=3D"styled-by-prettify"><br>&nbsp; </span><span style=3D"=
color: #008;" class=3D"styled-by-prettify">return</span><span style=3D"colo=
r: #000;" class=3D"styled-by-prettify"> flip_iterator</span><span style=3D"=
color: #660;" class=3D"styled-by-prettify">&lt;</span><span style=3D"color:=
 #606;" class=3D"styled-by-prettify">Iterator</span><span style=3D"color: #=
660;" class=3D"styled-by-prettify">&gt;(</span><span style=3D"color: #000;"=
 class=3D"styled-by-prettify">iter</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">);</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify"><br></span><span style=3D"color: #660;" class=3D"styled-by-=
prettify">}</span><span style=3D"color: #000;" class=3D"styled-by-prettify"=
><br><br><br></span><span style=3D"color: #008;" class=3D"styled-by-prettif=
y">int</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> mai=
n</span><span style=3D"color: #660;" class=3D"styled-by-prettify">()</span>=
<span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">{</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"><br>&nbsp; </span><span style=3D"co=
lor: #008;" class=3D"styled-by-prettify">int</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify"> ys</span><span style=3D"color: #660;" cl=
ass=3D"styled-by-prettify">[</span><span style=3D"color: #066;" class=3D"st=
yled-by-prettify">3</span><span style=3D"color: #660;" class=3D"styled-by-p=
rettify">];</span><span style=3D"color: #000;" class=3D"styled-by-prettify"=
><br>&nbsp; std</span><span style=3D"color: #660;" class=3D"styled-by-prett=
ify">::</span><span style=3D"color: #000;" class=3D"styled-by-prettify">cop=
y</span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><=
span style=3D"color: #000;" class=3D"styled-by-prettify">ys</span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"> ys</span><span style=3D"color: #66=
0;" class=3D"styled-by-prettify">+</span><span style=3D"color: #066;" class=
=3D"styled-by-prettify">3</span><span style=3D"color: #660;" class=3D"style=
d-by-prettify">,</span><span style=3D"color: #000;" class=3D"styled-by-pret=
tify"> flipped</span><span style=3D"color: #660;" class=3D"styled-by-pretti=
fy">(</span><span style=3D"color: #000;" class=3D"styled-by-prettify">std</=
span><span style=3D"color: #660;" class=3D"styled-by-prettify">::</span><sp=
an style=3D"color: #000;" class=3D"styled-by-prettify">istream_iterator</sp=
an><span style=3D"color: #080;" class=3D"styled-by-prettify">&lt;int&gt;</s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span=
 style=3D"color: #000;" class=3D"styled-by-prettify">std</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">::</span><span style=3D"colo=
r: #000;" class=3D"styled-by-prettify">cin</span><span style=3D"color: #660=
;" class=3D"styled-by-prettify">)));</span><span style=3D"color: #000;" cla=
ss=3D"styled-by-prettify"><br>&nbsp; std</span><span style=3D"color: #660;"=
 class=3D"styled-by-prettify">::</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify">copy</span><span style=3D"color: #660;" class=3D"st=
yled-by-prettify">(</span><span style=3D"color: #000;" class=3D"styled-by-p=
rettify">ys</span><span style=3D"color: #660;" class=3D"styled-by-prettify"=
>,</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> ys</spa=
n><span style=3D"color: #660;" class=3D"styled-by-prettify">+</span><span s=
tyle=3D"color: #066;" class=3D"styled-by-prettify">3</span><span style=3D"c=
olor: #660;" class=3D"styled-by-prettify">,</span><span style=3D"color: #00=
0;" class=3D"styled-by-prettify"> std</span><span style=3D"color: #660;" cl=
ass=3D"styled-by-prettify">::</span><span style=3D"color: #000;" class=3D"s=
tyled-by-prettify">ostream_iterator</span><span style=3D"color: #080;" clas=
s=3D"styled-by-prettify">&lt;int&gt;</span><span style=3D"color: #660;" cla=
ss=3D"styled-by-prettify">(</span><span style=3D"color: #000;" class=3D"sty=
led-by-prettify">std</span><span style=3D"color: #660;" class=3D"styled-by-=
prettify">::</span><span style=3D"color: #000;" class=3D"styled-by-prettify=
">cout</span><span style=3D"color: #660;" class=3D"styled-by-prettify">));<=
/span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; =
</span><span style=3D"color: #008;" class=3D"styled-by-prettify">return</sp=
an><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span =
style=3D"color: #066;" class=3D"styled-by-prettify">0</span><span style=3D"=
color: #660;" class=3D"styled-by-prettify">;</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify"><br></span><span style=3D"color: #660;" c=
lass=3D"styled-by-prettify">}</span></div></code></div><div><br></div></div=
><div>This lets me write certain algorithms very simply.</div><div><br></di=
v><div><div class=3D"prettyprint" style=3D"border: 1px solid rgb(187, 187, =
187); word-wrap: break-word; background-color: rgb(250, 250, 250);"><code c=
lass=3D"prettyprint"><div class=3D"subprettyprint"><span style=3D"color: #0=
08;" class=3D"styled-by-prettify">template</span><span style=3D"color: #660=
;" class=3D"styled-by-prettify">&lt;</span><span style=3D"color: #008;" cla=
ss=3D"styled-by-prettify">class</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify"> </span><span style=3D"color: #606;" class=3D"styled-b=
y-prettify">ForwardIterator</span><span style=3D"color: #660;" class=3D"sty=
led-by-prettify">,</span><span style=3D"color: #000;" class=3D"styled-by-pr=
ettify"> </span><span style=3D"color: #008;" class=3D"styled-by-prettify">c=
lass</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </spa=
n><span style=3D"color: rgb(102, 0, 102); font-size: 13.3333339691162px;"><=
span style=3D"color: #606;" class=3D"styled-by-prettify">ForwardIterator</s=
pan></span><span style=3D"color: #660;" class=3D"styled-by-prettify">,</spa=
n><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span s=
tyle=3D"color: #008;" class=3D"styled-by-prettify">class</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color=
: #606;" class=3D"styled-by-prettify">Predicate</span><span style=3D"color:=
 #660;" class=3D"styled-by-prettify">,</span><span style=3D"color: #000;" c=
lass=3D"styled-by-prettify"> </span><span style=3D"color: #008;" class=3D"s=
tyled-by-prettify">class</span><span style=3D"color: #000;" class=3D"styled=
-by-prettify"> T</span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">&gt;</span><span style=3D"color: #000;" class=3D"styled-by-prettify">=
<br></span><span style=3D"color: #008;" class=3D"styled-by-prettify">void</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify"> replace_if<=
/span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><sp=
an style=3D"color: #606;" class=3D"styled-by-prettify">ForwardIterator</spa=
n><span style=3D"color: #000;" class=3D"styled-by-prettify"> first</span><s=
pan style=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color=
: rgb(102, 0, 102); font-size: 13.3333339691162px;"><span style=3D"color: #=
606;" class=3D"styled-by-prettify">ForwardIterator</span></span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color=
: #008;" class=3D"styled-by-prettify">last</span><span style=3D"color: #660=
;" class=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp=
; &nbsp; </span><span style=3D"color: #606;" class=3D"styled-by-prettify">P=
redicate</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> p=
red</span><span style=3D"color: #660;" class=3D"styled-by-prettify">,</span=
><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span st=
yle=3D"color: #008;" class=3D"styled-by-prettify">const</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> T</span><span style=3D"colo=
r: #660;" class=3D"styled-by-prettify">&amp;</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify"> new_value</span><span style=3D"color: #6=
60;" class=3D"styled-by-prettify">)</span><span style=3D"color: #000;" clas=
s=3D"styled-by-prettify"> </span><span style=3D"color: #660;" class=3D"styl=
ed-by-prettify">{</span><span style=3D"color: #000;" class=3D"styled-by-pre=
ttify"><br>&nbsp; copy_if</span><span style=3D"color: #660;" class=3D"style=
d-by-prettify">(</span><span style=3D"color: #000;" class=3D"styled-by-pret=
tify">first</span><span style=3D"color: #660;" class=3D"styled-by-prettify"=
>,</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span>=
<span style=3D"color: #008;" class=3D"styled-by-prettify">last</span><span =
style=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; =
&nbsp; flipped</span><span style=3D"color: #660;" class=3D"styled-by-pretti=
fy">(</span><span style=3D"color: #000;" class=3D"styled-by-prettify">fille=
r</span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><=
span style=3D"color: #000;" class=3D"styled-by-prettify">std</span><span st=
yle=3D"color: #660;" class=3D"styled-by-prettify">::</span><span style=3D"c=
olor: #000;" class=3D"styled-by-prettify">cref</span><span style=3D"color: =
#660;" class=3D"styled-by-prettify">(</span><span style=3D"color: #000;" cl=
ass=3D"styled-by-prettify">new_value</span><span style=3D"color: #660;" cla=
ss=3D"styled-by-prettify">))),</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; pred</span><span=
 style=3D"color: #660;" class=3D"styled-by-prettify">);</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; </span><span styl=
e=3D"color: #800;" class=3D"styled-by-prettify">// Note: filler returns pse=
udo iterator, it, where *it =3D new_val</span><span style=3D"color: #000;" =
class=3D"styled-by-prettify"><br></span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">}</span></div></code></div><div><div class=3D"prett=
yprint" style=3D"border: 1px solid rgb(187, 187, 187); word-wrap: break-wor=
d; background-color: rgb(250, 250, 250);"><code class=3D"prettyprint"><div =
class=3D"subprettyprint"><span style=3D"color: #008;" class=3D"styled-by-pr=
ettify">template</span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">&lt;</span><span style=3D"color: #008;" class=3D"styled-by-prettify">=
class</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </sp=
an><span style=3D"color: #606;" class=3D"styled-by-prettify">ForwardIterato=
r</span><span style=3D"color: #660;" class=3D"styled-by-prettify">,</span><=
span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span styl=
e=3D"color: #008;" class=3D"styled-by-prettify">class</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: rg=
b(102, 0, 102); font-size: 13.3333339691162px;"><span style=3D"color: #606;=
" class=3D"styled-by-prettify">ForwardIterator</span></span><span style=3D"=
color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify"> </span><span style=3D"color: #008;" clas=
s=3D"styled-by-prettify">class</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify"> </span><span style=3D"color: #606;" class=3D"styled-by=
-prettify">Generator</span><span style=3D"color: #660;" class=3D"styled-by-=
prettify">&gt;</span><span style=3D"color: #000;" class=3D"styled-by-pretti=
fy"><br></span><span style=3D"color: #008;" class=3D"styled-by-prettify">vo=
id</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> generat=
e</span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><=
span style=3D"color: #606;" class=3D"styled-by-prettify">ForwardIterator</s=
pan><span style=3D"color: #000;" class=3D"styled-by-prettify"> first</span>=
<span style=3D"color: #660;" class=3D"styled-by-prettify">,</span><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"col=
or: rgb(102, 0, 102); font-size: 13.3333339691162px;"><span style=3D"color:=
 #606;" class=3D"styled-by-prettify">ForwardIterator</span></span><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"col=
or: #008;" class=3D"styled-by-prettify">last</span><span style=3D"color: #6=
60;" class=3D"styled-by-prettify">,</span><span style=3D"color: #000;" clas=
s=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbs=
p; </span><span style=3D"color: #606;" class=3D"styled-by-prettify">Generat=
or</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> gen</sp=
an><span style=3D"color: #660;" class=3D"styled-by-prettify">)</span><span =
style=3D"color: #000;" class=3D"styled-by-prettify"><br></span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">{</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"><br>&nbsp; copy</span><span style=3D"=
color: #660;" class=3D"styled-by-prettify">(</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify">first</span><span style=3D"color: #660;" =
class=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by=
-prettify">last</span><span style=3D"color: #660;" class=3D"styled-by-prett=
ify">,</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> fli=
pped</span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</spa=
n><span style=3D"color: #000;" class=3D"styled-by-prettify">generator</span=
><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span st=
yle=3D"color: #000;" class=3D"styled-by-prettify">std</span><span style=3D"=
color: #660;" class=3D"styled-by-prettify">::</span><span style=3D"color: #=
000;" class=3D"styled-by-prettify">move</span><span style=3D"color: #660;" =
class=3D"styled-by-prettify">(</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify">gen</span><span style=3D"color: #660;" class=3D"styled-=
by-prettify">))));</span><span style=3D"color: #000;" class=3D"styled-by-pr=
ettify"><br>&nbsp; </span><span style=3D"color: #800;" class=3D"styled-by-p=
rettify">// Note: generator returns a pseudo iterator where *it =3D gen()</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br></span><=
span style=3D"color: #660;" class=3D"styled-by-prettify">};</span></div></c=
ode></div><div><br></div></div></div><div>Although this solution feels a li=
ttle hacky and I'm sure it has pitfalls. Wouldn't an output-restricted algo=
rithm be more idiomatic? Or do you mean that some sort of iterator_traits p=
roperty should dispatch between "copy(from1, from2, to)" and "copy(to1, to2=
, from)"?</div><div>&nbsp;</div><blockquote class=3D"gmail_quote" style=3D"=
margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;=
"><div style=3D"word-wrap:break-word"><div><div><br></div><div>There are se=
veral approaches to getting algorithms to terminate:</div><div><br></div><d=
iv>1. Advance the iterator to a singular value which is equal to the defaul=
t-constructed value of the iterator type. IMHO this fits most elegantly wit=
h the existing iterator scheme, but current <font face=3D"Courier">ostream_=
iterator</font> and <font face=3D"Courier">ostreambuf_iterator</font> don=
=E2=80=99t support default construction nor equality checks.</div><div><br>=
</div><div>The algorithm would have to check against this value for every i=
teration of the output iterator. A good implementation would only do so for=
 restricted iterators, but implementations would be free to treat all Defau=
ltConstructible and EqualityComparable iterators the same.</div><div><br>2.=
 Let restricted iterators have a <font face=3D"Courier">failed()</font> met=
hod, as <font face=3D"Courier">ostreambuf_iterator</font> does. The algorit=
hm would have to check this function at every iteration. <font face=3D"Cour=
ier">failed</font> isn=E2=80=99t a bad name, it would add flexibility to ex=
isting&nbsp;<span style=3D"font-family:Courier">ostreambuf_iterator</span>&=
nbsp;<wbr>code, and it avoids losing the state of the iterator into a singu=
lar value.</div><div><br>3. Throw an exception. Then the algorithm doesn=E2=
=80=99t need to add checks to the critical path. The iterator still has to =
do its own checking, so the efficiency gain depends on whether the compiler=
 in options (1) or (2) would have leveraged inlining to identify the specia=
l case in the iterator code with the algorithm=E2=80=99s <font face=3D"Cour=
ier">it.failed()</font> or <font face=3D"Courier">it =3D=3D OutputIterator{=
}</font> check. (If so, then there=E2=80=99s no performance loss for zero-o=
verhead exceptions to save, so in the overall balance, they=E2=80=99re only=
 adding bloat and slowing down the early termination case.)</div><div><br><=
/div><div>In any case, it would be nice if algorithms defined the state of =
iterator advancement upon exceptions, i.e. whether <font face=3D"Courier">c=
opy</font> advances the <font face=3D"Courier">InputIterator</font> or <fon=
t face=3D"Courier">OutputIterator</font> first. However, observing this sta=
te requires saving it outside the iterator object itself. Stream iterators =
do this, but most others don=E2=80=99t.</div><div><br></div><div>=3D=3D=3D<=
/div><div><br></div><div>In the balance, I think I favor option (2). Pause-=
and-resume is orthogonal to existing generic iterator functionality. We alr=
eady have serviceable I/O-oriented iterators in <font face=3D"Courier">ostr=
eambuf_iterator</font>&nbsp;and that direction would encourage extension of=
 current good (perhaps best) practices. Currently, anything done between ba=
tches needs to go into <font face=3D"Courier">streambuf::underflow</font>, =
but deriving <font face=3D"Courier">streambuf</font> can be inconvenient.</=
div><div><br></div><div>And, (2) doesn=E2=80=99t preclude having (3) as wel=
l.</div><div><br></div><blockquote type=3D"cite"><div><ol style=3D"font-fam=
ily:Helvetica;font-size:12px;font-style:normal;font-variant:normal;font-wei=
ght:normal;letter-spacing:normal;line-height:normal;text-align:start;text-i=
ndent:0px;text-transform:none;white-space:normal;word-spacing:0px"><li>The =
programmer is only interested in the first n elements of the output.&nbsp; =
I have personally encountered situations in which I wanted to use<span>&nbs=
p;</span><span style=3D"font-family:'courier new',monospace">std::merge</sp=
an><span>&nbsp;</span>in this way.</li><li>The programmer needs to operate =
on a given range of input data in batches.&nbsp; For example, writing data =
into a memory-mapped file for communication with another process, or hardwa=
re.</li></ol></div></blockquote></div><br><div>(1) is just a matter of addi=
ng an early exit condition, but (2) requires effectively turning the algori=
thm into a coroutine or =E2=80=9Cresumable function.=E2=80=9D This is a tri=
vial problem for algorithms like <font face=3D"Courier">copy</font> and <fo=
nt face=3D"Courier">merge</font> which return all their internal state in a=
 form allowing it to be passed back into another invocation. Most of the re=
st you=E2=80=99ve listed should be the same, but a closer look would help.<=
/div></div></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_3823_903082608.1422215760492--
------=_Part_3822_1005245251.1422215760492--

.

--Apple-Mail=_57158DA6-31E9-4B3E-BC26-F05B8AF37258
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset=UTF-8


> On 2015=E2=80=9301=E2=80=9326, at 3:56 AM, Scott Prager <splinterofchaos@=
gmail.com> wrote:
>=20
>=20
>=20
> On Friday, January 23, 2015 at 9:16:25 PM UTC-5, David Krauss wrote:
>=20
>> On 2015=E2=80=9301=E2=80=9324, at 8:26 AM, ahmed....@gmail.com <javascri=
pt:> wrote:
>>=20
>> However, many algorithms in <algorithm> would benefit from having an out=
put-restricted variant, for at least two reasons:
>=20
> Rather than rewrite all the algorithms, why not define an output-restrict=
ed iterator category (perhaps together with an adaptor to generate one from=
 any unrestricted output iterator, and perhaps adding non-output iterators =
into the mix), and add constraints to the existing algorithms to ensure tha=
t the templates do the right thing?
>=20
> I actually had need of an output-restricted copy recently and ended up wr=
iting it, but I tried this suggestion and it's pretty short, so I'll post i=
t here.

I had to do a double take, but what=E2=80=99s flipped here is the sense of =
the assignment operator. You=E2=80=99re assigning the output values to the =
input sequence.

> Although this solution feels a little hacky and I'm sure it has pitfalls.=
 Wouldn't an output-restricted algorithm be more idiomatic? Or do you mean =
that some sort of iterator_traits property should dispatch between "copy(fr=
om1, from2, to)" and "copy(to1, to2, from)=E2=80=9D?

I was thinking of a range-like, iterable object with built-in knowledge of =
the termination condition.

copy( from1, from2, make_range( to1, to2 ) ); // return remaining range
auto remaining =3D copy( from1, from2,
    make_range( istream_iterator< int >( cin ), 42 ) ); // read 42 values
cout << remaining.count() << " expected values were not read\n";

I=E2=80=99m not really familiar enough with the ranges proposal to know whe=
ther it already includes this. (Likely, I suppose.)

However, the ability to resume with new output sequence locations after an =
algorithm terminates on =E2=80=9Cbuffer overrun=E2=80=9D may alone be new t=
erritory worth investigation.

--=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/.

--Apple-Mail=_57158DA6-31E9-4B3E-BC26-F05B8AF37258
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html; charset=UTF-8

<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html charset=
=3Dutf-8"></head><body style=3D"word-wrap: break-word; -webkit-nbsp-mode: s=
pace; -webkit-line-break: after-white-space;" class=3D""><br class=3D""><di=
v><blockquote type=3D"cite" class=3D""><div class=3D"">On 2015=E2=80=9301=
=E2=80=9326, at 3:56 AM, Scott Prager &lt;<a href=3D"mailto:splinterofchaos=
@gmail.com" class=3D"">splinterofchaos@gmail.com</a>&gt; wrote:</div><br cl=
ass=3D"Apple-interchange-newline"><div class=3D""><div dir=3D"ltr" class=3D=
""><br class=3D""><br class=3D"">On Friday, January 23, 2015 at 9:16:25 PM =
UTC-5, David Krauss wrote:<blockquote class=3D"gmail_quote" style=3D"margin=
: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div=
 style=3D"word-wrap:break-word" class=3D""><br class=3D""><div class=3D""><=
blockquote type=3D"cite" class=3D""><div class=3D"">On 2015=E2=80=9301=E2=
=80=9324, at 8:26 AM, <a href=3D"javascript:" target=3D"_blank" gdf-obfusca=
ted-mailto=3D"jVZ9oiWEorIJ" rel=3D"nofollow" onmousedown=3D"this.href=3D'ja=
vascript:';return true;" onclick=3D"this.href=3D'javascript:';return true;"=
 class=3D"">ahmed....@gmail.com</a> wrote:</div><br class=3D""><div class=
=3D""><span style=3D"font-family:Helvetica;font-size:12px;font-style:normal=
;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:n=
ormal;text-align:start;text-indent:0px;text-transform:none;white-space:norm=
al;word-spacing:0px;float:none;display:inline!important" class=3D"">However=
, many algorithms in<span class=3D"">&nbsp;</span></span><span style=3D"fon=
t-size:12px;font-style:normal;font-variant:normal;font-weight:normal;letter=
-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-tr=
ansform:none;white-space:normal;word-spacing:0px;font-family:'courier new',=
monospace" class=3D"">&lt;algorithm&gt;<span class=3D"">&nbsp;</span></span=
><span style=3D"font-family:Helvetica;font-size:12px;font-style:normal;font=
-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal=
;text-align:start;text-indent:0px;text-transform:none;white-space:normal;wo=
rd-spacing:0px;float:none;display:inline!important" class=3D"">would benefi=
t from having an output-restricted variant, for at least two reasons:</span=
><br style=3D"font-family:Helvetica;font-size:12px;font-style:normal;font-v=
ariant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;t=
ext-align:start;text-indent:0px;text-transform:none;white-space:normal;word=
-spacing:0px" class=3D""></div></blockquote><div class=3D""><br class=3D"">=
</div><div class=3D"">Rather than rewrite all the algorithms, why not defin=
e an output-restricted iterator category (perhaps together with an adaptor =
to generate one from any unrestricted output iterator, and perhaps adding n=
on-output iterators into the mix), and add constraints to the existing algo=
rithms to ensure that the templates do the right thing?</div></div></div></=
blockquote><div class=3D""><br class=3D""></div><div class=3D"">I actually =
had need of an output-restricted copy recently and ended up writing it, but=
 I tried this suggestion and it's pretty short, so I'll post it here.</div>=
</div></div></blockquote><div><br class=3D""></div><div>I had to do a doubl=
e take, but what=E2=80=99s flipped here is the sense of the assignment oper=
ator. You=E2=80=99re assigning the output values to the input sequence.</di=
v><br class=3D""><blockquote type=3D"cite" class=3D""><div dir=3D"ltr" clas=
s=3D""><div class=3D"">Although this solution feels a little hacky and I'm =
sure it has pitfalls. Wouldn't an output-restricted algorithm be more idiom=
atic? Or do you mean that some sort of iterator_traits property should disp=
atch between "copy(from1, from2, to)" and "copy(to1, to2, from)=E2=80=9D?</=
div></div></blockquote><div><br class=3D""></div><div>I was thinking of a r=
ange-like, iterable object with built-in knowledge of the termination condi=
tion.</div><div><br class=3D""></div><div><font face=3D"Courier" class=3D""=
>copy( from1, from2, make_range( to1, to2 ) ); // return remaining range</f=
ont></div><div><div><font face=3D"Courier" class=3D"">auto remaining =3D co=
py( from1, from2,</font></div><div><font face=3D"Courier" class=3D"">&nbsp;=
 &nbsp; make_range( istream_iterator&lt; int &gt;( cin ), 42 ) ); // read 4=
2 values</font></div><div><font face=3D"Courier" class=3D"">cout &lt;&lt; r=
emaining.count() &lt;&lt; " expected values were not read\n";</font></div><=
div class=3D""><br class=3D""></div></div><div>I=E2=80=99m not really famil=
iar enough with the ranges proposal to know whether it already includes thi=
s. (Likely, I suppose.)</div><div><br class=3D""></div><div>However, the ab=
ility to resume with new output sequence locations after an algorithm termi=
nates on =E2=80=9Cbuffer overrun=E2=80=9D may alone be new territory worth =
investigation.</div></div></body></html>

<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 />

--Apple-Mail=_57158DA6-31E9-4B3E-BC26-F05B8AF37258--

.