What is complexity of iteration over indexmap?

[AngelicosPhosphoros]

I recently discovered that std::collections::HashMap iterator iterates over all items in map for O(capacity), not O(length).
Indexmap probably can have iteration for O(length) using index based access. What is current complexity?

[cuviper]

The map iterators are based on the underlying vector of items, and that's contiguous, no deletion tombstones or anything like that. So yes, they should all be O(length).

That's also true for the simple set iterators. The multi-set ones like difference or union do add hash lookups, but that's still O(1) average, so I guess the same complexity overall.

[bluss]

This is basically described in the readme https://github.com/bluss/indexmap#performance but the readme is old and needs updating, so sure, it's hard to know what to trust.

[AngelicosPhosphoros]

Well, it says that iteration is performant, it doesn't say exact complexity :)

[bluss]

Hm, it says the key-value pairs are stored in a Vec and the iteration is over them, densely, that's why it's basically describing it.