?
?
有些容器擁有和 STL 算法同名的成員函數。
關聯容器提供了 count、find、lower_bound、upper_bound 和 euqal_range
list 提供了 remove、remove_if、unique、merge 和 reverse
?
大多數時候應該用成員函數代替手寫算法,這樣做的兩個理由:
比起算法,它們與容器結合的更好(尤其是關聯容器)
同名的算法很成員函數通常不是一樣的
?
假設 set<int> 容納一百萬個元素,想找到元素 727 的第一次出現的位置
1 set<int> s; 2 . . . 3 set<int>::iterator i = s.find(727); // 使用成員函數 4 if( i != s.end() ) . . . 5 set<int>::iterator i = find( s.begin(), s.end(), 727 ); // 使用 find 算法 6 if( i != s.end()) . . .
使用成員函數花費對數時間(set實現為紅黑樹),使用算法將花費線性時間
?
STL 算法判斷兩個對象是否相同的方法檢查的是它們是否相等,而關聯容器是用等價來測試它們的 “同一性”
?
對于標準關聯容器,選擇成員函數而不是同名算法幾個好處,首先,得到對數時間而不是線行時間的性能。其次,判斷連個元素 “相同”使用的是等價,這是關聯容器的默認定義。第三,當操縱 map 和 multimap 時,可以自動地只處理 key 值而不是(key, value)對。
?
list 的成員函數。每個被 list 作了特化的算法(remove、remove_if、unique、sort、merge 和 reverse)都要拷貝對象,而 list 的特別版本什么都沒有拷貝;它們只是簡單地操縱連接 list 的節點的指針。算法和成員函數的算法復雜度是相同的。
另外,list 的成員函數的行為和它們的同名算法的行為經常是不相同。如果真想從容器中清除對象,調用 remove、remove_if 和 unique 算法后,必須接著調用 erase 函數;但是,list 的 remove、remove_if 和 unique 成員函數真的去掉了元素,后面不再需要接著調用 erase
在 sort 算法和 list 的成員函數間的一個重要的區別是前者不能用于 list。作為單純的雙向迭代器, list 的迭代器不能傳給 sort 算法。merge 算法和 list 的merge 成員函數之間也同樣存在巨大差異
?