std :: map 키 클래스가 유효한 키가되기 위해 필요한 요구 사항은 무엇입니까?

Question

주어진 클래스의 객체를 다른 객체의 객체에 매핑하려고합니다. 그러나 키로 사용하려는 클래스는 저에게 작성된 것이 아니며 값이 약간있는 간단한 struct입니다. std :: map은 내용을 주문하고, 어떻게하는지, 그리고 임의의 클래스를 키로 사용할 수 있는지 또는 정의해야 할 요구 사항 집합 (연산자와 무엇이 아닌가)이 있는지 궁금합니다.

그렇다면 연산자 맵 사용을 구현하는 클래스에 대한 래퍼를 만들 수 있습니다. 먼저 구현해야 할 것이 무엇인지 알 필요가 있고 클래스 found online에 대한 참조가 없습니다.

Answer 1

그것을 복제 가능하고 할당 할 수 있다는 것입니다. 지도 내의 순서는 템플릿의 세 번째 인수 (사용 된 경우 생성자에 대한 인수)로 정의됩니다. 이 기본값은에서 std::less<KeyType>이며 기본값은 < 연산자 이지만 기본값을 사용할 필요는 없습니다. 그냥 (바람직 기능 개체로) 비교 연산자를 쓰기 : 그것은 엄격한 순서를 정의해야합니다 즉 CmpMyType()(a, b ) true를 반환하는 경우, 다음 CmpMyType()(b, a)는 false를 반환해야하며, 경우 모두, 거짓 반납

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

주 요소는 동일한 것으로 간주됩니다 ( 동등한 클래스의 멤버).

Answer 2

와 동일합니다. set과 동일합니다. 클래스는 "보다 작음"의 원칙에 따라 엄격한 순서가 있어야합니다. 적절한 operator<을 오버로드하거나 사용자 정의 조건자를 제공하십시오. 두 개의 객체 a 및 b에 대해 !(a<b) && !(b>a)이 동일한 것으로 간주됩니다.

지도 컨테이너는 실제로 모든 요소를 ​​해당 순서에 따라 제공되는 순서대로 유지하므로 O (log n) 조회 및 삽입 시간을 키 값으로 달성 할 수 있습니다.

Answer 3

답변은 실제로 "비교"템플리트 인수에 대한 설명 아래 연결된 참조 서에 있습니다.

Compare (기본값은 less<Key>이며 기본값은 operator<이며 키를 비교하는 데 사용됨)은 "엄격한 약한 정렬"이어야합니다.

Answer 4

는이 같은 예를 들어, 운영자 <을 정의해야합니다 모든 것을 핵심 요구되는

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)); 
}