Line data Source code
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)
7 :
8 : #ifndef BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H
9 : #define BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H
10 :
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
14 :
15 : #include <boost/next_prior.hpp>
16 :
17 : #include <algorithm> // for std::remove
18 : #include <utility>
19 : #include <vector>
20 : #include <list>
21 : #include <map>
22 : #include <set>
23 : #include <boost/unordered_set.hpp>
24 : #include <boost/unordered_map.hpp>
25 :
26 : #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
27 : #include <unordered_set>
28 : #endif
29 :
30 : #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
31 : #include <unordered_map>
32 : #endif
33 :
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)
37 : #else
38 : #define BOOST_PENDING_FWD_TYPE(type) type&&
39 : #define BOOST_PENDING_FWD_VALUE(type, var) (std::forward<type>((var)))
40 : #endif
41 :
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 {
47 :
48 : //======================================================================
49 : // Container Category Tags
50 : //
51 : // They use virtual inheritance because there are lots of
52 : // inheritance diamonds.
53 :
54 : struct container_tag { };
55 0 : struct forward_container_tag : virtual public container_tag { };
56 0 : struct reversible_container_tag : virtual public forward_container_tag { };
57 0 : struct random_access_container_tag
58 : : virtual public reversible_container_tag { };
59 :
60 0 : struct sequence_tag : virtual public forward_container_tag { };
61 :
62 : struct associative_container_tag : virtual public forward_container_tag { };
63 :
64 : struct sorted_associative_container_tag
65 : : virtual public associative_container_tag,
66 : virtual public reversible_container_tag { };
67 :
68 : struct front_insertion_sequence_tag : virtual public sequence_tag { };
69 0 : struct back_insertion_sequence_tag : virtual public sequence_tag { };
70 :
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 { };
79 :
80 :
81 : //======================================================================
82 : // Iterator Stability Tags
83 : //
84 : // Do mutating operations such as insert/erase/resize invalidate all
85 : // outstanding iterators?
86 :
87 : struct stable_tag { };
88 : struct unstable_tag { };
89 :
90 : //======================================================================
91 : // Container Traits Class and container_category() function
92 :
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;
98 : };
99 :
100 : // Use this as a compile-time assertion that X is stable
101 : inline void require_stable(stable_tag) { }
102 :
103 : // std::vector
104 0 : struct vector_tag :
105 : virtual public random_access_container_tag,
106 : virtual public back_insertion_sequence_tag { };
107 :
108 : template <class T, class Alloc>
109 0 : vector_tag container_category(const std::vector<T,Alloc>&)
110 0 : { return vector_tag(); }
111 :
112 : template <class T, class Alloc>
113 : unstable_tag iterator_stability(const std::vector<T,Alloc>&)
114 : { return unstable_tag(); }
115 :
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;
120 : };
121 :
122 : // std::list
123 0 : struct list_tag :
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
128 : { };
129 :
130 : template <class T, class Alloc>
131 0 : list_tag container_category(const std::list<T,Alloc>&)
132 0 : { return list_tag(); }
133 :
134 : template <class T, class Alloc>
135 : stable_tag iterator_stability(const std::list<T,Alloc>&)
136 : { return stable_tag(); }
137 :
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;
142 : };
143 :
144 : // std::set
145 : struct set_tag :
146 : virtual public sorted_associative_container_tag,
147 : virtual public simple_associative_container_tag,
148 : virtual public unique_associative_container_tag
149 : { };
150 :
151 : template <class Key, class Cmp, class Alloc>
152 : set_tag container_category(const std::set<Key,Cmp,Alloc>&)
153 : { return set_tag(); }
154 :
155 : template <class Key, class Cmp, class Alloc>
156 : stable_tag iterator_stability(const std::set<Key,Cmp,Alloc>&)
157 : { return stable_tag(); }
158 :
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;
163 : };
164 :
165 : // std::multiset
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
170 : { };
171 :
172 : template <class Key, class Cmp, class Alloc>
173 : multiset_tag container_category(const std::multiset<Key,Cmp,Alloc>&)
174 : { return multiset_tag(); }
175 :
176 : template <class Key, class Cmp, class Alloc>
177 : stable_tag iterator_stability(const std::multiset<Key,Cmp,Alloc>&)
178 : { return stable_tag(); }
179 :
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;
184 : };
185 :
186 : // deque
187 :
188 : // std::map
189 : struct map_tag :
190 : virtual public sorted_associative_container_tag,
191 : virtual public pair_associative_container_tag,
192 : virtual public unique_associative_container_tag
193 : { };
194 :
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;
199 : };
200 :
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(); }
204 :
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(); }
208 :
209 : // std::multimap
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
214 : { };
215 :
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;
220 : };
221 :
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(); }
225 :
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(); }
229 :
230 :
231 : // hash_set, hash_map
232 :
233 : struct unordered_set_tag :
234 : virtual public simple_associative_container_tag,
235 : virtual public unique_associative_container_tag
236 : { };
237 :
238 : struct unordered_multiset_tag :
239 : virtual public simple_associative_container_tag,
240 : virtual public multiple_associative_container_tag
241 : { };
242 :
243 :
244 : struct unordered_map_tag :
245 : virtual public pair_associative_container_tag,
246 : virtual public unique_associative_container_tag
247 : { };
248 :
249 : struct unordered_multimap_tag :
250 : virtual public pair_associative_container_tag,
251 : virtual public multiple_associative_container_tag
252 : { };
253 :
254 :
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;
259 : };
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;
264 : };
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;
269 : };
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;
274 : };
275 :
276 : template <class Key, class Eq, class Hash, class Alloc>
277 : unordered_set_tag
278 : container_category(const boost::unordered_set<Key,Eq,Hash,Alloc>&)
279 : { return unordered_set_tag(); }
280 :
281 : template <class Key, class T, class Eq, class Hash, class Alloc>
282 : unordered_map_tag
283 : container_category(const boost::unordered_map<Key,T,Eq,Hash,Alloc>&)
284 : { return unordered_map_tag(); }
285 :
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(); }
289 :
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(); }
297 :
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(); }
302 :
303 : template <class Key, class Eq, class Hash, class Alloc>
304 : unstable_tag
305 : iterator_stability(const boost::unordered_multiset<Key,Eq,Hash,Alloc>&)
306 : { return unstable_tag(); }
307 :
308 : template <class Key, class T, class Eq, class Hash, class Alloc>
309 : unstable_tag
310 : iterator_stability(const boost::unordered_multimap<Key,T,Eq,Hash,Alloc>&)
311 : { return unstable_tag(); }
312 :
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;
318 : };
319 : #endif
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;
325 : };
326 : #endif
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;
332 : };
333 : #endif
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;
339 : };
340 : #endif
341 : #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
342 : template <class Key, class Eq, class Hash, class Alloc>
343 : unordered_set_tag
344 : container_category(const std::unordered_set<Key,Eq,Hash,Alloc>&)
345 : { return unordered_set_tag(); }
346 : #endif
347 :
348 : #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
349 : template <class Key, class T, class Eq, class Hash, class Alloc>
350 : unordered_map_tag
351 : container_category(const std::unordered_map<Key,T,Eq,Hash,Alloc>&)
352 : { return unordered_map_tag(); }
353 : #endif
354 :
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(); }
359 : #endif
360 :
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(); }
365 : #endif
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(); }
371 : #endif
372 :
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(); }
378 : #endif
379 :
380 : #ifndef BOOST_NO_CXX11_HDR_UNORDERED_SET
381 : template <class Key, class Eq, class Hash, class Alloc>
382 : unstable_tag
383 : iterator_stability(const std::unordered_multiset<Key,Eq,Hash,Alloc>&)
384 : { return unstable_tag(); }
385 : #endif
386 :
387 : #ifndef BOOST_NO_CXX11_HDR_UNORDERED_MAP
388 : template <class Key, class T, class Eq, class Hash, class Alloc>
389 : unstable_tag
390 : iterator_stability(const std::unordered_multimap<Key,T,Eq,Hash,Alloc>&)
391 : { return unstable_tag(); }
392 : #endif
393 :
394 :
395 : //===========================================================================
396 : // Generalized Container Functions
397 :
398 :
399 : // Erase
400 : template <class Sequence, class T>
401 : void erase_dispatch(Sequence& c, const T& x,
402 : sequence_tag)
403 : {
404 : c.erase(std::remove(c.begin(), c.end(), x), c.end());
405 : }
406 :
407 : template <class AssociativeContainer, class T>
408 : void erase_dispatch(AssociativeContainer& c, const T& x,
409 : associative_container_tag)
410 : {
411 : c.erase(x);
412 : }
413 : template <class Container, class T>
414 : void erase(Container& c, const T& x)
415 : {
416 : erase_dispatch(c, x, container_category(c));
417 : }
418 :
419 : // Erase If
420 : template <class Sequence, class Predicate, class IteratorStability>
421 : void erase_if_dispatch(Sequence& c, Predicate p,
422 : sequence_tag, IteratorStability)
423 : {
424 : #if 0
425 : c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
426 : #else
427 : if (! c.empty())
428 : c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
429 : #endif
430 : }
431 : template <class AssociativeContainer, class Predicate>
432 : void erase_if_dispatch(AssociativeContainer& c, Predicate p,
433 : associative_container_tag, stable_tag)
434 : {
435 : typename AssociativeContainer::iterator i, next;
436 : for (i = next = c.begin(); next != c.end(); i = next) {
437 : ++next;
438 : if (p(*i))
439 : c.erase(i);
440 : }
441 : }
442 : template <class AssociativeContainer, class Predicate>
443 : void erase_if_dispatch(AssociativeContainer& c, Predicate p,
444 : associative_container_tag, unstable_tag)
445 : {
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();
451 : while (n--)
452 : for (i = c.begin(); i != c.end(); ++i)
453 : if (p(*i)) {
454 : c.erase(i);
455 : break;
456 : }
457 : }
458 : template <class Container, class Predicate>
459 : void erase_if(Container& c, Predicate p)
460 : {
461 : erase_if_dispatch(c, p, container_category(c), iterator_stability(c));
462 : }
463 :
464 : // Push
465 : template <class Container, class T>
466 : std::pair<typename Container::iterator, bool>
467 0 : push_dispatch(Container& c, BOOST_PENDING_FWD_TYPE(T) v, back_insertion_sequence_tag)
468 : {
469 0 : c.push_back(BOOST_PENDING_FWD_VALUE(T, v));
470 0 : return std::make_pair(boost::prior(c.end()), true);
471 : }
472 :
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)
476 : {
477 : c.push_front(BOOST_PENDING_FWD_VALUE(T, v));
478 : return std::make_pair(c.begin(), true);
479 : }
480 :
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)
485 : {
486 : return c.insert(BOOST_PENDING_FWD_VALUE(T, v));
487 : }
488 :
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)
493 : {
494 : return std::make_pair(c.insert(BOOST_PENDING_FWD_VALUE(T, v)), true);
495 : }
496 :
497 : template <class Container, class T>
498 : std::pair<typename Container::iterator,bool>
499 0 : push(Container& c, BOOST_PENDING_FWD_TYPE(T) v)
500 : {
501 0 : return push_dispatch(c, BOOST_PENDING_FWD_VALUE(T, v), container_category(c));
502 : }
503 :
504 : // Find
505 : template <class Container, class Value>
506 : typename Container::iterator
507 : find_dispatch(Container& c,
508 : const Value& value,
509 : container_tag)
510 : {
511 : return std::find(c.begin(), c.end(), value);
512 : }
513 :
514 : template <class AssociativeContainer, class Value>
515 : typename AssociativeContainer::iterator
516 : find_dispatch(AssociativeContainer& c,
517 : const Value& value,
518 : associative_container_tag)
519 : {
520 : return c.find(value);
521 : }
522 :
523 : template <class Container, class Value>
524 : typename Container::iterator
525 : find(Container& c,
526 : const Value& value)
527 : {
528 : return find_dispatch(c, value,
529 : graph_detail::container_category(c));
530 : }
531 :
532 : // Find (const versions)
533 : template <class Container, class Value>
534 : typename Container::const_iterator
535 : find_dispatch(const Container& c,
536 : const Value& value,
537 : container_tag)
538 : {
539 : return std::find(c.begin(), c.end(), value);
540 : }
541 :
542 : template <class AssociativeContainer, class Value>
543 : typename AssociativeContainer::const_iterator
544 : find_dispatch(const AssociativeContainer& c,
545 : const Value& value,
546 : associative_container_tag)
547 : {
548 : return c.find(value);
549 : }
550 :
551 : template <class Container, class Value>
552 : typename Container::const_iterator
553 : find(const Container& c,
554 : const Value& value)
555 : {
556 : return find_dispatch(c, value,
557 : graph_detail::container_category(c));
558 : }
559 :
560 : // Equal range
561 : #if 0
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,
570 : container_tag)
571 : {
572 : // c must be sorted for std::equal_range to behave properly.
573 : return std::equal_range(c.begin(), c.end(), value);
574 : }
575 : #endif
576 :
577 : template <class AssociativeContainer, class Value>
578 : std::pair<typename AssociativeContainer::iterator,
579 : typename AssociativeContainer::iterator>
580 : equal_range_dispatch(AssociativeContainer& c,
581 : const Value& value,
582 : associative_container_tag)
583 : {
584 : return c.equal_range(value);
585 : }
586 :
587 : template <class Container, class Value>
588 : std::pair<typename Container::iterator, typename Container::iterator>
589 : equal_range(Container& c,
590 : const Value& value)
591 : {
592 : return equal_range_dispatch(c, value,
593 : graph_detail::container_category(c));
594 : }
595 :
596 : }} // namespace boost::graph_detail
597 :
598 : #undef BOOST_PENDING_FWD_TYPE
599 : #undef BOOST_PENDING_FWD_VALUE
600 :
601 : #endif // BOOST_GRAPH_DETAIL_CONTAINER_TRAITS_H
|
