[ C++ ] 배열과 vector

배열

배열이란 index와 그에 대응되는 데이터들로 이루어진 자료구조이며, 일반적으로 같은 타입의 데이터들이 순차적으로 메모리에 저장된다. 

배열의 성질

1. O(1)에 k번째 원소를 확인/ 변경 가능
2. 추가적으로 소모되는 메모리의 양, 즉 overhead가 거의 없음
3. Cache hit rate가 높음
4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림
5. 배열의 선언 당시 지정된 크기로 고정됨.
   => 사이즈를 벗어난 인덱스에 접근 시, 런타임 에러 발생

int arr1[5]={1,2,3}	// 1,2,3,0,0
int arr2[]={1,2,3,4,5} 	//크기 5로 고정됨
int arr3[5]={0};	// 원소가 모두 0으로 초기화 됨
int arr4[5];	//원소가 모두 쓰레기값으로 초기화 됨

이때 배열의 크기는 상수로만 정의를 해야함을 잊지말자

배열의 기능에 따른 시간 복잡도

1. 임의의 위치에 있는 원소를 확인/변경 = O(1)
2. 원소를 끝에 추가 = O(1)
3. 마지막 원소를 제거 = O(1)
4. 임의의 위치에 원소를 추가/제거 = O(N)
   => 임의의 위치에 추가/제거 될 경우 뒤의 값들을 한칸씩 이동시켜야 하기 때문

배열 값 입력

int a[10];
int b[10][10];

//1.memset
memset(a,0,sizeof a);
memset(b,0,sizeof b);

//2.for
for(int i=0 ; i<10 ; i++)
	a[i]=0;
for(int i=0 ; i<10 ; i++)
	for(int i=0 ; i<10 ; i++)
    	b[i][j]=0;

//3.fill
fill(a,a+10,0);
for(int i=0 ; i<10 ; i++)
	fill(b[i],b[i]+10,0);

memset을 사용할 경우 의도치않은 문제들이 발생할 수 있다. 그에 반해 for문과 fill은 안정적으로 사용이 가능하다.
코드도 짧고 실수할 여지도 적은 fill을 가장 추천!\

---

정적인 크기의 자료구조인 배열을 쓰다보면 가끔 어려움이 발생할 때가 있다. 이때 사용하면 좋은것이 바로 C++에서 제공하는 STL중 하나인 벡터 클래스이다. 

STL vector

vector는 #inlcude <vector>헤더파일을 통해 사용할 수 있다.

벡터의 선언

vector<int> v1; 	//크기 미지정 1차원 벡터 생성
vector<int> v2(10); 	//크기가 10, 원소는 0으로 자동 초기화
vector<int> v3(10,5); 	//크기가 10, 원소는 5로 초기화
vector<vector<int>> v4; //크기 미지정 2차원 벡터 생성

벡터의 원소 접근

v[idx]; 		//idx번째의 원소를 참조
v.at(idx); 		//idx번째의 원소를 참조
v.front(); 		//벡터의 첫번째 원소를 참조
v.back(); 		//벡터의 마지막 원소를 참조
v.begin(); 		//벡터의 첫번째 원소의 위치를 참조
v.end(); 		//벡터의 마지막 원소의 위치를 참조

벡터의 원소 삽입/삭제

v.push_back(10); 	//벡터의 맨 끝에 데이터10을 삽입
v.pop_back(); 		//벡터의 맨 끝 데이터를 삭제
v.insert(v.begin()+1, 10); 	//원하는 위치에 데이터 10을 삽입
v.insert(3,5);
v.erase(4); 		//원하는 위치의 원소를 삭제

벡터의  크기 확인

v.size(); 		//벡터의 크기 반환
v.capacity(); 		//heap에 할당된 벡터의 실제크기(최대크기) 반환
v.empty(); 		//벡터가 빈공간이면 true, 값이 있다면 false
v.max_size(); 		//벡터가 시스템에서 만들어질 수 있는 최대 크기 반혼
v.reserve(50); 		//벡터의 크기를 50으로 설정
v.shrink_to_fit(); 	//capacity의 크기를 벡터의 실제 크기에 맞춤