switch to std::sorted_map for PrefixData

[wolfv]

We could switch to an std::sorted_map in PrefixData, and that would help to remove some manual sorting in micromamba.

[hp77-creator]

@wolfv switch from PrefixData::package_map to std::sorted_map? Are you talking about the following line

    const PrefixData::package_map& PrefixData::records() const

[wolfv]

yeah, I think so. package_map is defined here: https://github.com/mamba-org/mamba/blob/08f818719a552f09f41e2907b9f4594ed381fc25/include/mamba/core/prefix_data.hpp#L35 and here

https://github.com/mamba-org/mamba/blob/08f818719a552f09f41e2907b9f4594ed381fc25/include/mamba/core/prefix_data.hpp#L22

[jeewonkoo]

Hello, is it okay if I make a change regard this issue and create a new PR?

[wolfv]

yes, of course.

[jeewonkoo]

Sounds good. However, I think I need some detailed guidance about what you mean by 'switch from PrefixData::package_map to std::sorted_map'. Do you mean by change unordered map to std::map and sort it? I don't see any std::sorted_map in C++.

[shreve]

std::maps are always sorted internally, so I think that's what this ticket meant.

[jeewonkoo]

std::maps are always sorted internally, so I think that's what this ticket meant.

I see. So it seems like just simply change unordered_map to std::map?

[shreve]

simply change unordered_map to std::map?

That, then presumably take advantage of it being sorted in places like PrefixData::sorted_records().

As a disclaimer, I don't know. I'm here because I subscribed to this issue before hacktoberfest last year thinking I would get around to it 😅

[jeewonkoo]

simply change unordered_map to std::map?

That, then presumably take advantage of it being sorted in places like PrefixData::sorted_records().

As a disclaimer, I don't know. I'm here because I subscribed to this issue before hacktoberfest last year thinking I would get around to it 😅

No worries! Thanks for the kind advice :)

[Hind-M]

Hey @wolfv! I started looking into this, and it seems that we only do some sorting here: https://github.com/mamba-org/mamba/blob/f7a001e24df59ec8e35b45b2e404cd8b049c8eb9/libmamba/src/api/list.cpp#L62-L68 For the other places where we use records(), we do a search on the returned map. So I'm not sure that it's better to switch to a map instead of an unordered_map if we perform search several times... What do you think? I was also thinking about some benchmarking or at least a test to check that it's not slower after the change, so if you have something in mind that could be relevant, that would be great! :)