根據插入時間從std :: map中刪除元素

我需要根據插入時間（或其他更有效的方式）從std :: map中刪除元素。根據插入時間從std :: map中刪除元素

該地圖可能會包含數千個元素，如果我存儲時間並迭代地圖以檢查每個元素的時間，它可能最終會相當耗時。

有沒有人有任何好主意，當他們變老時如何從std :: map中擦除元素？

來源

2012-03-15 theAlse

你可能想看看boost多索引容器 – PlasmaHH 2012-03-15 14:46:44

舊嗎？你需要一個明確的標準來執行一個動作，除非你定義了一個動作，Q幾乎沒有方向性。 – 2012-03-15 14:47:01

@PlasmaHH耶提高本來不會但不可能在這個項目中使用 – theAlse 2012-03-15 14:56:14

std::map<>類型沒有插入元素的概念。它僅用於保存鍵/值對映射。它也沒有插入順序的概念，所以它甚至不能提供相對的插入類型。

要做你想做的事情，你需要在元素和插入時間之間添加一個關聯。如果你想要的只是相對的順序，那麼你可以使用與地圖配對的std::queue。每當您插入到地圖中時，也會插入std::queue。隊列前面的元素比後面的元素老，您可以使用相對年齡的元素

來源

2012-03-15 14:47:54 JaredPar

您可以使用隊列，並插入指向插入到地圖中的對象的指針。隊列中的下一個項目將是最早的一個。或者，如果您還需要插入時間，則可以將一對存儲在隊列中。

來源

2012-03-15 14:47:27 perreal

迭代器可能比指針更有用，但它們都不會受插入和擦除地圖的影響： http://stackoverflow.com/a/6438087/5987 – 2012-03-15 16:39:42

非常接近LRU Cache。

Boost.MultiIndex庫顯示了MRU Cache（最近使用）的示例，因此將其適配爲LRU應該是微不足道的。

基本上想法是保持兩個並聯的數據結構：

一個map與物品
一個deque與引用到地圖

Basic代碼：

static double const EXPIRY = 3600; // seconds 

std::map<Key, Value> map; 
std::deque<std::pair<std::map<Key, Value>::iterator, time_t>> deque; 

bool insert(Key const& k, Value const& v) { 
    std::pair<std::map<Key, Value>::iterator, bool> result = 
    map.insert(std::make_pair(k, v)); 

    if (result.second) { 
    deque.push_back(std::make_pair(result.first, time())); 
    } 

    return result.second; 
} 

// to be launched periodically 
void clean() { 
    while (not deque.empty() and difftime(time(), deque.front().second) < EXPIRY) { 
    map.erase(deque.front().first); 
    deque.pop_front(); 
    } 
}

當然，那些結構需要b如果意圖獲取多線程代碼，則進行同步。

來源

2012-03-15 15:59:00

非常感謝，我會嘗試一個非常好的IDE。 – theAlse 2012-03-16 12:57:32

根據插入時間從std :: map中刪除元素

回答

相關問題