std :: list和std :: map的常用算法？

我有一個興趣班（稱之爲X）。
我有一個標準::清單< X * >（稱之爲L）。
我有一個函數（稱之爲F）。根據檢查列表中每個X的內部狀態的算法，F（L）返回L的一個子集（std :: list < X * >）。我要添加到我的應用程序std :: map < int，X * >（稱之爲M），我需要定義F（M）以與F（L）相同的方式運行 - 也就是說，F（M）必須返回std :: list < X * >，通過檢查映射中每個X的內部狀態來確定。std :: list和std :: map的常用算法？

作爲一個自我描述的懶惰程序員，我立即發現算法將[在邏輯上]相同，並且每個數據類型（std :: list和std :: map）都是可迭代的模板。我不想兩次保持相同的算法，但我不知道如何前進。

一個辦法是採取X *的從F（M）（也就是‘從鍵 - 值映射值’），扔進一個std ::名單< X * >，和將處理轉到F（std :: list < X * >），傳遞返回std ::列表< X * >;通過。我看不出這是唯一的方法。

我的問題：我如何在一個地方維護核心算法，但仍保留迭代序列或對聯合容器值的能力？

謝謝！

來源

2009-12-14 Chris Tonkinson

首先，所有，但條件都可以用std::remove_copy_if完成。儘管名稱remove_copy_if不會從原始集合中刪除任何內容。我認爲人們會更容易理解它，如果它被稱爲filtered_copy。它將元素從一個集合複製到另一個集合。對於每個元素，它調用一個謂詞，並且當且僅當該謂詞對該元素返回false時纔會複製項目。

這使得你只有一個責任：以實現測試功能，着眼於每一個X *，並表示它是否應該被排除在外，你正在做的副本。既然你有兩種不同的方式應用邏輯，我會把邏輯封裝在一個類的私有函數中。那麼就可以提供給外部世界作爲類的operator()重載版本的方法有兩種：

class F { 
    bool do_test(X const *x) const { return x.internal_stuff; } 
public: 
    bool operator()(X const *x) const { return do_test(x); } 

    bool operator()(std::pair<int, X const *> const &p) const { 
     return do_test(p.second); 
    } 
};

由於operator()(X const *)是一個純粹的thunk到do_test()，你可能想擺脫它，但IMO那會可能會造成更多的傷害而非好處

無論如何，這會將您的邏輯完全留在一個地方（F::do_test）。它還提供了一個簡單，一致的語法創建的或者是list<X *>過濾副本或std::map<int, X *>：

std::list<X *> result; 
std::remove_copy_if(coll.begin(), coll.end(), std:back_inserter(result), F());

最後一點：std::list可能是最過度使用集合存在。儘管它有其用途，但它們確實非常罕見。 std::vector和std::deque都是非常好經常更好。

來源

2009-12-14 04:46:47

我喜歡這個，因爲函子真的很簡潔。和Mic和Anon一樣的想法。但我覺得最優雅。謝謝！ – 2009-12-14 07:07:43

@Chris - 我同意，我不知道remove_copy_if的行爲就像我自己（奇怪的命名），一定會將它添加到我自己的阿森納:)。 – Mic 2009-12-14 18:57:46

一種解決方案是將算法從兩個函數中移出，並且這些函數只是對它們的容器進行迭代，然後調用算法函數來確定某個特定項是否屬於返回列表中。

來源

2009-12-14 03:25:52

編寫一個接受兩個前向迭代器的函數，因爲它的參數（開始和結束），然後該函數只是測試迭代器的值，如果它通過了測試，將它添加到列表中，並增加迭代器並測試它沒有到達最後（如果是，就中斷）

然後您只需調用該函數並將集合的begin（）和end（）迭代器傳遞給它。

來源

2009-12-14 03:37:56

但std :: list的前向迭代器直接取消引用X *，而std :: map迭代器取消引用std :: pair – 2009-12-14 03:47:49

@Chris True，但有些方法只是遍歷鍵或地圖的值而不是成對的值。見http://stackoverflow.com/questions/1443793/iterate-keys-in-ac-map和http://stackoverflow.com/questions/259240/iterator-adapter-to-iterate-just-the-values-in -a-map – csj 2009-12-14 05:19:40

你可能是正確的，你建議的方法不是唯一的解決方案，但它可能是最容易正確編寫和理解。如果你正在寫產品代碼，我肯定會從那裏開始。對代碼進行簡檔，只有在需要時才能獲得更多發現。

在探索其他選項時，您可以查看boost::bind。當我嘗試做類似的事情時，我收到了this answer。我認爲std::tr1::bind基本上是一樣的，所以如果你沒有升壓，你應該可以替代TR1版本。

來源

2009-12-14 03:46:00

如何像：

template<typename T> 
struct func { 
    std::list<T>& r; 
    func(std::list<T>& r_) : r(r_) {} 

    bool algorithm(const T& t) { 
     return t<5; // obviously meant to be replaced :) 
    } 

    void operator()(const T& t) { 
     if (algorithm(t)) r.push_back(t); 
    } 

    void operator()(const std::pair<int, T>& t) { 
     if (algorithm(t.second)) r.push_back(t.second); 
    } 

}; 

template<typename T, typename ForwardIterator> 
std::list<T> subset(ForwardIterator begin, ForwardIterator end) { 
    std::list<T> r; 
    std::for_each(begin, end, func<T>(r)); 
    return r; 
}

來源

2009-12-14 03:51:04 Mic

std :: list和std :: map的常用算法？

回答

相關問題