Насколько я помню random access означает просто одинаковое время доступа к эл-ту, массив этому требованию удовлетворяет. Вероятно Вы имели ввиду ассоциативный контейнер, напр std::map/set. С таким конечно думать не надо, все операции очевидны (за что придется заплатить перегонками в др местах кода). И так ли уж это хорошо? Напр при большом кол-ве удаляемых std::set легко может оказаться медленнее. Вообще чем сортированный массив хуже? Тем что накладно вставлять/удалять? Так здесь это в одной интерактивной операции, не страшно. Что тут сложного/военного? Только то что никогда раньше это не делали
random access - это фактически доступ по индексу за константное время (например вектор).
Например в списке, даже сортированном, поиск будет "линейным", а не "логарифмическим", но..
Я хотел сказать, что если подразумевается возможное удаление, вставка элементов, то для вектора, даже с логарифмическим поиском, это будет затратнее в целом, чем, например, с тем же списком, хоть и с линейным поиском.
Вообщем, все эти пляски с частными случаями и оптимизацией сейчас напоминают миф о Сизифе..
Может имеет смысл/правильнее вернуться назад и пересмотреть архитектурно те решения, которые привели к этой задаче?)
