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)?

Unfortunately there isn't a container where all the operations are of constant time complexity. If there was one, then that would be the only one we ever needed. — Ron, Mar 19 '20 at 22:03
`std::vector`? selecting random is `C[rand()]`, `append` is `push_back` and `remove` is `std::swap(C.back(), C[i])` and `C.pop_back()` — fas, Mar 19 '20 at 22:05

score 5 · Answer 1 · edited Mar 19 '20 at 22:15

5

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

edited Mar 19 '20 at 22:15

Yakov Galka

70,775
16
139
220

answered Mar 19 '20 at 22:13

fas

1,393
10
20

2

No need to swap. Simply move the last element over the one that is about to be removed (or just copy, since it is int, but move should be used in generic case). – eerorika Mar 19 '20 at 22:14

ShadowRanger · Answer 2 · 2020-03-19T22:09:17.077

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.

edited Mar 19 '20 at 22:09

answered Mar 19 '20 at 22:07

ShadowRanger

143,180
12
188
271

`vector or deque, but removal is O(n)` if we care about order – fas Mar 19 '20 at 22:08
yeah. I think user3365922's comment is the answer for me. – Alec Jacobson Mar 19 '20 at 22:08

eerorika · Answer 3 · 2020-03-19T22:21:49.070

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.

STL container to select and remove random item?

3 Answers3