아이디어 : Vector와 Deque의 절충 컨테이너????

작업하다가
Vector나 Deque 같은 컨테이너가 필요해서 조목조목 들여다봤는데
둘다 별로 그다지 마음에 들진 않더군요.

임의 접근이 필요하며 멀티스레딩작업도 해야했습니다만.
사실 그보다는 이상적인 시퀸스 컨테이너에 욕심이 있었습니다 ㅡ,.ㅡ;

Vector는 2배씩 용량이 커지는거까지는 좋은데 모든 데이터가 재할당되는게 마음에 안들었고

Deque는 하나씩 데이터가 할당되는것도 마음에 안들었고(구현에따라다르지만.) 데이터를 추가할때마다 데이터를 가르키는 메모리맵이 재할당되야한다는게 마음에 들지 않았습니다.

그래서 그냥 생각해보다가 짬뽕시키면 어떨까 생각해봤습니다.
그러니까. Vector와 같이 용량은 두배씩 커지되 재할당되지는 않게.

먼저 데이터 블록을 가리키는 매모리맵 배열 32개를 둡니다.

void* pmemblock[32];

그리고 pmemblock[0]이 가르키는 데이터블록은 데이터가 2개 들어있습니다.

pmemblock[1] 은 Data 2개 블록을 가르킵니다.
pmemblock[2] 은 Data 4개 블록을 가르킵니다.
pmemblock[3] 은 Data 8개 블록을 가르킵니다.
pmemblock[4] 은 Data 16개 블록을 가르킵니다.
pmemblock[5] 은 Data 32개 블록을 가르킵니다.
pmemblock[6] 은 Data 64개 블록을 가르킵니다.
pmemblock[7] 은 Data 128개 블록을 가르킵니다.
pmemblock[8] 은 Data 256개 블록을 가르킵니다.
pmemblock[9] 은 Data 512개 블록을 가르킵니다.
...
pmemblock[31]은 Data 2147483648개 블록을 가르킵니다.

이렇게 하면 pmemblock[32]로 32비트 인덱스로 나타낼수있는 모든 데이터를 가리킬수 있으니까 pmemblock[32]는 재할당될 필요가 없겠죠

데이터가 2개가 들어가면 pmemblock[0] 에다가 2개 데이터만큼을 new 합니다.
4개가들어가면 pmemblock[1]까지 할당하고
8개가 들어가면 pmemblock[2] 까지 할당해야겠죠.

이렇게 할때 장점을 몇가지 꼽자면
1. Vector처럼 다 재할당하지 않고도 액세스시 케시 히트를 많이 높일수있다.

2. 멀티스레딩에 좀 더 좋다. 다수의 스레드에서 읽으면서 동시에 한 스레드에서 push_back 하는것이 안전하다.

3. 재할당 오버해드가 작음으로 push_back을 많이 하는것이 Vector나 Deque보다 빠르다.(측정결과 Deque는 데이터 하나추가할때마다 메모리 할당해서 2배 커질때마다 모두 재할당하는 Vector보다도 느렸음)

4. 데이터 축소가 Vector보다 유연하다. 마지막 메모리 블록만 해제하면 되니까.

5. 레퍼런스와 반복자가 재할당시에도 유효하다.

6. 여전히 임의접근이 가능하다.

그냥 생각이나서 올려봅니다 _-;;