Контейнер STL для выбора и удаления случайного элемента?

Question

Алгоритм, который я реализую, имеет структуру:

while C is not empty
  select a random entry e from C
  if some condition on e
    append some new entries to C (I don't care where)
  else
    remove e from C

Важно, чтобы каждая итерация l oop e выбиралась случайным образом (с одинаковой вероятностью).

В идеале все шаги select, append и remove - это O (1).

Если я правильно понимаю, при использовании std::list шаги append и remove будут равны O (1). ) но случайный выбор будет O (n) (например, с использованием std::advance, как в , это решение ).

, std::deque и std::vector, кажется, имеют дополняющее значение O ( 1) и операции O (n).

Я предполагаю, что std::set привнесет некоторую сложность O (log n).

Существует ли контейнер stl, который поддерживает все три операции, которые Мне нужно в постоянное время (или амортизированное постоянное время)?

Answer 1

Если вас не интересует порядок и уникальность элементов вашего контейнера, вы можете использовать следующее:

std::vector<int> C;
while (!C.empty()) {
  size_t pos = some_function_returning_a_number_between_zero_and_C_size_minus_one();
  if (condition())
    C.push_back(new_entry);
  else {
    C[i] = std::move(C.back());
    C.pop_back();
  }
}

Answer 2

Я предполагаю, что std :: set привнесет некоторую сложность O (log n).

Не совсем. Случайный выбор в наборе имеет линейную конкуренцию.

Есть ли контейнер stl, который поддерживает все три операции, которые мне нужны в постоянное время (или амортизированное постоянное время)?

Строго говоря, нет.

Однако, если вам не важен порядок элементов, то вы можете удалить из вектора или из deque в постоянное время. При таком ослаблении требований все операции будут иметь постоянную сложность.

---

В случае, если вам нужно будет поддерживать порядок между операциями, постоянная сложность все еще будет возможна, пока порядок элементов не ' Не нужно влиять на случайное распределение (т.е. вы хотите равномерное распределение). Решение состоит в том, чтобы использовать гибридный подход:

Сохранить значения в связанном списке. Сохраните итератор для каждого элемента в векторе. Используйте вектор для случайного выбора; Сотрите элемент списка с помощью итератора, который сохраняет порядок элементов; Стереть итератор из вектора, не поддерживая порядок итераторов. При добавлении элементов в список не забудьте добавить итератор.

Answer 3

Такой контейнер не существует, если порядок элементов должен быть согласованным. Вы можете получить O(1) выделение и (амортизироваться) добавить с vector или deque, но удаление - O(n). Вы можете получить O(1) (в среднем регистре) вставку и удаление с помощью unordered_map, но выбор равен O(n). list возвращает вас O(1) для добавления и удаления, но выбор O(n). Нет контейнера, в котором вы получите O(1) за все три операции. Выясните наименее часто используемый, выберите контейнер, который работает для других, и примите, что одна операция будет медленнее.

Если порядок контейнера не имеет значения для каждого комментария 3365922 , шаг удаления может быть выполнен в O(1) на vector / deque путем swap проверки связи удаляемого элемента с последним элементом, затем выполните pop_back.