「反向」關聯容器？

在stl或一般情況下是否存在一種「反向」關聯容器？例如我想有一個容器，其中相同的元素由一組鍵共享。「反向」關聯容器？

比方說，我的重點是int，那麼我將不得不例如：

container.at(3) -> some object A 
container.at(4) -> same object A 
container.at(1) -> other object B

這個容器必須（最好）同樣複雜性的std ::地圖爲不同的操作。這樣的事情可能嗎？

我在考慮首先使用std::map<int, T*>其中幾個索引指向同一個對象，但是當從地圖中移除一個項目時，運行時間在O（n）中，因爲您必須檢查另一個項目，看看你是否需要刪除T object

是否有這種容器「本地」在STL或在提升？

編輯：利用的一些例子：

container<int, myClass> myContainer; 
myClass obj(...); //new object 
myContainer.insert(3, obj); //insert object for specific key 
myContainer.insert(2, obj); //insert same object for specific key, since both objects would compare equal we would actually not "insert" a new object but have it shared by both keys 
myContainer.duplicate_object(2,5); //key 5 also has the same object as key 2 (and 3) 
myContainer.getAllKeys(2); //would return 2,3 and 5 since they all reference the same object as key 2 
myContainer.removeKey(3); 
myContainer.removeKey(2); 
myContainer.removeKey(5); //would destroy the object here, not before

來源

2012-09-19 lezebulon

我不明白這個問題。您的標題使用「反向」一詞，而您的問題使用「反向」一詞。無論哪種方式，你的例子仍然沒有澄清你的意思。你能舉一個你如何使用這樣一個容器的例子嗎？假設reverse_container或inverse_container存在，並寫一個main（）方法來說明它是如何工作的。 –

此外，某種計數器可以讓您在O（1）時間內仍然移除。每次添加對象時都會增加計數器，每次刪除時都會減少計數器。當計數達到零時，您可以刪除它。（當然，這可能意味着擴展或包裝std :: map。） –

@ Code-Guru：關於有一個計數器：你仍然需要在某個容器的某個地方存儲這個指針，這個指針被n個鍵使用，指針在地圖中。所以我不明白它是如何可能的O（1）當你不得不減少計數器給定的指針 – lezebulon

你可以使用一個

std::map<int,std::shared_ptr<myclass>>

在C++ 11是標準的一部分。否則，使用Boost庫提供的共享指針。

共享指針的想法是它在內部保持一個引用計數，即它跟蹤指針的一個副本被創建多少次。當您刪除映射條目時，共享指針對象的析構函數將確保計數器遞減。一旦達到零，對象將被刪除。

（編輯:)爲了使答案更完整，有幾個用法示例：

#include <map> 
#include <memory> 

struct myclass 
{ 

}; 


int main() 
{ 
    std::map<int,std::shared_ptr<myclass>> mymap; 

    /* std::make_shared() calls the constructor and creates a shared_ptr: */ 
    std::shared_ptr<myclass> object1 { std::make_shared<myclass>() }; 
    std::shared_ptr<myclass> object2 { std::make_shared<myclass>() }; 
    std::shared_ptr<myclass> object3 { std::make_shared<myclass>() }; 

    mymap[1] = object1; 
    mymap[2] = object2; 
    mymap[3] = object3; 
    mymap[4] = object2; 
    mymap[5] = object1; 

    mymap.erase(2); // erases the (2,object2) entry 
        // therefore, decreases the counter 
        // for object2 
        // but (4,object2) is still intact 

    return 0; 
}

來源

2012-09-19 00:46:59 jogojapan

順便提一句，boost_ptr_map（http://www.boost.org/doc/libs/1_51_0/libs/ptr_container/doc/ptr_map.html）等建議在shared_ptrs的容器上。 –

@RealzSlaw有趣;我對'ptr_map'沒有經驗，但是如果對推薦有一些理由，可能需要發佈一個單獨的答案。感謝您在任何情況下的評論。 – jogojapan

你的答案之間的區別是ONY表現。 AFAIK，它在功能上是等效的。 –

-1

所以，你想要什麼既快速插入和查找就像一個std ::地圖，而且還按價值快速刪除條目的能力。

有沒有這樣做的標準容器。但是，當你想自己寫一個，你可以通過維護兩個內部數據結構做到這一點：

一個std::map將鍵映射到值
第二std::multimap它映射值的集合指向鍵他們

當你想通過值刪除鍵，你可以在第二張地圖中查找它。

來源

2012-09-19 00:47:59 Philipp

你可能想看看Boost.MultiIndex;描述說：

升壓多指標集裝箱庫提供了一個類模板命名的multi_index_container使容器保持與不同的排序和訪問語義一個或多個索引的建設。

來源

2012-09-19 14:21:36

標題使它聽起來像這是他想要的，但他給出的例子使得它聽起來好像他只想將輕量級對象作爲值。 –

「反向」關聯容器？

回答

相關問題