C 复习之STL（一）—— erase和remove特异行为

quasiceo 2012-11-19

展开全文

C++复习之STL（一）—— erase和remove特异行为

C++的STL通过 iterator将container和algorithm分离，并通过functor提供高可定制性。iterator可以看作是一种契约，algorithm对iterator进行操作，algorithm很难对container进行直接操作，这是因为algorithm对 container所知甚少，一段代码，若未利用操作对象所知全部信息，将难以达到性能之极，并伴随其它种种折中现象。当然，这种“未知性”是必须的—— algorithm对于真正的操作对象container不能做出太多假设，若假设过多，何来一个algorithm可以作用若干不同container 的妙举，STL强大威力也将受损不少。

啰嗦几句，开个小头，转入正题。先给出几个关于STL中erase和remove(remove_if等，下称remove类函数)的事实，小小复习：

erase一般作为一个container的成员函数，是真正删除的元素，是物理上的删除
作为算法部分的remove类函数，是逻辑上的删除，将被删除的元素移动到容器末尾，然后返回新的末尾，此时容器的size不变化
部分容器提供remove类成员函数，那么代表的是真正物理意义上的删除元素
如果该容器是vector、string或者deque，使用erase-remove idiom或者erase-remove_if idiom
如果该容器是list，使用list::remove或者list:remove_if成员函数
如果该容器是一个associative container，使用asso_con::erase成员函数或者remove_copy_if结合swap等方式
有一些比较特殊的容器具现，比如vector<bool>等，暂不考虑。

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

综上一些信息，可以发现，STL提供给我们的“删除”语义并非真正统一，至少未达到最高层次的统一。有时候从一种容器换为另外一种容器，修修改改总少不了。

下面，提供一个统一的接口，来删除一个容器中的元素，原理较简单，使用编译器通过type deduce获知容器的类型，然后通过type traits在编译器就可以决定函数派送决定。比如，编译器知道当前容器是list，那么就会调用list:remove相关的成员函数，性能？inline当然少不了！代码来源是一个STL的教学视频上得之，做了些自以为是的简单修改，当然，我的修改可能让代码“恶”了，自己简单用了些容器做测试，程序行为正确，用了trace工具跟踪代码，足迹符合预期，当然，重在思想的运用，真正的代码使用还需要经过多次严格测试。

  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 idiom
132:         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 idiom
139:         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-function
146:         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-function
153:         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-function
160:         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 that
167:         //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 tree
175:                                     //Must have an iterator to the next element
176:                 else                //of c before call erase
177:                     ++ it;
178:             }
179:         }
180:     }
181: 
182:     //Interface function for erase
183:     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_if
191:     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++，就代表选择了折腾（这不也是种乐趣么！），如果容器内是raw pointer呢，你如果想删除，那还得手动去释放资源，万一又有异常发生，呃……好吧，使用auto_ptrs，可以么？（COAP！当然，也可以冒险使用之，注意auto_ptrs的行为特性）。嗯，使用shared_ptrs，较安全，c++ox或者boost。有时候，不得不用指针，因为我想虚多态动绑定。