STL :: 컨테이너(vector)
2011. 1. 8. 22:11출처 : http://blog.daum.net/coolprogramming/77
vector는 STL 컨테이너에서 가장 많이 사용하는 컨테이너 중 하나입니다.
STL 컨테이너는 각각 자신만의 특징을 가지고 있습니다. 각 컨테이너의 특징은 성능('시간 복잡도'나 '공간 복잡도')과 STL 여러 요소에 영향을 주기 때문에 각 컨테이너의 특징을 이해하는 것은 상당히 중요합니다. 그래야 자신의 프로그램에 맞는 적절한 컨테이너를 선택하여 사용할 수 있습니다.
vector의 주요 특징은 앞장에서 배운 것처럼 '시퀀스 컨테이너'이면서 '연속 메모리 기반 컨테이너'입니다. 또 컨테이너에 데이터가 삽입될수록 메모리가 자라나게 됩니다. 연속 메모리 기반이므로 메모리가 자라나면 기존 메모리를 삭제하고 새로운 메모리를 재할당하여 사용합니다.
vector의 주요 개념을 그림으로 표현하면
컨테이너에 앞서 계산 성능을 평가하는 '계산 시간 복잡도'를 간단히 정리하고 가겠습니다.
시간 복잡도는 "어떤 일을 얼마나 오랜 시간 동안 수행해야 하는가?"에 대한 함수로 나타내는 것을 의미합니다.
'시간 복잡도'는 크게 네 가지로 볼 수 있습니다.
- 상수 시간 복잡도(constant time complexity) : 작업양이 증가할 때 변하지 않는 일정한 수행 성능을 보인다는 것.
- 로그 시간 복잡도(logarithmic time complexity) : 작업양이 증가할 때 수행 시간도 일정하게 늘어나지만, 로그 함수의 비율로 늘어나는 것.
- 선형 시간 복잡도(linear time complexity) : 작업양이 증가할 때 수행 시간도 비례해서 늘어나는 것.
- 지수 시간 복잡도(exponential time complexity) : 작업양이 증가할 때 수행 시간도 지수함수의 비율로 늘어나는 것.
그림으로 보면
1, vector의 특징과 주요 함수
예제로 vector의 함수들을 공부합니다.
가장 간단한 예제(정수 추가 후 출력)
#include<vector>
using namespace std;
voidmain ( )
{
vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);
v.push_back(50);
for( int i = 0 ; i < v.size() ; i++)
cout << v[i] << ' ';
cout << endl;
}
- 10 20 30 40 50
- push_back()컨테이너 v에 요소를 추가하는 함수입니다. (모든 시퀀스 컨테이너는 요소를 끝에 추가할 수 있고 push_back()함수를 가지고 있습니다.)
- size()는 v 요소의 개수를 반환합니다. ( 모든 컨테이너는 컨테이너의 요소 개수를 반환하는 size()함수를 가지고 있습니다.)
- operator[]() 함수는 i 번째 인덱스의 요소를 반환합니다.( 모든 연속 메모리 기반의 컨테이너와 map은 operator[]()함수를 가지고 있습니다.)
vector의 중요한 특징 중 하나가 연속 메모리 기반 컨테이너이므로 요소가 추가될 때 메모리가 자라난다는 것입니다. 추가될 때마다 메모리가 자라난다는 것은 메모리를 재할당해야(메모리의 크기를 늘려야 하므로) 한다는 것을 말합니다. 그래서 너무 비효율적으로 메모리 재할당되는 것을 막기 위해 요소가 추가될 때마다 메모리를 늘리지 않고 미리 여유 메모리 공간을 확보합니다.(여유 메모리의 크기를 늘리는 정책은 컴파일러마다 조금씩 다릅니다. 우리는 VS2008을 사용합니다.)
중요 특징 - capacity(할당된 메모리 공간의 크기)와 size(저장된 데이터 요소의 개수)
#include<iostream>#include<vector>using namespace std;voidmain ( ){ vector<int> v;
cout << "size"<< ":" << "capacity " << endl; v.push_back(10); cout << v.size() << " : " << v.capacity() << endl; v.push_back(20); cout << v.size() << " : " << v.capacity() << endl; v.push_back(30); cout << v.size() << " : " << v.capacity() << endl; v.push_back(40); cout << v.size() << " : " << v.capacity() << endl; v.push_back(50); cout << v.size() << " : " << v.capacity() << endl; v.push_back(60); cout << v.size() << " : " << v.capacity() << endl; v.push_back(70); cout << v.size() << " : " << v.capacity() << endl; v.push_back(80); cout << v.size() << " : " << v.capacity() << endl; v.push_back(90); cout << v.size() << " : " << v.capacity() << endl; v.push_back(100); cout << v.size() << " : " << v.capacity() << endl; for( int i = 0 ; i < v.size() ; i++) cout << v[i] << ' '; cout << endl;}
- size:capacity
1 : 1
2 : 2
3 : 3
4 : 4
5 : 6
6 : 6
7 : 9
8 : 9
9 : 9
10 : 13
10 20 30 40 50 60 70 80 90 100
10개의 정수를 push_back()하고 있습니다. size는 v에 저장된 요소의 개수이며 capacity는 할당된 메모리 공간의 크기입니다. VS2008 컴파일러는 기존 메모리의 반만큼의 메모리를 더 늘려서 메모리를 할당합니다. 또 기존 메모리의 모든 컨테이너 요소를 재할당된 메모리로 복사합니다.
위 예제를 그림으로 보면
그래서 컨테이너 요소의 개수가 유동적인 곳에는 vector가 비효율적입니다.
위 내용을 해결하는 방법은 두 가지 정도가 있습니다.
첫째는 생성자를 이용하여 메모리 공간(capacity)과 크기(size)을 미리 확보하고 초기화하는 것입니다.
#include<vector>
using namespace std;
voidmain( )
{
vector<int> v(10);
cout << v.size() << " : " << v.capacity() << endl;
for(int i = 0 ; i < v.size() ; i++)
cout << v[i] << ' ';
cout << endl;
for(int i = 0 ; i < v.size() ; i++)
v[i] = (i+1)*10;
for(int i = 0 ; i < v.size() ; i++)
cout << v[i] << ' ';
cout << endl;
}
- 10 : 10
0 0 0 0 0 0 0 0 0 0
10 20 30 40 50 60 70 80 90 100
v(10) 처럼 size를 10으로 설정하면 0으로 초기화된 size 10개와 메모리 공간이 확보됩니다. 값을 변경할 때 operator[]()함수를 사용했습니다.
아래는 위 예제의 그림입니다.( vector<int> v(10); )
둘째는 reserve()함수를 이용하여 메모리 공간(capacity)만 미리 확보하는 것입니다.
#include<vector>
using namespace std;
voidmain( )
{
vector<int> v;
v.reserve(10);
cout << "size"<< ":" << "capacity " << endl;
cout << v.size() << " : " << v.capacity() << endl;
for(int i = 0 ; i < 10 ; i++)
{
v.push_back((i+1)*10);
cout << v.size() << " : " << v.capacity() << endl;
}
for(int i = 0 ; i < v.size() ; i++)
cout << v[i] << ' ';
cout << endl;
}
- size:capacity
0 : 10
1 : 10
2 : 10
3 : 10
4 : 10
5 : 10
6 : 10
7 : 10
8 : 10
9 : 10
10 : 10
10 20 30 40 50 60 70 80 90 100
메모리 공간(capacity)은 미리 확보했으므로 push_back()함수를 호출해도 메모리 재할당이 발생하지 않습니다.
아래는 위 예제의 그림입니다. ( v.reserve( 10 ); )
2, vector의 반복자
모든 컨테이너는 자신만의 반복자를 갖습니다.
반복자를 사용하는 간단한 예제
#include<vector>
using namespace std;
voidmain( )
{
vector<int> v;
for(int i = 0 ; i < 10 ; i++)
v.push_back(i+1);
vector<int>::iterator iter;
for( iter = v.begin() ; iter != v.end() ; iter++)
cout << *iter << endl;
}
- 1
2
3
4
5
6
7
8
9
10
모든 컨테이너의 반복자는 각 컨테이너 클래스의 내포 클래스(vector<int>::iterator)로 정의되어 있습니다. 또 반복자는 반복자끼리 비교할 수 있는 ==과 != 가 연산자 중복되어 있으며 다음 요소로 이동하도록 ++연산자와 반복자가 가리키는 컨테이너 요소에 접근하도록 *연산자와 ->연산자가 중복되어 있습니다.
위 예제를 그림으로 보이면
vector의 반복자는 임의 접근 반복자로 반복자에 산술 연산이 가능합니다.
#include<vector>
using namespace std;
voidmain( )
{
vector<int> v;
for(int i = 0 ; i < 10 ; i++)
v.push_back(i+1);
vector<int>::iterator iter;
for( iter = v.begin() ; iter != v.end() ; iter++)
cout << *iter << endl;
iter = v.begin();
iter += 3;
cout <<"[3] : " << *iter << endl;
*iter = 0;
cout <<"[3] : " << *iter << endl;
}
- 1
2
3
4
5
6
7
8
9
10
[3] : 4
[3] : 0
vector의 반복자는 iter에 산술연산이 가능합니다. (모든 연속메모리 기반 컨테이너는 임의 접근 반복자를 제공합니다.)
또 *연산자를 사용하여 반복자가 가리키는 메모리에 접근하고 변경할 수 있습니다.
그림으로 보면
만약 읽기만 가능한 반복자를 사용해야 한다면 const_iterator를 사용해야합니다.
#include<vector>
using namespace std;
voidmain( )
{
vector<int> v;
for(int i = 0 ; i < 10 ; i++)
v.push_back(i+1);
vector<int>::const_iterator iter;
for( iter = v.begin() ; iter != v.end() ; iter++)
cout << *iter << endl;
iter = v.begin();
iter += 3;
cout <<"[3] : " << *iter << endl;
//*iter = 0; 에러! const_iterator는 가리키는 요소를 변경할 수 없습니다.
cout <<"[3] : " << *iter << endl;
}
- 1
2
3
4
5
6
7
8
9
10
[3] : 4
[3] : 4
iter는 상수 반복자(const iterator)로 가리키는 요소의 변경이 불가능합니다. 반복자는 STL의 마지막 부분에서 자세히 공부합니다.
'프로그래밍 > STL' 카테고리의 다른 글
| STL :: 컨테이너(string) (0) | 2011.01.08 |
|---|---|
| STL :: 컨테이너(list) (0) | 2011.01.08 |
| STL :: 표준 C++ 라이브러리 (0) | 2011.01.04 |
| C++,STL :: vector 사용하기 (0) | 2010.10.26 |
| C++,STL :: list 사용하기 (0) | 2010.10.17 |
