Получить случайный элемент и удалить его

Проблема: мне нужно получить случайный элемент для контейнера и также удалить его из этого контейнера. Контейнер не нужно сортировать. Меня не волнует порядок.

• Вектор может получить случайный элемент в O (1) , но удалить его только в O (N)
• Список удаляет элемент в O (1) , но может получить случайный элемент только в O (N)

. Поэтому я придумал создать собственный вектор, который позволит вам удалить любой элемент по его индексу с помощью O (1) + сложность. Идея состоит в том, чтобы поменять местами последний элемент и элемент, который вы хотите удалить, а затем pop_back () . Если вам нужно удалить последний элемент - просто pop_back () . Порядок вектора не будет таким же, но вы получите метод быстрого удаления.

Насколько я понимаю, у deque более медленный доступ по индексу и худшая сложность удаления, чем у моего решения, но я не уверен на 100%.

Мне любопытно, существуют ли структуры данных с произвольным доступом и удалением элементов в O (1) или O (logN) по индексу или mb по значению?