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

[BGL] dijkstra_shortest_path fails to call initialize_vertex
by Michael Barrientos 14 Aug '06

14 Aug '06

In Boost 1.33.1, the documentation at http://boost.org/libs/graph/doc/dijkstra_shortest_paths.html for the Dijkstra's Shortest Path algorithm says that the initialize_vertex(v,g) method of a Dijkstra visitor is invoked on each vertex in the graph before the start of the algorithm, but when I created a visitor with an initialize_vertex method, it was never called. I did some digging into the source, and found that when the Dijkstra's algorithm delegates to the Breadth First Search algorithm, it calls breadth_first_visit. However, only breadth_first_search calls initialize_vertex. Thus initialize vertex is never called. For now, I've decided to work around it without patching BGL, but can this be fixed in a future version?

4 7

[Serialization] possible solns to vector of vectors ptr corruption
by Dan Notestein 14 Aug '06

14 Aug '06

Hi Robert, Any thoughts about my ideas for fixing the vector of vectors ptr corruption issue? I've reiterated my early msg below. If you don't have time to investigate, I would be willing to work on fixing the problem, if you don't mind me bugging you with questions occassionally. regards, Dan Notestein Original Message: ----------------------- Robert Ramey wrote: > Dan Notestein wrote: >> The other bug appears to be in the way moveable_objects_recent and >> moveable_objects_end are being set prior to calling >> reset_object_address. My assumption is the intent here is to modify >> the addresses of "trackable" sub-objects contained within the vector >> element being moved, so that ptrs will be hooked back up correctly, >> but the moveable ptrs are being set up in such a way that the vector >> elements (TObject) of the sub-vector (ObjectVector) are getting their >> addresses modified when the stack version of TObjectContainer is >> copied to the vector. > >> This seems wrong, because the TObjects are >> allocated on the heap, so their addresses should not be updated in >> the object_vector_id table when the ObjectVector is copied. The end >> result is that I'm getting bad pointers to the TObjects after >> deserialization. > > TObjects are de-serialized to the heap then added to the vector. > Since the tracking saves the address TObject is serialized to, the > address would be on the stack. reset_object_address sets the tracked > address to the heap address after the item is appended to the vector. > > I thought I considered the case of a vector of vectors - but maybe > not. I would expect that the objects get theire addresses fixed up > twice- once when they are moved from the stack to the heap and > once when the vector container itself is moved from the stack to the > heap. Its possible that there is something missng . Yes, the TObjects are fixed up twice, but I think the second fixup is an error because vector<> doesn't really contain the data elements, it contains a ptr to the data elements. When the vector container is "copied" from the stack to the heap, the newly allocated internal vector element array will be randomly allocated from somewhere else in the heap, so using an offset based off the address of the new copy of the vector container won't work. I can think of two possible theoretical solutions to the problem: 1) Use the container::swap function to exchange internal data ptrs of the stack and heap copy of the vector. This gives the heap vector the ownership of the stack vector's elements. This seems the most efficient technique since it avoid reallocating and copy constructing the elements. There's also no need to fixup the ptrs to the elements using this technique. 2) Continue to use the copy constructor for the vector when transferring the vector from stack to heap, and use the internal array ptr inside the new copy of the vector to fixup the elements. This definitely seems like the lesser of the two options. I would have tried to make a fix for this, but the algorithm for handling the moveable ptrs that define the range of addresses to fixup was a little complicated for me to follow. In particular, I wasn't sure how to make the fixups take place so that truly "contained" data gets fixed up, while avoiding fixing up the data that is merely "pointed" to by data members (and hence shouldn't be fixed up when the container is copied). One idea I had was to keep around the size of the data objects being moved, so that the reset_address function could look for ptrs in the moveable_ptr range that have addresses between old_address and old_address+object_size. But I also figured there was a good chance that there is already information available somewhere on which items in the object_id table are "contained" vs "pointed to". best regards, Dan Notestein

3 5

simple boost::bind question
by Manfred Doudar 14 Aug '06

14 Aug '06

Hello all: Hoping someone might help with a simple problem; how I might call a member on a boost::bind placeholder, see below ... #include <list> class Xtype { public: Xtype(int v) : value_(v) { } int the_value() const { return this->value_; } private: int value_; }; template <typename Predicate> class Excise { public: void operator()(std::list<Xtype>& li) const { li.remove_if(boost::bind(Predicate(), ::_1, 10)); } }; ... what I really want is something more like [, note the call of Xtype::this_value() ]: void operator()(std::list<Xtype>& li) const { li.remove_if(boost::bind(Predicate(), ::_1.the_value(), 10)); } But how do I achieve that (, if at all possible); as seemingly ::_1.the_value() is illegal/invalid code ? Thanks in advance, -- Manfred

2 4

[Boost][multi_array] copying a float array to a particular dimension of a multi_array
by Sebastien Fortier 14 Aug '06

14 Aug '06

I would like to know if it is possible to use memcpy to copy a float array to a particular dimension of a multi_array. ex.: I declare a 3 dimension multi_array of floats typedef boost::multi_array < float, 3 > array_type3D_f_t; int dim1 = 2; int dim2 = 2; int dim3 = 4; array_type3D_f_t valueMatrix(boost::extents[dim1][dim2][dim3]); then for each 3rd dimension I would like to copy a float array into it using memcpy (the final real multi_array will contain approx 21 000 000 elements, and thts why I do wish to iterate ). for (int i = 0; i < dim3; ++i) { // iterate over each 3rd dimension of the multi_array float *arr = NULL; arr = (float*)malloc(sizeof(float) * dim1 * dim2); function(&arr) // fills in the array (2D contiguous (dim1 * dim2)) memcpy(&valueMatrix[something...], arr, sizeof(float) * dim1 * dim2) // I want to copy the vector into the multi_array's 3rd dimension } then when I want to access an element I simply do valueMatrix[1][1][1]; what i used to do is int level = 0; while(it1 != it2){ // it1 and it2 are iterators to a list of records holding the data float* arr; readData(it1, &arr); // read the data into the array for (int j = 0; j < dim2; ++j){ for (int i = 0; i < dim1; ++i){ valueMatrix[i][j][level] = datavec[ j * dim1+i ]; } } ++it1; // change level ++level; } I would like to replace the nested loops by a memcpy, is this possible? -- Sébastien Fortier

2 2

[Lambda] Protecting expressions with "mixed placeholders"
by Irfan Adilovic 14 Aug '06

14 Aug '06

Hi all, Assuming "v" is an STL container, and "value" is a value the container can hold, I wish to do the following: ll::accumulate()(v.begin(), v.end(), true, _1 && (_2 != value)); which works: it returns true if all elements in the container are different from "value", false otherwise (might require a minute of thinking to come to that conclusion). Now I wish to make a lambda expression out of the above piece of code, which accepts "value" as the operator () argument, in order to be evaluated: bind(ll::accumulate(), v.begin(), v.end(), true, _1 && (_2 != value_placeholder)); where _1 and _2 should be protected but value_placeholder shouldn't (this is why I used "mixed placeholders" in the subject). In other words, should the bind-expression be evaluated with (value) as its operator() argument, only "value_placeholder" must be replaced by "value", the _1 or _2 placeholders must not. A simple protect: protect(_1 && (_2 != value_placeholder)) is obviously wrong, as "value_placeholder" cannot be replaced by "value" in an expression like: bind(ll::accumulate(), v.begin(), v.end(), true, protect(_1 && (_2 != value_placeholder)))(value); since "value_placeholder" itself, too, is protected. How to do this? I hope this was clear enough, I really tried. :-/ Regards, -- Irfy

1 0

[BGL] experience with rooting diff on dijkstra
by Jens Theisen 13 Aug '06

13 Aug '06

Hello, after the discussion about on-demand vertex initialisation I implemented a diffing algorithm on top of BGL's dijkstra. I thought the main problem is that BGL is inherently linear in the number of vertices (because it initialises some maps on each vertex prior to running the algo), but in practice, for diffing files, that's probably not too relevant, as the case of two files being pretty different is not a rare one (and two completely different files will need to access any node). The algorithm used by gnu diff is, though also quadratic in the input, linear in space usage, which one can't say for the dijsktra approach. (I haven't look at the algorithm, but they cite a paper which suggests that.) And gnu diff is much faster than my program in practice, though my one is probably fast enough for what I want to use it for. Jens

1 0

minor boost/lambda::bind documentation question
by Vyacheslav Lanovets 12 Aug '06

12 Aug '06

Here http://boost.org/doc/html/lambda/le_in_details.html#lambda.overriding_deduc… you can find such declaration: ... struct X { Y operator(int)(); }; ... What's that???

1 0

BOOST_CHECK_EQUAL and std::wstring
by Rob Caldecott 11 Aug '06

11 Aug '06

I am using the Boost unit test suite for the first time, but am having a problem using BOOST_CHECK_EQUAL with wide strings. For example: std::wstring str1 = L"unit"; std::wstring str2 = L"test"; BOOST_CHECK_EQUAL(str1, str2); This produces the following error: c:\boost\include\boost-1_33_1\boost\test\test_tools.hpp(274) : error C2679: binary '<<' : no operator found which takes a right-hand operand of type 'const std::wstring' (or there is no acceptable conversion) Any help would be appreciated.

3 2

[regex]Using regex in x64 exe with VC 8.0
by Bill Buklis 11 Aug '06

11 Aug '06

I was able to successfully compile the boost libraries for x64 under VC 8.0 using the following line: bjam "-sTOOLS=vc-8_0-amd64" As far as I can tell everything was successful (see note at end of message). There was, of course, a vast quantity of warnings, but all of the lib files seem to be there. Then I tried creating an app using regex. The test code essentially boils down to this: #include <boost/regex.hpp> bool testregex( const char* StringToMatch ) { return( boost::regex_match( StringToMatch, boost::regex("[A-Z]+") ) ); } It compiles fine, but fails to resolve three regex related functions in the linker. Paraphrasing to make it a little more readable (if you want to see the full text, let me know): basic_regex<char, regex_traits<char,w32_regex_traits<char> > >::do_assign re_detail::perl_matcher<...>::match re_detail::perl_matcher<...>::perl_matcher [constructor] All three of these functions reference boost::w32_regex_traits. Perhaps this is where the problem lies? Should it be w64_regex_traits? Am I missing a define somewhere? Any ideas? As an aside: I was only able to compile the boost libraries on a 64-bit machine. Running bjam on a 32-bit machine kept popping up a message box saying that (vc2005path...)\amd64\cl.exe was not a valid executable. Apparently the bjam configuration wants to use a true 64-bit executable version of cl. I wasn't even aware that any part of VS2005 was actually 64-bit. I thought it was a 32-bit application that could compile/link 64-bit executables. I certainly can compile 64-bit apps under the IDE. Anyway, I only mention this in case it somehow relates to the underlying problem. Thanks, -- Bill --

3 4

Regex crash
by Alan Gray 11 Aug '06

11 Aug '06

Hi all, Has anyone had troubles with using wregex? regex works fine for me. Here is the stack dump. 001B:78144D3A MSVCR80.dll, memcpy()+90 byte(s) 001B:7817FEF5 MSVCR80.dll, memcpy_s()+72 byte(s) 001B:7C421201 MSVCP80.dll, std::char_traits<char>::_Copy_s()+21 byte(s) 001B:7C4237EF MSVCP80.dll, std::basic_string<char,std::char_traits<char>,std::allocator<char> >::append()+145 byte(s) 001B:7C434713 MSVCP80.dll, ??$?HDU?$char_traits@D@std@@V?$allocator@D@1@@std@@YA?AV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@0@ABV10@0@Z()+45 byte(s) 001B:01EDF959 test.exe, boost::re_detail::w32_regex_traits_char_layer<wchar_t>::w32_regex_traits_char_layer<wchar_t>()+265 byte(s), h:\backup\boost_1_33_1\boost\regex\v4\w32_regex_traits.hpp, line 194+24 byte(s) 001B:01ED18F0 test.exe, boost::re_detail::w32_regex_traits_implementation<wchar_t>::w32_regex_traits_implementation<wchar_t>()+64 byte(s), h:\backup\boost_1_33_1\boost\regex\v4\w32_regex_traits.hpp, line 427+64 byte(s) 001B:01EC9076 test.exe, boost::object_cache<unsigned long,boost::re_detail::w32_regex_traits_implementation<wchar_t> >::do_get()+838 byte(s), h:\backup\boost_1_33_1\boost\regex\pending\object_cache.hpp, line 118+46 byte(s) 001B:01EC3D6F test.exe, boost::object_cache<unsigned long,boost::re_detail::w32_regex_traits_implementation<wchar_t> >::get()+95 byte(s), h:\backup\boost_1_33_1\boost\regex\pending\object_cache.hpp, line 69+17 byte(s) 001B:01EC164A test.exe, boost::re_detail::create_w32_regex_traits<wchar_t>()+26 byte(s), h:\backup\boost_1_33_1\boost\regex\v4\w32_regex_traits.hpp, line 545+15 byte(s) 001B:01EBF7A6 test.exe, boost::w32_regex_traits<wchar_t>::w32_regex_traits<wchar_t>()+22 byte(s), h:\backup\boost_1_33_1\boost\regex\v4\w32_regex_traits.hpp, line 564+22 byte(s) 001B:01EBF72F test.exe, boost::regex_traits<wchar_t,boost::w32_regex_traits<wchar_t> >::regex_traits<wchar_t,boost::w32_regex_traits<wchar_t> >()+15 byte(s), h:\backup\boost_1_33_1\boost\regex\v4\regex_traits.hpp, line 68+15 byte(s) 001B:01EBF70F test.exe, boost::regex_traits_wrapper<boost::regex_traits<wchar_t,boost::w32_regex_traits<wchar_t> > >::regex_traits_wrapper<boost::regex_traits<wchar_t,boost::w32_regex_traits<wchar_t> > >()+15 byte(s), h:\backup\boost_1_33_1\boost\regex\v4\regex_traits.hpp, line 162+15 byte(s) 001B:01EBF44A test.exe, boost::re_detail::regex_data<wchar_t,boost::regex_traits<wchar_t,boost::w32_regex_traits<wchar_t> > >::regex_data<wchar_t,boost::regex_traits<wchar_t,boost::w32_regex_traits<wchar_t> > >()+74 byte(s), h:\backup\boost_1_33_1\boost\regex\v4\basic_regex.hpp, line 54+74 byte(s) 001B:01EBE8BF test.exe, boost::re_detail::basic_regex_implementation<wchar_t,boost::regex_traits<wchar_t,boost::w32_regex_traits<wchar_t> > >::basic_regex_implementation<wchar_t,boost::regex_traits<wchar_t,boost::w32_regex_traits<wchar_t> > >()+15 byte(s), h:\backup\boost_1_33_1\boost\regex\v4\basic_regex.hpp, line 85+15 byte(s) 001B:01EB29E5 test.exe, boost::basic_regex<wchar_t,boost::regex_traits<wchar_t,boost::w32_regex_traits<wchar_t> > >::do_assign()+101 byte(s), h:\backup\boost_1_33_1\boost\regex\v4\basic_regex.hpp, line 517+34 byte(s) 001B:0152E48B test.exe, boost::basic_regex<wchar_t,boost::regex_traits<wchar_t,boost::w32_regex_traits<wchar_t> > >::assign()+27 byte(s), d:\usr\local\include\boost\regex\v4\basic_regex.hpp, line 255 001B:0152E2EA test.exe, boost::basic_regex<wchar_t,boost::regex_traits<wchar_t,boost::w32_regex_traits<wchar_t> > >::assign()+42 byte(s), d:\usr\local\include\boost\regex\v4\basic_regex.hpp, line 240 Using boost 1_33_1 Thanks in advance. Alan

2 9