From: asutton_at_[hidden]
Date: 2007-09-06 12:04:45
Author: asutton
Date: 2007-09-06 12:04:45 EDT (Thu, 06 Sep 2007)
New Revision: 39149
URL: http://svn.boost.org/trac/boost/changeset/39149
Log:
Relaxed iterator requirements on iterator property map and safe iterator
property map so they can be used with almost any container.
Text files modified:
sandbox/graph-v2/boost/property_map/iterator_property_map.hpp | 77 +++++++++++++++++++++------------------
1 files changed, 41 insertions(+), 36 deletions(-)
Modified: sandbox/graph-v2/boost/property_map/iterator_property_map.hpp
==============================================================================
--- sandbox/graph-v2/boost/property_map/iterator_property_map.hpp (original)
+++ sandbox/graph-v2/boost/property_map/iterator_property_map.hpp 2007-09-06 12:04:45 EDT (Thu, 06 Sep 2007)
@@ -9,6 +9,7 @@
#define BOOST_PROPERTY_MAP_ITERATOR_PROPERTY_MAP_HPP
#include <boost/assert.hpp>
+#include <boost/utility.hpp>
#include <boost/detail/iterator.hpp>
#include <boost/property_map/property_traits.hpp>
#include <boost/property_map/concepts.hpp>
@@ -37,17 +38,25 @@
// imap[key] returns a reference to the ith object past iter. The implication
// here is that the indices of objects are generally required to be in the
// range [0, n).
+ //
+ //
+ // ANS: Relaxed the iterator requirements on the iterator map. This is now
+ // allowed to support any forward iterator (e.g., list<>::iterator) as
+ // the basis for offsetting indices. Essentially, this allows us to build
+ // iterator maps over nearly any container type. Note that only random access
+ // iterators support constant time get() and put() functions. Otherwise,
+ // these functions are (painfully) linear.
template <
- class RandomAccessIterator,
+ class Iterator,
class IndexMap,
- class Type = typename boost::detail::iterator_traits<RandomAccessIterator>::value_type,
- class Reference = typename boost::detail::iterator_traits<RandomAccessIterator>::reference
+ class Type = typename boost::detail::iterator_traits<Iterator>::value_type,
+ class Reference = typename boost::detail::iterator_traits<Iterator>::reference
>
class iterator_property_map
: public put_get_helper<
Reference,
iterator_property_map<
- RandomAccessIterator,
+ Iterator,
IndexMap,
Type,
Reference
@@ -60,17 +69,17 @@
typedef Reference reference;
typedef lvalue_property_map_tag category;
- inline iterator_property_map(RandomAccessIterator cc = RandomAccessIterator(),
+ inline iterator_property_map(Iterator it = Iterator(),
const IndexMap& id = IndexMap())
- : iter(cc)
+ : iter(it)
, index(id)
{ }
inline reference operator[](const key_type& k) const
- { return *(iter + get(index, k)); }
+ { return *(next(iter, get(index, k))); }
protected:
- RandomAccessIterator iter;
+ Iterator iter;
IndexMap index;
};
@@ -81,22 +90,20 @@
// NOTE: The requirement that IndexMap model the ReadablePropertyMap concept
// is somewhat "recursive" since it both defines and the key type for the
// property map being constructed and provides its type for the function.
- template <class RandomAccessIterator, class IndexMap>
+ template <class Iterator, class IndexMap>
inline iterator_property_map<
- RandomAccessIterator,
- IndexMap,
- typename boost::detail::iterator_traits<RandomAccessIterator>::value_type,
- typename boost::detail::iterator_traits<RandomAccessIterator>::reference
+ Iterator, IndexMap,
+ typename boost::detail::iterator_traits<Iterator>::value_type,
+ typename boost::detail::iterator_traits<Iterator>::reference
>
- make_iterator_property_map(RandomAccessIterator iter, IndexMap id)
+ make_iterator_property_map(Iterator iter, IndexMap id)
{
- function_requires< RandomAccessIteratorConcept<RandomAccessIterator> >();
+ function_requires< ForwardIteratorConcept<Iterator> >();
function_requires< ReadablePropertyMapConcept<IndexMap, typename property_traits<IndexMap>::key_type> >();
typedef iterator_property_map<
- RandomAccessIterator,
- IndexMap,
- typename boost::detail::iterator_traits<RandomAccessIterator>::value_type,
- typename boost::detail::iterator_traits<RandomAccessIterator>::reference
+ Iterator, IndexMap,
+ typename boost::detail::iterator_traits<Iterator>::value_type,
+ typename boost::detail::iterator_traits<Iterator>::reference
> PropertyMap;
return PropertyMap(iter, id);
}
@@ -108,16 +115,16 @@
// that index types are unsigned.
template <
- class RandomAccessIterator,
+ class Iterator,
class IndexMap,
- class Type = typename boost::detail::iterator_traits<RandomAccessIterator>::value_type,
- class Reference = typename boost::detail::iterator_traits<RandomAccessIterator>::reference
+ class Type = typename boost::detail::iterator_traits<Iterator>::value_type,
+ class Reference = typename boost::detail::iterator_traits<Iterator>::reference
>
class safe_iterator_property_map
: public put_get_helper<
Reference,
iterator_property_map<
- RandomAccessIterator,
+ Iterator,
IndexMap,
Type,
Reference
@@ -130,7 +137,7 @@
typedef Reference reference;
typedef lvalue_property_map_tag category;
- inline safe_iterator_property_map(RandomAccessIterator first,
+ inline safe_iterator_property_map(Iterator first,
std::size_t n = 0,
const IndexMap& id = IndexMap())
: iter(first)
@@ -154,28 +161,26 @@
protected:
typedef typename property_traits<IndexMap>::value_type Index;
- RandomAccessIterator iter;
+ Iterator iter;
Index num;
IndexMap index;
};
// A generator function for creating safe iterator property maps.
- template <class RandomAccessIterator, class IndexMap>
+ template <class Iterator, class IndexMap>
inline safe_iterator_property_map<
- RandomAccessIterator,
- IndexMap,
- typename boost::detail::iterator_traits<RandomAccessIterator>::value_type,
- typename boost::detail::iterator_traits<RandomAccessIterator>::reference
+ Iterator, IndexMap,
+ typename boost::detail::iterator_traits<Iterator>::value_type,
+ typename boost::detail::iterator_traits<Iterator>::reference
>
- make_safe_iterator_property_map(RandomAccessIterator iter, std::size_t n, IndexMap id)
+ make_safe_iterator_property_map(Iterator iter, std::size_t n, IndexMap id)
{
- function_requires< RandomAccessIteratorConcept<RandomAccessIterator> >();
+ function_requires< ForwardIteratorConcept<Iterator> >();
function_requires< ReadablePropertyMapConcept<IndexMap, typename property_traits<IndexMap>::key_type> >();
typedef safe_iterator_property_map<
- RandomAccessIterator,
- IndexMap,
- typename boost::detail::iterator_traits<RandomAccessIterator>::value_type,
- typename boost::detail::iterator_traits<RandomAccessIterator>::reference
+ Iterator, IndexMap,
+ typename boost::detail::iterator_traits<Iterator>::value_type,
+ typename boost::detail::iterator_traits<Iterator>::reference
> PropertyMap;
return PropertyMap(iter, n, id);