C++에서 간단한 객체 지향 그래프 프로그래밍

Question

저는 더 나은 프로그래머가되고 더 많은 모듈화되고 체계적인 코드를 만들기 위해 정말로 노력하고 있습니다.

연습으로 저는 STL을 사용하여 C++에서 매우 간단한 Graph 클래스를 만들려고했습니다. 아래 코드에서 내 Node 개체는 because the commented line results in a reference to a reference in STL을 컴파일하지 않습니다.

#include <set> 

class KeyComparable 
{ 
public: 
    int key; 
}; 

bool operator <(const KeyComparable & lhs, const KeyComparable & rhs) 
{ 
    return lhs.key < rhs.key; 
} 

class Node : public KeyComparable 
{ 
public: 
    // the following line prevents compilation 
    // std::set<Node &> adjacent; 
}; 

내가 키에 의해 가장자리 빠르게 제거 할 수 있기 때문에 (key에 의해)을 set에 가장자리를 저장하고 싶습니다. list<Node*>을 저장하면 문제가 없지만 빠른 삭제를 허용하지 않습니다. key.

std::set<Node>을 사용하는 경우 가장자리를 통해 변경하면 로컬 사본 (실제로 인접한 Node 아님) 만 변경됩니다. std::set<Node*>을 사용하면 < 연산자가 포인터 자체에서 작동하고 색인을 생성하는 메모리가 아니기 때문에 작동하지 않을 것이라고 생각합니다.

다른 클래스, 아마도 내 KeyComparable 클래스의 래핑 참조 또는 포인터를 고려했습니다 (링크 된 페이지에 따르면, 어떻게 부스트가이를 처리하는지).

또는 std::list<Node*> 및 std::map<int, iterator>' of locations in the std :: list`를 저장할 수 있습니다. 목록을 변경하면서 이터레이터가 유효하게 유지되는지 확실하지 않습니다.

예전에는 모든 것이 포인터 일 뿐이므로 모든 데이터 구조를 수동으로 처리했습니다. 하지만 실제로 모든 프로그래밍 언어에서 프로그래밍을 중단하고 싶습니다. 실제로는 좋은 프로그래머가됩니다.

무엇이 최선의 방법이라고 생각하십니까?이 문제를 해결하는 방법은 무엇입니까? 고마워.

Answer 1

추측했듯이 저장된 항목의 요구 사항 중 하나가 할당 가능하기 때문에 STL 컨테이너에 참조를 저장할 수 없습니다. STL 컨테이너에 배열을 저장할 수없는 것과 같은 이유입니다. STL 클래스에 포인터를 저장하면 사용자 정의 형식을 사용할 수없는 것으로 보이는 사용자 정의 형식이 아닌 하나 이상의 연산자도 오버로드 할 수 없습니다.

그러나 여전히

struct NodePtrCompare { 
    bool operator()(const Node* left, const Node* right) const { 
     return left->key < right->key; 
    } 
}; 

std::set<Node*, NodePtrCompare> adjacent; 

그리고 당신이 원하는 것처럼 당신은 여전히 ​​key에 의해 빠르게 제거를 얻을 : 사용자 지정 비교 자 펑터를 set 주면 포인터 std::set를 사용합니다.