Ассоциированный массив с поиском по двум ключам

[-=RedCAT=-]

Необходимо создать ассоциированный массив (карту) на С++ удовлетворяющую следующим требованиям:

• К каждому элементу привязаны 2 ключа, и поиск должен происходить по любому одному из них
• К каждому элементу карты должен быть возможен произвольный доступ по номеру (как в обычном массиве)
• Возможно удаление элемента из карты (в этом случае удаляются оба его ключа)

Для поиска элемента по одному из двух ключей я хотел создать два красно-черных дерева, но в этом случае не получается реализовать произвольный доступ к элементам. Может надо какую-то другую стратегию применить я не знаю... Помогите, пожалуйста!
Заранее спасибо.