unordered_multiset’s API affects its big-O

An STL-style container’s performance can be dramatically affected by minor changes to the underlying data structure’s invariants, which in turn can be dramatically constrained by the container’s chosen API. Since the Boost.Unordered performance project has put std::unordered_foo back in the spotlight, I thought this would be a good week to talk about my favorite little-known STL trivia tidbit: std::unordered_multiset’s decision to support .equal_range dramatically affects its performance!