聯想/隨機訪問容器

我正在尋找一個數據結構來保存獨特元素的無序集合，這將支持以下操作聯想/隨機訪問容器

插入/在收集任何地方元素的缺失
查詢如果一個元素存在
訪問一個隨機元素

天真，1和2表明使用相聯的容器中，例如unordered_set，但是3的元素數量是線性的。使用隨機存取容器，例如vector，使得3容易，1可以在O（1）中完成，但是2又是O（N）。

的問題是，如果有解決這個線性複雜已知的方式？

編輯：用3中的隨機元素表示：給定N個元素的任意排序，檢索元素編號j其中j介於0和N-1之間。對於std::vector它只是下標，爲std::list或std::set它遞增列表/設置迭代器進行j次從begin()等

來源

2012-05-28 ev-br

std :: set怎麼樣？ – lezebulon

通過哪個鍵訪問隨機元素？如果它是無序的，那麼它不能是索引 - 這意味着std :: set或std :: hash_map或類似。 –

@lezebulon：對於std :: set 3仍然是O（N），不是嗎？ –

我一直在尋找這樣一個數據結構很長一段時間。

最近，我發現它有所有你需要的功能，很有前途庫。

見cntree ::設定在O（log n）的隨機訪問。

這裏是鏈接。 http://dl.dropbox.com/u/8437476/works/countertree/index.html

雖然它似乎在開發中，但我看到它是相當實用的。

來源

2012-06-13 15:08:24 Sungmin

看起來很有趣。這個圖書館的地位如何？ –

其實，我不是說出圖書館確切地位的人。至少我發現每個容器的基本功能都按我的預期工作。我在我的幾個項目中使用過這個庫，並沒有問題。但我不確定它是否足夠穩定。 – Sungmin

在源代碼中，有庫作者的電子郵件。我認爲直接詢問他會更好。 – Sungmin

std::unordered_set開始。如果使用索引j作爲關鍵字，則訪問元素不是O（N），而是O（1）。

你打算使用作爲關聯容器的關鍵還有什麼，如果你有，你要用於查找唯一索引，你不關心否則訂購？

來源

2012-05-28 21:52:40

確實支持'std :: unordered_set'索引？ –

它支持通過鍵訪問，爲什麼不使用你的「索引」作爲關鍵？ –

如果你需要使用別的東西（你沒有提到）作爲關鍵字，並想使用別的東西作爲「索引」，你可以保留一個單獨的'std :: vector :: iterator >'所以你可以索引到vector來獲取元素的迭代器，或者使用'boost :: multi_index'（它可以以同樣的方式使用，但是可以自動管理索引，而不需要單獨保存。） –

對於您的任務而言，最適合您的兩個標準容器是 - 如您所說，vector,1和2.O（n）和3.O（1）和set與1.和2。在O（log n）和3在O（n）中。根據數據結構的大小，算法複雜性並不重要。 A vector具有數據局部性的額外優勢，因此可以更好地利用CPU緩存。

如果元素的實際順序並不重要，在vector插入可以在攤銷O（1）（push_back）和刪除可以攤餘Ø來所做的一切（1）如果你swap元素你想用最後一個元素刪除並刪除它。

如果您確實擁有大數據結構，則可以使用Boost.Multi-Index構建一個數據結構，其中1.是O（n），2.是O（log n），3.是O（1）。但是，就像我說的，如果你的數據結構不是很大，vector應該可以工作。

如果在隨機訪問索引的順序並不重要，插入可以在攤銷O（log n）的（push_back）來完成。對於刪除，您不能使用swap技巧，因爲這會使其他索引無效。

來源

2012-05-28 21:55:46

如何插入和刪除向量中的任何地方分攤O（1）？當然是O（n）。 – juanchopanza

@juanchopanza我錯過了任何地方 - 感謝指出它 –

哦，不，它是O（1），因爲我不必維護順序：可以從最後一個位置交換元素。當然，這對數據局部性不利。 –

具體取決於您的需求＃3 std::unordered_set可能相當合適。

我正在尋找具有上述屬性的容器，以便我可以迭代類似於for(int i = 0; i < myset.size(); ++i) process(myset[i]);的所有元素。我發現this page其描述了std::unordered_set::bucket_count(),std::unordered_set::begin(size_t bucket_number)和std::unordered_set::end(size_t bucket_number)。

，如果你有OpenMP的循環，這就非常方便，所以你可以寫：

std::unordered_set<Element> myset; 

#pragma omp parallel for 
for(int i = 0; i < myset.bucket_count(); ++i) { 
    for(auto it = myset.begin(i); it != myset.end(i); ++it) 
     processElement(*it); 
}

這仍然沒有讓你myset[i]直接訪問，但仍非常接近你可以在編號訪問元素桶。

來源

2016-01-23 10:02:24

聯想/隨機訪問容器

回答

相關問題