이제부터 알아볼 것은 Modern C++에서 제공되는 Container에 대하여 알아볼 것이다.
어떤 Container가 있고, 어떤 특징을 가지는가??
순서 컨테이너(Sequence Container)
- 모든 요소를 특정 위치에 저장한 순서가 있는 모음
- 위치는 삽입한 시점과 위치에 따라 달라지며, 요소의 값과는 독립적 관계를 가짐.
- 대체로 배열 또는 연결 리스트로 구현.
> 종류 : array, vector, deque, list
연관 컨테이너(Associate Container)
- 요소의 위치가 자신의 값과 특정 정렬 기준에 따라 정해지는 정렬 모음.
- 삽입한 순서는 중요하지 않음. 오로지 요소의 값에 의해 순서가 결정.
- 대체로 이진트리로 구현.
> 종류 : set, multi_set, map, multi_map
비정렬 연관 컨테이너(Unordered Associate Container)
- 요소의 위치가 중요하지 않은 비정렬 모음.
- 오로지 특정한 요소가 이 모음 안에 있기만 하면 됨.
- 삽입의 순서, 요소의 값은 요소의 위치에 영향을 주지 않으며, 컨테이너가 존재하는 동안 그 위치가 변할 수도 있음.
- 대체로 해시 테이블로 구현.
> 종류 : unordered_set, unordered_multiset, unordered_map, unordered_multimap
이 중 오늘은 array와 vector에 대하여 알아보도록 하자.
array란?
우리는 이미 배열이라는 자료구조를 알고 있다.
배열은 무엇인가?
뭐 이런식으로 선언하면 메모리는 다음과 같이 할당된다.
메모리에 5개의 공간을 잡은 뒤, 1,2,3,4,5 값을 대입해준다.
배열의 특징은 메모리를 연속적인 위치에 할당한다는 것이다.
즉, 배열의 맨처음 주소에 해당 배열의 자료형만큼 바이트를 더해주면 그 다음 배열의 요소에 접근할 수 있다는 것이다.
00FBFD28 -> 00FBFD2C
int의 경우 4Byte이다. 그러므로, 28+04 = 2C(16진수) 이런식으로 메모리가 잡히게 되는 것이다.
정말 간단하다. 그럼 stl의 Array컨테이너는 그냥 단순히 얘랑 똑같을까?
같다. 어떻게 쓰든 크게 상관은 없다. 하지만, array라는 container를 사용했을 때의 이점은 다양한 내장 함수를 사용할 수 있다. 또한, 함수로 전달 시에 포인터로 형 변환되지 않는다. 또한 반복자(Iterator)를 사용할 수 있다. 그러므로, 배열을 사용할 때는 왠만하면 array<>를 사용하는 것이 좋다.
sort함수를 사용할 경우 원소를 정렬시킬 수 있다. 하지만, 이 함수를 사용하기 위해서는 반복자를 사용하여야만 한다. Iterator의 경우 나중에 다시 살펴볼 예정이며, 지금은 그냥 그렇다고 알아두면 될 것같다. begin의 경우 배열의 시작, end는 배열의 끝을 의미한다.
여기까지 array에 대해 살펴봤는데, array의 경우 정적 배열이므로, 프로그램 도중에 size를 바꿀 수 없다는 단점이 존재한다. 이를 해결하기 위해 존재하는 자료구조는 vector와 list라는 자료구조이다. 하지만, list의 경우 array와는 꽤나 많이 다르기 때문에, 우리는 이번시간에 vector에 대해 먼저 살펴보도록 할 것이다.
vector란?
array와 달리 동적으로 요소의 수를 바꿀 수 있는 배열이다.
우리는 c++을 배우기 이전에 c언어에서 malloc을 사용하여 동적으로 배열의 갯수를 늘려주거나 줄여줄 수 있었고, modern C++을 배우기 이전에는 c++에서 new를 사용하여 동적으로 배열의 갯수를 늘려주거나 줄여줄 수 있었다. 하지만, 이제부터 우리가 알아볼 vector를 사용하면, new또는 malloc을 이용하지 않고 배열의 갯수를 동적으로 바꿀 수 있다.
앞서 살펴본 array와 달리 vector에서 우리는 배열의 크기를 따로 정의하지 않았다. 단지 요소를 추가할 때 push_back이라는 함수를 이용하여 동적 배열에 자료를 추가하는 모습이다. 실행결과 주소를 보면, 배열과 마찬가지로 연속적인 메모리 할당이라는 특징을 볼 수 있다. 이는 동적 '배열'이기 때문이다.
이런식으로 우리가 push_back할 때마다 vector의 요소갯수가 1씩 증가하는 것을 확인할 수 있다.
그렇다면, vector의 실제크기는 어떨까?
capacity함수를 사용하면, 현재 실제로 할당되어 있는 벡터의 메모리가 얼마나 되는지 알 수 있다.
<어떤 원리인가?>
사실, vector는 현재 벡터에 있는 요소의 갯수보다 더 많은 공간을 할당하고 있다. 즉, 만약 내가 push_back을 하여 3개의 원소를 넣었다면, 현재 벡터에는 5개 정도가 들어있는 공간을 할당하고 있다. 만약 이 5개의 공간마저 다 차게된다면, 벡터는 데이터를 더 집어넣을 수 없다. 그러므로, 현재 메모리를 파괴시킨 후에 10개의 공간으로 재할당을 시도한다. 코드를 사용하여 표현해보도록 하자.
위에 있는 코드와 비슷하게 나오도록 vector를 구현해 보았다. 그럼 어떻게 구현했는지 확인해보자.
우선 템플릿으로 구현된 Vector클래스를 위해 template으로 data를 저장하도록 하였다. 그리고, 전에 공부했던 unique_ptr을 사용하였다. vecIdx의 경우 현재 벡터가 추가될 위치를 나타내는 인덱스이고, vecsize는 현재 vector의 실제 size를 나타낸다.
unique_ptr을 공부할 당시 우리는 더 이상 new와 delete를 사용하여 생성과 소멸을 할 필요가 없다는 것을 알았다. 따라서 소멸자의 구현부에는 아무 것도 없는 것을 확인할 수 있다. 생성자에서는 vector의 크기를 5로 할당하는 것을 확인할 수 있다.
vector는 동적배열이다. 따라서 데이터가 꽉차면 동적으로 배열의 크기를 늘려줘야 한다. 현재 코드를 보면, 배열의 크기만큼은 정상적으로 초기화 시키지만, 우리가 처음에 초기화 했던 크기인 5를 넘어가게 되면 전에 있던 데이터를 임시변수인 temp에 옮겨놓고 data를 배열의 크기 * 2로 재할당 해주는 것을 확인할 수 있다. 이후 전에 있던 데이터를 싹 옮겨준다. 이렇게 하면 아까 말한 것처럼 배열의 크기를 늘릴 수 있다. 이게 바로 vector의 원리이다. 나는 x2로 했지만, 실제로는 약간 차이가 있긴하다. 그런거는 중요하지 않은 것 같으니 패스.
At은 주어진 인덱스에 접근하여 데이터를 넘겨주는 함수이다. Size는 현재 인덱스의 값을 넘겨주는 함수이고 Capacity는 벡터의 실제 크기이다.
요약하자면, 벡터의 경우 추가/제거보다는 탐색에 최적화 되어있고, 배열과 비슷하지만, 동적으로 크기를 바꿔준다는 점에서 배열에 비해 큰 이점을 가지는 container라고 할 수 있다.
21.09.08 추가
vector의 2차원 배열을 접근/사용 하는 방법
-- 코딩 테스트할 때 잘 나오는 거라 외워야 함.
ex) vector<vector<int>> v1;
v1에는 [[1,3], [2,5], [2,6]] 이런식으로 데이터가 들어있다.
반복문을 돌린다고 가정했을 때, 두가지 방법이 있다.
int k = 0;
1. size()를 이용한 방법
for(int i = 0; i < v1.size(); i++)
{
for(int j = 0; j<v1[0].size(); j++) // v1[0]은 벡터 안에 있는 데이터의 첫 포인터,
{
k = v1[i][j];
cout<< k ;
}
}
이렇게 하면 2차원 배열을 순차적으로 접근할 수 있다.
2. iterator를 이용한 방법
int k = 0;
for(auto p : v1)
{
for(auto x : p)
{
k = x;
cout << k;
}
}
이렇게 해도 접근을 할 수는 있다. 하지만, 인덱스를 사용할 수는 없다.
내 생각엔 1번 방법이 코테볼때는 좀 더 유리할 것 같다. (인덱스 쓰는 것 때문에)
21.11.15 추가
vector와 list 둘 중에서 어떤 것이 탐색에서 효율적이고, 이유가 뭔가? 라는 의문이 생겨서 찾아봤다.
정답은 vector이다.
이유
vector는 선형적 자료구조이다. (즉, 0 1 2 3 ... 데이터 할당이 나란하게 되어있다.) 반면, List는 비선형적 자료구조이다. 그런데, 선형적 자료구조와 비선형적 자료구조인게 뭐 어떤 차이가 있길래 vector가 더 탐색이 빠르다는 것인가?
->이는 컴퓨터 구조 시간에 배웠던 어떤 데이터가 참조 되었을 때 참조된 지역 및 시간 근처에서 또 다시 참조될 가능성이 높다는 원칙 즉, 참조 지역성의 원칙 때문이다. 이런 원칙 때문에, 선형적 자료구조인 vector에서 탐색 속도가 더 빠르다.
이는 Cash의 Hit / Miss과 관련이 있다.
CPU <--> 캐쉬메모리 <--> 주메모리 <--> 보조메모리
Cash의 Hit이란, 프로세스가 요구하는 데이터가 메모리의 상위 계층(캐시메모리)에 있을 경우, 적중했다(Hit) 라고 하며 반대로, 프로세스가 요구하는 데이터가 메모리의 하위 계층(보조메모리)에 있을 경우, 적중 실패(Miss) 라고 한다.
이걸 비유해보자면, 나는 현재 천안에 있고, 친구를 만나기로 약속했다. 친구가 천안에 있을 경우 Hit, 천안이 아닌 서울에 있다면 Miss 라고 할 수 있을 것 같다. 그럼 결국 Hit인 경우 나는 천안에서 친구를 빠르게 만날 수 있으니 좋고, 반대로 서울에 친구가 있다면 친구가 서울에서 천안으로 와야 하니, 시간이 오래걸리기 때문에 빨리 만날 수 없어서 Miss라고 할 수 있을 것 같다.
-- 틀린 부분이 있으면 말씀해주세요 감사히 피드백 받겠습니다.
'Modern C++' 카테고리의 다른 글
| [C++] Container - Map (0) | 2021.07.20 |
|---|---|
| [C++] Container - List (0) | 2021.07.19 |
| [C++] SmartPointer - weak_ptr (0) | 2021.07.16 |
| [C++] SmartPointer - shared_ptr (0) | 2021.07.11 |
| [C++] SmartPointer - unique_ptr (0) | 2021.07.10 |