중간에 원소 추가가 없다는 가정이 전제된다.
우선 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도 충분히 빠를 것 같다.
사실 귀찮아서 일단 여기까지 쓰려고 한다.;
우선 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도 충분히 빠를 것 같다.
사실 귀찮아서 일단 여기까지 쓰려고 한다.;
'Application-level프로그래밍' 카테고리의 다른 글
(C++) Inline function (MSDN) (0) | 2009.10.11 |
---|---|
(C++) new 연산자 (MSDN) (0) | 2009.10.06 |
VS2005 이진파일이 디버그정보를 사용하여 빌드 되지 않았습니다. 디버깅 안되는 문제 (0) | 2009.09.17 |
C++ 연산자 우선순위 (0) | 2009.09.17 |
아스키 코드값 (0) | 2009.09.17 |