StableArray Class

항목들의 주소들을 변경하지 않은 상태로 저장하는 랜덤 컨테이너입니다.

template <class Type>
class StableArray : public RandomContainer< Type >

Template 파라미터

Type

배열이 저장하는 항목들의 타입입니다.

멤버

생성자

StableArray

StableArray 생성자입니다.

내용 관리

Swap	두 배열의 내용을 교환합니다.

내용 쿼리

Enumerate	배열 내용의 열거를 허용합니다.
Begin	배열의 1번째 항목을 참조하는 반복자(iterator)를 리턴합니다.
End	배열의 마지막 직전 항목을 참조하는 반복자(iterator)를 리턴합니다.

성능 튜닝

GetCapacity	배열의 용량을 리턴합니다.
GetFillFactor	배열의 채우기 요소를 리턴합니다.
GetPageSize	저장 페이지의 크기를 리턴합니다.
GetAllocationStrategy	할당 전략을 리턴합니다.
GetCompactionStrategy	압축 전략을 리턴합니다.
Compact	저장 페이지들을 압축하고 사용하지 않는 메모리를 해제합니다.

Public 타입

AllocationStrategy	가능한 할당 전략입니다.
CompactionStrategy	가능한 압축 전략입니다.
ConstIterator	StableArray의 상수 랜덤 반복자(iterator)의 타입입니다.
Iterator	StableArray의 랜덤 반복자(iterator)의 타입입니다.

설명

StableArray는 저장된 항목들의 주소들을 변경하지 않은 상태로 저장할 수 있는 RandomContainer 구현입니다. 이것은 메모리 페이지들에 상주하는 항목들에 대한 포인터들을 저장하는 맵 테이블을 이용하여 구현할 수 있습니다. 삽입 또는 제거시에 맵 테이블이 조작됩니다. 항목들 자체는 영향을 받지 않습니다. 할당 전략에 따라 1개 이상의 페이지들을 포함하는 할당 단위로 메모리를 할당합니다.
StableArray의 public 메소드들은 비-가상이며 적절한 경우 인라인입니다.

랜덤 컨테이너 구현 중에서 StableArray는 다음 장점을 갖고 있습니다:

• 기본적으로 항목들의 주소들은 안정적입니다. 그래서 항목들의 참조들을 장시간 저장할 수 있습니다. 삽입과 제거시에 재할당이 없으며 다만 항목들의 포인터들을 저장하는 맵 테이블만 조작됩니다. 항목들 자체는 메모리 페이지들에 상주합니다. 새로운 항목이 배열에 맞지 않으면, 새로운 페이지 (또는 할당 전략에 따른 새로운 페이지들)이 할당되고, 항상 새로운 페이지 상의 항목에 대한 새로운 포인터가 맵 테이블에 저장됩니다.
  그러나 제거 동작은 페이지들 상에 구멍을 남기므로 조각이 발생하고 메모리를 낭비합니다. 페이지들 상의 항목들을 압축하여 이것을 교정할 수 있습니다. (수동 또는 자동으로) 그러나 이 동작은 항목들을 이동하므로 항목들의 주소들이 변경될 것입니다! 차후 삽입 동작들 역시 구멍들을 채우게 된다는 것을 참고하십시오.
• 할당 연산자를 호출하여 항목을 하나씩 복사하는 대신 빠른 메모리 복사를 사용하여 삽입 또는 제거 지점 위의 항목들에 대한 포인터들만 복사하기 때문에 삽입과 삭제가 비교적 빠릅니다. 결과적으로 삽입과 삭제가 다른 랜덤 컨테이너 구현보다 10배 더 빠를 수 있습니다.
• 메모리 활용도가 좋습니다. 상수(constant) 할당 전략을 이용하면 최대 2 페이지만 낭비됩니다. 선형(linear) 할당 전략을 이용하면 최대 sqrt (8 * page_count + 1) - 2 페이지들까지 낭비됩니다. 그러나 지수(exponential) 할당 전략의 메모리 활용률은 나쁘고 그 특성은 Array의 그것과 비슷합니다.
• 메모리를 거의 할당하지 않으며 선형(4 Gb에서 최대 약 10000)과 지수(4 Gb에서 최대 32) 할당 전략으로 거의 할당 단위들을 보유하지 않습니다. 그러나 상수 할당 전략과 많은 수의 항목들을 할당하면 자주 할당하고 상대적으로 많은 수의 할당 단위들을 보유하게 됩니다. (이 경우 단일 페이지)

랜덤 컨테이너 구현 중에서 StableArray는 다음 단점을 갖고 있습니다:

• 제거 동작은 페이지들 상에 조각들을 만듭니다. 이것은 페이지들 상의 항목들을 압축하여 교정할 수 있습니다. (수동 또는 자동으로) 그러나 이 동작은 항목들을 이동시키므로 항목들의 주소들이 변경될 것입니다! 차후 삽입 동작들 역시 구멍들을 채우게 된다는 것을 참고하십시오.
• 항목들에게 상당한 저장 오버헤드를 부과합니다: 항목 저장 셀의 총 비용에는 항목 자체, 항목에 대한 포인터, 페이지들에 대한 포인터들을 포함하는 페이지 테이블로 인한 약간의 오버헤드가 포함됩니다. 만약 배열이 정수들을 포함한다면, 이 오버헤드는 최소한 총 비용을 2배 이상 증가시킬 것입니다.
• 큰 고유 크기를 갖고 있습니다: 현재 40 바이트입니다.

항목들은 기본 생성자와 복사 생성자, 할당 연산자를 가져야 합니다. 이외에도 비교 연산자(==와 !=)를 갖고 있다면, 값 종속적인 연산(예. Find, Count, Contains 등) 역시 사용할 수 있게 됩니다.

다음 그림은 StableArray의 내부 레이아웃을 보여줍니다:

요구사항

네임스페이스: GS

헤더: StableArray.hpp

참고사항

Array | PagedArray