Lập trình một đồ thị hướng đối tượng đơn giản trong C++

Question

Tôi thực sự đang cố gắng trở thành một lập trình viên tốt hơn, và tạo thêm mã tổ chức, mô đun.

Như một bài tập, tôi đã cố gắng tạo một lớp rất đơn giản Graph trong C++ với STL. Trong mã bên dưới, đối tượng Node của tôi không biên dịch 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; 
}; 

Tôi muốn để lưu trữ các cạnh trong một set (bởi key) vì nó cho phép loại bỏ nhanh chóng các cạnh bằng chìa khóa. Nếu tôi đã lưu trữ list<Node*>, điều đó sẽ hoạt động tốt, nhưng nó sẽ không cho phép xóa nhanh bởi key.

Nếu tôi sử dụng std::set<Node>, các thay đổi được thực hiện qua một cạnh sẽ chỉ thay đổi bản sao cục bộ (không thực sự là số Node liền kề). Nếu tôi sử dụng std::set<Node*>, tôi không tin rằng toán tử < sẽ hoạt động vì nó sẽ hoạt động trên chính con trỏ chứ không phải bộ nhớ mà chúng lập chỉ mục.

Tôi xem xét tham chiếu gói hoặc con trỏ trong lớp khác, có thể là lớp KeyComparable của tôi (theo trang được liên kết, đây là cách tăng cường xử lý nó).

Hoặc, tôi có thể lưu trữ std::list<Node*> và std::map<int, iterator>' of locations in the std :: list`. Tôi không chắc chắn nếu các vòng lặp sẽ vẫn hợp lệ khi tôi thay đổi danh sách.

Cách đây không lâu, mọi thứ ở đây chỉ là con trỏ và tôi sẽ xử lý tất cả các cấu trúc dữ liệu theo cách thủ công. Nhưng tôi thực sự muốn dừng lập trình theo kiểu C trong mọi ngôn ngữ tôi sử dụng và thực sự trở thành một lập trình viên giỏi.

Bạn nghĩ cách nào là cách tốt nhất để xử lý sự cố này? Cảm ơn rất nhiều.

Answer 1

Như bạn đã suy ra, bạn không thể lưu trữ các tham chiếu trong các vùng chứa STL vì một trong các yêu cầu của các mục được lưu trữ là chúng có thể được gán. Đó là lý do tại sao bạn không thể lưu trữ mảng trong các container STL. Bạn cũng không thể quá tải nhà khai thác mà không có ít nhất một là một loại người dùng định nghĩa, mà làm cho nó xuất hiện mà bạn không thể làm so sánh tùy chỉnh nếu bạn lưu trữ con trỏ trong một lớp STL ...

Tuy nhiên, bạn vẫn có thể sử dụng std::set với con trỏ nếu bạn cho set một comparer functor tùy chỉnh:

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

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

Và bạn vẫn nhận được gỡ bỏ nhanh chóng bởi key như bạn muốn.