Skip to content

Wrong first element popped in pop_first() for BTreeSet #68829

Closed
@SetTheorist

Description

@SetTheorist

Summary:
When popping elements using pop_first() from a BTreeSet, the first element popped is not the min element, though remaining elements are popped in expected order.

I tried this code:

#![feature(map_first_last)]
use std::collections::BTreeSet;

type D = isize;
#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct T(pub D, pub D);

pub fn main() {
    let mut s = BTreeSet::new();
    let v = vec![
        T(0, 0),
        T(63, 63),
        T(63, 252),
        T(126, 126),
        T(189, 189),
        T(252, 252),
        T(252, 441),
        T(315, 315),
        T(378, 378),
        T(441, 441),
        T(441, 503),
        T(504, 504),
    ];
    for x in &v {
        s.insert(x);
    }
    while let Some(x) = s.pop_first() {
        print!(" {:?}", x);
    }
    println!("");
}

I expected to see this happen:

 T(0, 0) T(63, 63) T(63, 252) T(126, 126) T(189, 189) T(252, 252) T(252, 441) T(315, 315) T(378, 378) T(441, 441) T(441, 503) T(504, 504)

Instead, this happened: (Note the first result).

 T(252, 441) T(0, 0) T(63, 63) T(63, 252) T(126, 126) T(189, 189) T(252, 252) T(315, 315) T(378, 378) T(441, 441) T(441, 503) T(504, 504)

For various subsets of the given inputs I tried, it appears to give the expected behaviour.

Meta

rustc --version --verbose:
rustc 1.42.0-nightly (8417d68 2020-02-03)
binary: rustc
commit-hash: 8417d68
commit-date: 2020-02-03
host: x86_64-unknown-linux-gnu
release: 1.42.0-nightly
LLVM version: 9.0

Metadata

Metadata

Assignees

No one assigned

    Labels

    A-collectionsArea: `std::collections`C-bugCategory: This is a bug.T-libs-apiRelevant to the library API team, which will review and decide on the PR/issue.requires-nightlyThis issue requires a nightly compiler in some way.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions