#include <iostream>
#include <stdio.h>
#include <vector>
#include <time.h>
#include <conio.h>
using namespace std;

#define MAX_SIZE 100000000
void main()
{
vector<int> vi(MAX_SIZE);
vi[(MAX_SIZE)-1] = 2;

vector<int>::iterator pvi;
clock_t start;

getch();
start = clock();
for(pvi = vi.begin() ; pvi != vi.end() ; ++pvi)
{
if( (*pvi) == 2 )
cout << "iterator를 사용해 순회한 시간" << clock() - start << endl;
}

getch();
start = clock();
for( int i = 0 ; i<vi.size() ; ++i)
{
if ( vi[i] == 2)
cout << "사이즈를 이용해 순회한 시간" << clock() - start << endl;
}

}

결과) (도스 콘솔 복사를 어떻게 하더라-_-;)
iterator = 1016
사이즈 = 390

한없이 초보이지만 저도 궁금해서 그냥 코딩해 보았습니다.... size를 이용해서 배열처럼 순회하는 것이 더 빠르다고 나오네요. 왜인지는 묻지 마세요(...) 밑의 분 태클 받겠습니다.

배열로 하는 쪽이 훨씬 빠릅니다. stl은 소스가 공개되어 있으므로(템플릿이니까.. 당연하지!) 직접 소스를 보시면 이해가 갈겁...(틀려!!)
암튼, vector 클래스 자체가 내부적으로 배열을 동적 할당하고, 이것을 래핑하여, 멤버 함수를 통해 접근하는 방식이니.. 당연하겠죠.

일단 측정을 잘못하셨습니다. -_-
첫번째 시간 측정하실 때 for 문을
for(pvi = vi.begin() ; pvi != vi.end() ; ++pvi) 이렇게 작성하시면 매번 돌 때마다 vi.end()를 호출합니다. 여기에서 부하가 걸립니다.
두번째에도 마찬가지죠. vi.size()를 매번 부릅니다. 시간 측정이 제대로 이루어질 수 없겠죠 ?

그래서 저도 테스트를 작성해보았습니다. -_-
#include "stdafx.h"
#include <vector>
#include <algorithm>
#include <mmsystem.h>

#pragma comment( lib, "winmm.lib" )

struct Test
{
void operator() ( int & t )
{
t = 3;
}
};

#define MAX_SIZE 10000000
int _tmain(int argc, _TCHAR* argv[])
{

std::vector<int> v( MAX_SIZE );

DWORD time = 0;

time = timeGetTime();
std::for_each( v.begin(), v.end(), Test() );
std::cout<<"iteration time using for_each : "<< (timeGetTime() - time)<<std::endl;

std::vector<int>::iterator itrBegin = v.begin(), itrEnd = v.end();
time = timeGetTime();
for ( ;itrBegin != itrEnd; ++itrBegin )
(*itrBegin) = 3;
std::cout<<"iteration time using iterator : "<< (timeGetTime() - time)<<std::endl;
UINT size = v.size();

time = timeGetTime();
for ( int i = 0; i<size; i++ )
v[i] = 3;
std::cout<<"iteration time using operator [] : "<< (timeGetTime() - time)<<std::endl;

getchar();
return 0;
}

윈 콘솔용으로 짠거라 -_- vc 에서만 돌아갑니다. -_-
제가 실행한 결과는
iteration time using for_each : 2432
iteration time using iterator : 1994
iteration time using operator[] = 3834
입니다. iterator가 제일 빠르고 그 다음이 for_each 이고 []이 제일 느립니다.
iterator의 동작을 살펴보면 ++itr 과 *itr 이 있습니다.
++itr은 포인터 더하기 연산이고 * 는 dereference 입니다.

operator []를 이용한 연산은
int 더하기 한번(i++)에 v[i] 는 *( v + i ) 이므로 포인터 더하기 한번 dereference 한번이 들어가 iterator 보다 연산이 많다는 걸 알 수 있습니다. 그래서 당연히 느릴 수 밖에 없죠.

문제는 for_each 인데 -_- 내부적으로 for_each는 iterator를 이용한 코드와 동일합니다. 따라서 같은 속도가 나와야 하는데, 조금 느려진 까닭은 struct를 operator( int &t )로 변환하면서 t를 대입하는 시간이 들어가 느려진 것 같습니다.

MEC++ 을 보면 될 수 있으면 for문을 돌지 말고 stl에서 제공하는 for_each, sort 등등을 사용하라고 권합니다. 당신들이 어지간히 최적화해서 만든 것 보다는 훨씬 빠를거라고 하면서요. 괜히 한 말은 아닙니다.

앗 쪽팔려(...)

그래도 release 모드로 들어가면 -_- 결과는 며느리도 모르게 됩니다. 각종 최적화 기법들이 적용되기 때문에 operator[]이 더 빠를수도 있습니다. 저건 단지 디버그 모드에서 최적화 안했을 때 있는 그대로를 비교하면 그렇다는 얘기입니다.

저도 예전에 이게 궁금해서 릴리즈모드 oprimize : minimize size 옵션에서 돌렸을때 첨자연산보다 iterator가 더 빨랐습니다

(STLport 사용 , VC 6.0)

ㅎㅎ 저도 무안하게 돼버렸네요. ^^;

모두들 감사합니다. for-each는 모르던 방법이네요 ㅋ 한가지 더 궁금한게 있습니다.
저는 for문 조건식에서 end()함수를 매번 썻었는데 그걸 미리 구해놓고 비교하는 방법은 생각못했었네요^^;
1. 근데 이 방법은 for문 안에서 vector의 값들이 변하지 않는 전제하에 가능한거 같은데 맞나요?
2. 만약에 for 루프 안에서 삽입 또는 삭제가 이루어진다면 end()함수를 조건식에서 사용해야만 하나요?
지금 당장 생각으로는 음.. 님의 소스처럼 for문 전에 itrEnd를 구해놓고 검사하다가 벡터의 애들이 변화가 있는 경우라면 그때에 itrEnd를 갱신하는 방법을 사용하면 괜찮을듯 싶은데
이런 경우 문제가 없을까요?
3. 다음과 같은 글을 봐서 여쭤봅니다.
"만일 capacity()=reserce()이면 벡터에 새 요소를 추가할때 메모리 재할당이 일어나며 현재의 모든 반복자들이 무효화됩니다."
정확한 의미가 무엇인지 여쭤봅니다.
4. 만약에 루프 안에서 vector의 요소 개수가 변화가 될수 있는 상황이라면 세 방법중에 어느게 더 빠를까요? 랩하는 좀비님 같은 결과가 나올까요?

질문이 또 많아졌네요;;

값들이 변하면 vector 와 같은 경우에 동작을 할 수는 있겠지만, 항상 제대로 동작한다고 보장할 순 없습니다. 말씀하신 3번과 같은 경우가 있거든요. 삽입, 삭제가 발생해서 itrEnd. itrBegin의 위치가 달라질 수 있으므로 사용하면 안됩니다.

왜 그런지 제대로 이해하기 위해서는 vector의 내부 동작을 이해해야 합니다. -_-
벡터를 처음 생성할 때 개수를 지정하지 않으면 c++ 표준에서 정의하지 않은 -_- 제작사 마음대로의 개수로 할당을 받습니다. 4개면 4개, 8개면 8개 16개면 16개 할당을 받고 여기에서 하나씩 빼서 주는겁니다.
안그러면 새로 삽입할 때 마다 새로 new를 해야 되는데 이건 속도 저하가 있죠.

만약에 초기 설정이 16개 였는데, 이미 16개를 다 넣었다고 칩시다. 그러면 17개째를 넣을때 넣을 공간이 없으므로 16개의 2배 (보통은 그렇습니다. -_- ) 32개를 새로 할당 받고 기존의 16개를 왕창 복사한 다음, 17번째를 넣고, 이전의 16개를 삭제합니다.
-_- 16개니까 다행이지 256개에서 257개 째를 삽입한다고 생각해보세요. 죽습니다. 이래서 vector는 초기의 개수를 알면 reserve로 개수를 정의해 놓고 쓰면 좋은 겁니다. 다른 곳에 할당을 받았으니 itrBegin, itrEnd는 당연히 제대로 된 주소일리가 없겠죠 ? 그래서 3번에서 모든 반복자들이 무효화 된다고 하는 겁니다.

4. 모든 상황에서 operator []은 제일 느립니다. iterator로 돌리던가, 귀찮으시면 for_each 를 쓰세요.

container 내부의 모든 원소를 탐험하면서 중간의 원소를 넣고 빼고 하는 경우가 생긴다면 이건 vector 를 쓰지 말고 다른 컨테이너를 쓰라는 계시입니다. vector는 연속된 메모리를 할당 받아서 사용하는 것이기 때문에
원소 200개가 있는데 10번째에 삽입한다고 그러면 10번째부터 200번째까지를 하나씩 밀고, 10번째를 삽입합니다. 10번째를 삭제하는 경우에도 10번째를 삭제하고, 11번째 부터 200번째 까지를 하나씩 앞으로 당깁니다. 배열과 다른게 하나도 없습니다.
이런 경우가 발생한다면 다른 container를 사용하세요.

More Effective STL 책에 있는 내용입니다. 좋은 책이니 사서 보세요.

음.. // 아 좋은 내용 감사합니다^^ 말씀을 요약하자면 vector는 데이터를 순차적(무조건 마지막)으로 삽입하는 상황과, 동적으로 데이터들 중간에 데이터를 삽입하거나 삭제하는 경우가 없을시에
유용하다. 그리고 vector를 생성하고 나서 여유있게 reserve()를 통해 개수를 초기화하는 것이 좋다. 라고 생각해도 되겠는지요?

그럼 반대 상황이라면 list라는 게 적당할거 같습니다만, 맞는지요?
그리고 짧은 생각으로는 검색속도는 vector보다 list가 느릴거 같은데 어떻게 생각하시는지요.

ps. 강컴에 가니까 Effective STL 책은 있는데 more 붙은게 없네요. 동일한 책인가요?

list는 링크드리스트랑 같은 개념이에요. ...검색속도는 list가 더 느릴겝니다;. 하지만 벡터에 비해서 삽입삭제가 빠르지요. 중간에 삽입하는 속도도 장난 아니구요.
...=_= 뭐 한없이 초보인 저는 이정도만 알고 있어요. 슈팅게임에서 총알 만들 때 대부분 리스트 사용하고 FPS에서 총질할 때는 벡터가 좋다고 그러더군요. ..넵.

네 방금 음.. 님의 테스트코드에 추가해서 실험해봤습니다. vector와 list의 삽입 속도(push_back으로 했음)는 vector가 3.3배 정도 빠르군요.. 탐색속도는 iterator로 한 결과 vector가 1.3배 정도 빠르네요. 탐색속도는 얼쭈 비슷한데 삽입 속도가 장난아니네요;; 아무래도 데이터들을 연결하는 시간이 포함된거 같습니다만, 데이터가 중간에 삽입 or 삭제가 없다면 vector가 아주 우세하네요.

박현만/ 네 ㅎㅎ 말씀하신대로 생각하셔도 무방할 듯 합니다. reserve는 너무 많이 잡지는 마시고 적당히.. ㅎㅎ
그리고 Effective STL이 맞습니다. more가 붙은 애는 more effective C++ 입니다. 같은 저자라 착각했네요. 이 책도 좋은 책입니다. 보시면 후회는 안합니다. 번역도 잘 되어 있어요.
랩하는 좀비님께서 말씀해 주셨듯이 list는 말 그대로 링크드 리스트를 구현해 놓은 겁니다. 연속적인 메모리가 아닙니다. 검색속도를 생각해보면 ++itr은 itr = (*itr).next 정도로 구현되니 벡터에 비해서 느립니다. 하지만 vector와 list가 사용되어야 할 곳이 분명히
다르니 그때 그때 상황에 맞게 사용하시면 됩니다.

음.. // 넵 감사합니다. 좋은 지식 얻어갑니다^^ 질문 하나만 더 할게요^^;;; 지금 벡터 관련자료 보고 있는데 '선형소요시간'이란 말이 나오고 '상수시간 소요'라는 말이 나오는데 정확한 의미가 무엇인지 궁금합니다.

알고리즘 실행시 상수소요 시간이란 어떤 작업을 해도 동일한 시간이 걸린다는 거구요(즉 속도상 최상의 알고리즘)

선형요소시간은 데이타가 많아지면 많아질수록 그에 정비례하게 알고리즘 실행에 시간이 더 들어간다는 소립니다 ^^

왜 '선형'(linear)인지는 1차방정식의 좌표상 모습을 생각해보셔요

알고리즘 책을 좀 보면 O(1) O(n) 이런식으로 나오죠..

cretom// 아 감사합니다^^