C++에서 할당 해제 (포인터의 벡터 배열)

Question

그래, Graph 클래스를 만들려고하는데 알고리즘을 실행할 수 있기를 바래서 나중에 자유 시간이있을 때 나중에이 여름에 GUI를 추가 할 수 있기를 바랍니다. 지금은 벡터의 배열 (각 꼭지점마다 하나씩)로 구현되는 adjList가 있습니다. 각 벡터는 연결된 각 꼭지점에서 다른 꼭지점으로가는 가장자리를 나타내는 포인터 목록입니다. 다음과 같이 내 그래프 클래스의 보호 된 멤버로 선언됩니다.

std::vector <Node*> *adjList; 
adjList = new std::vector<Node*>[V]; 

나는 측면 질문이 있습니다. 이제 여기에 포인터를 보유하는 벡터 배열 (포인터를 통해)이 있습니다. 대신이 배열이 아니라 노드 포인터의 단 하나의 벡터에 대한 포인터 아니었다면 그때과 같이 생성자를 호출 할 수 있습니다이 나를 동적 배열의 기본 크기를 지정할 수 있도록 할

adjList = new std::vector<Node*>(10); 

벡터,하지만 적어도 생성자를 호출 할 수없는 것 같아요, 또는 적어도 배열을 가질 때 구문을 올바르게 가져올 수 없습니다.

지금 내 관심사입니다. 내 포인터 배열에있는 각 벡터에 대해 addVertex 메서드에서 new 연산자를 호출하여 각 벡터에 노드 포인터를 추가합니다. 이제는이 모든 것을 올바르게 할당 해제 처리해야합니다. 나는 이것이 C++에서 어떻게 작동해야하는지에 대한 이해를 가지고 있다고 믿지만, 포인터가 까다 롭다는 것을 알고 있으므로 누군가이 코드 기반을 많이 추가하기 전에 살펴 보길 원했다. 내가 가지고있는 것과 매우 흡사 한 몇 가지 검색으로는 아무 것도 찾을 수 없었습니다. 여기 내 할당 해제 위치 :

for(int i =0; i < V; i++) 
    for (unsigned int j = 0; j < adjList[i].size(); j++) 
     delete adjList[i][j]; 
delete adjList; 

메모리가 모두 비게됩니까? 또한 확실하게 확인할 수있는 쉬운 방법이 있습니다. 내가 디버깅하는 동안 새 메모리를 사용하여 할당 된 메모리 양을 유지하려면?

[편집 : 추가 정보를 원하시면/w 업데이트 여기

내가 psuedocode에 주어진 구현하려면 걸려 알고리즘 중 하나를 보여주는 구글 도서에 link입니다. 폭 확대 우선 검색의이 버전은 인접성 목록 (포인터 목록 배열)에서 작동합니다. 인접성 목록을 사용하여 각 노드에 지정된 속성 때문에 포인터를 사용해야합니다.

각 노드가 실행 된 후에 저장된 내 BFS 알고리즘에서이 속성을 유지하려고합니다. 다른 방법으로이를 수행 할 수 있다는 것을 알고 있습니다. 아마도 노드를 인덱싱하고 병렬 배열을 사용하여 특성을 저장할 수 있습니다. 그러나이 psuedo-code (링크의 BFS 용)와 비슷한 코드를 원했습니다.

Answer 1

1. 왜 벡터 배열을 사용하고 있습니까?
2. 왜 벡터에 대한 포인터를 유지하고 있습니까?
3. 왜 포인터 벡터를 유지하고 있습니까?

이러한 세 가지 결정 모두 비용이 들며 벡터 클래스의 메모리 관리 기능을 직접적으로 무효화합니다. 벡터는 단순히 덮개 아래에서 자랄 수있는 배열이 아니라 RAII이라는 패턴을 통해 메모리를 관리합니다.

포인터의 벡터를 만들 때 벡터는 포인터가 파괴 될 때 참조하는 메모리를 정리할 수 없으므로 벡터의 모든 요소에 대해 delete을 호출해야합니다.

벡터에 대한 포인터를 만들 때 벡터가 소멸자에 할당 한 메모리를 할당 해제한다는 사실을 이용할 수 없습니다. 따라서 메모리 누수를 방지하기 위해 다시 벡터에 delete을 호출해야하므로 벡터의 메모리 관리 기능을 무효화합니다.

벡터 배열을 유지 관리하면 ... 이미 벡터를 사용하고 있습니다. 왜 vector<vector<T>>을 사용하지 않으시겠습니까?

벡터 유형은 사용자가 지금 직면하고있는 문제를 피하기 위해 동적으로 메모리를 할당합니다. 물론, 자신의 메모리를 관리 할 수 ​​있습니다 (할당 한 반대 순서로 할당을 해제하면됩니다).하지만 메커니즘을 사용할 때 방해가되는 이유는 무엇입니까?

여기서는 디자인 목표를 이해하지 못합니다. 단순히 vector<vector<Edge>>을 사용하고 이러한 문제를 완전히 없애지 않는 이유는 무엇입니까?

class Edge { 
    // whatever 
} 

class Graph { 
private: 
    // when instances of this class go out of scope, 
    // all of the memory allocated to these vectors is deallocated for you! 
    vector<vector<Edge>> vertices; 
} 

Answer 2

당신이 포인터를 통해 내부 객체에 대한 색인의 많은 클래스를 구축하는 경우, 하나의 방법은는 메모리 풀을 유지하는 것입니다 후에는 메모리 위치에서만 을 개체를 삭제할 수 있도록합니다. 예를 들어 std::vector<Node*> Graph::memPool 명의 회원이있을 수 있습니다. Graph을 삭제할 때 Graph::memPool에있는 모든 항목을 삭제하고 개별 노드의 adjList에있는 색인은 삭제하지 마십시오. 새로운 노드가 생성 될 때마다 메모리 풀에 추가하십시오.

현재 예제에서 두 노드가 동일한 노드의 가장자리를 갖고 있으면 잘못된 메모리 위치를 삭제할 수 있습니다.

또 다른 대안은 포인터 대신 번호가 매겨진 색인을 사용하는 것입니다. 그래프에는 노드의 마스터 벡터가 있고 각 노드의 인접성 목록에는 벡터 인덱스가 있습니다.

class Graph 
{ 
    std::vector<Node> all_nodes; 
    ... 
}; 

struct Node 
{ 
    std::vector<size_t> adjList; 
    SomeDataType nodeData;//e.g. node cost, weight, reward, etc 
    ... 
}; 

이 경우 명시 적 dellocation이 필요하지 않습니다. 포인터를 사용하는 것과 마찬가지로 그래프에서 노드를 제거하려면 인덱스를 업데이트하기 위해 인접 목록을 검색해야합니다.