무작위로 임의의 원소를 하나씩 접근하고 지우는 데 있어 좋은 STL container

중간에 원소 추가가 없다는 가정이 전제된다.


우선 vector는 random iterator를 지원한다. 이로부터 iterator를 상수 시간만에 임의의 위치로 옮길 수 있다.
그리고 이 iterator에 해당하는 원소를 지우는 작업은, 지워지는 원소 뒤의 원소들 개수에 대한 선형 복잡도를 갖는다. (http://www.cplusplus.com/reference/stl/vector/erase/) 엄밀히는 지우는 원소의 개수도 판단해야겠지만. 일단 하나씩 접근하고 하나씩 지운다고 가정한다.

지우는 시간으로 따지면, set의 경우 logN (N:set이 포함하는 전체 원소 개수) 복잡도를 갖는다.
이것은  map도 그렇다. 그러나 이들은 임의 접근을 빨리 할 수가 없다.

set은 erase가 빠르고, vetor는 임의접근이 빠르다는 얘기인데..
같은 개수의 원소들이 있는 상태에서 무작위로 하나씩 접근함과 동시에 컨테이너에서 제거하는 루틴을 짜보고 비교해봤다.
결과는 vector 가 우세.

임의접근이 가능한 container 는 ,deque 이 있는데
deque도 충분히 빠를 것 같다. 
사실 귀찮아서 일단 여기까지 쓰려고 한다.;