[c++ 11] 새로 등장한 유용한 컨테이너들

Posted by 적분 ∫2tdt=t²+c
2013.08.02 17:14 프로그래밍/테크닉



c++  11로 넘어오면서 표준 컨테이너에 유용한 녀석들이 대게 추가되었는데요, 시간을 잠시 내어 간략하게 살펴보려고 합니다.


1. std::array

하하, 이름대로 정말 단순히 배열을 담는 컨테이너입니다. vector와는 무엇이 다르냐? 하면 크기가 고정이 되어있다는 것이지요.



살펴보면 정말 별거 없습니다. 기존의 c++  에서는 배열은 포인터의 일종처럼 다루어져서, 어떤 메소드를 가지지도 못하고, 서로 대입하거나 비교하는 것도 불가능했죠. 이점에서 참 객체지향언어답지 못했습니다. c++  11에서 추가된 array 컨테이너는 이런 배열을 클래스화하여, 각종 메소드를 추가하고 좀더 직관적으로 코딩할 수 있게 만들어줬네요!

위의 예시를 살펴보면, 기존에 두 배열을 비교하기 위해선 일일히 배열을 순회하면서 다른 요소가 있는지 확인하는 방법 밖에 없었습니다. 굉장히 귀찮은 일이지요. 대입의 경우 memcpy를 이용하거나(단, 이 방법은 클래스나 구조체 등에 사용할 수 없죠. 생성자가 제대로 호출되지 않기때문에) 역시 반복문을 순회하는 방법밖에 없습니다.

하지만 c++  11에 추가된 array 컨테이너를 이용하면 비교 연산자를 이용하여 쉽게 비교할수 있고, 대입 연산자를 이용해 쉽게 대입할 수 있습니다. 코드가 직관적으로 바뀌었습니다! 그리고 여타 다른 컨테이너와 마찬가지로 begin(), end() 메소드를 지원하므로 stl 알고리즘을 사용할때도 일관성을 유지할 수 있죠.

그리고 범위기반 for loop를 사용할 수 있습니다. (아 이건 그냥 배열에서도 사용가능합니다...)


2. std::forward_list

싱글링크드 리스트입니다. 기존의 c++  에서는 std::list로 이중링크드 리스트만 제공했는데(도대체 왜?!) 드디어 c++  11에서 싱글링크드 리스트가 추가되었습니다. 다른 사용방법은 std::list와 동일하지만, 요놈은 싱글링크드 리스트라 한 방향으로만 순회가 가능합니다. 당연히 이중링크드 리스트보다 메모리를 덜 사용하지요. 양방향 순회가 필요없는 경우에 사용하면 좋겠죠?


3. 대거 추가된 해쉬 컨테이너들

std::unordered_set, std::unordered_map, std::unordered_multiset, std::unordered_multimap이 추가되었습니다. 기존의 std::set, std::map, std::multiset, std::multimap의 해쉬 버전이라고 할 수 있습니다. 거의 모든 메소드가 동일하므로 기존의 코드를 수정하여 unordered버전으로 바꾸는 데에도 문제가 없습니다. (다만 unordered 컨테이너는 말 그대로 정렬 대신 해쉬를 이용하므로 lower_bound, upper_bound는 제공하지 않습니다.)

해쉬를 이용한다는 특성 덕분에 요소에 접근하는데 걸리는 시간이 평균적으로 O(1), 최악의 경우에 O(n)이 걸립니다. (비교를 통해 요소를 찾는 기존의 set, map, multiset, multimap의 경우 접근 시간이 평균 O(log n)이었죠.)

기존의 컨테이너보다 메모리를 더 사용한다는 단점이 있지만(벤치마크에서는 2배 정도 더 사용하는 걸로 나타났네요. 링크), 접근속도가 비약적으로 상승합니다. 요소가 정렬되어 저장될 필요가 없고, 접근이 잦은 경우 set, map, multiset, multimap 대신 unorderd_set, unordered_map, unordered_multiset, unordered_multimap을 사용하면 좋겠죠?


해쉬를 위해서 c++  11에 std::hash라는 해쉬 계산을 위한 템플릿 구조체가 추가되었습니다. 표준에는 c언어 기본 타입(int, double, char, bool, 포인터 등)에 대한 std::hash가 정의되어있고, 또한 std::string, std::wstring 등의 문자열 타입, std::shared_ptr, std::unique_ptr 등의 포인터 타입 등등이 정의되어 있습니다. 이외의 타입을 키로 사용할 경우에는 std::hash를 정의해주어야합니다.



std::hash를 직접 정의할때 주의할 점은 해쉬 충돌을 최소화할 수 있도록 해야한다는 거죠. 쉬프트와 xor을 함께 이용하는게 비교적 저렴하면서도 좋은 성능을 가져올 수 있다고 알려져 있습니다.

예로 std::unordered_map만 들었지만, 나머지 역시 같은 방법으로 사용할 수 있습니다.


여기까지 c++  11에서 새로 추가된 컨테이너에 대해서 살펴보았습니다. c++  11 컴파일러를 사용할수 있다면, 약간의 수정만을 통해서, 훨씬 직관적이면서도 성능 좋은 프로그램을 생산할 수 있다는거 명심하세요.

Tags
이 댓글을 비밀 댓글로
    • SeHwa
    • 2013.08.02 18:55
    좋은 글 감사합니다