標準庫算法是否允許複製謂詞參數？

假設我們想從一個向量int s中刪除重複的值。通常的解決方案是對矢量進行排序並使用擦除刪除方式擦除重複項。但是我們需要維護不會被刪除的元素的順序，所以我們無法排序。所以有人會想出這樣的斷言，並使用與remove_if算法：標準庫算法是否允許複製謂詞參數？

struct comp { 
    std::set<int> s; 
    comp() : s() {} 
    bool operator()(int i) 
    { 
     return !(s.insert(i)).second; 
    } 
};

但是，這將打破，如果謂詞對象將被複製出於某種原因，因爲我們將得到set成員的兩個副本。事實上，海灣合作委員會的執行remove_if正是這麼做的：

template<typename _ForwardIterator, typename _Predicate> 
    _ForwardIterator 
    remove_if(_ForwardIterator __first, _ForwardIterator __last, 
      _Predicate __pred) 
    { 

     __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred); 

     if(__first == __last)        // ^^^^^ here a copy is made 
     return __first; 
     _ForwardIterator __result = __first; 
     ++__first; 
     for(; __first != __last; ++__first) 
     if(!bool(__pred(*__first))) 
      { 
      *__result = _GLIBCXX_MOVE(*__first); 
      ++__result; 
      } 
     return __result; 
    }

的解決辦法是讓我們的仿函數靜態的set成員：

struct comp { 
    static set<int> s; 
    comp() { s. clear(); } 
    bool operator()(int i) 
    { 
     return !(s.insert(i)).second; 
    } 
}; 
set<int> comp::s;

但問題依然存在：

難道我們需要確保謂詞仿函數的可能副本不會破壞我們的邏輯？ 標準中是否有任何規定（或禁止）關於此問題的某些行爲？或者它是實施中的錯誤？

來源

2012-06-17 jrok

是的，標準沒有指定謂詞將被複制的次數，也沒有說明謂詞將以什麼順序應用於容器的元素。基本上，謂詞必須像pure functions一樣行事;他們必須沒有可觀察到的狀態。因此remove_if聽起來不像這裏適當的算法。諸如將set外部存儲到仿函數的竅門將不能解決問題;你仍然會調用未定義的行爲。

_{1.對於更深入的討論，請參見第39項（「製作謂詞純函數」）的斯科特邁爾斯Effective STL。}

來源

2012-06-17 13:34:38

+1關於純功能和良好參考的好處。 – juanchopanza

有標準指定順序的算法。像'std :: copy'，不是？標準中的「備註：穩定」是什麼意思，是不是要求訂單得到保留？ – jrok

@jrok：只有在保留元素的相對順序不會改變的意義上，它纔是穩定的，而不是OP所希望的。（並且'copy'不帶謂詞，'copy_if'不帶謂詞，'copy_if'只帶一個，但沒有指定它的應用順序。） –

是的，他們被允許複製參數不確定的次數。比使靜態成員集更好的方法是在函數外創建集並將其作爲構造函數參數傳遞。內部存儲一個指針。

來源

2012-06-17 13:24:49

我相信這樣的結果仍然沒有明確定義;該標準沒有強制命令'remove_if'必須將謂詞應用於容器元素。 –

@OliCharlesworth：true，但是，由於標準指定它適用於Forward Iterator，所以大多數實現將實際應用它以便出於效率原因。有時候我想知道標準是否應該明確要求這個標準，標準的問題不能保證通常提出的是人們最終依賴（通常沒有意識到）依賴於實現依賴的保證。 –

@OliCharlesworth：除了什麼馬修已經提到的，該結果被存儲在一個'OutputIterator'（即它不能走回頭路）和謂詞的執行次數恰好是容器的大小更重要。除了測試每個元素的前向循環以及決定是否複製之外，以任何其他方式執行都是不可能的。 –

我們是否需要確保謂詞仿函數的可能副本不會破壞我們的邏輯？

是的，你應該假設謂詞被複制。在C++ 11中，您可以考慮使用std::ref or std::cref。

~~另一種方法是修改 comp結構參照採取 set：~~

struct comp { 
    std::set<int>& s; 
    comp(std::set<int> s) : s(s) {} 
    bool operator()(int i) 
    { 
     return !(s.insert(i)).second; 
    } 
};

注意：我沒有做出是否這將與remove_if工作的任何聲明，我只是解決包含不應複製的狀態的複製謂詞問題。

編輯正如在評論中指出的那樣，這種方法從根本上被打破了。謂詞調用的結果不應該依賴於可變狀態。

來源

2012-06-17 13:25:27 juanchopanza

我相信這個結果還沒有明確定義;該標準沒有強制命令'remove_if'必須將謂詞應用於容器元素。 –

@OliCharlesworth我甚至沒有考慮'remove_if'，只是處理複製的謂詞問題。我會澄清我的答案。 – juanchopanza

這是同一問題的一部分。謂詞必須表現爲[純函數]（http://en.wikipedia.org/wiki/Pure_function）。 –

標準庫算法是否允許複製謂詞參數？

回答

相關問題