네이밍은 의도적으로 좀 이상하게 했음.

프갤한다고 자랑할 수는 없으니

 

단순 이해용

struct node{

     vector<node*> link;

};

 

노드수가 1회 한번 정해진다면

vector<node> data;

아니라면

vector<node*> data;

 

 

 

 

 

 

위 단순한 노드 디자인은 노드가 많아지면 메모리 단편화 문제가 있어. 노드 마다 갯수가 다른 다른 link가 여러개라서 서로 다른 크기가 각자 할당되

그래서 기본 이해용 코드보다 조금 복잡해지지만 이렇게 개선할수 있어

그런데 이코드는 노드수 연결수를 미리 알고 있는 경우야

 

struct node{

size_t id_begin;

size_t id_end;

};

vector<node> data;

 

struct nodelink{

size_t id_nodeFrom;

size_t id_nodeTo;

};

vector<nodelink> link; // 노드별 연결정보를 1차원 배열로 밖으로 뺀거야

 

 

1 data를 노드 수만금 reserve해주고 하나씩 삽입

2 노드연결정보를 link에 수집

3. id_nodeFrom을 기준으로 소트해 // 순서대로 들어왔다면 그럴 필요 없지

4. 이제 link element들을 쭉 돌면서 보면 nodelinke들이 id_nodeFrom이 같은건 뭉쳐있잖아

    그걸 가지고 해당 되는 node의 id_begin, id_end를 현재 연속되는 element 인덱스를 설정해주면 되