Yêu cầu nào cần phải có: lớp khóa bản đồ đáp ứng được các khóa hợp lệ?

Question

Tôi muốn ánh xạ các đối tượng của một lớp nhất định đến các đối tượng khác. Tuy nhiên, lớp tôi muốn sử dụng làm khóa không được viết bởi tôi và đơn giản là struct với một vài giá trị. std :: đơn đặt hàng bản đồ là nội dung, và tôi đã tự hỏi nó như thế nào, và nếu bất kỳ lớp tùy ý nào có thể được sử dụng như một khóa hoặc nếu có một bộ yêu cầu (toán tử và những gì không) cần được xác định.

Nếu có, tôi có thể tạo trình bao bọc cho lớp triển khai bản đồ toán tử sử dụng. Tôi chỉ cần biết những gì tôi cần phải thực hiện đầu tiên, và không có tham chiếu nào cho lớp I found online chỉ định chúng.

Answer 1

Tất cả những gì được yêu cầu của khóa là nó được copiable và chuyển nhượng. Thứ tự trong bản đồ được xác định bởi đối số thứ ba cho mẫu (và đối số cho hàm tạo, nếu được sử dụng). Điều này giá trị mặc định đến std::less<KeyType>, mặc định là toán tử <, nhưng không yêu cầu sử dụng giá trị mặc định. Chỉ cần viết một toán tử so sánh (tốt nhất là một đối tượng chức năng):

struct CmpMyType 
{ 
    bool operator()(MyType const& lhs, MyType const& rhs) const 
    { 
     // ... 
    } 
}; 

Lưu ý rằng nó phải xác định một trật tự nghiêm ngặt, tức là nếu CmpMyType()(a, b ) trả về true, sau đó CmpMyType()(b, a) phải trả về false, và nếu cả hai trở lại sai, các yếu tố được coi là bình đẳng (các thành viên của cùng một lớp tương đương).

Answer 2

Tương tự như đối với set: Lớp học phải có thứ tự nghiêm ngặt theo tinh thần "ít hơn". Hoặc là quá tải operator< thích hợp hoặc cung cấp vị từ tùy chỉnh. Bất kỳ hai đối tượng nào a và b mà !(a<b) && !(b>a) sẽ được xem là bằng nhau.

Vùng chứa bản đồ sẽ thực sự lưu giữ tất cả các phần tử theo thứ tự được cung cấp theo thứ tự đó, đó là cách bạn có thể đạt được thời gian tra cứu và chèn O (log n) theo giá trị khóa.

Answer 3

Câu trả lời thực sự nằm trong liên kết tham chiếu bạn, trong phần mô tả đối số mẫu "So sánh".

Yêu cầu duy nhất là Compare (mặc định là less<Key>, mặc định là sử dụng operator< để so sánh khóa) phải là "thứ tự yếu nghiêm ngặt".

Answer 4

Bạn cần phải xác định các nhà điều hành <, ví dụ như thế này:

struct A 
{ 
    int a; 
    std::string b; 
}; 

// Simple but wrong as it does not provide the strict weak ordering.  
// As A(5,"a") and A(5,"b") would be considered equal using this function. 
bool operator<(const A& l, const A& r) 
{ 
    return (l.a < r.a) && (l.b < r.b); 
} 

// Better brute force. 
bool operator<(const A& l, const A& r) 
{ 
    if (l.a < r.a) return true; 
    if (l.a > r.a) return false; 

    // Otherwise a are equal 
    if (l.b < r.b) return true; 
    if (l.b > r.b) return false; 

    // Otherwise both are equal 
    return false; 
} 

// This can often be seen written as 
bool operator<(const A& l, const A& r) 
{ 
    // This is fine for a small number of members. 
    // But I prefer the brute force approach when you start to get lots of members. 
    return (l.a < r.a) || 
      ((l.a == r.a) && (l.b < r.b)); 
}