Skip to content

Tracking issue for BinaryHeap sorted iterator methods #59278

@jonhoo

Description

@jonhoo
Contributor

This tracks the stabilization of BinaryHeap::into_iter_sorted (binary_heap_into_iter_sorted) and BinaryHeap::drain_sorted (binary_heap_drain_sorted) implemented in #65091.

EDIT much later:

  • Stabilize feature(binary_heap_into_iter_sorted) #76234 looked at stabilizing part of this, but didn't come to a conclusion that it was ready-to-go as-is. The questions from there (such as consistency in order with into_sorted_vec) need to be addressed before a future attempt to stabilize.

Original feature request:


Currently, both BinaryHeap::into_iter and BinaryHeap::drain yield the heap elements in an arbitrary order. This seems counter-intuitive given the nature of a heap. Sadly, we can't simply change their behavior behind the scenes, as we would have to remove the implementation of DoubleEndedIterator. Should we perhaps add into_ordered_iter and drain_ordered? The implementation is pretty straightforward so I'd be happy to submit a PR.

Activity

added
T-libs-apiRelevant to the library API team, which will review and decide on the PR/issue.
on Mar 18, 2019
clarfonthey

clarfonthey commented on Mar 30, 2019

@clarfonthey
Contributor

Isn't into_sorted_vec().into_iter() sufficient?

scottmcm

scottmcm commented on Apr 1, 2019

@scottmcm
Member

@clarfon No, because getting the largest k items from that is O(n lg n + k), whereas with into_ordered_iter() it would be O(k lg n).

ckaran

ckaran commented on Apr 2, 2019

@ckaran
clarfonthey

clarfonthey commented on Apr 3, 2019

@clarfonthey
ckaran

ckaran commented on Apr 8, 2019

@ckaran
added
C-enhancementCategory: An issue proposing an enhancement or a PR with one.
C-feature-requestCategory: A feature request, i.e: not implemented / a PR.
and removed
C-enhancementCategory: An issue proposing an enhancement or a PR with one.
on Jun 6, 2019
sekineh

sekineh commented on Oct 2, 2019

@sekineh
Contributor

Hi,

I've implemented both API in the local rust tree.
I see some problems in the API and I'm proposing the better version at the bottom of this comment.

Any ideas?

Currently proposed API

.into_ordered_iter(self)

    /// Returns an iterator which retrieves elements in heap order.
    /// This method consumes the original heap.
    ///
    /// # Examples
    ///
    /// Basic usage:
    ///
    /// ```
    /// #![feature(binary_heap_into_ordered_iter)]
    /// use std::collections::BinaryHeap;
    /// let heap = BinaryHeap::from(vec![1, 2, 3, 4, 5]);
    ///
    /// assert_eq!(heap.into_ordered_iter().take(2).collect::<Vec<_>>(), vec![5, 4]);
    /// ```
    #[unstable(feature = "binary_heap_into_ordered_iter", issue = "59278")]
    pub fn into_ordered_iter(self) -> IntoOrderedIter<T> {
        IntoOrderedIter {
            inner: self,
        }
    }

.drain_ordered(&mut self)

    /// Returns an iterator which retrieves elements in heap order.
    /// The retrieved elements will be removed from the original heap.
    ///
    /// Note: Unlike other `.drain()` methods, this method removes elements *lazily*.
    /// Only the retrieved elements will be removed.
    ///
    /// # Examples
    ///
    /// Basic usage:
    ///
    /// ```
    /// #![feature(binary_heap_drain_ordered)]
    /// use std::collections::BinaryHeap;
    ///
    /// let mut heap = BinaryHeap::from(vec![1, 2, 3, 4, 5]);
    /// assert_eq!(heap.len(), 5);
    ///
    /// let removed = heap.drain_ordered().take(2).collect::<Vec<_>>(); 
    /// assert_eq!(removed, vec![5, 4]);
    /// assert_eq!(heap.len(), 3);
    ///
    /// let removed = heap.drain_ordered().take(3).collect::<Vec<_>>(); 
    /// assert_eq!(removed, vec![3, 2, 1]);
    /// assert_eq!(heap.len(), 0);
    /// ```
    #[inline]
    #[unstable(feature = "binary_heap_drain_ordered", issue = "59278")]
    pub fn drain_ordered(&mut self) -> DrainOrdered<'_, T> {
        DrainOrdered {
            inner: self,
        }
    }

Problems I see

  • (P1) Too many iters: New users won't get to the right one.
    => Edit: BinaryHeap doc example could be updated after this feature would be stabilized.
  • (P2) Code duplication: The impl of .into_ordered_iter and .drain_ordered is essentially the same. They are duplicated codes.
    => @scottmcm: Both owning and borrowing versions are useful.
  • (P3) .drain() inconsistency: The semantics of .drain_ordered() is lazy. Other all .drain() method immediately removes elements.
    => @scottmcm: I agree that drop(foo.drain_ordered()); should result in an empty foo. But that can be accomplished by just clearing in the iterator's drop (assuming it's safe so doesn't need to amplify).

Better API (Solution)

  • Implement one method .into_ordered_iter(&mut self).
    This is the mix of above .into_ordered_iter(self) and .drain_ordered(&mut self). I picked more useful one and changed the name.
  • Do not implement .drain_ordered() method.

-> Solves P2 and P3. Partially solves P1 (discoverability).

scottmcm

scottmcm commented on Oct 2, 2019

@scottmcm
Member

Both owning and borrowing versions are useful. I can't return a version that borrows from a local variable, but I can return the version that moves it.

That said, I agree that drop(foo.drain_ordered()); should result in an empty foo. But that can be accomplished by just clearing in the iterator's drop (assuming it's safe so doesn't need to amplify).

(I'm not worried about discoverability here; people have presumably been taught about the difference in things like Vec, which also has .into_iter() and .drain(..).)

sekineh

sekineh commented on Oct 2, 2019

@sekineh
Contributor

Thanks @scottmcm for the comment. I updated my comment accordingly.

@jonhoo, are you still working on PR for this?

jonhoo

jonhoo commented on Oct 3, 2019

@jonhoo
ContributorAuthor

@sekineh nope, not currently working on a PR

24 remaining items

Loading
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    A-collectionsArea: `std::collections`A-iteratorsArea: IteratorsB-unstableBlocker: Implemented in the nightly compiler and unstable.C-tracking-issueCategory: An issue tracking the progress of sth. like the implementation of an RFCLibs-TrackedLibs issues that are tracked on the team's project board.T-libs-apiRelevant to the library API team, which will review and decide on the PR/issue.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

      Development

      No branches or pull requests

        Participants

        @jonhoo@MiSawa@alexeymuranov@estebank@jonas-schievink

        Issue actions

          Tracking issue for `BinaryHeap` sorted iterator methods · Issue #59278 · rust-lang/rust