Здравствуйте, Аноним, Вы писали:

А>какие могут быть еще варианты ?
могу предложить два варианта: boost::flat_map, aurgmented RB-tree с подсчетом детей справа и слева (за основу можно взять что-ни будь такое: http://kaba.hilvi.org/pastel/pastel/sys/redblacktree.htm )