C++的std ::設置自定義比較

嗯，我的問題是，我使用的std ::使用自定義設置比較，像：C++的std ::設置自定義比較

class A 
{ 
public: 
    A(int x, int y): 
     _x(x), _y(y) 
    { 
    } 

    int hashCode(){ return (_y << 16) | _x; } 

private: 
    short int _y; 
    short int _x; 
}; 

struct comp 
{ 
    bool operator() (A* g1, A* g2) const 
    { 
     return g1->hashCode() < g2->hashCode(); 
    } 
};

所以，我用它像

std::set<A*, comp> myset; 

// Insert some data 
A* a = new A(2,1); 
A* b = new A(1,3); 
myset.insert(a); 
myset.insert(b);

現在我的問題是，我想這樣做：

myset.find((2 << 16) | 1);

但是，當然，它節選A *不是短整型。

所以，我知道我可以使用std :: find_if，但不會渲染無用的自定義比較器？它會遍歷整個列表，不是嗎？有沒有什麼辦法可以使用hashCode而不是對象本身來查找？

謝謝！

來源

2013-05-02 Guillem

如何使用std :: find_if與比較器（調整爲相等）？ – stardust 2013-05-02 12:03:16

對不起，這就是我寫'std :: find'時的意思，應該是'std :: find_if'。它不會迭代整個列表，並且根本不優化搜索嗎？我使用'std :: set'的原因是它的O（log（n））搜索成本。 – Guillem 2013-05-02 12:05:27

set::find需要參數類型key_type（參見討論Why is set::find not a template?）。使用std :: set你必須構造一個臨時對象來使用find。

myset.find(A(2, 1));

如果A不便宜構建你可能想使用一個std::map<int, A>（或圍繞它的包裝）來代替。

來源

2013-05-02 12:04:15 hansmaad

A確實不便宜。如果我要使用地圖，最好是使用「map」還是「unordered_map」。我目前使用'google :: dense_hash_map'來爲其他一些帶有int鍵的地圖。插入成本根本不重要，搜索成本是。 – Guillem 2013-05-02 12:09:30

@ProStage如果排序無關緊要，應該使用'unordered_map'或'unordered_set'。 – hansmaad 2013-05-02 12:10:49

@ProStage你展示的'A'非常便宜。 – 2013-05-02 12:13:25

你不能這樣做std::set，因爲std::set<>::find是不是（成員）模板;爭論必須是關鍵類型。對於像您這樣的簡單類，很可能使用 std::vector<A>並對其進行排序（使用std::lower_bound 進行查找並作爲插入點）將會同樣快。並與std::lower_bound，你可以通過比較，和使用任何你想要的類型作爲關鍵。所有你所要做的就是確保您comp類能夠處理混合型比較，如：

struct Comp 
{ 
    bool operator()(A const&, B const&) const; 
    bool operator()(A const&, int) const; 
    bool operator()(int, A const&) const; 
};

來源

2013-05-02 12:11:04

事情是類不是那麼簡單。它實際上擁有一張可以增長到1000個元素的地圖。 'A'對象的數量也可以增長到1000+，它們都是唯一的。搜索時間/成本很重要，矢量不會是一個選項。另外，插入/擦除時會出現線程問題，因爲所有迭代器都會失效。 – Guillem 2013-05-02 12:13:46

@ProStage然後你必須找到解決辦法。一個'std :: shared_ptr'的向量可能會訣竅;或者，你也可以嘗試實現一個「虛擬」版本的'A'，這個版本並不昂貴，並且可以用作'std :: set'的一個鍵。（沒有條目的'map'並不是昂貴的構建，或者只是將實現或至少其昂貴的部分移動到委託中;然後可以將具有指向委託的空指針的實例創建爲索引，並且如果代理使用智能指針進行管理，複製可能會非常便宜。） – 2013-05-02 13:20:55

myset.find(&A(2, 1));

或者

A a(2, 1); 
myset.find(&a);

來源

2013-05-02 12:11:08

第一個不是合法的C++。 – 2013-05-02 12:11:52

取決於編譯器，但是，這是一種糟糕的風格... – 2013-05-02 15:29:05

它不依賴於編譯器。該標準明確禁止它（除非類'A'已被覆蓋'運算符&');是一個編譯器接受它（當作爲C++編譯器調用時），它被打破了（如果編譯器接受它，我實際上會感到很驚訝。畢竟，從C最早的日子開始計算。但是，在一些編譯器接受這些事情之前，我感到很驚訝。） – 2013-05-02 15:35:19

您已經定義了一個std::set<A*, comp> myset;，所以std::find()必須採取A*的說法。

std::set<A*, comp> myset; 

// Insert some data 
A* a = new A(2,1); 
A* b = new A(1,3); 
myset.insert(a); 
myset.insert(b);

然後，你需要做的

myset.find(&A(2,1))

回到你的問題，std::find()不考慮您的自定義比較。實際上，您需要使用std::find_if。

來源

2013-05-02 15:46:05 octoback

C++的std ::設置自定義比較

回答

相關問題