강의 보고 공부한 것을 정리하는 목적으로 작성된 글이므로 틀린 점이 있을 수 있음에 양해 부탁드립니다. (피드백 환영입니다)
자료구조는 결국 자료를 어떤식으로 저장할 것인가?를 의미하는 것이다.
그래서 실제로 STL에서는 container라는 애들을 통해서 자료구조를 구현을 한 상태로 제공을 해준다.
container는 자료를 관리할 목적으로 만들어진 클래스이다.
container는 크게 두가지로 구분이 된다.
Sequence Containers는 vector, list 이런식으로 순차적으로 연결된 자료구조이고
연관 컨테이너는 map, hashmap, set 이런식으로 저장되는 순서가 추가하는 순서랑 다른 자료구조(특정 기준에 따라 정렬?)
Vector
저번에 Vector를 간단하게 사용을 해봤는데 그것을 복습할 겸 새로 공부할 겸 적어본다.
vector<int> v{1, 2, 3, 4, 5};이러한 벡터가 있을 때
벡터에는 이러한 것들이 있었다.
- size
- capacity(reserve)
- 삽입/삭제
- 시작 O(N)
- 중간 O(N)
- 끝 O(1)
- push_back, front, back
- 임의 접근 v[i]
- v.remove(10)
그럼 퀴즈를 내보겠다.
vector에서 size와 capacity(reserve)의 차이는 무엇이 있을까?
둘의 차이는 size는 실제 데이터 크기이고 capacity는 실제로 할당된 공간이다.
그럼 reserve를 먼저하고 작업을 왜 하는 것일까?
왜냐하면 이사비용을 아낄 수 있기 때문이다.
vector특성상 capacity를 초과하면 capacity를 늘리고 그 안에 있는 값을 다 복사해서 가져오기 때문에 처음에 reserve를 해준다면 이사비용을 아껴줄 수 있다.
push_back은 맨 뒤에 값을 넣어주는 함수로 빠르다(O(1)).
시작과 중간에 넣어주는 것은 O(N)은 값을 하나씩 밀어야 하기 때문에 느리다.
그래서 STL에서 지원을 해주지 않는다.
front와 back 첫 번째 데이터와 마지막 데이터를 가져오는 것이기 때문에 시작복잡도는 O(1)이다.
임의 접근은 당연하게도 O(1)이다.
그리고 우리가 컨테이너를 공부를 할 때는 무엇에 사용할지를 생각해보면 된다.
보통 데이터 추가, 삭제, 순회, 검색 이것들 위주로 살펴보면 된다.
개념 및 의문점 해결
벡터를 초기화 하는 방법은 다양하게 있었다.
vector<int> v(5); // 데이터 5개 세팅
vector<int> v(5, -1); // 데이터를 5개로 세팅시키고 -1로 초기화
vector<int> v{1, 2, 3, 4, 5}; // 1,2,3,4,5를 넣기만약 vector<int> v{ 1, 2, 3, 4, 5 }이러한 벡터를 만들었을 때
vector<int> v2 = v이런식으로 넣어준다면 "어? vector는 동적배열이니 힙에 저장되니까 참조가 되나?" 할 수 있다.
그럼 여기서 v2[0] = 100;을 하면 v도 바뀔까?
하지만 바뀌지 않는다. v2에다가 v를 복사한 것이기 때문에 v2의 0번만 100으로 바뀌었을 것이다.
그래서 함수든 어디든 벡터를 넘겨줄 때는 복사가 되기 때문에 주의를 해야한다.
만약 복사비용을 아끼고 싶다면 &(주소값)을 넘겨줘서 원본을 건드리면 된다.
그래서 실질적으로 벡터를 함수나 다른곳에 사용할 때는 항상 참조값을 넘겨서 사용할 때가 더 많다.
그리고 만약 vector<int> v{1, 2, 3, 4, 5};이러한 벡터가 있을 때
v.clear();를 한다면 이때 size와 capacity는 어떻게 될까?
v.clear()는 vector안에있는 데이터를 다 날려버리는 함수이다.
(ALL pop_back)
이때 size는 0이 되고 capacity는 원래 크기 그대로이다.
즉 데이터를 다지우고 싶어서 지웠는데 할당된 크기는 그대로 라는 것이다.
그럼 왜 capacity는 안 줄어들까? 애당초에 capacity가 한 번 고점을 찍어다는 것은 다시 그 고점까지갈 가능성이 있기 때문에 capacity는 줄어들지 않는다.
만약 데이터가 적어졌다고 capacity가 줄어든다면 데이터를 추가 할 때마다 이사비용이 들 수 있기 때문에 합리적이지 않아서 이런식으로 구현이 되어 있는 것 같다.
만약 진짜로 capacity를 줄이고 싶다면
빈 vector를 만들고 swap이라는 함수를 통해서 바꿔주면 된다.
하지만 실전에서는 사용하지 않는다.
왜냐하면 애당초에 한 번 늘어났으면 그것을 감안하고 가는것이고 저 정도 더 차지한다고 해서 심각한 오류는 나지 않기 때문이다.
iterator
iterator는 반복자, 포인터라고 생각하면된다.
vector<int> v{ 1, 2, 3, 4, 5 } 가 있다고 가정을 한다.
그리고 인덱스로 접근을 해줄 수도 있지만 포인터로 접근한다고 가정을 하면
int* ptr = &v[0];
int value = *ptr;
// 다음 데이터
ptr++; // 4를 더하면 안됨 데이터의 크기만큼 더해짐
// 다다음 데이터
ptr += 2;이런식으로 접근할 수 있다.
이 작업을 iterator라는 개념을 추가해 만들어보자
그 전에 위에 보다 더 좋은 예시인 순회로 만들어서 살펴보자.
vector<int> v{ 1, 2, 3, 4, 5 };
int* ptr = &v[0];
int* ptrEnd = &v[4] + 1; // 마지막 다음 데이터 가르키기
while(ptr != ptrEnd)
{
cout << *ptr << endl;
ptr++;
}이 코드를 iterator를 사용하여 만들어 볼 것이다.
iterator는 모든 자료구조들이 가지고 있는 공통적인 개념이라고 볼 수 있다.
우리는 vector를 대상으로 iterator를 실습해볼 것이다.
vector<int> v{ 1, 2, 3, 4, 5 };
vector<int>::iteraotr it = v.begin(); // 시작점을 가르킴
vector<int>::iteraotr itEnd = v.end(); // 마지막 + 1
while(it != itEnd)
{
cout << *it << endl;
it++;
}이런식으로 만들 수 있는데 위 포인터방식과 매우 유사하다는 것을 알 수 있다.
근데 "이러면 그냥 포인터 쓰면 되는거 아닌까?" 라고 생각할 수 있는데
나중에 다른 자료구조를 배우게 된다면 사용하게 될 텐데 list를 사용한다면
그냥 vector에서 list로 바꿔주기만 해도 잘 작동이 된다는 것을 볼 수 있다.
list<int> v{ 1, 2, 3, 4, 5 };
list<int>::iteraotr it = v.begin(); // 시작점을 가르킴
list<int>::iteraotr itEnd = v.end(); // 마지막 + 1
while(it != itEnd)
{
cout << *it << endl;
it++;
}즉, 어떠한 컨테이너를 이용해 어떠한 자료구조를 사용하는 것은 나중에 정할 수 있지만 인터페이스는 동일하게 만들어져있기에 동일한 코드를 유지할 수 있다는 점이 장점이다.
일단 iterator는 개념적으로 어떠한 위치를 가르키는 포인터라고 생각을 하면 된다.
물론 지금은 vector이기 때문에 포인터에서 다음다음으로 갈 수 있지만 만약 연결리스트라면 노드를 타고 다음 데이터로 넘어가야 한다.
그래서 세부적인 구현은 다르더라도 기본적인 인터페이스는 크게 다를빠가 없다.
그리고 위에 코드를 for문으로 만든다면
vector<int> v{ 1, 2, 3, 4, 5 };
for(vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
int data = *it;
cout << data << endl;
}이런식으로 만들 수 있다.
순회를 할 때 인덱스 기반으로 순회를 하여도 되지만 일단 이렇게 iterator로 하는 방법도 알고 있어야 한다.
그리고 느린건 알지만 꼭 중간에 삭제해야 할 것이 있다면
v.erase()를 사용하여서 삭제할 수 있다.
v.erase는 매개변수에 iterator를 넣어줘서 그 데이터를 삭제시킬 수 있고
매개변수를 2개 넣는다면 범위를 지정해 줄 수도 있다.
그래서 iterator가 단순히 포인터 용도 뿐만 아니라 실제로 나머지 기능들과도 연관이 되어 유용하다는 것을 알 수 있다.
여기서 많이 하는 작업중 하나가
모든 데이터를 순회하면서 특정 조건에 걸리면 제거하는 경우가 생긴다.
(몬스터가 죽으면 삭제 처럼)
여기서 사람들이 실수를 많이 한다.
vector<int> v{ 1, 2, 3, 4, 5 };
for(vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
int value = *it;
if(value & 2 == 0) // 짝수
v.erase(it);
}
for(vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
cout << *it << endl;
}전체를 순회하여 짝수를 삭제하고 전체를 출력하는 코드이다.
하지만 여기서 실행을 시킨다면 크래시가 날 것이다.
v.erase는 받은 위치를 삭제하고 그 다음 데이터가 와야하는 위치를 반환해준다.
그래서 보면 처음에 2를 삭제한 순간에 한 칸씩 앞당겨지는데
그러면 한 칸을 건너뛰기 때문에 4를 가르키게 된다.
그래서 우리는 3을 가르키기 위해서 it = v.erase(it);이런식의 코드로 바꿔줘야 한다.
이렇게 되면 2가 삭제되고 iterator가 갱신이 되면서 3이 된다.
그래서 결국 erase를 할 때는 받아주거나 erase를 하자마자 break나 return을 해줘야 한다.
이렇게 실행을 해주면 1, 3, 5가 정상적으로 출력이 되지만 여기에는 함정이 하나가 있다.
2가 삭제가 되고 3으로 갱신이 되었는데 바로 it++이 되어서 3은 확인도 하지 않고 바로 4로 넘어가버리기 때문에 로직에 문제가 있다.
그래서 순회를 할 때는 저런식으로 코드를 만들면 안되고
vector<int> v{ 1, 2, 3, 4, 5 };
for(vector<int>::iterator it = v.begin(); it != v.end();)
{
int value = *it;
if(value & 2 == 0) // 짝수
it = v.erase(it);
else
it++;
}
for(vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
cout << *it << endl;
}이런식으로 erase가 될 때와 안 될 때를 구분하여서 만들어줘야 한다.
그래서 erase를 해줄 때에는
받아주거나 break를 하거나 둘 중 하나를 해야한다.
어떤 container를 사용할 때 모든 데이터를 서치하면서 추가하거나 삭제하는 것에 대해서는 조심해야한다.
마무리
일단 여기까지가 vector와 iterator의 기본적인 내용이고 다음에는 iterator에 대해서 더 알아볼 생각이다.
