在std :: multiset中維護插入順序相同的元素

我有一個std :: multiset的排序的自定義對象。在多重集中，兩個相同的對象（基於<運算符）可能包含一些不相等的字段。在這種情況下，我需要維持多集中對象的插入順序> <>。在std :: multiset中維護插入順序相同的元素

我知道這不是一個問題，如果我使用C++ 11，但我們不在這一點。

我看到的另一種解決方案是使用<ctime>中的類中的時間戳字段，但分辨率爲1秒。如果我在同一秒有2個插入，那麼我無法在比較操作中使用時間戳。我們不能/不能在這個項目上使用boost :: chrono。

我還有另外一種方法可以確保插入順序得到維護嗎？

2012-11-02 Chinmay Nerurkar

這是有可能使用's.upper_bound」後，立即對所有其他等效項查找插入點。我不知道的是，如果std :: set的實現可能因其他後續操作而重新排序它。 –

這是一個瘋狂的想法：正如@Jerry所建議的，保持一個計數器。由於對象和計數器對是唯一的，我們現在可以使用一組（按照字典順序排列）。然後我們使用lower_bound查找插入點和計算下一個計數器值：

unsigned int const uimax = std::numeric_limits<unsigned int>::max(); 

typedef std::set<std::pair<T, unsigned int>> pair_set; 

void counted_insert(pair_set & s, T const & t) 
{ 
    pair_set::iterator it = s.lower_bound(std::make_pair(t, uimax)); 

    if (it == s.begin() || !(*--it == t)) 
    { 
     s.insert(it, std::make_pair(t, 0)); 
    } 
    else 
    { 
     s.insert(it, std::make_pair(t, it->first + 1)); 
    } 
}

來源

2012-11-02 20:32:01

兩件事。 1）你的意思是'it == s.end（）'和2）你應該使用等價性，而不是相等的比較。其實，經過第二次考慮，我不認爲lower_bound會在這種情況下返回你想要的。 lower_bound返回不小於請求元素的第一個元素。由於（t，0）小於（t，uimax），它只會在第一次插入，之後失敗。 –

@DaveS：你說得對，我超前了。我認爲現在好多了。 –

我只是使用一個計數器，每當您插入一個新項目時就會增加一個計數器，並將其作爲最後一個字段進行比較。在典型情況下，您需要讓計數器成爲管理集合的類的靜態成員。

來源

2012-11-02 20:15:32

事實上，計數器可以從多重集中的最後一個值（或在這種情況下設置）中計算出來...... –

@KerrekSB：如果您有組合鍵，則不能保證最後一個值具有最大計數器。 – aschepler

在std :: multiset中維護插入順序相同的元素

回答

相關問題