1 // (C) Copyright Jeremy Siek 2004
2 // (C) Copyright Thomas Claveirole 2010
3 // (C) Copyright Ignacy Gawedzki 2010
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
8 #ifndef BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H
9 #define BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H
11 // Sure would be nice to be able to forward declare these
12 // instead of pulling in all the headers. Too bad that
13 // is not legal. There ought to be a standard <stlfwd> header. -JGS
15 #include <boost/next_prior.hpp>
17 #include <algorithm> // for std::remove
23 #include <boost/unordered_set.hpp>
24 #include <boost/unordered_map.hpp>
26 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
27 #include <unordered_set>
30 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
31 #include <unordered_map>
34 #ifdef BOOST_NO_CXX11_RVALUE_REFERENCES
35 #define BOOST_PENDING_FWD_TYPE(type) const type&
36 #define BOOST_PENDING_FWD_VALUE(type, var) (var)
38 #define BOOST_PENDING_FWD_TYPE(type) type&&
39 #define BOOST_PENDING_FWD_VALUE(type, var) (std::forward<type>((var)))
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 // don't use this unless there is partial specialization
94 template <class Container>
95 struct container_traits {
96 typedef typename Container::category category;
97 typedef typename Container::iterator_stability iterator_stability;
100 // Use this as a compile-time assertion that X is stable
101 inline void require_stable(stable_tag) { }
105 virtual public random_access_container_tag,
106 virtual public back_insertion_sequence_tag { };
108 template <class T, class Alloc>
109 vector_tag container_category(const std::vector<T,Alloc>&)
110 { return vector_tag(); }
112 template <class T, class Alloc>
113 unstable_tag iterator_stability(const std::vector<T,Alloc>&)
114 { return unstable_tag(); }
116 template <class T, class Alloc>
117 struct container_traits< std::vector<T,Alloc> > {
118 typedef vector_tag category;
119 typedef unstable_tag iterator_stability;
124 virtual public reversible_container_tag,
125 virtual public back_insertion_sequence_tag
126 // this causes problems for push_dispatch...
127 // virtual public front_insertion_sequence_tag
130 template <class T, class Alloc>
131 list_tag container_category(const std::list<T,Alloc>&)
132 { return list_tag(); }
134 template <class T, class Alloc>
135 stable_tag iterator_stability(const std::list<T,Alloc>&)
136 { return stable_tag(); }
138 template <class T, class Alloc>
139 struct container_traits< std::list<T,Alloc> > {
140 typedef list_tag category;
141 typedef stable_tag iterator_stability;
146 virtual public sorted_associative_container_tag,
147 virtual public simple_associative_container_tag,
148 virtual public unique_associative_container_tag
151 template <class Key, class Cmp, class Alloc>
152 set_tag container_category(const std::set<Key,Cmp,Alloc>&)
153 { return set_tag(); }
155 template <class Key, class Cmp, class Alloc>
156 stable_tag iterator_stability(const std::set<Key,Cmp,Alloc>&)
157 { return stable_tag(); }
159 template <class Key, class Cmp, class Alloc>
160 struct container_traits< std::set<Key,Cmp,Alloc> > {
161 typedef set_tag category;
162 typedef stable_tag iterator_stability;
166 struct multiset_tag :
167 virtual public sorted_associative_container_tag,
168 virtual public simple_associative_container_tag,
169 virtual public multiple_associative_container_tag
172 template <class Key, class Cmp, class Alloc>
173 multiset_tag container_category(const std::multiset<Key,Cmp,Alloc>&)
174 { return multiset_tag(); }
176 template <class Key, class Cmp, class Alloc>
177 stable_tag iterator_stability(const std::multiset<Key,Cmp,Alloc>&)
178 { return stable_tag(); }
180 template <class Key, class Cmp, class Alloc>
181 struct container_traits< std::multiset<Key,Cmp,Alloc> > {
182 typedef multiset_tag category;
183 typedef stable_tag iterator_stability;
190 virtual public sorted_associative_container_tag,
191 virtual public pair_associative_container_tag,
192 virtual public unique_associative_container_tag
195 template <class Key, class T, class Cmp, class Alloc>
196 struct container_traits< std::map<Key,T,Cmp,Alloc> > {
197 typedef map_tag category;
198 typedef stable_tag iterator_stability;
201 template <class Key, class T, class Cmp, class Alloc>
202 map_tag container_category(const std::map<Key,T,Cmp,Alloc>&)
203 { return map_tag(); }
205 template <class Key, class T, class Cmp, class Alloc>
206 stable_tag iterator_stability(const std::map<Key,T,Cmp,Alloc>&)
207 { return stable_tag(); }
210 struct multimap_tag :
211 virtual public sorted_associative_container_tag,
212 virtual public pair_associative_container_tag,
213 virtual public multiple_associative_container_tag
216 template <class Key, class T, class Cmp, class Alloc>
217 struct container_traits< std::multimap<Key,T,Cmp,Alloc> > {
218 typedef multimap_tag category;
219 typedef stable_tag iterator_stability;
222 template <class Key, class T, class Cmp, class Alloc>
223 multimap_tag container_category(const std::multimap<Key,T,Cmp,Alloc>&)
224 { return multimap_tag(); }
226 template <class Key, class T, class Cmp, class Alloc>
227 stable_tag iterator_stability(const std::multimap<Key,T,Cmp,Alloc>&)
228 { return stable_tag(); }
231 // hash_set, hash_map
233 struct unordered_set_tag :
234 virtual public simple_associative_container_tag,
235 virtual public unique_associative_container_tag
238 struct unordered_multiset_tag :
239 virtual public simple_associative_container_tag,
240 virtual public multiple_associative_container_tag
244 struct unordered_map_tag :
245 virtual public pair_associative_container_tag,
246 virtual public unique_associative_container_tag
249 struct unordered_multimap_tag :
250 virtual public pair_associative_container_tag,
251 virtual public multiple_associative_container_tag
255 template <class Key, class Eq, class Hash, class Alloc>
256 struct container_traits< boost::unordered_set<Key,Eq,Hash,Alloc> > {
257 typedef unordered_set_tag category;
258 typedef unstable_tag iterator_stability;
260 template <class Key, class T, class Eq, class Hash, class Alloc>
261 struct container_traits< boost::unordered_map<Key,T,Eq,Hash,Alloc> > {
262 typedef unordered_map_tag category;
263 typedef unstable_tag iterator_stability;
265 template <class Key, class Eq, class Hash, class Alloc>
266 struct container_traits< boost::unordered_multiset<Key,Eq,Hash,Alloc> > {
267 typedef unordered_multiset_tag category;
268 typedef unstable_tag iterator_stability;
270 template <class Key, class T, class Eq, class Hash, class Alloc>
271 struct container_traits< boost::unordered_multimap<Key,T,Eq,Hash,Alloc> > {
272 typedef unordered_multimap_tag category;
273 typedef unstable_tag iterator_stability;
276 template <class Key, class Eq, class Hash, class Alloc>
278 container_category(const boost::unordered_set<Key,Eq,Hash,Alloc>&)
279 { return unordered_set_tag(); }
281 template <class Key, class T, class Eq, class Hash, class Alloc>
283 container_category(const boost::unordered_map<Key,T,Eq,Hash,Alloc>&)
284 { return unordered_map_tag(); }
286 template <class Key, class Eq, class Hash, class Alloc>
287 unstable_tag iterator_stability(const boost::unordered_set<Key,Eq,Hash,Alloc>&)
288 { return unstable_tag(); }
290 template <class Key, class T, class Eq, class Hash, class Alloc>
291 unstable_tag iterator_stability(const boost::unordered_map<Key,T,Eq,Hash,Alloc>&)
292 { return unstable_tag(); }
293 template <class Key, class Eq, class Hash, class Alloc>
294 unordered_multiset_tag
295 container_category(const boost::unordered_multiset<Key,Eq,Hash,Alloc>&)
296 { return unordered_multiset_tag(); }
298 template <class Key, class T, class Eq, class Hash, class Alloc>
299 unordered_multimap_tag
300 container_category(const boost::unordered_multimap<Key,T,Eq,Hash,Alloc>&)
301 { return unordered_multimap_tag(); }
303 template <class Key, class Eq, class Hash, class Alloc>
305 iterator_stability(const boost::unordered_multiset<Key,Eq,Hash,Alloc>&)
306 { return unstable_tag(); }
308 template <class Key, class T, class Eq, class Hash, class Alloc>
310 iterator_stability(const boost::unordered_multimap<Key,T,Eq,Hash,Alloc>&)
311 { return unstable_tag(); }
313 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
314 template <class Key, class Eq, class Hash, class Alloc>
315 struct container_traits< std::unordered_set<Key,Eq,Hash,Alloc> > {
316 typedef unordered_set_tag category;
317 typedef unstable_tag iterator_stability;
320 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
321 template <class Key, class T, class Eq, class Hash, class Alloc>
322 struct container_traits< std::unordered_map<Key,T,Eq,Hash,Alloc> > {
323 typedef unordered_map_tag category;
324 typedef unstable_tag iterator_stability;
327 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
328 template <class Key, class Eq, class Hash, class Alloc>
329 struct container_traits< std::unordered_multiset<Key,Eq,Hash,Alloc> > {
330 typedef unordered_multiset_tag category;
331 typedef unstable_tag iterator_stability;
334 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
335 template <class Key, class T, class Eq, class Hash, class Alloc>
336 struct container_traits< std::unordered_multimap<Key,T,Eq,Hash,Alloc> > {
337 typedef unordered_multimap_tag category;
338 typedef unstable_tag iterator_stability;
341 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
342 template <class Key, class Eq, class Hash, class Alloc>
344 container_category(const std::unordered_set<Key,Eq,Hash,Alloc>&)
345 { return unordered_set_tag(); }
348 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
349 template <class Key, class T, class Eq, class Hash, class Alloc>
351 container_category(const std::unordered_map<Key,T,Eq,Hash,Alloc>&)
352 { return unordered_map_tag(); }
355 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
356 template <class Key, class Eq, class Hash, class Alloc>
357 unstable_tag iterator_stability(const std::unordered_set<Key,Eq,Hash,Alloc>&)
358 { return unstable_tag(); }
361 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
362 template <class Key, class T, class Eq, class Hash, class Alloc>
363 unstable_tag iterator_stability(const std::unordered_map<Key,T,Eq,Hash,Alloc>&)
364 { return unstable_tag(); }
366 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
367 template <class Key, class Eq, class Hash, class Alloc>
368 unordered_multiset_tag
369 container_category(const std::unordered_multiset<Key,Eq,Hash,Alloc>&)
370 { return unordered_multiset_tag(); }
373 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
374 template <class Key, class T, class Eq, class Hash, class Alloc>
375 unordered_multimap_tag
376 container_category(const std::unordered_multimap<Key,T,Eq,Hash,Alloc>&)
377 { return unordered_multimap_tag(); }
380 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
381 template <class Key, class Eq, class Hash, class Alloc>
383 iterator_stability(const std::unordered_multiset<Key,Eq,Hash,Alloc>&)
384 { return unstable_tag(); }
387 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
388 template <class Key, class T, class Eq, class Hash, class Alloc>
390 iterator_stability(const std::unordered_multimap<Key,T,Eq,Hash,Alloc>&)
391 { return unstable_tag(); }
395 //===========================================================================
396 // Generalized Container Functions
400 template <class Sequence, class T>
401 void erase_dispatch(Sequence& c, const T& x,
404 c.erase(std::remove(c.begin(), c.end(), x), c.end());
407 template <class AssociativeContainer, class T>
408 void erase_dispatch(AssociativeContainer& c, const T& x,
409 associative_container_tag)
413 template <class Container, class T>
414 void erase(Container& c, const T& x)
416 erase_dispatch(c, x, container_category(c));
420 template <class Sequence, class Predicate, class IteratorStability>
421 void erase_if_dispatch(Sequence& c, Predicate p,
422 sequence_tag, IteratorStability)
425 c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
428 c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
431 template <class AssociativeContainer, class Predicate>
432 void erase_if_dispatch(AssociativeContainer& c, Predicate p,
433 associative_container_tag, stable_tag)
435 typename AssociativeContainer::iterator i, next;
436 for (i = next = c.begin(); next != c.end(); i = next) {
442 template <class AssociativeContainer, class Predicate>
443 void erase_if_dispatch(AssociativeContainer& c, Predicate p,
444 associative_container_tag, unstable_tag)
446 // This method is really slow, so hopefully we won't have any
447 // associative containers with unstable iterators!
448 // Is there a better way to do this?
449 typename AssociativeContainer::iterator i;
450 typename AssociativeContainer::size_type n = c.size();
452 for (i = c.begin(); i != c.end(); ++i)
458 template <class Container, class Predicate>
459 void erase_if(Container& c, Predicate p)
461 erase_if_dispatch(c, p, container_category(c), iterator_stability(c));
465 template <class Container, class T>
466 std::pair<typename Container::iterator, bool>
467 push_dispatch(Container& c, BOOST_PENDING_FWD_TYPE(T) v, back_insertion_sequence_tag)
469 c.push_back(BOOST_PENDING_FWD_VALUE(T, v));
470 return std::make_pair(boost::prior(c.end()), true);
473 template <class Container, class T>
474 std::pair<typename Container::iterator, bool>
475 push_dispatch(Container& c, BOOST_PENDING_FWD_TYPE(T) v, front_insertion_sequence_tag)
477 c.push_front(BOOST_PENDING_FWD_VALUE(T, v));
478 return std::make_pair(c.begin(), true);
481 template <class AssociativeContainer, class T>
482 std::pair<typename AssociativeContainer::iterator, bool>
483 push_dispatch(AssociativeContainer& c, BOOST_PENDING_FWD_TYPE(T) v,
484 unique_associative_container_tag)
486 return c.insert(BOOST_PENDING_FWD_VALUE(T, v));
489 template <class AssociativeContainer, class T>
490 std::pair<typename AssociativeContainer::iterator, bool>
491 push_dispatch(AssociativeContainer& c, BOOST_PENDING_FWD_TYPE(T) v,
492 multiple_associative_container_tag)
494 return std::make_pair(c.insert(BOOST_PENDING_FWD_VALUE(T, v)), true);
497 template <class Container, class T>
498 std::pair<typename Container::iterator,bool>
499 push(Container& c, BOOST_PENDING_FWD_TYPE(T) v)
501 return push_dispatch(c, BOOST_PENDING_FWD_VALUE(T, v), container_category(c));
505 template <class Container, class Value>
506 typename Container::iterator
507 find_dispatch(Container& c,
511 return std::find(c.begin(), c.end(), value);
514 template <class AssociativeContainer, class Value>
515 typename AssociativeContainer::iterator
516 find_dispatch(AssociativeContainer& c,
518 associative_container_tag)
520 return c.find(value);
523 template <class Container, class Value>
524 typename Container::iterator
528 return find_dispatch(c, value,
529 graph_detail::container_category(c));
532 // Find (const versions)
533 template <class Container, class Value>
534 typename Container::const_iterator
535 find_dispatch(const Container& c,
539 return std::find(c.begin(), c.end(), value);
542 template <class AssociativeContainer, class Value>
543 typename AssociativeContainer::const_iterator
544 find_dispatch(const AssociativeContainer& c,
546 associative_container_tag)
548 return c.find(value);
551 template <class Container, class Value>
552 typename Container::const_iterator
553 find(const Container& c,
556 return find_dispatch(c, value,
557 graph_detail::container_category(c));
562 // Make the dispatch fail if c is not an Associative Container (and thus
563 // doesn't have equal_range unless it is sorted, which we cannot check
564 // statically and is not typically true for BGL's uses of this function).
565 template <class Container,
566 class LessThanComparable>
567 std::pair<typename Container::iterator, typename Container::iterator>
568 equal_range_dispatch(Container& c,
569 const LessThanComparable& value,
572 // c must be sorted for std::equal_range to behave properly.
573 return std::equal_range(c.begin(), c.end(), value);
577 template <class AssociativeContainer, class Value>
578 std::pair<typename AssociativeContainer::iterator,
579 typename AssociativeContainer::iterator>
580 equal_range_dispatch(AssociativeContainer& c,
582 associative_container_tag)
584 return c.equal_range(value);
587 template <class Container, class Value>
588 std::pair<typename Container::iterator, typename Container::iterator>
589 equal_range(Container& c,
592 return equal_range_dispatch(c, value,
593 graph_detail::container_category(c));
596 }} // namespace boost::graph_detail
598 #undef BOOST_PENDING_FWD_TYPE
599 #undef BOOST_PENDING_FWD_VALUE
601 #endif // BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H