Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Tracking issue for BinaryHeap::{push_pop, replace} #28147

Closed
eefriedman opened this issue Sep 1, 2015 · 15 comments
Closed

Tracking issue for BinaryHeap::{push_pop, replace} #28147

eefriedman opened this issue Sep 1, 2015 · 15 comments
Labels
B-unstable Blocker: Implemented in the nightly compiler and unstable. final-comment-period In the final comment period and will be merged soon unless new substantive objections are raised. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.

Comments

@eefriedman
Copy link
Contributor

Updated issue

Tracking issue for

  • BinaryHeap::push_pop
  • BinaryHeap::replace

Original Report

std::collections::BinaryHeap has a bunch of unstable methods without proper stability markings; filing an issue to point them at. Someone please label this B-unstable.
@alexcrichton alexcrichton added T-libs-api Relevant to the library API team, which will review and decide on the PR/issue. B-unstable Blocker: Implemented in the nightly compiler and unstable. labels Sep 1, 2015
@BurntSushi
Copy link
Member

It looks like the unstable methods are: from_vec, push_pop, replace, into_vec, into_sorted_vec and drain. Except for drain, is there any writing on why these methods were not stabilized? Were there any specific reservations about those methods?

@alexcrichton
Copy link
Member

I believe they weren't stabilized mostly because they didn't fit into any existing collections conventions and to be conservative we didn't add too much special functionality to collections around 1.0. They're pretty innocuous though, so I'd imagine they're ripe for some small modernization followed by stabilization.

@sfackler
Copy link
Member

from_vec and into_vec seem like super obvious and straightforward methods to stabilize as is.

push_pop and replace seems a bit weirder. What use cases are they targeting? What kind of performance improvements do you actually see using them vs replicating their behavior naively? C++ and Java don't have any equivalent functionality.

@aturon
Copy link
Member

aturon commented Sep 23, 2015

Should replace from_vec with an impl of the From trait.

@sfackler
Copy link
Member

We should be careful to document the impl so that people can ctrl+f heapify and find it.

@alexcrichton
Copy link
Member

This issue is now entering its cycle-long FCP for stabilization in 1.5

The specific actions to be taken here will be:

  • Deprecate from_vec in favor of From<Vec<T>> for BinaryHeap<T>
  • Stabilize into_vec as well as add Into<Vec<T>> for BinaryHeap<T>
  • Stabilize intoto_sorted_vec

The push_pop and replace methods will have an FCP at a later time.

@alexcrichton alexcrichton added final-comment-period In the final comment period and will be merged soon unless new substantive objections are raised. and removed I-nominated labels Sep 24, 2015
@BurntSushi
Copy link
Member

I think we want From<BinaryHeap<T>> for Vec<T> instead? (I think this gives us the Into impl automatically.)

@steveklabnik steveklabnik added this to the 1.5 milestone Oct 1, 2015
@photino
Copy link

photino commented Oct 21, 2015

If we have already stabilized the into_vec method, are there any good reasons for adding Into<Vec<T>> for BinaryHeap<T> with the same functionality?

@sfackler
Copy link
Member

Into<Vec<T>> can be used in generic contexts.

@alexcrichton
Copy link
Member

The libs team discussed this today and the decision was to stabilize.

@alexcrichton alexcrichton mentioned this issue Oct 23, 2015
Merged
alexcrichton added a commit to alexcrichton/rust that referenced this issue Oct 25, 2015
@alexcrichton
std: Stabilize library APIs for 1.5
ff49733 
This commit stabilizes and deprecates library APIs whose FCP has closed in the
last cycle, specifically:

Stabilized APIs:

* `fs::canonicalize`
* `Path::{metadata, symlink_metadata, canonicalize, read_link, read_dir, exists,
   is_file, is_dir}` - all moved to inherent methods from the `PathExt` trait.
* `Formatter::fill`
* `Formatter::width`
* `Formatter::precision`
* `Formatter::sign_plus`
* `Formatter::sign_minus`
* `Formatter::alternate`
* `Formatter::sign_aware_zero_pad`
* `string::ParseError`
* `Utf8Error::valid_up_to`
* `Iterator::{cmp, partial_cmp, eq, ne, lt, le, gt, ge}`
* `<[T]>::split_{first,last}{,_mut}`
* `Condvar::wait_timeout` - note that `wait_timeout_ms` is not yet deprecated
  but will be once 1.5 is released.
* `str::{R,}MatchIndices`
* `str::{r,}match_indices`
* `char::from_u32_unchecked`
* `VecDeque::insert`
* `VecDeque::shrink_to_fit`
* `VecDeque::as_slices`
* `VecDeque::as_mut_slices`
* `VecDeque::swap_remove_front` - (renamed from `swap_front_remove`)
* `VecDeque::swap_remove_back` - (renamed from `swap_back_remove`)
* `Vec::resize`
* `str::slice_mut_unchecked`
* `FileTypeExt`
* `FileTypeExt::{is_block_device, is_char_device, is_fifo, is_socket}`
* `BinaryHeap::from` - `from_vec` deprecated in favor of this
* `BinaryHeap::into_vec` - plus a `Into` impl
* `BinaryHeap::into_sorted_vec`

Deprecated APIs

* `slice::ref_slice`
* `slice::mut_ref_slice`
* `iter::{range_inclusive, RangeInclusive}`
* `std::dynamic_lib`

Closes rust-lang#27706
Closes rust-lang#27725
cc rust-lang#27726 (align not stabilized yet)
Closes rust-lang#27734
Closes rust-lang#27737
Closes rust-lang#27742
Closes rust-lang#27743
Closes rust-lang#27772
Closes rust-lang#27774
Closes rust-lang#27777
Closes rust-lang#27781
cc rust-lang#27788 (a few remaining methods though)
Closes rust-lang#27790
Closes rust-lang#27793
Closes rust-lang#27796
Closes rust-lang#27810
cc rust-lang#28147 (not all parts stabilized)
bors added a commit that referenced this issue Oct 25, 2015
@bors
Auto merge of #29254 - alexcrichton:stabilize-1.5, r=brson
e02ada6 
This commit stabilizes and deprecates library APIs whose FCP has closed in the
last cycle, specifically:

Stabilized APIs:

* `fs::canonicalize`
* `Path::{metadata, symlink_metadata, canonicalize, read_link, read_dir, exists,
   is_file, is_dir}` - all moved to inherent methods from the `PathExt` trait.
* `Formatter::fill`
* `Formatter::width`
* `Formatter::precision`
* `Formatter::sign_plus`
* `Formatter::sign_minus`
* `Formatter::alternate`
* `Formatter::sign_aware_zero_pad`
* `string::ParseError`
* `Utf8Error::valid_up_to`
* `Iterator::{cmp, partial_cmp, eq, ne, lt, le, gt, ge}`
* `<[T]>::split_{first,last}{,_mut}`
* `Condvar::wait_timeout` - note that `wait_timeout_ms` is not yet deprecated
  but will be once 1.5 is released.
* `str::{R,}MatchIndices`
* `str::{r,}match_indices`
* `char::from_u32_unchecked`
* `VecDeque::insert`
* `VecDeque::shrink_to_fit`
* `VecDeque::as_slices`
* `VecDeque::as_mut_slices`
* `VecDeque::swap_remove_front` - (renamed from `swap_front_remove`)
* `VecDeque::swap_remove_back` - (renamed from `swap_back_remove`)
* `Vec::resize`
* `str::slice_mut_unchecked`
* `FileTypeExt`
* `FileTypeExt::{is_block_device, is_char_device, is_fifo, is_socket}`
* `BinaryHeap::from` - `from_vec` deprecated in favor of this
* `BinaryHeap::into_vec` - plus a `Into` impl
* `BinaryHeap::into_sorted_vec`

Deprecated APIs

* `slice::ref_slice`
* `slice::mut_ref_slice`
* `iter::{range_inclusive, RangeInclusive}`
* `std::dynamic_lib`

Closes #27706
Closes #27725
cc #27726 (align not stabilized yet)
Closes #27734
Closes #27737
Closes #27742
Closes #27743
Closes #27772
Closes #27774
Closes #27777
Closes #27781
cc #27788 (a few remaining methods though)
Closes #27790
Closes #27793
Closes #27796
Closes #27810
cc #28147 (not all parts stabilized)
@alexcrichton alexcrichton removed the final-comment-period In the final comment period and will be merged soon unless new substantive objections are raised. label Nov 4, 2015
@alexcrichton alexcrichton removed this from the 1.5 milestone Nov 4, 2015
@alexcrichton alexcrichton changed the title Tracking issue for BinaryHeap Tracking issue for BinaryHeap::{push_pop, replace} Nov 4, 2015
@xosmig xosmig mentioned this issue Apr 15, 2016
Merged
@constituent
Copy link

I'd like to ask a question about replace.

It seems it's the optimized (and suggested) way if you are sure that one item will be pushed after a pop. Sometimes the pushed item is related with the popped one, say, pop an x: u32 and then push x / 2 back. In this situation replace(&mut self, item: T) cannot be used as the will-be-pushed item is not known while calling replace.

Should I use normal pop & push, or replace can have a more generalized signature?

Furthermore, is it possible to push back conditionally, e.g. only if x > 1 (else break the pop-push-pop-... loop)

@bsteinb
Copy link

bsteinb commented Jul 16, 2016

@constituent I think you might be interested in contain-rs/discuss#13

@sfackler
Copy link
Member

I believe the functionality of replace is subsumed by peek_mut.

@sfackler sfackler added final-comment-period In the final comment period and will be merged soon unless new substantive objections are raised. and removed I-nominated labels Sep 7, 2016
@sfackler
Copy link
Member

sfackler commented Sep 7, 2016

The libs team discussed the remaining unstable methods, and are putting them in a final comment period to deprecate. They're fairly niche, and peek_mut provides similar functionality in a more flexible API.

@alexcrichton
Copy link
Member

The libs team discussed this at triage the other day and the conclusion was to deprecate

@alexcrichton alexcrichton mentioned this issue Sep 29, 2016
Merged
alexcrichton added a commit to alexcrichton/rust that referenced this issue Oct 3, 2016
@alexcrichton
std: Stabilize and deprecate APIs for 1.13
10c3134 
This commit is intended to be backported to the 1.13 branch, and works with the
following APIs:

Stabilized

* `i32::checked_abs`
* `i32::wrapping_abs`
* `i32::overflowing_abs`
* `RefCell::try_borrow`
* `RefCell::try_borrow_mut`
* `DefaultHasher`
* `DefaultHasher::new`
* `DefaultHasher::default`

Deprecated

* `BinaryHeap::push_pop`
* `BinaryHeap::replace`
* `SipHash13`
* `SipHash24`
* `SipHasher` - use `DefaultHasher` instead in the `std::collections::hash_map`
  module

Closes rust-lang#28147
Closes rust-lang#34767
Closes rust-lang#35057
Closes rust-lang#35070
bors added a commit that referenced this issue Oct 3, 2016
@bors
Auto merge of #36815 - alexcrichton:stabilize-1.13, r=aturon
7a26aec 
std: Stabilize and deprecate APIs for 1.13

This commit is intended to be backported to the 1.13 branch, and works with the
following APIs:

Stabilized

* `i32::checked_abs`
* `i32::wrapping_abs`
* `i32::overflowing_abs`
* `RefCell::try_borrow`
* `RefCell::try_borrow_mut`

Deprecated

* `BinaryHeap::push_pop`
* `BinaryHeap::replace`
* `SipHash13`
* `SipHash24`
* `SipHasher` - use `DefaultHasher` instead in the `std::collections::hash_map`
  module

Closes #28147
Closes #34767
Closes #35057
Closes #35070
alexcrichton added a commit to alexcrichton/rust that referenced this issue Oct 10, 2016
@alexcrichton
std: Stabilize and deprecate APIs for 1.13
2d1feef 
This commit is intended to be backported to the 1.13 branch, and works with the
following APIs:

Stabilized

* `i32::checked_abs`
* `i32::wrapping_abs`
* `i32::overflowing_abs`
* `RefCell::try_borrow`
* `RefCell::try_borrow_mut`
* `DefaultHasher`
* `DefaultHasher::new`
* `DefaultHasher::default`

Deprecated

* `BinaryHeap::push_pop`
* `BinaryHeap::replace`
* `SipHash13`
* `SipHash24`
* `SipHasher` - use `DefaultHasher` instead in the `std::collections::hash_map`
  module

Closes rust-lang#28147
Closes rust-lang#34767
Closes rust-lang#35057
Closes rust-lang#35070
@lopopolo lopopolo mentioned this issue May 5, 2021
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
B-unstable Blocker: Implemented in the nightly compiler and unstable. final-comment-period In the final comment period and will be merged soon unless new substantive objections are raised. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
9 participants
@steveklabnik @alexcrichton @BurntSushi @aturon @sfackler @photino @bsteinb @eefriedman @constituent