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.
48 namespace graph_detail
51 //======================================================================
52 // Container Category Tags
54 // They use virtual inheritance because there are lots of
55 // inheritance diamonds.
60 struct forward_container_tag : virtual public container_tag
63 struct reversible_container_tag : virtual public forward_container_tag
66 struct random_access_container_tag : virtual public reversible_container_tag
70 struct sequence_tag : virtual public forward_container_tag
74 struct associative_container_tag : virtual public forward_container_tag
78 struct sorted_associative_container_tag
79 : virtual public associative_container_tag,
80 virtual public reversible_container_tag
84 struct front_insertion_sequence_tag : virtual public sequence_tag
87 struct back_insertion_sequence_tag : virtual public sequence_tag
91 struct unique_associative_container_tag
92 : virtual public associative_container_tag
95 struct multiple_associative_container_tag
96 : virtual public associative_container_tag
99 struct simple_associative_container_tag
100 : virtual public associative_container_tag
103 struct pair_associative_container_tag
104 : virtual public associative_container_tag
108 //======================================================================
109 // Iterator Stability Tags
111 // Do mutating operations such as insert/erase/resize invalidate all
112 // outstanding iterators?
121 //======================================================================
122 // Container Traits Class and container_category() function
124 // don't use this unless there is partial specialization
125 template < class Container > struct container_traits
127 typedef typename Container::category category;
128 typedef typename Container::iterator_stability iterator_stability;
131 // Use this as a compile-time assertion that X is stable
132 inline void require_stable(stable_tag) {}
135 struct vector_tag : virtual public random_access_container_tag,
136 virtual public back_insertion_sequence_tag
140 template < class T, class Alloc >
141 vector_tag container_category(const std::vector< T, Alloc >&)
146 template < class T, class Alloc >
147 unstable_tag iterator_stability(const std::vector< T, Alloc >&)
149 return unstable_tag();
152 template < class T, class Alloc >
153 struct container_traits< std::vector< T, Alloc > >
155 typedef vector_tag category;
156 typedef unstable_tag iterator_stability;
160 struct list_tag : virtual public reversible_container_tag,
161 virtual public back_insertion_sequence_tag
162 // this causes problems for push_dispatch...
163 // virtual public front_insertion_sequence_tag
167 template < class T, class Alloc >
168 list_tag container_category(const std::list< T, Alloc >&)
173 template < class T, class Alloc >
174 stable_tag iterator_stability(const std::list< T, Alloc >&)
179 template < class T, class Alloc >
180 struct container_traits< std::list< T, Alloc > >
182 typedef list_tag category;
183 typedef stable_tag iterator_stability;
187 struct set_tag : virtual public sorted_associative_container_tag,
188 virtual public simple_associative_container_tag,
189 virtual public unique_associative_container_tag
193 template < class Key, class Cmp, class Alloc >
194 set_tag container_category(const std::set< Key, Cmp, Alloc >&)
199 template < class Key, class Cmp, class Alloc >
200 stable_tag iterator_stability(const std::set< Key, Cmp, Alloc >&)
205 template < class Key, class Cmp, class Alloc >
206 struct container_traits< std::set< Key, Cmp, Alloc > >
208 typedef set_tag category;
209 typedef stable_tag iterator_stability;
213 struct multiset_tag : virtual public sorted_associative_container_tag,
214 virtual public simple_associative_container_tag,
215 virtual public multiple_associative_container_tag
219 template < class Key, class Cmp, class Alloc >
220 multiset_tag container_category(const std::multiset< Key, Cmp, Alloc >&)
222 return multiset_tag();
225 template < class Key, class Cmp, class Alloc >
226 stable_tag iterator_stability(const std::multiset< Key, Cmp, Alloc >&)
231 template < class Key, class Cmp, class Alloc >
232 struct container_traits< std::multiset< Key, Cmp, Alloc > >
234 typedef multiset_tag category;
235 typedef stable_tag iterator_stability;
241 struct map_tag : virtual public sorted_associative_container_tag,
242 virtual public pair_associative_container_tag,
243 virtual public unique_associative_container_tag
247 template < class Key, class T, class Cmp, class Alloc >
248 struct container_traits< std::map< Key, T, Cmp, Alloc > >
250 typedef map_tag category;
251 typedef stable_tag iterator_stability;
254 template < class Key, class T, class Cmp, class Alloc >
255 map_tag container_category(const std::map< Key, T, Cmp, Alloc >&)
260 template < class Key, class T, class Cmp, class Alloc >
261 stable_tag iterator_stability(const std::map< Key, T, Cmp, Alloc >&)
267 struct multimap_tag : virtual public sorted_associative_container_tag,
268 virtual public pair_associative_container_tag,
269 virtual public multiple_associative_container_tag
273 template < class Key, class T, class Cmp, class Alloc >
274 struct container_traits< std::multimap< Key, T, Cmp, Alloc > >
276 typedef multimap_tag category;
277 typedef stable_tag iterator_stability;
280 template < class Key, class T, class Cmp, class Alloc >
281 multimap_tag container_category(const std::multimap< Key, T, Cmp, Alloc >&)
283 return multimap_tag();
286 template < class Key, class T, class Cmp, class Alloc >
287 stable_tag iterator_stability(const std::multimap< Key, T, Cmp, Alloc >&)
292 // hash_set, hash_map
294 struct unordered_set_tag : virtual public simple_associative_container_tag,
295 virtual public unique_associative_container_tag
299 struct unordered_multiset_tag
300 : virtual public simple_associative_container_tag,
301 virtual public multiple_associative_container_tag
305 struct unordered_map_tag : virtual public pair_associative_container_tag,
306 virtual public unique_associative_container_tag
310 struct unordered_multimap_tag
311 : virtual public pair_associative_container_tag,
312 virtual public multiple_associative_container_tag
316 template < class Key, class Eq, class Hash, class Alloc >
317 struct container_traits< boost::unordered_set< Key, Eq, Hash, Alloc > >
319 typedef unordered_set_tag category;
320 typedef unstable_tag iterator_stability;
322 template < class Key, class T, class Eq, class Hash, class Alloc >
323 struct container_traits< boost::unordered_map< Key, T, Eq, Hash, Alloc > >
325 typedef unordered_map_tag category;
326 typedef unstable_tag iterator_stability;
328 template < class Key, class Eq, class Hash, class Alloc >
329 struct container_traits< boost::unordered_multiset< Key, Eq, Hash, Alloc > >
331 typedef unordered_multiset_tag category;
332 typedef unstable_tag iterator_stability;
334 template < class Key, class T, class Eq, class Hash, class Alloc >
335 struct container_traits<
336 boost::unordered_multimap< Key, T, Eq, Hash, Alloc > >
338 typedef unordered_multimap_tag category;
339 typedef unstable_tag iterator_stability;
342 template < class Key, class Eq, class Hash, class Alloc >
343 unordered_set_tag container_category(
344 const boost::unordered_set< Key, Eq, Hash, Alloc >&)
346 return unordered_set_tag();
349 template < class Key, class T, class Eq, class Hash, class Alloc >
350 unordered_map_tag container_category(
351 const boost::unordered_map< Key, T, Eq, Hash, Alloc >&)
353 return unordered_map_tag();
356 template < class Key, class Eq, class Hash, class Alloc >
357 unstable_tag iterator_stability(
358 const boost::unordered_set< Key, Eq, Hash, Alloc >&)
360 return unstable_tag();
363 template < class Key, class T, class Eq, class Hash, class Alloc >
364 unstable_tag iterator_stability(
365 const boost::unordered_map< Key, T, Eq, Hash, Alloc >&)
367 return unstable_tag();
369 template < class Key, class Eq, class Hash, class Alloc >
370 unordered_multiset_tag container_category(
371 const boost::unordered_multiset< Key, Eq, Hash, Alloc >&)
373 return unordered_multiset_tag();
376 template < class Key, class T, class Eq, class Hash, class Alloc >
377 unordered_multimap_tag container_category(
378 const boost::unordered_multimap< Key, T, Eq, Hash, Alloc >&)
380 return unordered_multimap_tag();
383 template < class Key, class Eq, class Hash, class Alloc >
384 unstable_tag iterator_stability(
385 const boost::unordered_multiset< Key, Eq, Hash, Alloc >&)
387 return unstable_tag();
390 template < class Key, class T, class Eq, class Hash, class Alloc >
391 unstable_tag iterator_stability(
392 const boost::unordered_multimap< Key, T, Eq, Hash, Alloc >&)
394 return unstable_tag();
397 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
398 template < class Key, class Eq, class Hash, class Alloc >
399 struct container_traits< std::unordered_set< Key, Eq, Hash, Alloc > >
401 typedef unordered_set_tag category;
402 typedef unstable_tag iterator_stability;
405 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
406 template < class Key, class T, class Eq, class Hash, class Alloc >
407 struct container_traits< std::unordered_map< Key, T, Eq, Hash, Alloc > >
409 typedef unordered_map_tag category;
410 typedef unstable_tag iterator_stability;
413 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
414 template < class Key, class Eq, class Hash, class Alloc >
415 struct container_traits< std::unordered_multiset< Key, Eq, Hash, Alloc > >
417 typedef unordered_multiset_tag category;
418 typedef unstable_tag iterator_stability;
421 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
422 template < class Key, class T, class Eq, class Hash, class Alloc >
423 struct container_traits<
424 std::unordered_multimap< Key, T, Eq, Hash, Alloc > >
426 typedef unordered_multimap_tag category;
427 typedef unstable_tag iterator_stability;
430 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
431 template < class Key, class Eq, class Hash, class Alloc >
432 unordered_set_tag container_category(
433 const std::unordered_set< Key, Eq, Hash, Alloc >&)
435 return unordered_set_tag();
439 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
440 template < class Key, class T, class Eq, class Hash, class Alloc >
441 unordered_map_tag container_category(
442 const std::unordered_map< Key, T, Eq, Hash, Alloc >&)
444 return unordered_map_tag();
448 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
449 template < class Key, class Eq, class Hash, class Alloc >
450 unstable_tag iterator_stability(
451 const std::unordered_set< Key, Eq, Hash, Alloc >&)
453 return unstable_tag();
457 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
458 template < class Key, class T, class Eq, class Hash, class Alloc >
459 unstable_tag iterator_stability(
460 const std::unordered_map< Key, T, Eq, Hash, Alloc >&)
462 return unstable_tag();
465 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
466 template < class Key, class Eq, class Hash, class Alloc >
467 unordered_multiset_tag container_category(
468 const std::unordered_multiset< Key, Eq, Hash, Alloc >&)
470 return unordered_multiset_tag();
474 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
475 template < class Key, class T, class Eq, class Hash, class Alloc >
476 unordered_multimap_tag container_category(
477 const std::unordered_multimap< Key, T, Eq, Hash, Alloc >&)
479 return unordered_multimap_tag();
483 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
484 template < class Key, class Eq, class Hash, class Alloc >
485 unstable_tag iterator_stability(
486 const std::unordered_multiset< Key, Eq, Hash, Alloc >&)
488 return unstable_tag();
492 #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
493 template < class Key, class T, class Eq, class Hash, class Alloc >
494 unstable_tag iterator_stability(
495 const std::unordered_multimap< Key, T, Eq, Hash, Alloc >&)
497 return unstable_tag();
501 //===========================================================================
502 // Generalized Container Functions
505 template < class Sequence, class T >
506 void erase_dispatch(Sequence& c, const T& x, sequence_tag)
508 c.erase(std::remove(c.begin(), c.end(), x), c.end());
511 template < class AssociativeContainer, class T >
513 AssociativeContainer& c, const T& x, associative_container_tag)
517 template < class Container, class T > void erase(Container& c, const T& x)
519 erase_dispatch(c, x, container_category(c));
523 template < class Sequence, class Predicate, class IteratorStability >
524 void erase_if_dispatch(
525 Sequence& c, Predicate p, sequence_tag, IteratorStability)
528 c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
531 c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
534 template < class AssociativeContainer, class Predicate >
535 void erase_if_dispatch(AssociativeContainer& c, Predicate p,
536 associative_container_tag, stable_tag)
538 typename AssociativeContainer::iterator i, next;
539 for (i = next = c.begin(); next != c.end(); i = next)
546 template < class AssociativeContainer, class Predicate >
547 void erase_if_dispatch(AssociativeContainer& c, Predicate p,
548 associative_container_tag, unstable_tag)
550 // This method is really slow, so hopefully we won't have any
551 // associative containers with unstable iterators!
552 // Is there a better way to do this?
553 typename AssociativeContainer::iterator i;
554 typename AssociativeContainer::size_type n = c.size();
556 for (i = c.begin(); i != c.end(); ++i)
563 template < class Container, class Predicate >
564 void erase_if(Container& c, Predicate p)
566 erase_if_dispatch(c, p, container_category(c), iterator_stability(c));
570 template < class Container, class T >
571 std::pair< typename Container::iterator, bool > push_dispatch(
572 Container& c, BOOST_PENDING_FWD_TYPE(T) v, back_insertion_sequence_tag)
574 c.push_back(BOOST_PENDING_FWD_VALUE(T, v));
575 return std::make_pair(boost::prior(c.end()), true);
578 template < class Container, class T >
579 std::pair< typename Container::iterator, bool > push_dispatch(
580 Container& c, BOOST_PENDING_FWD_TYPE(T) v, front_insertion_sequence_tag)
582 c.push_front(BOOST_PENDING_FWD_VALUE(T, v));
583 return std::make_pair(c.begin(), true);
586 template < class AssociativeContainer, class T >
587 std::pair< typename AssociativeContainer::iterator, bool > push_dispatch(
588 AssociativeContainer& c, BOOST_PENDING_FWD_TYPE(T) v,
589 unique_associative_container_tag)
591 return c.insert(BOOST_PENDING_FWD_VALUE(T, v));
594 template < class AssociativeContainer, class T >
595 std::pair< typename AssociativeContainer::iterator, bool > push_dispatch(
596 AssociativeContainer& c, BOOST_PENDING_FWD_TYPE(T) v,
597 multiple_associative_container_tag)
599 return std::make_pair(c.insert(BOOST_PENDING_FWD_VALUE(T, v)), true);
602 template < class Container, class T >
603 std::pair< typename Container::iterator, bool > push(
604 Container& c, BOOST_PENDING_FWD_TYPE(T) v)
606 return push_dispatch(
607 c, BOOST_PENDING_FWD_VALUE(T, v), container_category(c));
611 template < class Container, class Value >
612 typename Container::iterator find_dispatch(
613 Container& c, const Value& value, container_tag)
615 return std::find(c.begin(), c.end(), value);
618 template < class AssociativeContainer, class Value >
619 typename AssociativeContainer::iterator find_dispatch(
620 AssociativeContainer& c, const Value& value, associative_container_tag)
622 return c.find(value);
625 template < class Container, class Value >
626 typename Container::iterator find(Container& c, const Value& value)
628 return find_dispatch(c, value, graph_detail::container_category(c));
631 // Find (const versions)
632 template < class Container, class Value >
633 typename Container::const_iterator find_dispatch(
634 const Container& c, const Value& value, container_tag)
636 return std::find(c.begin(), c.end(), value);
639 template < class AssociativeContainer, class Value >
640 typename AssociativeContainer::const_iterator find_dispatch(
641 const AssociativeContainer& c, const Value& value,
642 associative_container_tag)
644 return c.find(value);
647 template < class Container, class Value >
648 typename Container::const_iterator find(
649 const Container& c, const Value& value)
651 return find_dispatch(c, value, graph_detail::container_category(c));
656 // Make the dispatch fail if c is not an Associative Container (and thus
657 // doesn't have equal_range unless it is sorted, which we cannot check
658 // statically and is not typically true for BGL's uses of this function).
659 template <class Container,
660 class LessThanComparable>
661 std::pair<typename Container::iterator, typename Container::iterator>
662 equal_range_dispatch(Container& c,
663 const LessThanComparable& value,
666 // c must be sorted for std::equal_range to behave properly.
667 return std::equal_range(c.begin(), c.end(), value);
671 template < class AssociativeContainer, class Value >
672 std::pair< typename AssociativeContainer::iterator,
673 typename AssociativeContainer::iterator >
674 equal_range_dispatch(
675 AssociativeContainer& c, const Value& value, associative_container_tag)
677 return c.equal_range(value);
680 template < class Container, class Value >
681 std::pair< typename Container::iterator, typename Container::iterator >
682 equal_range(Container& c, const Value& value)
684 return equal_range_dispatch(
685 c, value, graph_detail::container_category(c));
689 } // namespace boost::graph_detail
691 #undef BOOST_PENDING_FWD_TYPE
692 #undef BOOST_PENDING_FWD_VALUE
694 #endif // BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H