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...

[cuviper]

@OvermindDL1 that just means that it has some properties that are not part of the equality check. You could say the same about iteration order on a regular HashMap (different even when the maps compare equal), or capacity() on any collection. We've chosen to follow HashMap semantics here, where equality just means that they contain the same things, regardless of order.

[OvermindDL1]

std's HashMap's don't have an indexed access, and iterators by it are defined as undetermined order, thus their only public direct access API is by key, so matching on that is fine. IndexMap/Set on the other hand has both key and index direct access, and just like how on a HashMap you'd expect every key to return the same value in eq hashmaps, one would expect the value returned from the same get_index in IndexMap to return the same value as well for the same input.

In short, wouldn't expect capacities to be the same or so forth, but would expect for each key and index to have the same value output in both indexmaps that are equal as the index is a key.

[vasilakisfil]

It's a bit of gray zone whether it should take into account the key order in equality. I think it's fine as it is, since it's just a HashMap in the end. However, I think it would be nice if it provided a method to check for equality that takes into account the order of the keys.

[cuviper]

The Slice API shipped in 2.0.0 with order-aware comparisons -- hope that helps!

use indexmap::IndexMap;

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

playground

[cuviper]

FYI: I've reintroduced ordermap as a newtype wrapper that is more order-aware:
https://crates.io/crates/ordermap/0.5.0

[conradkleinespel]

Thanks for your work and examples on this issue @cuviper ! Really helpful a year later when asking myself the same questions 👍