내가 묻는 것과 같은 용기가 있습니까?

Question

나는 다음과 같은 속성을 가진 C++ 컨테이너 개체를 구현을 찾고 있었다 :

1. 가 연속적으로 메모리에있는 모든 요소가 어떤 캐시 미스를 유발하지 않고 이상 반복 할 수 있도록 유지합니다.
2. 확장 가능하며 고정 된 크기의 배열이 아니라 stl의 벡터와 유사하게 할당 된 메모리를 조정하여 추가 한만큼의 요소를 수용 할 수 있습니다.
3. std 벡터의 경우와 같이 크기를 조정할 때 요소를 메모리의 새 위치에 재 할당하지 않습니다. 컨테이너에있는 요소에 대한 포인터를 유지해야하므로 새 요소를 추가 할 때 포인터를 무효화하면 안됩니다.
4. 범위 기반 루프와 호환되어야하므로 내용을 효율적으로 반복 할 수 있습니다.

외부 라이브러리에서 이러한 요구 사항을 충족시키는 컨테이너가 있습니까? 아니면이 경우에 구현해야합니까?

일부 의견에서 지적한 바와 같이 원하는 속성을 모두 구현할 수있는 것은 아닙니다. 나는 이것을 끝내야했고, 마음에있는 구현이있다. 연속적으로 연속적으로 만드는 것은 불가능하므로 일부 불연속성을 수용 할 수 있습니다. 예를 들어, 데이터 컨테이너는 초기에 10 개의 요소에 대해 공간을 할당하고 제한에 도달하면 이전 블록의 양을 두 배로 메모리의 다른 부분을 할당하지만 기존 요소를 새 블록에 복사하지 않습니다. 대신 새로운 블록을 새로운 요소로 채 웁니다. 이렇게하면 불연속의 양이 최소화됩니다.

그래서 이미 구현 한 데이터 구조가 있습니까?

Answer 1

IMHO, 가장 가까운 데이터 구조는 deque입니다. 기본적으로 연속적인 메모리 덩어리를 저장하고 은 임의 액세스 반복기와 안정성을 push_back 에 제공합니다 (반복자가 무효화 되더라도 요소는 같은 위치에 있습니다). 제약 조건의 유일한 문제는 메모리가 연속적이지 않다는 것입니다. 도처 다른 사용자가 주석을 달았으므로 을 완전히 만족 시키려면 사용자의 요구 사항이 호환되지 않습니다. 그런데이 컨테이너로 한가지 달콤한 것은 앞에 을 밀 수 있다는 것입니다.