[UNSEEN 테스트 대비] Map, Unordered_map, list, vector, array 동작원리

벡터(Vector)

 

• 동적 배열 구조(런타임에 임의로 크기 조절 가능), 배열과 같이 연속된 자료구조이므로 캐시 친화적이다.
• 메모리에 데이터가 연속적으로 위치한다.
• 벡터의 메모리 할당 방식은 size(실제 사용 메모리 크기) 와 capacity(여유분 포함 메모리 크기) 로 이루어진다. (항상 size <= capacity)
• 임의접근반복자(random access iterator)를 사용하므로 배열의 원소에 즉시 접근 가능하다. (반복자를 5가지를 알아두면 도움이 된다)
• emplace를 하면 복제 과정 없이 바로 원소를 삽입할 수 있어서 push_back보다 비용이 절감된다.
• 벡터에 데이터를 삽입할 때, 할당된 공간이 전부 차면 배열을 통째로 복사해 새로운 벡터에 할당하는 방식으로 메모리 크기를 늘린다. 때문에 벡터의 메모리를 적게 할당하고 계속 데이터를 늘릴 경우 복사 비용이 지속적으로 들어 비효율적이게 된다. 따라서 가급적 벡터의 size를 충분히 확보한 상태에서 사용하는 것이 좋다.
• 반복자 무효화가 발생할 수 있다. (참조가 유효하지 않게 되는 현상)

 

push_back() VS emplace_back()

push 방식은 임시객체를 만들어서 벡터에 삽입하는 방식인데 반해 emplace 는 객체를 만들기 위한 매개변수를 넘겨 함수내부에서 객체를 만들어 삽입하는 방식이므로

결론적으로는 불필요한 객체 생성을 하나 줄일 수 있다. 일반적인 경우에서는 emplace 가 더 빠르지만 무조건 좋다 라고는 할 수 없다.

 

 

반복자 무효화
- 컨테이너의 메모리가 재할당 될 때(vector resize, push_back 등)나 요소 삭제를 하는 등의 동작에서 발생할 수 있습니다.
만약 STL의 erase를 사용한다면 erase한 원소 포함해서 뒤의 원소를 가리키는 모든 반복자가 무효화됩니다. 이는 삭제 후 뒤에 있는 요소를 모두 땡겨줘야 하기 때문입니다.
단, erase 함수는 다음주소를 가리키는 iterator를 리턴해주기 때문에, 이것을 사용하여 순회를 계속 할 수 있습니다. 그러므로, for문과 같이 iter를 계속해서 ++해주는 코드를 사용할 때 주의해야 합니다.

벡터 요소의 삽입
- 삽입한 위치 뒤를 가리키는 반복자들은 무효화된다(나머지 원소를 전부 밀어줘야하기때문에), 삽입 앞은 재할당에 따라 무효화일수도있고 아닐수도있으나 안전한 프로그래밍을 위해선 무효화라고 보는게 맞다(삽입 앞은 원소의 위치 변동이 없으나, 메모리 재할당(크기 초과로 인한 재할당 등))이 일어날 수 있기 때문이다.

벡터 요소의 삭제
- 삭제 뒤는 무효화(뒤에 있는 원소들을 땡겨줘야하니까), 삭제 앞은 무효화되지 않음
(재할당이 일어날 일이 없다)

 

배열(Array)

• 벡터와 마찬가지로 메모리에 데이터가 연속적으로 위치한다.
• C 스타일 배열과 다르게 메모리를 자동으로 할당한 후 해제한다.
• 배열은 연속된 메모리들의 첫 주소를 담는 포인터이다.
• 크기가 고정이기 때문에 처음 설정한 데이터의 크기를 넘어서 데이터를 저장할 수 없으므로 원소의 추가나 삭제가 불가능하다.
• 특정 원소를 인덱스로 임의 접근(Random Access) 이 가능.

 

리스트(List)

• 노드 기반 컨테이너이다.
• 이중 연결 리스트와 같은 형식으로 구현되어 있다.
• 데이터가 메모리 상에 비연속적으로 저장된다.
• 단/양방향 반복자를 사용한다. 이로 인해 임의 접근이 불가능하므로, 어떤 원소에 접근하기 위해선 해당 위치까지 순회해야 한다.(list의 advance 함수는 임의 접근처럼 보이지만 실 구현은 순회로 구현되어 있다) 삽입과 삭제가 상수 시간을 가진다.  포인터를 사용하여 서로를 연결. 삽입과 삭제가 빈번한 구조에 사용하기 좋다.
• 중간 부분에서의 데이터 삭제가 벡터보다 효율적이다. (데이터를 하나씩 밀거나 당길 필요 없이 링크 필드만 변경해주면 되기 때문)

 

연관 컨테이너

 

- Key - Value 구조를 가지는 컨테이너, 특정 기준에 따라 원소를 자동 정렬하는 컨테이너

맵(Map)

• 각 노드가 Key와 Value 의 쌍으로 이루어진 트리
• 중복을 허용하지 않는다.
• map 의 각 원소들은 pair 객체로 저장되는데, first 가 key, second 가 value 로 저장된다.
• Red-Black Tree(자가 균형 이진 탐색 트리) 로 구성되어 있다.
• 자료를 저장할 때 자동으로 Key 값을 기준으로 오름차순 정렬한다. (내림차순 정렬 시에 map<type1, type2, greater<type1>> 과 같이 선언)
• 자동 정렬하기 때문에 원소의 삽입이나 삭제가 빈번할 경우 성능 저하(오버헤드가 생긴다.)
• Key 를 통해 value에 접근한다.

 

map<int, string> m;

m[1] = "ABC";
cout << m[1];

실행 결과 : ABC

 

- 균형이진트리의 일종인 레드-블랙 트리로 구현되어 있다. 이진 탐색을 사용하므로 검색이 빠른 편이다. 삽입, 삭제 시 균형트리이기 때문에 균형을 유지하는데에 오버헤드가 생긴다.
맵에 삽입하는 경우 이미 있는 key라면 값을 삽입하지 않고 이미 키가 있는 해당 노드의 키/값을 리턴한다.
정확히는 map은 insert를 할 경우 무조건 pair를 리턴하는데
pair<  std::pair(key,value) ,   bool >  을 리턴한다. bool은 해당 key가 이미 맵에 있느냐, 없느냐를 의미한다. 해당 키가 있으면 false, 없으면 true리턴.  앞의 pair는 키,값이다.

 

Unordered_map

• 정렬되지 않고 랜덤하게 저장되는 map
• map과 다르게 Hash Table로 구현되어 있다. (상수 시간 탐색 가능)
• 여유 공간이 실제 공간보다 많이 필요하다. 공간을 적게 잡으면 충돌이 자주 일어난다.
• 많은 자료를 저장하고, 검색 속도가 빨라야 하는 경우에 사용하면 좋다.(자료 양이 적을 떄는 메모리 낭비 발생)
• 나머지는 map 과 동일

 

해시맵을 구현하는 방법으로는 개방 주소법, 체이닝이 있다.

 

 

 

 

----- 읽어볼거리 -----

 

 

해시맵의 구현법 별 장점

 

체이닝(Chaining) 의 장점

• 연결 리스트만 사용하면 된다. 즉, 복잡한 계산논리를 사용할 필요가 개방주소법에 비해 적다.
• 해시테이블이 채워질수록, Lookup 성능저하가 선형적으로 발생한다. (그림 참조)

 

 

개방 주소법(Open Addressing)의 장점
◎ 개방주소법(Open Addressing)의 장점
→ 체이닝처럼 포인터가 필요없고, 지정한 메모리 외 추가적인 저장공간도 필요없다.
→ 삽입, 삭제시 오버헤드가 적다.
→ 저장할 데이터가 적을 때 더 유리하다.
개방 주소법의 탐색 종류
선형 탐색(선형 조사)(Linear Probing): 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.
제곱 탐색(Quadratic Probing): 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..)
이중 해시(Double Hashing): 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함

언오더드 맵(unordered map)
C++ 11 이전엔 정렬이 필요하지 않은 경우에도 std::map을 사용하여 불필요한 오버헤드를 감수해야 했다. 또는 비표준 라이브러리의 hash_map 컨테이너를 사용해야 했다. 그러다 표준에도 해시맵이 필요하다는 말이 많아졌는지 C++ 11에서 std::unordered_map이라는 컨테이너가 등장했고, 기존의 std::map과 달리 이진 탐색트리가 아닌 해시 테이블로 구현되어 있다. 때문에 요소를 자동으로 정렬하지 않으며 요소의 검색, 삽입, 삭제 연산이 평균적으로 상수 시간에 가능하다. (std::set, std::unordered_set 도 동일한 관계)  [unordered_map의 내부 동작]기본적으로 해시맵과 동일하므로 해시맵의 동작 방식을 살펴보자. 앞으로 해시맵 또는 그냥 맵(map)이라고 부르자. 일단 map이라는 것은 key에 value를 매칭시켜 pair(쌍) 형태로 데이터를 저장하는 연관 컨테이너이다.  따라서 각 요소는 pair<key, value> 형태로 저장되며 우리는 key를 통해 value에 접근할 수 있다.

 

여기까진 맵의 기본적인 특징이고, 해시맵의 특징은 바로 key를 통한 value로의 접근이 빠르다는 것이다. 그 이유가 바로 hash 때문이다. hash는 다음과 같이 어떤 데이터를 특정 연산을 통해 특별한 값(보통 integer)으로 변환시켜주는 개념이다.

 

hash 연산을 하는 함수를 해시 함수라 하며 해시 알고리듬은 MD5, SHA 같의 여러 종류의 알고리듬이 존재한다. 해시맵은 해시 함수를 통해 key를 특정 값으로 변환시키고 이 값을 value를 저장할 공간의 인덱스로 사용한다. 저장되는 공간은 보통 bucket 또는 slot이라고 부르며 다음 그림과 같이 저장된다.

 

"Hi" 라는 데이터를 동일한 해시 함수에 넣으면 항상 23이라는 데이터를 반환한다. 사실 함수마다 다르지만 원래는 해시 함수의 반환값을 bucket size로 나눈 나머지(mod) 값을 인덱스로 사용하는 방법도 있다. 그러면 무조건 [0, bucket size) 범위의 인덱스가 나오니까. 어쨌든 이는 key를 통해 value가 저장된 인덱스에 상수 시간에 접근할 수 있다는 걸 뜻한다. 즉 O(1)의 시간복잡도를 가진다는 말이다. key-value 쌍이 10개든 100개든 1000개든 해시 함수 한번에 value의 index를 얻을 수 있기 때문이다. 물론 사용하는 해시 함수의 시간 복잡도가 key-value 쌍의 개수에 영향을 받아선 안될 것이다.(그럴 일이 있나 싶겠지만) 해시 함수가 아닌 key를 직접 비교해가며 value를 찾는다면 위 그림에선 24번 비교해야 23번 인덱스의 값에 접근할 수 있을 것이다.
정리해보면 만약 "Apple" - "Samsung"을 쌍으로 저장하고 싶다면 "Apple"을 해시 함수에 넣어 인덱스를 얻고 그 인덱스에 "Samsung"이라는 value를 저장한다. 만약 "Apple"의 value를 읽어오고 싶다면 똑같이 "Apple"을 해시 함수에 넣어 인덱스를 얻은 뒤 bucket에서 읽어오면 된다. 참고로 역은 성립하지 않아서 해시값을 통해 역으로 "Hi"라는 데이터에 접근할 순 없다.

 

 

 

출처

 

https://velog.io/@doorbals_512/UNSEEN-%ED%85%8C%EC%8A%A4%ED%8A%B8-%EB%8C%80%EB%B9%84-C-%EC%BB%A8%ED%85%8C%EC%9D%B4%EB%84%88%EB%93%A4%EC%9D%98-%EB%8F%99%EC%9E%91-%EC%9B%90%EB%A6%AC

[UNSEEN] 테스트 대비 4. C++ 컨테이너들의 동작 원리

 

 

https://www.yamyamcoding.com/91c0b5c9-d4da-414a-8b24-35ccf8b8475c#5e082235aba742c4828730a1e1e05f9f

게임 프로그래머 취업 비법서(인터뷰 자료)