Получить случайный элемент и удалить его - PullRequest
Новая
       16

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

9 голосов
/ 10 февраля 2012

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

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

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

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

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

Ответы [ 3 ]

14 голосов
/ 10 февраля 2012

У вас есть решение, и оно кажется совершенно нормальным.Идиоматический способ написать его на C ++ - это не создать другой класс (и , пожалуйста , не наследовать от std::vector), а просто написать функцию: 

template <typename T>
void remove_at(std::vector<T>& v, typename std::vector<T>::size_type n)
{
    std::swap(v[n], v.back());
    v.pop_back();
}

Использование: 

remove_at(v, 42);

Это дает ту же гарантию исключения, что и std::swap<T>.

Теперь, если вы хотите вернуть объект, и у вас есть доступ к C ++11 компилятор, вы можете сделать это следующим образом.Сложной задачей является обеспечение базовой гарантии исключения во всех случаях: 

template <typename T>
T remove_at(std::vector<T>&v, typename std::vector<T>::size_type n)
{
    T ans = std::move_if_noexcept(v[n]);
    v[n] = std::move_if_noexcept(v.back());
    v.pop_back();
    return ans;
}

Действительно, вы не хотите, чтобы вектор оставался в недопустимом состоянии, если во время операции перемещения выдается исключение.

0 голосов
/ 10 февраля 2012

Да, есть решение, хорошо сбалансированное бинарное дерево.

По одному на каждый узел вам нужно будет хранить количество узлов на каждой стороне.Отсюда O (log N), чтобы найти n-й элемент.

Удаление n-го элемента также является O (log N), так как вам нужно вернуться обратно к дереву, чтобы исправить все значения.Любая перебалансировка тоже будет не более O (log N).

Дерево считается хорошо сбалансированным, если ни один листовой узел не находится на 2 узла глубже другого.Посмотрите деревья AVL, чтобы получить алгоритм балансировки.

Было бы неплохо, если бы стандартная библиотека «открыла» использование деревьев, используемых для std :: set и std :: map, в качестве открытого интерфейса для использования.в пользовательских деревьях.

0 голосов
/ 10 февраля 2012

С O (n) сложностью

vec.erase (vec.begin () + randomIdx); randomIdx будет между 0 и vec.size () - 1

Если вам нужна сложность O (1), вы можете либо использовать контейнер списка, например, либо заменить элемент последним и удалить его. (Как уже упоминалось)

...