C++復(fù)習之STL（一）—— erase和remove特異行為

C++的STL通過iterator將container和algorithm分離，并通過functor提供高可定制性。iterator可以看作是一種契約，algorithm對iterator進行操作，algorithm很難對container進行直接操作，這是因為algorithm對container所知甚少，一段代碼，若未利用操作對象所知全部信息，將難以達到性能之極，并伴隨其它種種折中現(xiàn)象。當然，這種“未知性”是必須的——algorithm對于真正的操作對象container不能做出太多假設(shè)，若假設(shè)過多，何來一個algorithm可以作用若干不同container的妙舉，STL強大威力也將受損不少。

啰嗦幾句，開個小頭，轉(zhuǎn)入正題。 先給出幾個關(guān)于STL中erase和remove(remove_if等，下稱remove類函數(shù))的事實，小小復(fù)習：

1. erase一般作為一個container的成員函數(shù)，是真正刪除的元素，是物理上的刪除
2. 作為算法部分的remove類函數(shù)，是邏輯上的刪除，將被刪除的元素移動到容器末尾，然后返回新的末尾，此時容器的size不變化
3. 部分容器提供remove類成員函數(shù)，那么代表的是真正物理意義上的刪除元素
4. 如果該容器是vector、string或者deque，使用erase-remove idiom或者erase-remove_if idiom
5. 如果該容器是list，使用list::remove或者list:remove_if成員函數(shù)
6. 如果該容器是一個associative container，使用asso_con::erase成員函數(shù)或者remove_copy_if結(jié)合swap等方式
7. 有一些比較特殊的容器具現(xiàn)，比如vector<bool>等，暫不考慮。

更多信息，可以參考《Effective STL》

綜上一些信息，可以發(fā)現(xiàn)，STL提供給我們的“刪除”語義并非真正統(tǒng)一，至少未達到最高層次的統(tǒng)一。有時候從一種容器換為另外一種容器，修修改改總少不了。

下面，提供一個統(tǒng)一的接口，來刪除一個容器中的元素，原理較簡單，使用編譯器通過type deduce獲知容器的類型，然后通過type traits在編譯器就可以決定函數(shù)派送決定。比如，編譯器知道當前容器是list，那么就會調(diào)用list:remove相關(guān)的成員函數(shù)，性能？inline當然少不了！代碼來源是一個STL的教學(xué)視頻上得之，做了些自以為是的簡單修改，當然，我的修改可能讓代碼“惡”了，自己簡單用了些容器做測試，程序行為正確，用了trace工具跟蹤代碼，足跡符合預(yù)期，當然，重在思想的運用，真正的代碼使用還需要經(jīng)過多次嚴格測試。

  1: //  2: //Source code originally from MSDN Channel 9 Video  3: //Modified by techmush  4: //NOTE: the original code may be perfect, the modified version may be buggy!  5: //Modifies: add string container, add some template parameters, alert some name  6: //            add some notes, code style.  7: //  8:   9: #pragma once 10:  11: #ifndef erasecontainer_h__ 12: #define erasecontainer_h__ 13:  14: #include <algorithm> 15: #include <deque> 16: #include <forward_list> 17: #include <list> 18: #include <map> 19: #include <set> 20: #include <vector> 21: #include <string>        //string "as" a vector 22: #include <unordered_map> 23: #include <unordered_set> 24:  25: namespace techmush 26: { 27:     namespace detail  28:     { 29:         //erasing behavior like vector: vector, queue, string 30:         struct vector_like_tag 31:         { 32:         }; 33:  34:         //erasing behavior like list: list, forward_list 35:         struct list_like_tag  36:         { 37:         }; 38:  39:         //erasing behaviod like set: set, map, multiset, multimap, unordered_set, unordered_map 40:         //unordered_multiset, unordered_multimap 41:         struct associative_like_tag  42:         { 43:         }; 44:  45:         //type traits for containers 46:         template <typename Cont> struct container_traits; 47:  48:         template <typename Elem, typename Alloc>  49:         struct container_traits<std::vector<Elem,Alloc> > 50:         { 51:             typedef vector_like_tag container_category; 52:         }; 53:  54:         template <typename Elem, typename Alloc> 55:         struct container_traits<std::deque<Elem,Alloc> > 56:         { 57:             typedef vector_like_tag container_category; 58:         }; 59:  60:         //full specialization traits for string 61:         template <> struct container_traits<std::string>  62:         { 63:             typedef vector_like_tag container_category; 64:         }; 65:  66:  67:         template <typename Elem, typename Alloc> 68:         struct container_traits<std::list<Elem,Alloc> > 69:         { 70:             typedef list_like_tag container_category; 71:         }; 72:  73:         template <typename Elem, typename Alloc> 74:         struct container_traits<std::forward_list<Elem,Alloc> > 75:         { 76:             typedef list_like_tag container_category; 77:         }; 78:  79:         template <typename Key, typename Pred, typename Alloc> 80:         struct container_traits<std::set<Key,Pred,Alloc> > 81:         { 82:             typedef associative_like_tag container_category; 83:              84:         }; 85:  86:         //If a multiset contains duplicates, you can't use erase()  87:         //to remove only the first element of these duplicates. 88:         template <typename Key, typename Pred, typename Alloc> 89:         struct container_traits<std::multiset<Key,Pred,Alloc> > 90:         { 91:             typedef associative_like_tag container_category; 92:         }; 93:  94:         template <typename Key, typename Hash, typename Equal, typename Alloc> 95:         struct container_traits<std::unordered_set<Key,Hash,Equal,Alloc> > 96:         { 97:             typedef associative_like_tag container_category; 98:         }; 99: 100:         template <typename Key, typename Hash, typename Equal, typename Alloc>101:         struct container_traits<std::unordered_multiset<Key,Hash,Equal,Alloc> >102:         {103:             typedef associative_like_tag container_category;104:         };105: 106:         template <typename Key, typename Val, typename Pred, typename Alloc>107:         struct container_traits<std::map<Key,Val,Pred,Alloc> >108:         {109:             typedef associative_like_tag container_category;110:         };111: 112:         template <typename Key, typename Val, typename Pred, typename Alloc>113:         struct container_traits<std::multimap<Key,Val,Pred,Alloc> >114:         {115:             typedef associative_like_tag container_category;116:         };117: 118:         template <typename Key, typename Val, typename Hash, typename Equal, typename Alloc>119:         struct container_traits<std::unordered_map<Key,Val,Hash,Equal,Alloc> >120:         {121:             typedef associative_like_tag container_category;122:         };123: 124:         template <typename Key, typename Val, typename Hash, typename Equal, typename Alloc>125:         struct container_traits<std::unordered_multimap<Key,Val,Hash,Equal,Alloc> >126:         {127:             typedef associative_like_tag container_category;128:         };129:         130: 131:         //for vector-like containers, use the erase-remove idiom132:         template <typename Cont, typename Elem>133:         inline void erase_helper(Cont& c, const Elem& x, vector_like_tag /*ignored*/)134:         {135:             c.erase(std::remove(c.begin(), c.end(), x), c.end());136:         }137: 138:         //for vector-like containers, use the erase-remove_if idiom139:         template <typename Cont, typename Pred>140:         inline void erase_if_helper(Cont& c, Pred p, vector_like_tag)141:         {142:             c.erase(std::remove_if(c.begin(), c.end(), p), c.end());143:         }144: 145:         //for list-like containers, use the remove member-function146:         template <typename Cont, typename Elem>147:         inline void erase_helper(Cont& c, const Elem& x, list_like_tag)148:         {149:             c.remove(x);150:         }151: 152:         //for list-like containers, use the remove_if member-function153:         template <typename Cont, typename Pred>154:         inline void erase_if_helper(Cont& c, Pred p, list_like_tag)155:         {156:             c.remove_if(p);157:         }158: 159:         //for associative containers, use the erase member-function160:         template <typename Cont, typename Elem>161:         inline void erase_helper(Cont& c, const Elem& x, associative_like_tag)162:         {163:             c.erase(x);164:         }165: 166:         //When an element of a container is erased, all iterators that point to that167:         //element are invalidated. Once c.erase(it) reuturns, it has been invalidated. 168:         template <typename Cont, typename Pred>169:         inline void erase_if_helper(Cont& c, Pred p, associative_like_tag)170:         {171:             for (auto it = c.begin(); it != c.end(); /*nothing*/) 172:             {173:                 if (p(*it))174:                     c.erase(it++);    //Rebalance the tree175:                                     //Must have an iterator to the next element176:                 else                //of c before call erase177:                     ++ it;178:             }179:         }180:     }181: 182:     //Interface function for erase183:     template <typename Cont, typename Elem>184:     inline void erase(Cont& c, const Elem& x)185:     {    186:         detail::erase_helper(c, x, typename /*a type*/detail::container_traits<Cont>::container_category());187:     }188: 189: 190:     //Interface function for erase_if191:     template <typename Cont, typename Pred>192:     inline void erase_if(Cont& c, Pred p)193:     {194:         detail::erase_if_helper(c, p, typename detail::container_traits<Cont>::container_category());195:     }196: }197: #endif // erasecontainer_h__

當然，既然選擇了C++，就代表選擇了折騰（這不也是種樂趣么?。?，如果容器內(nèi)是raw pointer呢，你如果想刪除，那還得手動去釋放資源，萬一又有異常發(fā)生，呃……好吧，使用auto_ptrs，可以么？（COAP！當然，也可以冒險使用之，注意auto_ptrs的行為特性）。嗯，使用shared_ptrs，較安全，c++ox或者boost。有時候，不得不用指針，因為我想虛多態(tài)動綁定。