Problem: I need to get a random element for a container and also delete it from that container. Container does not need to be sorted. I dont care about the order.
- Vector can get me random element in
O(1)
but delete it only inO(N)
- List deletes element in
O(1)
but can only get random element inO(N)
So I came up with an idea of making a custom vector that allow you to remove any element by its index with O(1)+
complexity.
The idea is to swap the last element and an element you want to remove and then pop_back()
.
If you need to remove the last elemtent - just pop_back()
.
The order of the vector will not be the same but you get a fast remove method.
As i can understand deque have slower access by index and worse removal complexity then my solution but im not 100% sure.
I'm curious are there data structures that have random access and element removal in O(1)
or O(logN)
by index or mb by value ?