使用重複鍵排序對象

我需要一個由其中一個參數排序的長對象列表。 C++中最快的方法是什麼？我需要能夠添加和刪除元素到這個列表中，並仍然按照這個特定的參數進行排序。使用重複鍵排序對象

Class Foo { 
private: 
    int rank; 
}

我想按升序排列，當一個新的添加或刪除，應該採取正確的點順序上市我所有的Foo對象。也可以有多個對象使用相同的rank，因此鍵值是不可能的。

任何想法如何我可以在C++中做到這一點？我在看make_heap()，但我不確定如何使用它（或者如果它可以使用）與對象。

來源

2012-04-10 networkprofile

使用std ::地圖... – 2012-04-10 22:31:57

或者說的std ::設置 - 除非你需要改變的元素。 – 2012-04-10 22:52:00

雖然地圖需要一個唯一的鍵，但在我的場景中，可能有幾個對象我要排列的對象的參數是相同的 – networkprofile 2012-04-11 00:35:37

首先你應該定義爲operator<Foo（像這樣）......

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

這將需要聲明的Foo的一個朋友：

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

現在您可以創建一個std::multiset<Foo>，這將使Foo s按rank排序，例如

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

來源

2012-04-11 01:46:48 Fraser

這是如何工作的，在將對象添加到多重集之前是否要調用操作符？如果兩個隊伍平等，會發生什麼？謝謝你的幫助！ – networkprofile 2012-04-11 02:05:50

'multiset'使用'std :: less'，它使用'operator <'來確定排序順序。除了根據我的答案定義這些內容外，您無需執行任何操作，而且您可以輕鬆前往。 'multiset'迎合多個元素的鍵，這些元素的鍵是相同的，所以你可以在容器中保留多個具有相同排名的'Foo'。 – Fraser 2012-04-11 02:17:42

還有一個問題：無論多重集中的對象是否有序，性能是否重要？我對模型做了一些修改，我不需要再訂購它們，我只需要使用相同的密鑰快速訪問項目。 – networkprofile 2012-04-11 19:22:53

使用重複鍵排序對象

回答

相關問題