STL集合::發現重新定義搜索

我的計劃是根據各地對的集合，即STL集合::發現重新定義搜索

typedef std::pair<int,int> innerPair; 
typedef std::pair<innerPair,int> setElement; 
std::set<setElement> Foo;

的innerPair元素是真正定義setElement，但我需要一組ID附加到每一個元素，因此後者定義爲setElement。

在程序的其餘部分，我需要找到innerPair無論其組ID，所以我基本上需要一個功能

std::set<setElement>::iterator find(innePair);

會找到innerPair不管其組ID。就目前而言，我可以簡單地遍歷所有可用的組ID，並執行多個find（）調用，但效率不高。

有定義執行某種通配符搜索，或者我需要用我自己的定義重載它find(...)成員函數的一個簡潔的方式？

來源

2012-11-25 jgyou

你是說'innerPair'是關鍵，並且組ID是值？如果是這樣，爲什麼不使用「地圖」？ – Mehrdad

看起來你實際上想要'std :: map '。 –

您是否在尋找特定的innerpair，或者您是否在尋找具有給定組ID的所有innerPairs？ – didierc

如果您有多個具有相同內部對和不同組ID的元素，則可以使用std::multimap<innerPair, int>。

這允許您存儲具有相同innerPair的多個元素。

它還簡化了與lower_bound/upper_bound或equal_range的搜索。

來源

2012-11-25 22:05:57

如果你想繼續使用std::set那麼你可以使用std::find_if自定義謂詞，看看這個answer。

基本上你將定義一個函數

bool pairCorresponds(std::pair<int,int> element)

，將做的工作適合你。

來源

2012-11-25 21:57:50 Jack

注意時間複雜性。 – Mehrdad

這將運行在線性時間，而不是對數。 –

我看到兩種可能的設計。一個可能比另一個更適用。

爲innerPair爲與3個成員（第一，第二，和組ID）或std::tuple<int, int, int>一個結構可能是更合適的。 innerPair對象的組ID是否是部分？如果是這樣，那麼我建議這是更好的設計。

如果不是（說實話，我認爲在你的情況下不是），你應該使用std::map<innerPair,int>創建一個從innerPair對象到組ID的映射。然後你可以很容易地找到一個元素：

std::map<innerPair,int> mapping; 
// Fill your map 
innerPair key = {1, 2}; 
auto found_iter = mapping.find(key);

您還可以獲得組ID特定innerPair有：

int group_id = mapping[key];

你並不需要提供一個自定義的比較，因爲operator<已經定義爲std::pair。

來源

2012-11-25 21:58:45

組ID不是對象本身的一部分。地圖容器提供了許多有趣的功能，我肯定會選擇這個設計，而不是結構或元組！ – jgyou

如果要通過部分對象進行搜索，你可能是最好關閉不使用std::set<...>而是std::map<...>：

std::map<std::pair<int, int>, int>

這幾乎是值類型您std::set<...>針對性反正（區別在於first成員被宣佈爲const）。

如果你真的堅持使用std::set<...>，你需要創建一個比較器類型，忽略最後的second成員。我不確定std::set<...>是否支持混合類型比較（我想認爲它不）。

來源

2012-11-25 21:59:15

只要它提供了一個嚴格的弱順序，你可以通過'innerPair'命令整個集合，並在所有情況下忽略組標識。 –

感謝您給我啓發這種類型的容器！我對C++的瞭解仍然非常有限，因爲我不是CS學生，而是需要編寫大量代碼的物理學學生。地圖真的是我需要的。 – jgyou

你可以使用一個multiset，使用自定義比較函數，或仿函數，例如：

struct innerPairCompare 
{ 
    bool operator() (const setElement &a, const setElement &b) 
    { 
     const innerPair &a_ = a.first; 
     const innerPair &b_ = b.first; 
     return (a_.first > b_.first || a_.first = b_.first && a_.second > b_.second); 
    } 

};

然後用它爲您的multiset：

std::multiset<setElement,innerPairCompare> Foo;

它將所有setElement 4S店與在同一個列表中同樣的innerPair。

或者，如果你需要的所有innerPair與給定GroupID，使用上比較組ID的功能。

最後，如果你真的不需要保持GroupID和innerPair在一起，你可以使用map（或multimap），使用GroupID或innerPair作爲Key。

來源

2012-11-25 22:16:02 didierc

STL集合::發現重新定義搜索

回答

相關問題