從一段代碼引用開始:
std::vector< std::pair<int, std::string> > v1 = ... // v1 is filled with datastd::vector< std::pair<int, std::string> > v2 = ... // v2 is filled with datastd::vector< std::pair<int, std::string> > results;std::sort(v1.begin(), v1.end());std::sort(v2.begin(), v2.end());std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result), compareFirst);我們在兩個排好序的vector v1 和 v2上調用std::set_difference. std::set_difference 把結果寫入 result, std::back_inserter 確保輸出的結果從result 的后面添入. 自定義的compareFirst 作為比較函數提供給std::set_difference
默認地, std::set_difference 通過 std::pair 默認的比較函數來比較里面的元素(比較pair的first和second), 我們自定義了compareFirst, 希望只比較pair的first. compareFirst不是STL的函數, 需要我們自己實現.
std::set_difference 使用的前提是input已經排好序, 倘若我們自定義比較函數C, 而通過C我們能把元素排好序, 那么我們使用這個C代替sort的默認排序也是可以的.
在此例中, 我們使用std::set_difference 只對pair的first進行排序, 盡管它們已經通過”first + second”的方式排序完了.
下面來實現compareFirst. 初版:
實際上, 上面的代碼不會得到我們預期的結果. 為什么? 畢竟std::set_difference 會檢查元素跟另一個容器的元素是否相等(equal), 不是嗎?
為了理解上面的內容, 我們把STL大概地分為兩類: 操作排序元素的 和操作亂序元素的.
Comparing elements
C++中描述”a is the same as b” 有兩種方法
- the natural way: a == b. This is called equality. Equality is based on Operator==.- the other way: a is not smaller than b and b is not smaller than a, so !(a<b) && !(b<a). This is called equivalence. Equivalence is based on operator<.這兩個問題涉及到另一個名詞: equivalence
How is it different from equality?
對于基本類型如int, 甚至實踐中大多數類型, equivalence 和quality 是相通的. 但是正如Scott Meyers 在<< Effective STL>> 一書條目19中指出的, 對于有一些類型, 即使”并非罕見”, equivalence 和 equality 是不同的, 如 大小寫不敏感的string類型.
Why such a far-fetched way to exPRess a simple thing?
當我們使用算法對容器內元素進行排序時, 很容易理解必須有獨一無二的排序方法(如有多種排序方法, 會很笨重, 并可能產生不一致的結果). 所以對于一個特定的容器, 排序時, “==” 和”<” 只能選一個.
對于STL中排序的部分, 我們別無選擇: 排序時必須使用”<”; 而亂序部分, 則沒有這個約束, 我們可以使用”==”.
Implementing the comparator
STL的排序部分使用”==”, 而亂序部分使用”<”. 我們自定義的比較函數也必須遵循這種邏輯.
現在我們可以理解怎么自定義實現std::set_difference 的比較函數compareFirst 了.
原文地址: http://www.fluentcpp.com/2017/02/16/custom-comparison-equality-equivalence-stl/
新聞熱點
疑難解答
