Subject: [Boost-commit] svn:boost r60198 - in trunk/boost: graph graph/detail pending
From: jewillco_at_[hidden]
Date: 2010-03-05 13:27:44
Author: jewillco
Date: 2010-03-05 13:27:43 EST (Fri, 05 Mar 2010)
New Revision: 60198
URL: http://svn.boost.org/trac/boost/changeset/60198
Log:
Added in container_traits and adjacency_list patches to fix unordered container issues (patch from #3972); fixes #3972
Text files modified:
trunk/boost/graph/adjacency_list.hpp | 13 ++++++
trunk/boost/graph/detail/adjacency_list.hpp | 11 +++--
trunk/boost/pending/container_traits.hpp | 74 ++++++++++++++++++++++++++++++++++++---
3 files changed, 86 insertions(+), 12 deletions(-)
Modified: trunk/boost/graph/adjacency_list.hpp
==============================================================================
--- trunk/boost/graph/adjacency_list.hpp (original)
+++ trunk/boost/graph/adjacency_list.hpp 2010-03-05 13:27:43 EST (Fri, 05 Mar 2010)
@@ -1,6 +1,7 @@
//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
-// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
+// Copyright 2010 Thomas Claveirole
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Thomas Claveirole
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
@@ -254,6 +255,16 @@
typedef disallow_parallel_edge_tag type;
};
+ template <>
+ struct parallel_edge_traits<hash_multisetS> {
+ typedef allow_parallel_edge_tag type;
+ };
+
+ template <>
+ struct parallel_edge_traits<hash_multimapS> {
+ typedef allow_parallel_edge_tag type;
+ };
+
namespace detail {
template <class Directed> struct is_random_access {
enum { value = false};
Modified: trunk/boost/graph/detail/adjacency_list.hpp
==============================================================================
--- trunk/boost/graph/detail/adjacency_list.hpp (original)
+++ trunk/boost/graph/detail/adjacency_list.hpp 2010-03-05 13:27:43 EST (Fri, 05 Mar 2010)
@@ -1,7 +1,8 @@
// -*- c++ -*-
//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
-// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
+// Copyright 2010 Thomas Claveirole
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Thomas Claveirole
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
@@ -1633,6 +1634,7 @@
const Graph& g = static_cast<const Graph&>(g_);
return g_.edge_dispatch(g, u, v, Cat());
}
+
template <class Config, class Base>
inline std::pair<typename Config::out_edge_iterator,
typename Config::out_edge_iterator>
@@ -1648,10 +1650,9 @@
typename Config::OutEdgeList& el = g.out_edge_list(u);
typename Config::OutEdgeList::iterator first, last;
typename Config::EdgeContainer fake_edge_container;
- tie(first, last) =
- std::equal_range(el.begin(), el.end(),
- StoredEdge(v, fake_edge_container.end(),
- &fake_edge_container));
+ tie(first, last) = graph_detail::
+ equal_range(el, StoredEdge(v, fake_edge_container.end(),
+ &fake_edge_container));
return std::make_pair(out_edge_iterator(first, u),
out_edge_iterator(last, u));
}
Modified: trunk/boost/pending/container_traits.hpp
==============================================================================
--- trunk/boost/pending/container_traits.hpp (original)
+++ trunk/boost/pending/container_traits.hpp 2010-03-05 13:27:43 EST (Fri, 05 Mar 2010)
@@ -1,4 +1,5 @@
// (C) Copyright Jeremy Siek 2004
+// (C) Copyright Thomas Claveirole 2010
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
@@ -267,12 +268,22 @@
template <class Key, class Eq, class Hash, class Alloc>
struct container_traits< boost::unordered_set<Key,Eq,Hash,Alloc> > {
typedef set_tag category;
- typedef stable_tag iterator_stability; // is this right?
+ typedef unstable_tag iterator_stability;
};
template <class Key, class T, class Eq, class Hash, class Alloc>
struct container_traits< boost::unordered_map<Key,T,Eq,Hash,Alloc> > {
typedef map_tag category;
- typedef stable_tag iterator_stability; // is this right?
+ typedef unstable_tag iterator_stability;
+ };
+ template <class Key, class Eq, class Hash, class Alloc>
+ struct container_traits< boost::unordered_multiset<Key,Eq,Hash,Alloc> > {
+ typedef multiset_tag category;
+ typedef unstable_tag iterator_stability;
+ };
+ template <class Key, class T, class Eq, class Hash, class Alloc>
+ struct container_traits< boost::unordered_multimap<Key,T,Eq,Hash,Alloc> > {
+ typedef multimap_tag category;
+ typedef unstable_tag iterator_stability;
};
#endif
template <class Key, class Eq, class Hash, class Alloc>
@@ -284,12 +295,31 @@
{ return map_tag(); }
template <class Key, class Eq, class Hash, class Alloc>
- stable_tag iterator_stability(const boost::unordered_set<Key,Eq,Hash,Alloc>&)
- { return stable_tag(); }
+ unstable_tag iterator_stability(const boost::unordered_set<Key,Eq,Hash,Alloc>&)
+ { return unstable_tag(); }
template <class Key, class T, class Eq, class Hash, class Alloc>
- stable_tag iterator_stability(const boost::unordered_map<Key,T,Eq,Hash,Alloc>&)
- { return stable_tag(); }
+ unstable_tag iterator_stability(const boost::unordered_map<Key,T,Eq,Hash,Alloc>&)
+ { return unstable_tag(); }
+ template <class Key, class Eq, class Hash, class Alloc>
+ multiset_tag
+ container_category(const boost::unordered_multiset<Key,Eq,Hash,Alloc>&)
+ { return multiset_tag(); }
+
+ template <class Key, class T, class Eq, class Hash, class Alloc>
+ multimap_tag
+ container_category(const boost::unordered_multimap<Key,T,Eq,Hash,Alloc>&)
+ { return multimap_tag(); }
+
+ template <class Key, class Eq, class Hash, class Alloc>
+ unstable_tag
+ iterator_stability(const boost::unordered_multiset<Key,Eq,Hash,Alloc>&)
+ { return unstable_tag(); }
+
+ template <class Key, class T, class Eq, class Hash, class Alloc>
+ unstable_tag
+ iterator_stability(const boost::unordered_multimap<Key,T,Eq,Hash,Alloc>&)
+ { return unstable_tag(); }
#endif
@@ -403,6 +433,38 @@
return push_dispatch(c, v, container_category(c));
}
+ // Equal range
+ template <class Container,
+ class LessThanComparable,
+ class ContainerCategory>
+ std::pair<typename Container::iterator, typename Container::iterator>
+ equal_range_dispatch(Container& c,
+ const LessThanComparable& value,
+ const ContainerCategory&)
+ {
+ // c must be sorted for std::equal_range to behave properly.
+ return std::equal_range(c.begin(), c.end(), value);
+ }
+
+ template <class AssociativeContainer, class LessThanComparable>
+ std::pair<typename AssociativeContainer::iterator,
+ typename AssociativeContainer::iterator>
+ equal_range_dispatch(AssociativeContainer& c,
+ const LessThanComparable& value,
+ const associative_container_tag&)
+ {
+ return c.equal_range(value);
+ }
+
+ template <class Container, class LessThanComparable>
+ std::pair<typename Container::iterator, typename Container::iterator>
+ equal_range(Container& c,
+ const LessThanComparable& value)
+ {
+ return equal_range_dispatch(c, value,
+ graph_detail::container_category(c));
+ }
+
}} // namespace boost::graph_detail
#if BOOST_WORKAROUND(BOOST_MSVC, < 1300)