IndexMap / IndexSet comparison isn't order-aware.

[emilio]

This looks like a bug to me. I'd expect this test-case to pass:

    #[test]
    fn eq() {
        let m1: IndexMap<_, _> = vec![(1, 1), (2, 2)].into_iter().collect();
        let m2: IndexMap<_, _> = vec![(2, 2), (1, 1)].into_iter().collect();
        assert_ne!(m1, m2);
    }

The maps are most definitely not the same, and if you're using IndexMap is because you care about ordering.

This came up because I was doing some Firefox profiling, and transitioning youtube from fullscreen to not-fullscreen or vice versa spends a lot of time under find() comparing custom properties (doing the lookup in IndexMap::eq). Turns out we don't actually need to do any lookup, and not being ordering aware is a correctness issue.

[cuviper]

It's been this way ever since PartialEq + Eq were implemented for the original OrderMap in #23, with the goal of HashMap consistency, and I followed suit in #46 when adding OrderSet. It also came up in #91 (comment) where I acknowledged that this may be surprising. Maybe we need to emphasize this point in documentation.

I've added this as a possible change for 2.0 in #135.

[bluss]

IndexMap is definitely a bit inbetween, it partly wants to be a drop-in for HashMap (that's the starting design, drop-in with extra features). That's the reason for preserving the same equality semantics.

I think that a fully order preserving hashmap would be a different crate than this one. (One that preserves order on remove, efficiently).

[mwillsey]

I would love to see an opt-in order-preserving comparison. Here's an idea that wouldn't require a 2.0:

Add an additional type parameter <..., E = Unordered> to IndexMap and IndexSet. E is one of the two unsized marker types Ordered and Unordered, which determines the equality semantics. This could also allow for Ord + Hash on IndexMap<..., Ordered. I think the implementations for Ordered could just defer to the underlying entries: Vec.

Happy to put together a PR if people are excited.

[cuviper]

I fear a proliferation of type parameters -- I proposed an index type in #147, and I think it's likely we'll want an Allocator type once that stabilized in the standard library. But IndexMap<K, V, S, I, A> already scares me.

An ordering parameter seems less necessary to me, because that's a relatively superficial change which you could implement with a wrapper, just using Iterator::cmp. We could even add a method for that, but you'll want a wrapper to get that behavior in generic Ord contexts, kind of like std::cmp::Reverse.

FWIW, I also did add order-aware comparisons for the slice proposal in #177.

[mwillsey]

Yeah, that makes sense. The proposed Slice type is sufficient for my use case anyway! It makes order-sensitive comparison on a newtyped IndexMap easy and cheap.

[OvermindDL1]

Ran into this bug as well, and yes it is a bug, because when get_index'ing into the maps, even though they tested as equal, they returned different values, thus they are obviously not equal...