>>538
SGIの実装がlinearなだけ
ttp://www.sgi.com/tech/stl/FAQ.html

仕様では、constant timeのほうが良いとされているけど。