いや、set/mapは厳密に要件を満たすのは結構むずかしいよ。
単純な２分木だと、最悪条件ができる可能性があって、
STLのset/mapはそれを許さないから。

で、結局どの実装も赤黒木になってると思った。