------=_Part_7712_849716352.1412303154391
Content-Type: text/plain; charset=UTF-8

I propose changing the first requirement of pop_heap() from "The range
[first, last) shall be a valid non-empty heap" to "The range [first, last -
1) shall be a valid heap". Specifically, this would allow the last element
in the non-empty [first, last) to not be in heap order. Since the Effects
clause would still be "swaps the value in the location first with the value
in the location last-1 and makes [first, last-1) into a valid heap", this
allows pop_heap to act as a pop-then-push method in a more efficient manner
than separate calls to pop_heap() and push_heap(). This can be
significantly more efficient if the pushed value would end up at the top of
the heap.

Due to the existing requirement that the first thing done must be swapping
*first and *(last-1), I do not think any standard library would need to
change their algorithm. However, due to the "as-if" rule, they could
theoretically take advantage of the existing heap order. The only change
libraries would need to make would be to relax their debugging assertions
(which is why I am proposing this in the first place).

Assuming this is considered worth doing, these three methods are natural
related additions to std::priority_queue:
Type pop_push(const Type&);
Type pop_push(Type&&);
template <class... Args> void pop_emplace(Args&&... args);

Thoughts?

--

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

<div dir=3D"ltr">I propose changing the first requirement of pop_heap() fro=
m "The range [first, last) shall be a valid non-empty heap" to "The range [=
first, last - 1) shall be a valid heap". Specifically, this would allow the=
 last element in the non-empty [first, last) to not be in heap order. Since=
 the Effects clause would still be "swaps the value in the location first w=
ith the value in the location last-1 and makes [first, last-1) into a valid=
 heap", this allows pop_heap to act as a pop-then-push method in a more eff=
icient manner than separate calls to pop_heap() and push_heap(). This can b=
e significantly more efficient if the pushed value would end up at the top =
of the heap.<br><br>Due to the existing requirement that the first thing do=
ne must be swapping *first and *(last-1), I do not think any standard libra=
ry would need to change their algorithm. However, due to the "as-if" rule, =
they could theoretically take advantage of the existing heap order. The onl=
y change libraries would need to make would be to relax their debugging ass=
ertions (which is why I am proposing this in the first place).<br><br>Assum=
ing this is considered worth doing, these three methods are natural related=
 additions to std::priority_queue:<br>Type pop_push(const Type&amp;);<br>Ty=
pe pop_push(Type&amp;&amp;);<br>template &lt;class... Args&gt; void pop_emp=
lace(Args&amp;&amp;... args);<br><br>Thoughts?<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_7712_849716352.1412303154391--

.