[Boost-users] Problem with iterator_property_map

From: Jens Müller (jens.mueller_at_[hidden])
Date: 2007-03-08 04:58:11

I have a problem with the iterator property map adapter ...

I have the following call in my program:

  bucket_sort(out_edges(*vi,g).first,
         out_edges(*vi,g).second,
         make_iterator_property_map(ord.begin(), get(edge_index, g)),
         std::back_inserter(sorted_edge_lists[get(get(vertex_index, g), 
*vi)].first)

Bucket sort is a function written by me:

/**
   Bucket sort algorithm. Accepts a range of object with a pair of
   ForwardIterators and outputs the elements in ascending order with
   an OutputIterator.

   \todo Maybe adding a sort order parameter is useful?

   \param begin Iterator pointing to the first element to be sorted.
   \param end Iterator pointing after the last element to be sorted.
   \param values ReadablePropertyMap with values of type int
       and keys having the type of *begin.
   \param out output iterator for the sorted elements.
   */
   template<class ForwardIterator, class ValueMap, class OutputIterator>
   void bucket_sort(ForwardIterator begin, ForwardIterator end,
     ValueMap values, OutputIterator out)
   {
     int max = get(values, *begin);
     int min = get(values, *begin);

     for(ForwardIterator i = begin; i!=end; ++i)
     {
       if(get(values, *i)>max)
         max = get(values, *i);
       if(get(values, *i)<min)
         min = get(values, *i);
     }

     int n = (max - min)+1;

     std::cout << "max: " <<  max << ", min: " << min << std::endl;

     typedef typename std::iterator_traits<ForwardIterator>::value_type 
value_type;
     std::vector< std::list<value_type> > bucket(n);
     for(ForwardIterator i = begin; i!=end; ++i)
     {
       int index = get(values, *i);
       bucket[index-min].push_back(*i);
     }

     for(int i=0;i<n;++i)
     {
       typedef typename std::list<value_type>::iterator iter;
       for(iter b = bucket[i].begin(), e = bucket[i].end(); b!=e; ++b)
       {
         *out = *b;
       }
     } // for
   } // bucket_sort

My graph is a LEDA graph, the edge_index property map is created by this 
code in leda_graph.hpp:

class leda_graph_id_map
     : public put_get_helper<int, leda_graph_id_map>
   {
   public:
     typedef readable_property_map_tag category;
     typedef int value_type;
     typedef int reference;
     typedef leda::node key_type;
     leda_graph_id_map() { }
     template <class T>
     long operator[](T x) const { return x->id(); }
   };
   template <class vtype, class etype>
   inline leda_graph_id_map
   get(vertex_index_t, const leda::GRAPH<vtype, etype>& g) {
     return leda_graph_id_map();
   }
   template <class vtype, class etype>
   inline leda_graph_id_map
   get(edge_index_t, const leda::GRAPH<vtype, etype>& g) {
     return leda_graph_id_map();
   }

  template <class Tag>
   struct leda_property_map { };

   template <>
   struct leda_property_map<vertex_index_t> {
     template <class vtype, class etype>
     struct bind_ {
       typedef leda_graph_id_map type;
       typedef leda_graph_id_map const_type;
     };
   };
   template <>
   struct leda_property_map<edge_index_t> {
     template <class vtype, class etype>
     struct bind_ {
       typedef leda_graph_id_map type;
       typedef leda_graph_id_map const_type;
     };
   };

(The edge_index part of this is new, I think).

Well, when I try to compile it, I get:

/home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/property_map.hpp: 
In function `Reference boost::get(const boost::put_get_helper<Reference, 
PropertyMap>&, const K&) [with PropertyMap = 
boost::iterator_property_map<__gnu_cxx::__normal_iterator<int*, 
std::vector<int, std::allocator<int> > >, boost::leda_graph_id_map, int, 
int&>, Reference = int&, K = leda::edge_struct*]':
bucket_sort.hpp:27:   instantiated from `void 
separator::bucket_sort(ForwardIterator, ForwardIterator, ValueMap, 
OutputIterator) [with ForwardIterator = 
boost::graph_traits<leda::GRAPH<int, int> >::out_edge_iterator, ValueMap 
= boost::iterator_property_map<__gnu_cxx::__normal_iterator<int*, 
std::vector<int, std::allocator<int> > >, boost::leda_graph_id_map, int, 
int&>, OutputIterator = 
std::back_insert_iterator<std::list<leda::edge_struct*, 
std::allocator<leda::edge_struct*> > >]'

special_bfs.hpp:323:   instantiated from `void 
separator::balanced_breadth_first_visit(const EdgeListGraph&, const 
typename boost::graph_traits<G>::vertex_descriptor&, BFSVisitor, 
ColorMap) [with EdgeListGraph = leda::GRAPH<int, int>, BFSVisitor = 
boost::bfs_visitor<boost::distance_recorder<boost::leda_node_property_map<int, 
int&, leda::node_map<int, leda::graph, -0x000000001>*>, 
boost::on_tree_edge> >, ColorMap = 
MapAsColorMap<boost::leda_node_property_map<int, int&, 
leda::node_map<int, leda::graph, -0x000000001>*>, 
boost::default_color_type>]'

[...]

/home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/property_map.hpp:312: 
error: no match for 'operator[]' in '(const 
boost::iterator_property_map<__gnu_cxx::__normal_iterator<int*, 
std::vector<int, std::allocator<int> > >, boost::leda_graph_id_map, int, 
int&>&)((const 
boost::iterator_property_map<__gnu_cxx::__normal_iterator<int*, 
std::vector<int, std::allocator<int> > >, boost::leda_graph_id_map, int, 
int&>*)(&pa))[k]'
/home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/property_map.hpp:349: 
note: candidates are: R 
boost::iterator_property_map<RandomAccessIterator, IndexMap, T, 
R>::operator[](typename boost::property_traits<IndexMap>::key_type) 
const [with RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, 
std::vector<int, std::allocator<int> > >, IndexMap = 
boost::leda_graph_id_map, T = int, R = int&]

Does anyone have any suggestions what I am doing wrong here?