동적 메모리를 std :: vector에서 어떻게 관리합니까?

Question

std :: vector는 변경 요소 수의 관리를 어떻게 구현합니까? realloc() 함수를 사용합니까? 아니면 연결된 목록을 사용합니까?

감사합니다.

Answer 1

두 번째 템플릿 매개 변수로 지정된 할당자를 사용합니다. 이 때처럼. 그런

... 
if(_size == _capacity) { // size is never greater than capacity 
    // reallocate 
    T * _begin1 = alloc.allocate(_capacity * 2, 0); 
    size_type _capacity1 = _capacity * 2; 

    // copy construct items (copy over from old location). 
    for(size_type i=0; i<_size; i++) 
     alloc.construct(_begin1 + i, *(_begin + i)); 
    alloc.construct(_begin1 + _size, t); 

    // destruct old ones. dtors are not allowed to throw here. 
    // if they do, behavior is undefined (17.4.3.6/2) 
    for(size_type i=0;i<_size; i++) 
     alloc.destroy(_begin + i); 
    alloc.deallocate(_begin, _capacity); 

    // set new stuff, after everything worked out nicely 
    _begin = _begin1; 
    _capacity = _capacity1; 
} else { // size less than capacity 
    // tell the allocator to allocate an object at the right 
    // memory place previously allocated 
    alloc.construct(_begin + _size, t); 
} 
_size++; // now, we have one more item in us 
... 

뭔가 : t 객체가 추진 될 수 있도록, 그와 push_back에 말. 할당자는 메모리 할당에 신경을 쓸 것이다.메모리를 할당하고 그 메모리에 객체를 생성하는 단계를 유지하므로 메모리를 미리 할당 할 수 있지만 생성자를 호출 할 수는 없습니다. 재 할당하는 동안 벡터는 복사 생성자가 던진 예외에주의해야합니다. 이는 문제를 다소 복잡하게 만듭니다. 위 코드는 실제 코드가 아닌 몇 가지 가상 코드입니다. 아마도 많은 버그가있을 수 있습니다. 크기가 용량보다 커지면 할당 자에게 새로운 큰 메모리 블록을 할당하도록 요청하고, 그렇지 않으면 이전에 할당 된 공간에서 구성합니다.

정확한 의미는 할당 자에 따라 다릅니다. 이 표준 할당 인 경우,

new ((void*)(_start + n)) T(t); // known as "placement new" 

을 할 것입니다 구성 그리고는 allocate 그냥 ::operator new에서 메모리를 얻을 것이다 할당합니다. destroy는 소멸자

(_start + n)->~T(); 

모든 것은이 할당 뒤에 추상화되고 벡터 그냥 사용을 부를 것이다. 스택 또는 풀링 할당자는 완전히 다르게 작동 할 수 있습니다. reserve(N)를 호출 한 후

• 중요하다 vector에 대한 몇 가지 중요한 포인트는, 당신은 재 할당을 위험없이 당신의 벡터에 삽입 N 항목까지 할 수 있습니다. 그때까지는 size() <= capacity()까지 오랫동안 유효하며 그 요소에 대한 참조 및 반복자는 유효합니다.
• 벡터의 저장 공간이 연속적입니다. & v [0]을 현재 벡터에있는 요소를 많이 포함하는 버퍼로 처리 할 수 ​​있습니다.

Answer 2

std::vector에 의해 관리되는 메모리는 동적 배열의 시작 부분에 대한 포인터로 &vec[0]을 처리 할 수 ​​있도록 연속적으로 보장됩니다.

실제로 주어진 재 할당을 실제로 관리하는 방법은 구현에 따라 다릅니다.

Answer 3

벡터의 쉽고 빠른 규칙 중 하나는 데이터가 하나의 인접한 메모리 블록에 저장된다는 것입니다.

당신이 이론적으로이 작업을 수행 할 수있어 그 방법 :

const Widget* pWidgetArrayBegin = &(vecWidget[0]); 

그런 다음 매개 변수로 배열을 원하는 기능에 pWidgetArrayBegin를 전달할 수 있습니다.

예외는 std :: vector <bool> 전문화입니다. 사실 전혀 bool이 아니지만 그것은 또 다른 이야기입니다.

따라서 std :: vector는 메모리를 다시 할당하고 링크 된 목록을 사용하지 않습니다.

이것은 당신이 수행하여 스스로 발을 쏠 수 있다는 것을 의미합니다 : 당신이 알고있는 모든 내용은

Widget* pInteresting = &(vecWidget.back()); 
vecWidget.push_back(anotherWidget); 

을의와 push_back 호출은 무효 메모리의 완전히 새로운 블록으로 내용을 이동하는 벡터의 원인이 수 주목됩니다.

Answer 4

std :: vector 연속 메모리 블록에 데이터를 저장합니다.

벡터를 다음과 같이 선언한다고 가정합니다.

std :: vector intvect;

처음에는 x 개 요소의 메모리가 생성됩니다. 여기서 x는 구현에 의존합니다.

사용자가 x 개 이상의 요소를 삽입하는 경우 새 메모리 블록보다 2 배 (두 배 크기) 요소가 만들어지고 초기 벡터가이 메모리 블록에 복사됩니다.

예약 함수를 호출하여 벡터 메모리를 예약하는 것이 항상 권장되는 이유는 무엇입니까?

intvect.reserve (100);

벡터 데이터의 삭제 및 복사를 피하기 위해.