I think explicitly stating what it doesn’t guarantee is the right thing to do. Otherwise, the API becomes tied to your implementation through implicit details, which can prevent future generic performance improvements (e.g. unordered_map pointer stability in C++ prevents the implementation from being changed to a different representation like absl::flat_hash_map, even though that’s a guarantee that most people don’t care about).

Re: performance considerations. This is important, but for a performance critical application, any compiler, library etc version change can cause regressions, so it seems better to benchmark often and then tackle this, rather than make assumptions based on implicit (or even explicit) guarantees.