태그 보관물: c++

c++

C ++에서 벡터의 초기 용량 예약으로 배열을 만들

이란 무엇입니까 capacity()의 std::vector기본 constructor에를 사용하여 생성되는가? 나는 그것이 size()0 이라는 것을 압니다 . 기본 생성 벡터가 힙 메모리 할당을 호출하지 않는다고 말할 수 있습니까?

이런 식으로 .NET과 같은 단일 할당을 사용하여 임의 예약으로 배열을 만들 수 있습니다 std::vector<int> iv; iv.reserve(2345);. 어떤 이유로 size()2345 에서 시작하고 싶지 않다고 가정 해 봅시다 .

예 : Linux (g ++ 4.4.5, 커널 2.6.32 amd64)

#include <iostream>
#include <vector>

int main()
{
  using namespace std;
  cout << vector<int>().capacity() << "," << vector<int>(10).capacity() << endl;
  return 0;
}

인쇄 0,10. 규칙입니까, 아니면 STL 공급 업체에 따라 다릅니 까?

답변

표준은 capacity컨테이너 의 이니셜 이 무엇인지 지정하지 않으므로 구현에 의존하고 있습니다. 일반적인 구현은 용량을 0에서 시작하지만 보장 할 수는 없습니다. 반면에 당신의 전략을 더 잘할 방법이 std::vector<int> iv; iv.reserve(2345);없으므로 그것을 고수하십시오.

답변

std :: vector의 저장소 구현은 크게 다르지만 제가 본 모든 것은 0부터 시작합니다.

다음 코드 :

#include <iostream>
#include <vector>

int main()
{
  using namespace std;

  vector<int> normal;
  cout << normal.capacity() << endl;

  for (unsigned int loop = 0; loop != 10; ++loop)
  {
      normal.push_back(1);
      cout << normal.capacity() << endl;
  }

  cin.get();
  return 0;
}

다음 출력을 제공합니다.

0
1
2
4
4
8
8
8
8
16
16

GCC 5.1 및 :

0
1
2
3
4
6
6
9
9
9
13

MSVC 2013에서.

답변

표준을 이해하는 한 (실제로 참조 이름을 지정할 수는 없지만) 컨테이너 인스턴스화 및 메모리 할당은 합당한 이유로 의도적으로 분리되었습니다. 따라서 당신은

  • constructor 컨테이너 자체를 만들려면
  • reserve() 주어진 개체 수를 최소한 (!) 수용하기 위해 적절하게 큰 메모리 블록을 미리 할당합니다.

그리고 이것은 많은 의미가 있습니다. 존재하는 유일한 권리 reserve()는 벡터를 성장시킬 때 비용이 많이 드는 재 할당을 코딩 할 기회를주는 것입니다. 유용하게 사용하려면 저장할 개체의 수를 알고 있거나 최소한 교육 된 추측을 할 수 있어야합니다. 이것이 주어지지 않으면 reserve()낭비되는 메모리에 대한 재 할당을 변경하므로 멀리하는 것이 좋습니다 .

그래서 모두 합치면 :

  • 표준은 의도적 으로 특정 수의 객체에 대해 메모리 블록을 미리 할당 할 수있는 생성자를 지정 하지 않습니다 (이는 구현에 특정한 고정 “무언가”를 할당하는 것보다 적어도 더 바람직 할 것입니다).
  • 할당은 암시 적이 어서는 안됩니다. 따라서 블록을 미리 할당하려면 별도의 호출을 reserve()해야하며 동일한 건설 장소에있을 필요는 없습니다 (수용에 필요한 크기를 알게 된 후 나중에 가능할 수도 있습니다).
  • 따라서 벡터가 항상 구현 정의 된 크기의 메모리 블록을 미리 할당하면의 의도 된 작업을 망칠 reserve()수 있지 않습니까?
  • STL이 의도 한 목적과 벡터의 예상 크기를 자연스럽게 알 수없는 경우 블록을 사전 할당하면 어떤 이점이 있습니까? 비생산적이지 않다면 다소 무의미 할 것입니다.
  • 대신 적절한 해결책은 push_back().NET에 의해 이전에 명시 적으로 할당되지 않은 경우 첫 번째로 특정 블록을 할당하고 구현 하는 것 reserve()입니다.
  • 필요한 재 할당의 경우 블록 크기의 증가도 구현에 따라 다릅니다. 내가 아는 벡터 구현은 크기가 기하 급수적으로 증가하는 것으로 시작하지만 엄청난 양의 메모리를 낭비하거나 심지어 날려 버리는 것을 피하기 위해 특정 최대 값으로 증가율을 제한합니다.

이 모든 것은 할당 생성자에 의해 방해받지 않는 경우에만 완전한 작동과 이점을 제공합니다. 요청시 reserve()(및 shrink_to_fit()) 로 재정의 할 수있는 일반적인 시나리오에 대한 합리적인 기본값이 있습니다 . 따라서 표준이 명시 적으로 명시하지 않더라도 새로 생성 된 벡터가 사전 할당되지 않는 것이 현재의 모든 구현에 대해 매우 안전한 방법이라고 가정합니다.

답변

다른 답변에 약간의 추가로 Visual Studio를 사용하여 디버그 조건에서 실행할 때 용량이 0에서 시작하더라도 기본 구성된 벡터가 여전히 힙에 할당된다는 것을 발견했습니다.

특히 _ITERATOR_DEBUG_LEVEL! = 0이면 벡터는 반복기 검사를 돕기 위해 약간의 공간을 할당합니다.

https://docs.microsoft.com/en-gb/cpp/standard-library/iterator-debug-level

당시 사용자 지정 할당자를 사용하고 있었고 추가 할당을 기대하지 않았기 때문에 약간 짜증이났습니다.

답변

이것은 오래된 질문이며 여기에있는 모든 답변은 표준의 관점과 std::vector::reserve;

그러나 어떤 STL 구현에서도 std::vector<T>객체 생성시 메모리를 할당하는 것이 왜 이치에 맞지 않는지 설명하겠습니다 .

  1. std::vector<T> 불완전한 유형의;

    C ++ 17 이전에는 인스턴스화 시점에서 std::vector<T>의 정의를 T아직 알 수없는 경우 a를 생성하는 것이 정의되지 않은 동작이었습니다 . 그러나 이러한 제약은 C ++ 17에서 완화되었습니다 .

    객체에 메모리를 효율적으로 할당하려면 크기를 알아야합니다. C ++ 17 이상에서 클라이언트는 std::vector<T>클래스가 T. 유형 완전성에 따라 메모리 할당 특성을 갖는 것이 합리적입니까?

  2. Unwanted Memory allocations

    소프트웨어에서 그래프를 모델링해야하는 경우가 많이 있습니다. (나무는 그래프입니다.) 다음과 같이 모델링 할 가능성이 높습니다.

    class Node {
    ....
    std::vector<Node> children; //or std::vector< *some pointer type* > children;
    ....
 };

    이제 잠시 생각하고 터미널 노드가 많다고 상상해보십시오. STL 구현이 단순히 .NET Framework에 개체가있을 것으로 예상하여 추가 메모리를 할당하면 매우 화가 날 것입니다 children.

    이것은 하나의 예일뿐입니다.

답변

Standard는 용량에 대한 초기 값을 지정하지 않지만 STL 컨테이너는 최대 크기를 초과하지 않는 경우 입력 한만큼의 데이터를 수용하도록 자동으로 커집니다 (알려면 max_size 멤버 함수 사용). 벡터 및 문자열의 경우 더 많은 공간이 필요할 때마다 realloc에 ​​의해 증가가 처리됩니다. 1-1000 값을 갖는 벡터를 만들고 싶다고 가정합니다. 예약을 사용하지 않으면 코드는 일반적으로 다음 루프 동안 2 ~ 18 번의 재 할당이 발생합니다.

vector<int> v;
for ( int i = 1; i <= 1000; i++) v.push_back(i);

예약을 사용하도록 코드를 수정하면 루프 중에 할당이 0이 될 수 있습니다.

vector<int> v;
v.reserve(1000);

for ( int i = 1; i <= 1000; i++) v.push_back(i);

대략적으로 말하면 벡터 및 스트링 용량은 매번 1.5에서 2 배씩 증가합니다.

답변