STL container to select and remove random item?

Question

The algorithm I'm implementing has the structure:

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

It's important that each iteration of the loop e is chosen at random (with uniform probability).

Ideally the select, append and remove steps are all O(1).

If I understand correctly, using std::list the append and remove steps will be O(1) but the random selection will be O(n) (e.g., using std::advance as in this solution).

And std::deque and std::vector seem to have complementary O(1) and O(n) operations.

I'm guessing that std::set will introduce some O(log n) complexity.

Is there any stl container that supports all three operations that I need in constant time (or amortized constant time)?

Answer 1

No such container exists if element order should be consistent. You can get O(1) selection and (amortized) append with vector or deque, but removal is O(n). You can get O(1) (average case) insertion and removal with unordered_map, but selection is O(n). list gets you O(1) for append and removal, but O(n) selection. There is no container that will get you O(1) for all three operations. Figure out the least commonly used one, choose a container which works for the others, and accept the one operation will be slower.

If the order of the container doesn't matter per use 3365922's comment, the removal step could be done in O(1) on a vector/deque by swapping the element to be removed with the final element, then performing a pop_back.

Answer 2

I'm guessing that std::set will introduce some O(log n) complexity.

Not quite. Random selection in a set has linear compexity.

Is there any stl container that supports all three operations that I need in constant time (or amortized constant time)?

Strictly speaking no.

However, if you don't care about the order of the elements, then you can remove from a vector or deque in constant time. With this relaxation of requirements, all operations would have constant complexity.

---

In case you did need to keep the order between operations, constant complexity would still be possible as long as the order of the elements doesn't need to affect the random distribution (i.e. you want even distribution). The solution is to use a hybrid approach:

Store the values in a linked list. Store iterator to each element in a vector. Use the vector for random selection; Erase the element of the list using the iterator which keeps the order of elements; Erase the iterator from the vector without maintaining order of the iterators. When adding elements to the list, remember to add the iterator.

Answer 3

If you don't care about order and uniqueness of elements in your container, you can use the following:

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();
  }
}