------=_Part_262_1496417593.1443457886806
Content-Type: text/plain; charset=UTF-8

Since deque is internally a doubly linked list of blocks, why not add a new method list std::splice that will concatenate one deque at the end of the other in constant time by splicing the internal lists?
This should be feasible to do in constant time regardless of the size of the containers.

Is there anything preventing this?

A more narrow definition would limit this to be done only at the beginning or the end of the deque (splice_back/splice_front).

--Adi

--

---
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_262_1496417593.1443457886806--

.

------=_Part_686_2047384938.1443459065386
Content-Type: multipart/alternative;
 boundary="----=_Part_687_1709221910.1443459065386"

------=_Part_687_1709221910.1443459065386
Content-Type: text/plain; charset=UTF-8

On Monday, September 28, 2015 at 12:31:26 PM UTC-4, Adi Shavit wrote:
>
> Since deque is internally a doubly linked list of blocks, why not add a
> new method list std::splice that will concatenate one deque at the end of
> the other in constant time by splicing the internal lists?
> This should be feasible to do in constant time regardless of the size of
> the containers.
>
> Is there anything preventing this?
>

Ignoring the fact that implementations are allowed to implement deque
however they want, even in a linked-list implementation what you want
simply can't happen.

The reason being that only the first and last blocks in a deque are allowed
to be partially empty.

Let's say you have a deque with a block size of 10 elements. And the deque
has 2 blocks, the first with 3 elements and the last with 9.

How do you splice that onto another deque? That would require that the
receiving deque be able to handle empty blocks in the middle of the
sequence. When getting to the new block, it would have to look at something
that told it which elements in the block are valid.

This would only be necessary where "splice" exists. And it would needlessly
take up performance from any `deque` user who doesn't use "splice", since
every block access has to check the two indices to tell where the valid
elements are.

At the end of the day, it's just not a good idea.

--

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

<div dir=3D"ltr">On Monday, September 28, 2015 at 12:31:26 PM UTC-4, Adi Sh=
avit wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left=
: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">Since deque is inte=
rnally a doubly linked list of blocks, why not add a new method list std::s=
plice that will concatenate one deque at the end of the other in constant t=
ime by splicing the internal lists?<br>This should be feasible to do in con=
stant time regardless of the size of the containers. <p>Is there anything p=
reventing this?</p></blockquote><div><br>Ignoring the fact that implementat=
ions are allowed to implement deque however they want, even in a linked-lis=
t implementation what you want simply can&#39;t happen.<br><br>The reason b=
eing that only the first and last blocks in a deque are allowed to be parti=
ally empty.<br><br>Let&#39;s say you have a deque with a block size of 10 e=
lements. And the deque has 2 blocks, the first with 3 elements and the last=
 with 9.<br><br>How do you splice that onto another deque? That would requi=
re that the receiving deque be able to handle empty blocks in the middle of=
 the sequence. When getting to the new block, it would have to look at some=
thing that told it which elements in the block are valid.<br><br>This would=
 only be necessary where &quot;splice&quot; exists. And it would needlessly=
 take up performance from any `deque` user who doesn&#39;t use &quot;splice=
&quot;, since every block access has to check the two indices to tell where=
 the valid elements are.<br><br>At the end of the day, it&#39;s just not a =
good idea.</div></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_687_1709221910.1443459065386--
------=_Part_686_2047384938.1443459065386--

.

--047d7b5d52ca70c7050520fba144
Content-Type: text/plain; charset=UTF-8

>
>
> Ignoring the fact that implementations are allowed to implement deque
> however they want, even in a linked-list implementation what you want
> simply can't happen.
> The reason being that only the first and last blocks in a deque are
> allowed to be partially empty.
>

AFAIK, the standard does not dictate that only the first and last blocks
can be partially empty.


>
> This would only be necessary where "splice" exists. And it would
> needlessly take up performance from any `deque` user who doesn't use
> "splice", since every block access has to check the two indices to tell
> where the valid elements are.
>

Keeping 2 pointers instead of one is an O(1) overhead is not really a good
reason to *not* do this.
Looking deeper into the standard, the problem would actually be the
requirement for constant time random access. With fixed size blocks this is
not a problem. However, allowing for empty slots means that finding a
single element with O(1) would be tricky.

Thanks,
Adi


> --
>
> ---
> You received this message because you are subscribed to a topic in the
> Google Groups "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/a/isocpp.org/d/topic/std-proposals/hPHs98Z7X-g/unsubscribe
> .
> To unsubscribe from this group and all its topics, send an email to
> std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> Visit this group at
> http://groups.google.com/a/isocpp.org/group/std-proposals/.
>

--

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

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

<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote"><blo=
ckquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left=
-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;paddi=
ng-left:1ex"><div dir=3D"ltr"><div><br>Ignoring the fact that implementatio=
ns are allowed to implement deque however they want, even in a linked-list =
implementation what you want simply can&#39;t happen.<br>The reason being t=
hat only the first and last blocks in a deque are allowed to be partially e=
mpty.<br></div></div></blockquote><div><br></div>AFAIK, the standard does n=
ot dictate that only the first and last blocks can be partially empty.=C2=
=A0<div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0=
px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);borde=
r-left-style:solid;padding-left:1ex"><div dir=3D"ltr"><div><br>This would o=
nly be necessary where &quot;splice&quot; exists. And it would needlessly t=
ake up performance from any `deque` user who doesn&#39;t use &quot;splice&q=
uot;, since every block access has to check the two indices to tell where t=
he valid elements are.<br></div></div></blockquote><div><br></div>Keeping 2=
 pointers instead of one is an O(1) overhead is not really a good reason to=
 <i>not</i> do this.<div>Looking deeper into the standard, the problem woul=
d actually be the requirement for constant time random access. With fixed s=
ize blocks this is not a problem. However, allowing for empty slots means t=
hat finding a single element with O(1) would be tricky.=C2=A0</div><div><br=
></div><div>Thanks,</div><div>Adi<br>=C2=A0</div><blockquote class=3D"gmail=
_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left=
-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div clas=
s=3D""><div class=3D"h5">

<p></p>

-- <br>
<br>
--- <br>
You received this message because you are subscribed to a topic in the Goog=
le Groups &quot;ISO C++ Standard - Future Proposals&quot; group.<br>
To unsubscribe from this topic, visit <a href=3D"https://groups.google.com/=
a/isocpp.org/d/topic/std-proposals/hPHs98Z7X-g/unsubscribe" target=3D"_blan=
k">https://groups.google.com/a/isocpp.org/d/topic/std-proposals/hPHs98Z7X-g=
/unsubscribe</a>.<br>
To unsubscribe from this group and all its topics, send an email to <a href=
=3D"mailto:std-proposals+unsubscribe@isocpp.org" target=3D"_blank">std-prop=
osals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" target=3D"_blank">http://groups.google.com/a/isocpp.org/gro=
up/std-proposals/</a>.<br>
</div></div></blockquote></div><br></div></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 />

--047d7b5d52ca70c7050520fba144--

.

> On 2015=E2=80=9309=E2=80=9329, at 12:31 AM, Adi Shavit <adishavit@gmail.c=
om> wrote:
>=20
> Since deque is internally a doubly linked list of blocks,

No, a deque is a table-of-contents array which links to various blocks.

> why not add a new method list std::splice that will concatenate one deque=
 at the end of the other in constant time by splicing the internal lists?
> This should be feasible to do in constant time regardless of the size of =
the containers.=20

Given a spliced deque with gaps in the middle, finding the n'th element wou=
ld not be constant-time.

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

.

There is one very limited form of deque splice that I consider very importa=
nt.  The good news is that we don=E2=80=99t need a change in the standard f=
or vendors to be able to supply it.  But I don=E2=80=99t know if vendors ac=
tually do supply it.

When used as a FIFO queue, a std::deque should quickly reach equilibrium wi=
th regards to allocations/deallocations and no longer allocate as long as t=
he average size() stabilizes.  This can be accomplished by leaving an empty=
 array on one end of the deque after a pop, and reusing it on the other end=
 of the deque for a subsequent push.

Here is a test that should detect whether or not your implementation perfor=
ms this conforming optimization:

    #include <chrono>
    #include <cstdio>
    #include <cstdlib>
    #include <deque>
    #include <new>

    void* operator new (size_t sz)
    {
        std::printf("allocating\n");
        void* p =3D std::malloc(sz);
        return p;
    }

    void operator delete(void* p) noexcept
    {
        std::printf("deallocating\n");
        return std::free(p);
    }

    int
    main()
    {
        using namespace std::literals;
        std::deque<int> d(20, 0);
        auto end =3D std::chrono::steady_clock::now() + 3s;
        while (std::chrono::steady_clock::now() < end)
        {
            d.pop_front();
            d.push_back(0);
        }
    }

Using libc++ this outputs:

    allocating
    allocating
    allocating
    allocating
    deallocating
    deallocating
    deallocating
    deallocating

On an implementation that does not perform this optimization I would expect=
 orders of magnitudes more allocating/deallocating statements.

Howard

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

.

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

> > why not add a new method list std::splice that will concatenate one
> deque at the end of the other in constant time by splicing the internal
> lists?
> > This should be feasible to do in constant time regardless of the size of
> the containers.
>
> Given a spliced deque with gaps in the middle, finding the n'th element
> would not be constant-time.


Yes, that is exactly what I meant.

--

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

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

<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote"><div=
>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px =
0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-=
style:solid;padding-left:1ex"><span class=3D"">
&gt; why not add a new method list std::splice that will concatenate one de=
que at the end of the other in constant time by splicing the internal lists=
?<br>
&gt; This should be feasible to do in constant time regardless of the size =
of the containers.<br>
<br>
</span>Given a spliced deque with gaps in the middle, finding the n&#39;th =
element would not be constant-time.</blockquote><div><br></div><div><div>Ye=
s, that is exactly what I meant.</div></div><div><br></div><div>=C2=A0</div=
></div></div></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 />

--001a11c2382ce76d8f0521057170--

.

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

This messages is just a plain contradiction:

On Thu, Oct 1, 2015 at 7:48 AM, Adi Shavit <adishavit@gmail.com> wrote:

>
>> > This should be feasible to do in constant time regardless of the size
>> of the containers.
>>
>> Given a spliced deque with gaps in the middle, finding the n'th element
>> would not be constant-time.
>
>
> Yes, that is exactly what I meant.
>
>
Line 1: Should be doable in constant time
Line 2: Cannot be done in constant time
Line 3: Exactly what I mean. !?!?!

   David

--

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

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

<div dir=3D"ltr">This messages is just a plain contradiction:<div class=3D"=
gmail_extra"><br><div class=3D"gmail_quote">On Thu, Oct 1, 2015 at 7:48 AM,=
 Adi Shavit <span dir=3D"ltr">&lt;<a href=3D"mailto:adishavit@gmail.com" ta=
rget=3D"_blank">adishavit@gmail.com</a>&gt;</span> wrote:<br><blockquote cl=
ass=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;p=
adding-left:1ex"><div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"=
gmail_quote"><span class=3D""><blockquote class=3D"gmail_quote" style=3D"ma=
rgin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,=
204);border-left-style:solid;padding-left:1ex"><span><br>&gt; This should b=
e feasible to do in constant time regardless of the size of the containers.=
<br>
<br>
</span>Given a spliced deque with gaps in the middle, finding the n&#39;th =
element would not be constant-time.</blockquote><div><br></div></span><div>=
<div>Yes, that is exactly what I meant.</div></div><div><br></div></div></d=
iv></div></blockquote><div><br>Line 1: Should be doable in constant time<br=
>Line 2: Cannot be done in constant time<br>Line 3: Exactly what I mean. !?=
!?!<br><br>=C2=A0 =C2=A0David=C2=A0</div></div></div></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 />

--001a1130cca009e7f2052106f759--

.

--Apple-Mail=_673AE3D4-4163-4B10-924E-B0D97E216933
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset=UTF-8

Sorry for the confusion, the complexity statements were referring to 2 diff=
erent things=E2=80=A6

My first post asked about the possibility of adding a constant time splice.=
=20
Implementing this would ass empty slots in the blocks

After further investigation, I posted a second post where I acknowledged th=
at constant time random access, as required by the standard, would be probl=
ematic if constant time splice was added (because of the potential empty sl=
ots in each block) - this was David Krauss=E2=80=99s point too.

Adi

> On Oct 1, 2015, at 11:38, David Rodr=C3=ADguez Ibeas <dibeas@ieee.org> wr=
ote:
>=20
> This messages is just a plain contradiction:
>=20
> On Thu, Oct 1, 2015 at 7:48 AM, Adi Shavit <adishavit@gmail.com <mailto:a=
dishavit@gmail.com>> wrote:
>=20
> > This should be feasible to do in constant time regardless of the size o=
f the containers.
>=20
> Given a spliced deque with gaps in the middle, finding the n'th element w=
ould not be constant-time.
>=20
> Yes, that is exactly what I meant.
>=20
>=20
> Line 1: Should be doable in constant time
> Line 2: Cannot be done in constant time
> Line 3: Exactly what I mean. !?!?!
>=20
>    David=20
>=20
> --=20
>=20
> ---=20
> You received this message because you are subscribed to a topic in the Go=
ogle Groups "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this topic, visit https://groups.google.com/a/isocpp.=
org/d/topic/std-proposals/hPHs98Z7X-g/unsubscribe <https://groups.google.co=
m/a/isocpp.org/d/topic/std-proposals/hPHs98Z7X-g/unsubscribe>.
> To unsubscribe from this group and all its topics, send an email to std-p=
roposals+unsubscribe@isocpp.org <mailto:std-proposals+unsubscribe@isocpp.or=
g>.
> To post to this group, send email to std-proposals@isocpp.org <mailto:std=
-proposals@isocpp.org>.
> Visit this group at http://groups.google.com/a/isocpp.org/group/std-propo=
sals/ <http://groups.google.com/a/isocpp.org/group/std-proposals/>.

--=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=_673AE3D4-4163-4B10-924E-B0D97E216933
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""><div class=3D"">So=
rry for the confusion, the complexity statements were referring to 2 differ=
ent things=E2=80=A6</div><div class=3D""><br class=3D""></div>My first post=
 asked about the possibility of adding a constant time <i class=3D"">splice=
</i>.&nbsp;<div class=3D"">Implementing this would ass empty slots in the b=
locks<br class=3D""><div class=3D""><br class=3D""></div><div class=3D"">Af=
ter further investigation, I posted a second post where I acknowledged that=
 constant time <i class=3D"">random access</i>, as required by the standard=
<i class=3D"">,&nbsp;</i>would be problematic if constant time splice was a=
dded (because of the potential empty slots in each block) - this was David =
Krauss=E2=80=99s point too.</div><div class=3D""><br class=3D""></div><div =
class=3D"">Adi</div><div class=3D""><br class=3D""><div><blockquote type=3D=
"cite" class=3D""><div class=3D"">On Oct 1, 2015, at 11:38, David Rodr=C3=
=ADguez Ibeas &lt;<a href=3D"mailto:dibeas@ieee.org" class=3D"">dibeas@ieee=
..org</a>&gt; wrote:</div><br class=3D"Apple-interchange-newline"><div class=
=3D""><div dir=3D"ltr" class=3D"">This messages is just a plain contradicti=
on:<div class=3D"gmail_extra"><br class=3D""><div class=3D"gmail_quote">On =
Thu, Oct 1, 2015 at 7:48 AM, Adi Shavit <span dir=3D"ltr" class=3D"">&lt;<a=
 href=3D"mailto:adishavit@gmail.com" target=3D"_blank" class=3D"">adishavit=
@gmail.com</a>&gt;</span> wrote:<br class=3D""><blockquote class=3D"gmail_q=
uote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1e=
x"><div dir=3D"ltr" class=3D""><div class=3D"gmail_extra"><div class=3D"gma=
il_quote"><span class=3D""><blockquote class=3D"gmail_quote" style=3D"margi=
n:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204=
);border-left-style:solid;padding-left:1ex"><span class=3D""><br class=3D""=
>&gt; This should be feasible to do in constant time regardless of the size=
 of the containers.<br class=3D"">
<br class=3D"">
</span>Given a spliced deque with gaps in the middle, finding the n'th elem=
ent would not be constant-time.</blockquote><div class=3D""><br class=3D"">=
</div></span><div class=3D""><div class=3D"">Yes, that is exactly what I me=
ant.</div></div><div class=3D""><br class=3D""></div></div></div></div></bl=
ockquote><div class=3D""><br class=3D"">Line 1: Should be doable in constan=
t time<br class=3D"">Line 2: Cannot be done in constant time<br class=3D"">=
Line 3: Exactly what I mean. !?!?!<br class=3D""><br class=3D"">&nbsp; &nbs=
p;David&nbsp;</div></div></div></div><div class=3D""><br class=3D"webkit-bl=
ock-placeholder"></div>

-- <br class=3D"">
<br class=3D"">
--- <br class=3D"">
You received this message because you are subscribed to a topic in the Goog=
le Groups "ISO C++ Standard - Future Proposals" group.<br class=3D"">
To unsubscribe from this topic, visit <a href=3D"https://groups.google.com/=
a/isocpp.org/d/topic/std-proposals/hPHs98Z7X-g/unsubscribe" class=3D"">http=
s://groups.google.com/a/isocpp.org/d/topic/std-proposals/hPHs98Z7X-g/unsubs=
cribe</a>.<br class=3D"">
To unsubscribe from this group and all its topics, send an email to <a href=
=3D"mailto:std-proposals+unsubscribe@isocpp.org" class=3D"">std-proposals+u=
nsubscribe@isocpp.org</a>.<br class=3D"">
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" class=3D"">std-proposals@isocpp.org</a>.<br class=3D"">
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" class=3D"">http://groups.google.com/a/isocpp.org/group/std-=
proposals/</a>.<br class=3D"">
</div></blockquote></div><br class=3D""></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=_673AE3D4-4163-4B10-924E-B0D97E216933--

.

--Apple-Mail-D2FC734C-28A1-4358-BF85-E106E052257C
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

Neither `splice()` nor `push_back()` on a `std::deque<T>` can be done in wo=
rst case O(1) complexity. There are O(1) operations on `T` objects but the =
outer array contains O(n) pointers to inner arrays and upon appending it ma=
y require O(n) operations to move them to a new location.

The more inportant issue with `splice()`ing internal arrays of a `std::dequ=
e<T>` is that the size of these arrays is not defined and is highly unlikel=
y coincide with any size reasonable for some application. Also, to move an =
inner array just to end of an existing object the last inner array of the o=
bject needs to be fully used. Allowing partially filled inner arrays would =
break existing complexity requirements, e.g., O(1) random access.

I can imagine specialized needs for a container moving blocks of objects bu=
t I don't think `std::deque<T>` is that container. However, the whole point=
 of generic algorithms is support for creation of specialized containers.

> On 1 Oct 2015, at 09:38, David Rodr=C3=ADguez Ibeas <dibeas@ieee.org> wro=
te:
>=20
> This messages is just a plain contradiction:
>=20
> On Thu, Oct 1, 2015 at 7:48 AM, Adi Shavit <adishavit@gmail.com> wrote:
>>>=20
>>> > This should be feasible to do in constant time regardless of the size=
 of the containers.
>>>=20
>>> Given a spliced deque with gaps in the middle, finding the n'th element=
 would not be constant-time.
>>=20
>> Yes, that is exactly what I meant.
>=20
> Line 1: Should be doable in constant time
> Line 2: Cannot be done in constant time
> Line 3: Exactly what I mean. !?!?!
>=20
>    David=20

--=20

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

--Apple-Mail-D2FC734C-28A1-4358-BF85-E106E052257C
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<html><head><meta http-equiv=3D"content-type" content=3D"text/html; charset=
=3Dutf-8"></head><body dir=3D"auto"><div>Neither `splice()` nor `push_back(=
)` on a `std::deque&lt;T&gt;` can be done in worst case O(1) complexity. Th=
ere are O(1) operations on `T` objects but the outer array contains O(n) po=
inters to inner arrays and upon appending it may require O(n) operations to=
 move them to a new location.</div><div id=3D"AppleMailSignature"><br></div=
><div id=3D"AppleMailSignature">The more inportant issue with `splice()`ing=
 internal arrays of a `std::deque&lt;T&gt;` is that the size of these array=
s is not defined and is highly unlikely coincide with any size reasonable f=
or some application. Also, to move an inner array just to end of an existin=
g object the last inner array of the object needs to be fully used. Allowin=
g partially filled inner arrays would break existing complexity requirement=
s, e.g., O(1) random access.<br><br></div><div id=3D"AppleMailSignature">I =
can imagine specialized needs for a container moving blocks of objects but =
I don't think `std::deque&lt;T&gt;` is that container. However, the whole p=
oint of generic algorithms is support for creation of specialized container=
s.</div><div><br>On 1 Oct 2015, at 09:38, David Rodr=C3=ADguez Ibeas &lt;<a=
 href=3D"mailto:dibeas@ieee.org">dibeas@ieee.org</a>&gt; wrote:<br><br></di=
v><blockquote type=3D"cite"><div><div dir=3D"ltr">This messages is just a p=
lain contradiction:<div class=3D"gmail_extra"><br><div class=3D"gmail_quote=
">On Thu, Oct 1, 2015 at 7:48 AM, Adi Shavit <span dir=3D"ltr">&lt;<a href=
=3D"mailto:adishavit@gmail.com" target=3D"_blank">adishavit@gmail.com</a>&g=
t;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0=
 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div cl=
ass=3D"gmail_extra"><div class=3D"gmail_quote"><span class=3D""><blockquote=
 class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:=
1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left=
:1ex"><span><br>&gt; This should be feasible to do in constant time regardl=
ess of the size of the containers.<br>
<br>
</span>Given a spliced deque with gaps in the middle, finding the n'th elem=
ent would not be constant-time.</blockquote><div><br></div></span><div><div=
>Yes, that is exactly what I meant.</div></div><div><br></div></div></div><=
/div></blockquote><div><br>Line 1: Should be doable in constant time<br>Lin=
e 2: Cannot be done in constant time<br>Line 3: Exactly what I mean. !?!?!<=
br><br>&nbsp; &nbsp;David&nbsp;</div></div></div></div>
</div></blockquote></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-D2FC734C-28A1-4358-BF85-E106E052257C--

.

On 2015-09-28 9:31 , Adi Shavit wrote:
> Since deque is internally a doubly linked list of blocks, why not add a new method list std::splice that will concatenate one deque at the end of the other in constant time by splicing the internal lists?
> This should be feasible to do in constant time regardless of the size of the containers.
>
> Is there anything preventing this?
>
> A more narrow definition would limit this to be done only at the beginning or the end of the deque (splice_back/splice_front).
>
> --Adi
>

maybe the resistance you're encountering is due to the word "splice"?
appending a deque onto another deque should be doable in constant time.
a "push_front" api should work, too.

the generalized splice() might not work, but maybe we don't care?

--

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

.

--Apple-Mail=_72A06012-DDD4-4A6F-B4D7-0B32C5647E26
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset=UTF-8


> On 2015=E2=80=9310=E2=80=9301, at 4:59 PM, Dietmar K=C3=BChl <dietmar.kue=
hl@gmail.com> wrote:
>=20
> Neither `splice()` nor `push_back()` on a `std::deque<T>` can be done in =
worst case O(1) complexity. There are O(1) operations on `T` objects but th=
e outer array contains O(n) pointers to inner arrays and upon appending it =
may require O(n) operations to move them to a new location.

This isn=E2=80=99t necessary. Instead of making the blocks all equally size=
d, you can use a back-to-back pair of geometric series, like std::vector bu=
t without move-construction. Then there are only O(ln N) blocks in the wors=
t case (using it as a vector), and exactly 2 blocks for a ring buffer of co=
nstant size (at equilibrium). In the 2-block case, an empty one can be kept=
 around for Howard=E2=80=99s optimization.

For example, say I create a deque<int>(100, 0). Then I have an allocation b=
lock of size 100. (Let=E2=80=99s keep it simple.)

100(100 used)

Now I push_back.

100(100) 100(1)

After another 100 push_backs:

100(100) 100(100) 200(1)

Then push_front:

200(1) 100(100) 100(100) 200(1)

This is the worst-case utilization factor not resulting from removal, 1/3. =
Improving this would be tricky.

Now 201 pop_fronts:

200(1)

One push_front and the low utilization factor causes it to try a smaller bl=
ock:

100(1) 200(1)


I=E2=80=99ve been meaning to implement this for a while. It needs to count =
leading bits during indexing, and C++ hasn=E2=80=99t standardized such a fa=
cility yet (and it=E2=80=99s not necessarily hardware-optimized even if it =
were). I call the idea =E2=80=9Cpowerdeque.=E2=80=9D

--=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=_72A06012-DDD4-4A6F-B4D7-0B32C5647E26
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=9310=
=E2=80=9301, at 4:59 PM, Dietmar K=C3=BChl &lt;<a href=3D"mailto:dietmar.ku=
ehl@gmail.com" class=3D"">dietmar.kuehl@gmail.com</a>&gt; wrote:</div><br c=
lass=3D"Apple-interchange-newline"><div class=3D""><div style=3D"font-famil=
y: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; fo=
nt-weight: normal; letter-spacing: normal; line-height: normal; orphans: au=
to; text-align: start; text-indent: 0px; text-transform: none; white-space:=
 normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" =
class=3D"">Neither `splice()` nor `push_back()` on a `std::deque&lt;T&gt;` =
can be done in worst case O(1) complexity. There are O(1) operations on `T`=
 objects but the outer array contains O(n) pointers to inner arrays and upo=
n appending it may require O(n) operations to move them to a new location.<=
/div></div></blockquote><br class=3D""></div><div>This isn=E2=80=99t necess=
ary. Instead of making the blocks all equally sized, you can use a back-to-=
back pair of geometric series, like <font face=3D"Courier" class=3D"">std::=
vector</font> but without move-construction. Then there are only O(ln N) bl=
ocks in the worst case (using it as a vector), and exactly 2 blocks for a r=
ing buffer of constant size (at equilibrium). In the 2-block case, an empty=
 one can be kept around for Howard=E2=80=99s optimization.</div><div><br cl=
ass=3D""></div><div>For example, say I create a deque&lt;int&gt;(100, 0). T=
hen I have an allocation block of size 100. (Let=E2=80=99s keep it simple.)=
</div><div><br class=3D""></div><div>100(100 used)</div><div><br class=3D""=
></div><div>Now I push_back.</div><div><br class=3D""></div><div>100(100) 1=
00(1)</div><div><br class=3D""></div><div>After another 100 push_backs:</di=
v><div><br class=3D""></div><div>100(100) 100(100) 200(1)</div><div><br cla=
ss=3D""></div><div>Then push_front:</div><div><br class=3D""></div><div>200=
(1) 100(100) 100(100) 200(1)</div><div><br class=3D""></div><div>This is th=
e worst-case utilization factor not resulting from removal, 1/3. Improving =
this would be tricky.</div><div><br class=3D""></div><div>Now 201 pop_front=
s:</div><div><br class=3D""></div><div>200(1)</div><div><br class=3D""></di=
v><div>One push_front and the low&nbsp;utilization&nbsp;factor causes it to=
 try a smaller block:</div><div><br class=3D""></div><div>100(1) 200(1)</di=
v><div><br class=3D""></div><br class=3D""><div class=3D"">I=E2=80=99ve bee=
n meaning to implement this for a while. It needs to count leading bits dur=
ing indexing, and C++ hasn=E2=80=99t standardized such a facility yet (and =
it=E2=80=99s not necessarily hardware-optimized even if it were). I call th=
e idea =E2=80=9Cpowerdeque.=E2=80=9D</div><div class=3D""><br class=3D""></=
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=_72A06012-DDD4-4A6F-B4D7-0B32C5647E26--

.

--089e0122e6b2d80c3d05210974f2
Content-Type: text/plain; charset=UTF-8

I used the term "splice" to imply that the source deque would lose its
contents as this is not a copy, more like a moving push or insert.
I have to particular love for the word. I borrowed it from
std::list::splice().

Even a constant time "push_front"/"push_back" api would be of great value.
How would you do this while keeping to the standard requirements?



On Thu, Oct 1, 2015 at 1:22 PM, maurice barnum <pixi@burble.org> wrote:

> On 2015-09-28 9:31 , Adi Shavit wrote:
>
>> Since deque is internally a doubly linked list of blocks, why not add a
>> new method list std::splice that will concatenate one deque at the end of
>> the other in constant time by splicing the internal lists?
>> This should be feasible to do in constant time regardless of the size of
>> the containers.
>>
>> Is there anything preventing this?
>>
>> A more narrow definition would limit this to be done only at the
>> beginning or the end of the deque (splice_back/splice_front).
>>
>> --Adi
>>
>>
> maybe the resistance you're encountering is due to the word "splice"?
> appending a deque onto another deque should be doable in constant time.
> a "push_front" api should work, too.
>
> the generalized splice() might not work, but maybe we don't care?
>
>
> --
>
> --- You received this message because you are subscribed to a topic in the
> Google Groups "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/a/isocpp.org/d/topic/std-proposals/hPHs98Z7X-g/unsubscribe
> .
> To unsubscribe from this group and all its topics, send an email to
> std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> Visit this group at
> http://groups.google.com/a/isocpp.org/group/std-proposals/.
>

--

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

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

<div dir=3D"ltr">I used the term &quot;splice&quot; to imply that the sourc=
e deque would lose its contents as this is not a copy, more like a moving p=
ush or insert.=C2=A0<div>I have to particular love for the word. I borrowed=
 it from std::list::splice().<div><br></div><div>Even a constant time &quot=
;push_front&quot;/&quot;push_back&quot; api would be of great value.=C2=A0<=
div>How would you do this while keeping to the standard requirements?</div>=
<div><br></div><div><br></div></div></div></div><div class=3D"gmail_extra">=
<br><div class=3D"gmail_quote">On Thu, Oct 1, 2015 at 1:22 PM, maurice barn=
um <span dir=3D"ltr">&lt;<a href=3D"mailto:pixi@burble.org" target=3D"_blan=
k">pixi@burble.org</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quot=
e" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">=
<span class=3D"">On 2015-09-28 9:31 , Adi Shavit wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
Since deque is internally a doubly linked list of blocks, why not add a new=
 method list std::splice that will concatenate one deque at the end of the =
other in constant time by splicing the internal lists?<br>
This should be feasible to do in constant time regardless of the size of th=
e containers.<br>
<br>
Is there anything preventing this?<br>
<br>
A more narrow definition would limit this to be done only at the beginning =
or the end of the deque (splice_back/splice_front).<br>
<br>
--Adi<br>
<br>
</blockquote>
<br></span>
maybe the resistance you&#39;re encountering is due to the word &quot;splic=
e&quot;? appending a deque onto another deque should be doable in constant =
time.<br>
a &quot;push_front&quot; api should work, too.<br>
<br>
the generalized splice() might not work, but maybe we don&#39;t care?<div c=
lass=3D"HOEnZb"><div class=3D"h5"><br>
<br>
-- <br>
<br>
--- You received this message because you are subscribed to a topic in the =
Google Groups &quot;ISO C++ Standard - Future Proposals&quot; group.<br>
To unsubscribe from this topic, visit <a href=3D"https://groups.google.com/=
a/isocpp.org/d/topic/std-proposals/hPHs98Z7X-g/unsubscribe" rel=3D"noreferr=
er" target=3D"_blank">https://groups.google.com/a/isocpp.org/d/topic/std-pr=
oposals/hPHs98Z7X-g/unsubscribe</a>.<br>
To unsubscribe from this group and all its topics, send an email to <a href=
=3D"mailto:std-proposals%2Bunsubscribe@isocpp.org" target=3D"_blank">std-pr=
oposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" rel=3D"noreferrer" target=3D"_blank">http://groups.google.c=
om/a/isocpp.org/group/std-proposals/</a>.<br>
</div></div></blockquote></div><br></div>

<p></p>

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

--089e0122e6b2d80c3d05210974f2--

.

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

Typo: "I have *no *particular love for the word"

On Thu, Oct 1, 2015 at 2:35 PM, Adi Shavit <adishavit@gmail.com> wrote:

> I used the term "splice" to imply that the source deque would lose its
> contents as this is not a copy, more like a moving push or insert.
> I have to particular love for the word. I borrowed it from
> std::list::splice().
>
> Even a constant time "push_front"/"push_back" api would be of great value.
> How would you do this while keeping to the standard requirements?
>
>
>
> On Thu, Oct 1, 2015 at 1:22 PM, maurice barnum <pixi@burble.org> wrote:
>
>> On 2015-09-28 9:31 , Adi Shavit wrote:
>>
>>> Since deque is internally a doubly linked list of blocks, why not add a
>>> new method list std::splice that will concatenate one deque at the end of
>>> the other in constant time by splicing the internal lists?
>>> This should be feasible to do in constant time regardless of the size of
>>> the containers.
>>>
>>> Is there anything preventing this?
>>>
>>> A more narrow definition would limit this to be done only at the
>>> beginning or the end of the deque (splice_back/splice_front).
>>>
>>> --Adi
>>>
>>>
>> maybe the resistance you're encountering is due to the word "splice"?
>> appending a deque onto another deque should be doable in constant time.
>> a "push_front" api should work, too.
>>
>> the generalized splice() might not work, but maybe we don't care?
>>
>>
>> --
>>
>> --- You received this message because you are subscribed to a topic in
>> the Google Groups "ISO C++ Standard - Future Proposals" group.
>> To unsubscribe from this topic, visit
>> https://groups.google.com/a/isocpp.org/d/topic/std-proposals/hPHs98Z7X-g/unsubscribe
>> .
>> To unsubscribe from this group and all its topics, send an email to
>> std-proposals+unsubscribe@isocpp.org.
>> To post to this group, send email to std-proposals@isocpp.org.
>> Visit this group at
>> http://groups.google.com/a/isocpp.org/group/std-proposals/.
>>
>
>

--

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

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

<div dir=3D"ltr">Typo: &quot;<span style=3D"font-size:12.8px">I have <b><i>=
no </i></b>particular love for the word</span>&quot;</div><div class=3D"gma=
il_extra"><br><div class=3D"gmail_quote">On Thu, Oct 1, 2015 at 2:35 PM, Ad=
i Shavit <span dir=3D"ltr">&lt;<a href=3D"mailto:adishavit@gmail.com" targe=
t=3D"_blank">adishavit@gmail.com</a>&gt;</span> wrote:<br><blockquote class=
=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padd=
ing-left:1ex"><div dir=3D"ltr">I used the term &quot;splice&quot; to imply =
that the source deque would lose its contents as this is not a copy, more l=
ike a moving push or insert.=C2=A0<div>I have to particular love for the wo=
rd. I borrowed it from std::list::splice().<div><br></div><div>Even a const=
ant time &quot;push_front&quot;/&quot;push_back&quot; api would be of great=
 value.=C2=A0<div>How would you do this while keeping to the standard requi=
rements?</div><div><br></div><div><br></div></div></div></div><div class=3D=
"HOEnZb"><div class=3D"h5"><div class=3D"gmail_extra"><br><div class=3D"gma=
il_quote">On Thu, Oct 1, 2015 at 1:22 PM, maurice barnum <span dir=3D"ltr">=
&lt;<a href=3D"mailto:pixi@burble.org" target=3D"_blank">pixi@burble.org</a=
>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 =
0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span>On 2015-09-28 9=
:31 , Adi Shavit wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
Since deque is internally a doubly linked list of blocks, why not add a new=
 method list std::splice that will concatenate one deque at the end of the =
other in constant time by splicing the internal lists?<br>
This should be feasible to do in constant time regardless of the size of th=
e containers.<br>
<br>
Is there anything preventing this?<br>
<br>
A more narrow definition would limit this to be done only at the beginning =
or the end of the deque (splice_back/splice_front).<br>
<br>
--Adi<br>
<br>
</blockquote>
<br></span>
maybe the resistance you&#39;re encountering is due to the word &quot;splic=
e&quot;? appending a deque onto another deque should be doable in constant =
time.<br>
a &quot;push_front&quot; api should work, too.<br>
<br>
the generalized splice() might not work, but maybe we don&#39;t care?<div><=
div><br>
<br>
-- <br>
<br>
--- You received this message because you are subscribed to a topic in the =
Google Groups &quot;ISO C++ Standard - Future Proposals&quot; group.<br>
To unsubscribe from this topic, visit <a href=3D"https://groups.google.com/=
a/isocpp.org/d/topic/std-proposals/hPHs98Z7X-g/unsubscribe" rel=3D"noreferr=
er" target=3D"_blank">https://groups.google.com/a/isocpp.org/d/topic/std-pr=
oposals/hPHs98Z7X-g/unsubscribe</a>.<br>
To unsubscribe from this group and all its topics, send an email to <a href=
=3D"mailto:std-proposals%2Bunsubscribe@isocpp.org" target=3D"_blank">std-pr=
oposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" rel=3D"noreferrer" target=3D"_blank">http://groups.google.c=
om/a/isocpp.org/group/std-proposals/</a>.<br>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>

<p></p>

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

--001a11c25e3c0b54420521097c61--

.