1 // (C) Copyright Jeremy Siek 2004
2 // Distributed under the Boost Software License, Version 1.0. (See
3 // accompanying file LICENSE_1_0.txt or copy at
4 // http://www.boost.org/LICENSE_1_0.txt)
6 #ifndef BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H
7 #define BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H
9 // Sure would be nice to be able to forward declare these
10 // instead of pulling in all the headers. Too bad that
11 // is not legal. There ought to be a standard <stlfwd> header. -JGS
13 #include <boost/next_prior.hpp>
15 #include <algorithm> // for std::remove
21 #if !defined BOOST_NO_HASH
22 # ifdef BOOST_HASH_SET_HEADER
23 # include BOOST_HASH_SET_HEADER
27 # ifdef BOOST_HASH_MAP_HEADER
28 # include BOOST_HASH_MAP_HEADER
34 #if !defined BOOST_NO_SLIST
35 # ifdef BOOST_SLIST_HEADER
36 # include BOOST_SLIST_HEADER
42 // The content of this file is in 'graph_detail' because otherwise
43 // there will be name clashes with
44 // sandbox/boost/sequence_algo/container_traits.hpp
45 // The 'detail' subnamespace will still cause problems.
46 namespace boost { namespace graph_detail {
48 //======================================================================
49 // Container Category Tags
51 // They use virtual inheritance because there are lots of
52 // inheritance diamonds.
54 struct container_tag { };
55 struct forward_container_tag : virtual public container_tag { };
56 struct reversible_container_tag : virtual public forward_container_tag { };
57 struct random_access_container_tag
58 : virtual public reversible_container_tag { };
60 struct sequence_tag : virtual public forward_container_tag { };
62 struct associative_container_tag : virtual public forward_container_tag { };
64 struct sorted_associative_container_tag
65 : virtual public associative_container_tag,
66 virtual public reversible_container_tag { };
68 struct front_insertion_sequence_tag : virtual public sequence_tag { };
69 struct back_insertion_sequence_tag : virtual public sequence_tag { };
71 struct unique_associative_container_tag
72 : virtual public associative_container_tag { };
73 struct multiple_associative_container_tag
74 : virtual public associative_container_tag { };
75 struct simple_associative_container_tag
76 : virtual public associative_container_tag { };
77 struct pair_associative_container_tag
78 : virtual public associative_container_tag { };
81 //======================================================================
82 // Iterator Stability Tags
84 // Do mutating operations such as insert/erase/resize invalidate all
85 // outstanding iterators?
87 struct stable_tag { };
88 struct unstable_tag { };
90 //======================================================================
91 // Container Traits Class and container_category() function
93 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
94 // don't use this unless there is partial specialization
95 template <class Container>
96 struct container_traits {
97 typedef typename Container::category category;
98 typedef typename Container::iterator_stability iterator_stability;
102 // Use this as a compile-time assertion that X is stable
103 inline void require_stable(stable_tag) { }
107 virtual public random_access_container_tag,
108 virtual public back_insertion_sequence_tag { };
110 template <class T, class Alloc>
111 vector_tag container_category(const std::vector<T,Alloc>&)
112 { return vector_tag(); }
114 template <class T, class Alloc>
115 unstable_tag iterator_stability(const std::vector<T,Alloc>&)
116 { return unstable_tag(); }
118 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
119 template <class T, class Alloc>
120 struct container_traits< std::vector<T,Alloc> > {
121 typedef vector_tag category;
122 typedef unstable_tag iterator_stability;
128 virtual public reversible_container_tag,
129 virtual public back_insertion_sequence_tag
130 // this causes problems for push_dispatch...
131 // virtual public front_insertion_sequence_tag
134 template <class T, class Alloc>
135 list_tag container_category(const std::list<T,Alloc>&)
136 { return list_tag(); }
138 template <class T, class Alloc>
139 stable_tag iterator_stability(const std::list<T,Alloc>&)
140 { return stable_tag(); }
142 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
143 template <class T, class Alloc>
144 struct container_traits< std::list<T,Alloc> > {
145 typedef list_tag category;
146 typedef stable_tag iterator_stability;
152 #ifndef BOOST_NO_SLIST
153 # ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
154 template <class T, class Alloc>
155 struct container_traits<BOOST_STD_EXTENSION_NAMESPACE::slist<T,Alloc> > {
156 typedef front_insertion_sequence_tag category;
157 typedef stable_tag iterator_stability;
160 template <class T, class Alloc>
161 front_insertion_sequence_tag container_category(
162 const BOOST_STD_EXTENSION_NAMESPACE::slist<T,Alloc>&
164 { return front_insertion_sequence_tag(); }
166 template <class T, class Alloc>
167 stable_tag iterator_stability(
168 const BOOST_STD_EXTENSION_NAMESPACE::slist<T,Alloc>&)
169 { return stable_tag(); }
175 virtual public sorted_associative_container_tag,
176 virtual public simple_associative_container_tag,
177 virtual public unique_associative_container_tag
180 template <class Key, class Cmp, class Alloc>
181 set_tag container_category(const std::set<Key,Cmp,Alloc>&)
182 { return set_tag(); }
184 template <class Key, class Cmp, class Alloc>
185 stable_tag iterator_stability(const std::set<Key,Cmp,Alloc>&)
186 { return stable_tag(); }
188 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
189 template <class Key, class Cmp, class Alloc>
190 struct container_traits< std::set<Key,Cmp,Alloc> > {
191 typedef set_tag category;
192 typedef stable_tag iterator_stability;
197 struct multiset_tag :
198 virtual public sorted_associative_container_tag,
199 virtual public simple_associative_container_tag,
200 virtual public multiple_associative_container_tag
203 template <class Key, class Cmp, class Alloc>
204 multiset_tag container_category(const std::multiset<Key,Cmp,Alloc>&)
205 { return multiset_tag(); }
207 template <class Key, class Cmp, class Alloc>
208 stable_tag iterator_stability(const std::multiset<Key,Cmp,Alloc>&)
209 { return stable_tag(); }
211 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
212 template <class Key, class Cmp, class Alloc>
213 struct container_traits< std::multiset<Key,Cmp,Alloc> > {
214 typedef multiset_tag category;
215 typedef stable_tag iterator_stability;
223 virtual public sorted_associative_container_tag,
224 virtual public pair_associative_container_tag,
225 virtual public unique_associative_container_tag
228 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
229 template <class Key, class T, class Cmp, class Alloc>
230 struct container_traits< std::map<Key,T,Cmp,Alloc> > {
231 typedef map_tag category;
232 typedef stable_tag iterator_stability;
236 template <class Key, class T, class Cmp, class Alloc>
237 map_tag container_category(const std::map<Key,T,Cmp,Alloc>&)
238 { return map_tag(); }
240 template <class Key, class T, class Cmp, class Alloc>
241 stable_tag iterator_stability(const std::map<Key,T,Cmp,Alloc>&)
242 { return stable_tag(); }
245 struct multimap_tag :
246 virtual public sorted_associative_container_tag,
247 virtual public pair_associative_container_tag,
248 virtual public multiple_associative_container_tag
251 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
252 template <class Key, class T, class Cmp, class Alloc>
253 struct container_traits< std::multimap<Key,T,Cmp,Alloc> > {
254 typedef multimap_tag category;
255 typedef stable_tag iterator_stability;
259 template <class Key, class T, class Cmp, class Alloc>
260 multimap_tag container_category(const std::multimap<Key,T,Cmp,Alloc>&)
261 { return multimap_tag(); }
263 template <class Key, class T, class Cmp, class Alloc>
264 stable_tag iterator_stability(const std::multimap<Key,T,Cmp,Alloc>&)
265 { return stable_tag(); }
268 // hash_set, hash_map
270 #ifndef BOOST_NO_HASH
271 #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
272 template <class Key, class Eq, class Hash, class Alloc>
273 struct container_traits< BOOST_STD_EXTENSION_NAMESPACE::hash_set<Key,Eq,Hash,Alloc> > {
274 typedef set_tag category;
275 typedef stable_tag iterator_stability; // is this right?
277 template <class Key, class T, class Eq, class Hash, class Alloc>
278 struct container_traits< BOOST_STD_EXTENSION_NAMESPACE::hash_map<Key,T,Eq,Hash,Alloc> > {
279 typedef map_tag category;
280 typedef stable_tag iterator_stability; // is this right?
283 template <class Key, class Eq, class Hash, class Alloc>
284 set_tag container_category(const BOOST_STD_EXTENSION_NAMESPACE::hash_set<Key,Eq,Hash,Alloc>&)
285 { return set_tag(); }
287 template <class Key, class T, class Eq, class Hash, class Alloc>
288 map_tag container_category(const BOOST_STD_EXTENSION_NAMESPACE::hash_map<Key,T,Eq,Hash,Alloc>&)
289 { return map_tag(); }
291 template <class Key, class Eq, class Hash, class Alloc>
292 stable_tag iterator_stability(const BOOST_STD_EXTENSION_NAMESPACE::hash_set<Key,Eq,Hash,Alloc>&)
293 { return stable_tag(); }
295 template <class Key, class T, class Eq, class Hash, class Alloc>
296 stable_tag iterator_stability(const BOOST_STD_EXTENSION_NAMESPACE::hash_map<Key,T,Eq,Hash,Alloc>&)
297 { return stable_tag(); }
302 //===========================================================================
303 // Generalized Container Functions
307 template <class Sequence, class T>
308 void erase_dispatch(Sequence& c, const T& x,
311 c.erase(std::remove(c.begin(), c.end(), x), c.end());
314 template <class AssociativeContainer, class T>
315 void erase_dispatch(AssociativeContainer& c, const T& x,
316 associative_container_tag)
320 template <class Container, class T>
321 void erase(Container& c, const T& x)
323 erase_dispatch(c, x, container_category(c));
327 template <class Sequence, class Predicate, class IteratorStability>
328 void erase_if_dispatch(Sequence& c, Predicate p,
329 sequence_tag, IteratorStability)
332 c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
335 c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
338 template <class AssociativeContainer, class Predicate>
339 void erase_if_dispatch(AssociativeContainer& c, Predicate p,
340 associative_container_tag, stable_tag)
342 typename AssociativeContainer::iterator i, next;
343 for (i = next = c.begin(); next != c.end(); i = next) {
349 template <class AssociativeContainer, class Predicate>
350 void erase_if_dispatch(AssociativeContainer& c, Predicate p,
351 associative_container_tag, unstable_tag)
353 // This method is really slow, so hopefully we won't have any
354 // associative containers with unstable iterators!
355 // Is there a better way to do this?
356 typename AssociativeContainer::iterator i;
357 typename AssociativeContainer::size_type n = c.size();
359 for (i = c.begin(); i != c.end(); ++i)
365 template <class Container, class Predicate>
366 void erase_if(Container& c, Predicate p)
368 erase_if_dispatch(c, p, container_category(c), iterator_stability(c));
372 template <class Container, class T>
373 std::pair<typename Container::iterator, bool>
374 push_dispatch(Container& c, const T& v, back_insertion_sequence_tag)
377 return std::make_pair(boost::prior(c.end()), true);
380 template <class Container, class T>
381 std::pair<typename Container::iterator, bool>
382 push_dispatch(Container& c, const T& v, front_insertion_sequence_tag)
385 return std::make_pair(c.begin(), true);
388 template <class AssociativeContainer, class T>
389 std::pair<typename AssociativeContainer::iterator, bool>
390 push_dispatch(AssociativeContainer& c, const T& v,
391 unique_associative_container_tag)
396 template <class AssociativeContainer, class T>
397 std::pair<typename AssociativeContainer::iterator, bool>
398 push_dispatch(AssociativeContainer& c, const T& v,
399 multiple_associative_container_tag)
401 return std::make_pair(c.insert(v), true);
404 template <class Container, class T>
405 std::pair<typename Container::iterator,bool>
406 push(Container& c, const T& v)
408 return push_dispatch(c, v, container_category(c));
411 }} // namespace boost::graph_detail
413 #endif // BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H