C++에서 포인터 속성으로 struct 속성을 변환하는 방법은 무엇입니까?

Question

DAG는 JSON 형식으로되어 있습니다. 각 노드는 항목이고 두 개의 배열이 있습니다. 하나의 배열은 화살표가 들어있는 다른 노드를위한 배열이고,이 노드가 향하는 노드의 배열 (나가는 화살표)입니다.

따라서, 예를 들어 :

{ 
    'id': 'A', 
    'connected_from' : ['B','C'], 
    'connects_to' : ['D','E'] 
} 

그리고 그 모두 함께 DAG를 형성,이 노드의 컬렉션을 가지고있다.

나는 ID가 단순히 문자열이 노드를 개최 구조체에 노드를지도하고 싶습니다, 나는이 구조체의 포인터의 벡터로 배열을 싶습니다

struct node { 
    string id; 
    vector<node*> connected_from; 
    vector<node*> connected_to; 
} 

JSON 배열의 'id'노드 항목을 해당 노드를 보유하는 올바른 구조체에 대한 포인터로 변환하려면 어떻게해야합니까?

하나의 확실한 접근법은 키 - 값 쌍의 맵을 작성하는 것입니다. 여기서 key = id, value = 해당 ID를 가진 구조체에 대한 포인터이며 조회는 수행하지만 더 좋은 방법이 있습니까?

Answer 1

아니요. 제공된 정보 만 더 좋은 방법은 아닙니다.지도를 만들어야합니다.

그러나 단일 문자 id의 경우지도는 가능한 한 간단한 배열 형식을 취할 수 있습니다. 영어 알파벳 26 항목.

Answer 2

모든 노드를 보유하고있는 컨테이너 객체가있을 것입니다. 그렇지 않으면 누출 될 것입니다. 노드를 찾기 위해 컨테이너를 항상 검사 할 수 있습니다. 그러나 이는 비효율적 일 것입니다 - O (N^2)이고지도 조회는 O (N log N)입니다.

개체를 컨테이너에 정렬 된 순서로 저장하거나 정렬 된 컨테이너를 사용하면 두 경우를 모두 O (N 로그 N)로 줄일 수 있습니다.

하지만 작은 그래프의 경우 스캔 속도가 더 빠를 수도 있습니다.

Answer 3

당신의 제안은 괜찮다고 생각합니다 ... ID에서 노드로 매핑하십시오. 실용적인 목적으로는 간단하고 직관적이며 빠릅니다. 데이터가 JSON에서 구문 분석 중이므로 저장소 및 조회가 성능에 큰 영향을주지는 않습니다. 당신이 정말로 염려한다면 사전을 구현하여지도를 대체하십시오.

일반적으로 나는 항상 작업을 완료하는 가장 단순하고, 가장 깨끗한 접근 방식을지지합니다. 너무 많은 사람들이 코드의 실제 병목 현상이 다른 곳에있는 경우 알고리즘에서 메모리 또는 성능 적중에 집착합니다.