중복 키로 개체 정렬

Question

매개 변수 중 하나에 의해 정렬 된 개체의 긴 목록이 필요합니다. C++에서 이렇게하는 가장 빠른 방법은 무엇입니까? 이 목록에 요소를 추가 및 제거하고 해당 매개 변수별로 정렬 할 수 있어야합니다.

Class Foo { 
private: 
    int rank; 
} 

나는 내 모든 Foo 객체가 오름차순으로 새로운 하나를 추가하거나 순서의 정확한 지점을해야 삭제 에 나열하고자합니다. rank과 같은 객체가 둘 이상있을 수 있으므로 키 - 값을 사용할 수 없습니다.

어떻게 C++에서이 작업을 수행 할 수 있습니까? make_heap()을보고 있었지만 객체를 사용하는 방법 (또는 사용할 수있는 경우)을 잘 모르겠습니다.

class Foo { 
public: 
    explicit Foo(int rank_init) : rank(rank_init) {} 
    friend bool operator< (const Foo&, const Foo&); 
private: 
    int rank; 
}; 

:

Answer 1

첫째로 당신은 아마 필요합니다

inline bool operator< (const Foo& lhs, const Foo& rhs) { 
    return lhs.rank < rhs.rank; 
} 

은 Foo 's의 친구로 선언 할 ... (이 같은) Foo에 대한 operator<을 정의해야합니다 이제 Foo을 정렬하여 오름차순으로 rank을 유지하는 std::multiset<Foo>을 만들 수 있습니다.

std::multiset<Foo> foo_multiset; 
foo_multiset.insert(Foo(5)); // 5 
foo_multiset.insert(Foo(3)); // 3, 5 
foo_multiset.insert(Foo(1)); // 1, 3, 5 
foo_multiset.insert(Foo(3)); // 1, 3, 3, 5 
size_t erased_count(foo_multiset.erase(Foo(3))); // 1, 5 (erased_count == 2) 

특별한 경우에 "가장 빠른"옵션이 될 수 있습니다. 그것을 위해 프로파일 링해야합니다. 요소 수, 삽입/삭제 작업 빈도 및 STL 구현에 따라 정렬 된 std::vector<Foo>이 사용자 요구에 더 잘 맞음을 알 수 있습니다.

스콧 마이어스 'Effective STL은이 항목의 경우가 될 수있는 방법을 설명합니다 (23)