colorful

今天看書剛剛看的，就記錄下來吧。這可能是老生常談了，權且作為一個警醒的例子吧。

大家都知道STL有兩個非常重要的組成部分，容器和算法。

算法就是一個個的函數，通過迭代器和容器關聯在一起，完成一些工作。

算法和容器的分離為程序設計提供了很大的靈活性，但是也帶來了一些負面效果，下面我講的這個問題就是一個例子。

STL的算法里有一個remove函數，而list自身也有一個remove函數，功能都是一樣的，移除某一個元素，那我們應該使用哪一個呢？

看一下下面這段程序

 1     list<int> numbers;  2   3     for ( int number = 0; number <= 6; number ++ ) {  4         numbers.push_front(number);  5         numbers.push_back(number);  6     }  7   8     copy(numbers.begin(), numbers.end(),  9             ostream_iterator<int>(cout, " ")); 10     cout << endl; 11  12     // remove algorithm will remove element but not erase the element from container 13     // it will return the logical desination of container 14     list<int>::iterator endOfNumbers = remove(numbers.begin(), numbers.end(), 3); 15  16     copy(numbers.begin(), numbers.end(), 17             ostream_iterator<int>(cout, " ")); 18     cout << endl;

輸出是什么呢？

第一行肯定是6 5 4 3 2 1 0 0 1 2 3 4 5 6，那么第二行會輸出什么？

如果是沒有仔細看過STL的人肯定會認為remove(number.begin(), numbers.end(), 3)會移除所有值為3的元素。所以輸出是：6 5 4 2 1 0 0 1 2 4 5 6。

但是，我們看一下它真正的輸出：

6 5 4 2 1 0 0 1 2 4 5 6 5 6

你可能會非常驚訝，為什么最后會多出5和6兩個數呢？

我們來講一下remove算法的原理。

remove算法工作時并不是直接把元素刪除，而是用后面的元素替代前面的元素，也即是說如果我對1234這個序列remove 2，返回的序列是 1344（3被復制到2的位置，4被復制到3的位置）。

這樣上面的例子就好解釋了，那兩個3的元素并沒有被移除，而是用后面的元素覆蓋了前面的元素。多出的那兩個數沒有被移除掉而已。

那么我們應該如何真正完成移除呢？remove函數會返回一個迭代器，那個迭代器是這個序列的邏輯終點，也即是我代碼里的endOfNumbers，它指向倒數第二個5上。

于是我們要利用list的erase函數完成元素移除

numbers.erase(endOfNumbers, numbers.end());

這樣我們就完成了我們的工作，稍稍有點曲折……

其實我們可以把這兩步放在一起，比如如果我想接著移除所有值為2的元素

numbers.erase(remove(numbers.begin(), numbers.end(), 2), numbers.end());

這樣我們就可以一步到位了。

但是這樣好么？

不好。

大家會發現，remove函數的原理是復制而不是指針的移動（因為函數操縱的是迭代器，而C++的迭代器沒有定義刪除操作），這樣會帶來一個問題：我們使用list是因為它的修改的效率非常高，改變一下指針就可以了。而這里我們復制了元素，如果在vector中，可能還是高效的，因為vector無論如何都要復制，而對于list就不是如此了，會極度降低我們的效率。

那我們怎么辦呢？

答案是使用list自己的remove函數

numbers.remove(1);

我們可以這樣刪除所有值為1的元素。

也即是說，如果要刪除list中的元素，我們應該使用list的remove成員函數，而不是remove算法！

小結

我們都知道，STL是一個效率、復用性、靈活性折衷的產物，其中效率至關重要，所以STL已經禁止了一些效率低的操作（比如list的隨機訪問），而鼓勵你去使用其它的容器。

但是，在算法中，為了靈活性，STL還是會犧牲一些東西，比如我們這個例子。

個人覺得，STL作為C++標準庫的一個組成部分，特點和C++本身一模一樣，強大而復雜，有些地方難以理解，很多細節需要學習注意，我們要學會避免陷入某些陷阱之中，比如這個例子就是一個效率陷阱。

其它更多的陷阱是錯誤處理方面的，STL本身并沒有規定過多的錯誤處理，大部分的錯誤處理都交給了我們，理由很簡單：性能至上，如果一個東西自身沒有錯誤檢查，我們可以包裝一個帶錯誤檢查的類；但是如果這個東西自身就帶了錯誤檢查，那么我們就沒有任何方法提升它的效率了。這也是很多C和C++庫的設計原則。

所以，很多時候，需要我們深入細節，然后再決定到底怎么做。因為C++就是如此：有很多路可以走，需要我們自己選擇最好的一條路。