Không thể sử dụng bản đồ stl với struct?

Question

struct Node 
{ 
int a; 
int b; 
}; 

Node node; 
node.a = 2; 
node.b = 3; 

map<int, int> aa; 
aa[1]=1; //O.K. 

map<Node, int> bb; 
bb[node]=1; //Compile Error 

Khi tôi cố gắng ánh xạ một cấu trúc thành int, nó đã cho tôi một lỗi biên dịch. Tại sao? Cảm ơn bạn!

Answer 1

Để có thể sử dụng được làm khóa trong bản đồ, bạn phải có thể so sánh nó bằng cách sử dụng operator<(). Bạn cần thêm toán tử như vậy vào lớp nút của mình:

struct Node 
{ 
int a; 
int b; 

bool operator<(const Node & n) const { 
    return this->a < n.a; // for example 
} 
}; 

Tất nhiên, toán tử thực sự phụ thuộc vào ý nghĩa thực sự so với cấu trúc của bạn.

Answer 2

Bạn có thể vui lòng đăng lỗi trình biên dịch không - Chúng có ý định báo cho bạn, điều gì sai.

Tôi đoán lỗi của bạn xảy ra vì Node không triển khai toán tử so sánh do bản đồ yêu cầu để xác định các phần tử của nó.

Answer 3

Bạn phải thông báo cho std :: map cách so sánh các đối tượng Nút. Theo mặc định, nó cố gắng làm như vậy bằng cách sử dụng toán tử nhỏ hơn. Nhưng bạn không cung cấp bất kỳ toán tử nào thấp hơn cho Node. Giải pháp đơn giản nhất là cung cấp một giải pháp.

chức năng miễn phí ví dụ:

bool operator<(Node const& n1, Node const& n2) 
{ 
    return n1.a<n2.a || (n1.a==n2.a && n1.b<n2.b); 
} 

Lưu ý rằng, đối với bất kỳ cặp nút đối tượng x, y với !(x<y) và !(y<x) bản đồ sẽ coi x và y như bằng nhau (cùng một key).

Answer 4

Bạn cần phải xác định ít hơn điều hành để cho phép so sánh cho loại Node của bạn:

struct Node 
{ 
int a; 
int b; 
}; 

bool operator<(Node const& n1, Node const& n2) 
{ 
    // TODO: Specify condition as you need 
    return ... ; 
} 

Ở đây bạn có thể kiểm tra những gì LessThan Comparable nghĩa cho một loại người dùng định nghĩa.

Giải pháp thay thế là xác định hàm functor dựa trên std::binary_function. Từ quan điểm thiết kế, tùy chọn này có lợi thế bởi vì so sánh được tách ra một cách hiệu quả từ lớp Node. Điều này làm cho nó có thể xác định bản đồ chuyên biệt với điều kiện so sánh khác nhau (functors).

#include <map> 

struct Node 
{ 
int a; 
int b; 
}; 

struct NodeLessThan 
    : public std::binary_function<Node, Node, bool> 
{ 
    bool operator() (Node const& n1, Node const& n2) const 
    { 
     // TODO: your condition 
     return n1.a < n2.a; 
    } 
}; 

int main() 
{ 
    Node node; 
    node.a = 2; 
    node.b = 3; 

    typedef std::map<Node, int, NodeLessThan> node_map_t; 
    node_map_t bb; 
    bb[node] = 1; 
} 

Vì vậy, bạn có thể định nghĩa so sánh hơn chỉ NodeLessThan, ví dụ sử dụng các điều kiện khác nhau hoặc một chỉ so sánh bởi Node::a khác so sánh cả hai thành phần, Node::a và Node::b. Sau đó, xác định các loại bản đồ khác nhau:

typedef std::map<Node, int, NodeLessThan> node_map_t; 
typedef std::map<Node, int, NodeLessThanByA> node_map_a_t; 

Tách lớp này ít xâm phạm hơn (không chạm vào nút Node) và có lợi để đạt được giải pháp mở rộng hơn.

Answer 5

Nếu bạn không thực sự cần phải có dữ liệu của bạn được sắp xếp theo mã, bạn có thể sử dụng unordered_map mới:

#include <unordered_map> 

... 

std::tr1::unordered_map<Node, int> aa; // Doesn't require operator<(Node, Node) 

Bạn sẽ cần một trình biên dịch gần đây cho tiện làm việc.

CẬP NHẬT Vì Neil chỉ ra bạn cần có hàm băm chuyên dụng nếu bạn muốn một khóa unordered_map có Node.

struct NodeHash : std::unary_function<Node, size_t> 
{ 
    size_t operator()(Node const & node) const 
    { 
     return static_cast<size_t>(node.a + 1) * static_cast<size_t>(node.b + 1); 
    } 
}; 

Và sau đó bản đồ trở thành:

std::tr1::unordered_map<Node, int, NodeHash> aa; 

Ngoài ra, như sellibitze nói, một nhà điều hành == là cần thiết để so sánh các phím trong trường hợp va chạm băm:

bool operator==(const Node & lhs, const Node & rhs) 
{ 
    return lhs.a == rhs.a && rhs.b == rhs.b; 
} 

Vì vậy, tôi đoán rằng std :: bản đồ dễ sử dụng hơn nhiều.