March 2007 - Boost-users - lists.preview.boost.org

Problem with iterator_property_map
by Jens Müller 10 Mar '07

10 Mar '07

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?

1 2

Use boost on AIX 5.2L?
by Aaron Tan 10 Mar '07

10 Mar '07

Hi, Does anyone know how to use boost libraries with VisualAge C++ 6 on AIX 5.2L? Regards, Aaron ____________________________________________________ Yahoo! Singapore Answers Real people. Real questions. Real answers. Share what you know at http://answers.yahoo.com.sg

4 3

another problem with bind
by Christian Henning 09 Mar '07

09 Mar '07

Hi there, for whatever reason the compiler cannot decide the right call to "make". Please consider the following code: using namespace std; using namespace boost; template< typename T > void make( const T& t ) {} template< typename T > void make( const T& t, int i ) {} template< typename T > void make( const T& t, int i, int j ) {} struct a {}; struct b {}; void foo( string& s, a ) {} void foo( string& s, b ) {} int _tmain(int argc, _TCHAR* argv[]) { string str( "Hello" ); make( ( bind( static_cast<void(*)(string&, a )>( &foo ), _1, _2)( ref( str ) , a() )) ); return 0; } I want to make a call to the first make taking just on parameter, the bind object. But the compiler thinks something else: test.cpp(29) : error C2780: 'void make(const T &,int,int)' : expects 3 arguments - 1 provided test.cpp(16) : see declaration of 'make' test.cpp(29) : error C2780: 'void make(const T &,int)' : expects 2 arguments - 1 provided test.cpp(13) : see declaration of 'make' test.cpp(29) : error C2784: 'void make(const T &)' : could not deduce template argument for 'const T1 &' from 'boost::_bi::bind_t<R,F,L>::result_type' with [ R=void, F=void (__cdecl *)(std::string &,a), L=boost::_bi::list2<boost::_bi::list_av_2<boost::arg<1>,boost::arg<2>>::B1,boost::_bi::list_av_2<boost::arg<1>,boost::arg<2>>::B2> ] test.cpp(10) : see declaration of 'make' How can I make that clear to the compiler? Thanks ahead, Christian

1 0

problem with bind and non-member function
by Christian Henning 09 Mar '07

09 Mar '07

Hi there, I'm using MSVC 7.1 and cannot get the following program to compile. I have tried the mailing list but couldn't find anything related. I'm sure it's a trivial problem but I cannot see right now. Anyone any idea? using namespace std; using namespace boost; struct a {}; struct b {}; void foo( string& s, a ) {} void foo( string& s, b ) {} int _tmain(int argc, _TCHAR* argv[]) { string str( "Hello" ); bind( static_cast<void(*)(string&, a )>( &foo ), ( ref( str ), a() )); return 0; } The error message is: c:\boost\boost\bind.hpp(63) : error C2825: 'F::result_type': cannot form a qualified name c:\boost\boost\bind\bind_template.hpp(15) : see reference to class template instantiation 'boost::_bi::result_traits<R,F>' being compiled with [ R=boost::_bi::unspecified, F=void (__cdecl *)(std::string &,a) ] test.cpp(18) : see reference to class template instantiation 'boost::_bi::bind_t<R,F,L>' being compiled with [ R=boost::_bi::unspecified, F=void (__cdecl *)(std::string &,a), L=boost::_bi::list1<boost::_bi::list_av_1<a>::B1> ] c:\boost\boost\bind.hpp(63) : error C2039: 'result_type' : is not a member of 'operator``global namespace''' c:\boost\boost\bind.hpp(63) : error C2146: syntax error : missing ';' before identifier 'type' c:\boost\boost\bind.hpp(63) : error C2955: 'boost::_bi::type' : use of class template requires template argument list c:\boost\boost\bind.hpp(112) : see declaration of 'boost::_bi::type' c:\boost\boost\bind.hpp(63) : fatal error C1903: unable to recover from previous error(s); stopping compilation

2 4

iostream large file - performance
by Aljaz 09 Mar '07

09 Mar '07

Hello.. I've been testing fstream libary to read a huge text file (45 megabytes), which has around 2 million lines.. When I do (using fstream): Code: int line = 0; string str; ifstream is("file.txt"); while (!is.eof()) { getline(is, str); line++; }It takes about 9 seconds to read the whole file.. If I open file it with any 'good' text editor (editplus, notepad++ for instance) it takes a few seconds to read/load the whole file.. So I'm wondering.. What am I doing wrong? What should I do to achieve that speed - better preformance? Can boost::iostream do any better? Another thing: I tried writing data to deque (deque.pushback(str)) and was shocked on what happened.. It took ages to process the file, cpu constant at 99% so I closed the program after around 3 minutes.. Whats the 'proper' way to read files to memory? How do text editors do this? They load the same file in 4 seconds! I need a fastest way to read about 10 000 lines from text file at once.. Any help highly appreciated! Best regards A

7 7

[BGL] Visitor events
by Anton A. Patrushev 09 Mar '07

09 Mar '07

Hi, I want to implement my own edge-based visitor. I need to implement new visitor events (for example on_initialize_edge or on_finish_edge). So, what should I do? Do I need to redefine entire visitor concept? Regards, Anton.

2 2

Circular buffer library in boost
by Meryl Silverburgh 09 Mar '07

09 Mar '07

Hi, Is there a Circular buffer library in boost? If not, can you please tell me if there is a circular buffer library in c++? Thank you.

2 1

[BGL] Dijkstra algorithm help!!!
by Alejandro Marcos Aragón 09 Mar '07

09 Mar '07

Hi, I would like to know if anyone knows about a simplified version of the Dijkstra algorithm code. The one in the library is too difficult for me to understand and modify since my knowledge about templates is limited. I need to modify it somehow to make it do something I want and I don't think I can use the visitor concept to do this. I posted a message before, where I explained that I was trying to use a visitor to solve my problem but I didn't get anywhere. This is what I'm trying to do: I want to store all the distances for a vertex i, not only the smallest distance. In the current algorithm, when an edge is relaxed (meaning that the distance from the source is less than the one before), the distance is overwritten in the DistanceMap. I would like to keep all the distances with their respective vertices. Therefore, I thought that a priority queue (min heap) would be the right data structure to use. However, I don't know how to access to this information using the visitor. Imagine a graph like this one: 3 B------C | / | / 2| /6 | / | / A Imagine that the A is the source and it finds first that the distance to C is 6 (A-C edge). Then, when it finds that a lower distance is obtained through A-B and B-C (5), I would like to keep the previous result as well in a priority queue. For vertex C the priority queue looks then like this: (5,B) / / / (6,A) I would appreciate any suggestions. Alejandro

2 2

[state_saver] An extra constructor and a swapping destructor?
by Niels Dekker - mail address until 2007-11-30 08 Mar '07

08 Mar '07

The state_saver class at www.boost.org/boost/state_saver.hpp appears to be very useful for me. But I would like to propose two changes: First of all, I would like to have an extra constructor that would allow specifying a new value for the object (whose previous value will be restored when state_saver is destructed). Such a constructor would be very convenient, and it would also be conforming to io_state_saver's classes, by Daryle Walker. www.boost.org/libs/io/doc/ios_state.html A possible implementation would be: state_saver( T & object, const T & new_value ) : previous_value(object), previous_ref(object) { previous_ref = new_value; } Secondly I would suggest using a swap instead of an assignment, when restoring the previous value (when state_saver is destructed). A swap is much more likely to be fail-safe and efficient than an assignment. So I would propose the destructor to look as follows: ~state_saver() { // Doing "using std::swap", as suggested by Scott Meyers, // Effective C++ 3rd Edition, item 25, "Consider support // for a non-throwing swap" using std::swap; swap(previous_ref, previous_value); } Will these changes generally be considered an improvement? I already wrote Robert Ramey, the owner of state_saver.hpp. He also recommanded posting a message on this subject. So please let me know what you think! -- Niels Dekker http://www.xs4all.nl/~nd/dekkerware C++ programmer at LKEB, Leiden University Medical Center

1 0

BOOST_CHECK_PREDICATE vs BOOST_WARN_PREDICATE
by Alex Flint 08 Mar '07

08 Mar '07

The documentation page for the PREDICATE testing macros gives quite different syntax for the WARN vs CHECK methods: BOOST_WARN_PREDICATE( moo, (12)(i)(j) ); BOOST_CHECK_PREDICATE( std::not_equal_to<int>(), 2, (i,17) ); Since BOOST_WARN_PREDICATE and BOOST_CHECK_PREDICATE are only slight variants of one another, I'm confused as to why the syntax differs so much. Can anyone shed some light on this for me? Thanks, Alex

2 3