C++ Technical Report 1 : Containers

Containers
Tuple Types
std::pair의 확장형으로 std::pair가 2개의 요소를 갖는다면 tuple은 n개의 요소를 갖는다는 것이 차이점 입니다. tuple자체의 영어 뜻이 ...개의 요소로된 집합이라는 뜻입니다. 간단히 struct 대용으로 사용할 수 있을 듯 보입니다.

#include <tuple>

bool TTR1_Tuple01::Test()
{
    typedef tr1::tuple<int, char, string> triple;
    triple test = tr1::make_tuple(1, 't', "test");
    cout << "0: " << tr1::get<0>(test) << endl;
    cout << "1: " << tr1::get<1>(test) << endl;
    cout << "2: " << tr1::get<2>(test) << endl;
   
    int element01;
    //tr1::ignore 요소를 얻지 않음
    tr1::tie(element01, tr1::ignore, tr1::ignore) = test;
    cout << "element: " << tr1::get<0>(test) << endl;


    return true;
}

Fixed Size Array
array에 대한 정식 지원인 듯 보입니다. 전에는 생성한 뒤에 vector나 list에 대입해서 썼는데 이제는 그럴 필요가 없는 듯 보입니다. 그 외에 별반 특징이 보이지는 않습니다.

#include <array>

bool TTR1_Array01::Test()
{
    tr1::array< int ,5> test = { {1,2,3,4,5} };
    copy(test.begin(), test.end(), ostream_iterator< int >(cout, "\n" ));


    return true;
}

Unordered Associative Containers (Hash Tables)
STL에서는 제외되었던 해쉬테이블입니다. 자료관리 시간에 배우는 기본 자료구조 중에 하나이죠. 가장 큰 특징은 평균적으로 O(1) 즉 상수 시간내에 원소를 찾을 수 있다는 점입니다. 그러나 레드블랙 트리(stl::map, stl::set에 사용된 자료구조)가 O(logN)의 일정한 시간내에 찾는데 비하여 해쉬 테이블은 최악의 경우 O(N)의 시간에 원소를 찾습니다.
 사용법은 기존의 stl::map과 비슷한 듯 보이며 자료구조 정석대로라면 원소의 양이 많을 경우 stl::map이나 stl::set을 사용하며 원소의 양이 적을 경우 tr1::unordered_set이나 tr1::unordered_map을 사용하면 됩니다. 이는 해쉬테이블이 STL에서 제외되었던 이유입니다. 해쉬함수에 의한 충돌시 3가지 방법(선형탐지(Linear Probing), 이차탐지(Quadratic Probing), 리해슁(rehashing))으로 충돌을 해결한다 해도 데이터가 해쉬함수에 의하여 고루게 분포하지 않으면 최악의 경우 O(N)의 시간에 원소를 찾게되어 있기 떄문입니다. 개인적으로 데이터가 많을 수록 처리시간이 최악이 될 확률은 높아질 듯 보입니다.
 <unordered_map>과 <unordered_set>헤더를 사용하기 위하여  include해야 합니다.

컨테이너 종류	설 명
unordered_set	요소의 중복을 허락하지 않는 집합
unordered_multiset	요소의 중복을 허락하는 집합
unordered_map	요소의 중복을 허락하지 않는 사전
unordered_multimap	요소의 중복을 허락하는 사전

참조사이트

jacking님의 노트 '01. Boost C++0x TR1 - Install, array, shared_ptr, weak_ptr' jacking님의 노트 '02. Boost C++0x TR1 - tuple' jacking님의 노트 '04. Boost C++0x TR1 - unordered' 봔님의 블로그 큐(Queue), 스택(Stack), 그리고 해쉬테이블(Hashtable) 중 해쉬테이블(Hashtable)

.Net 컬렉션에 대한 글이지만 자료구조는 기본적인 내용이 같고 리해쉬(rehashing)기법을 설명하기 위하여 기존의 충돌 해결 방법에 대하여 잘 설명해 놓았습니다.