- Boost - lists.preview.boost.org

Re: [boost] [Bind] How do I get bind to deduce the return type of for_each?
by Thomas Jordan 20 Apr '10

20 Apr '10

Thomas Jordan wrote: > [snip] > Thanks for the suggestion, Roland, I am sure you could get something like this to work easily enough. However, if I understand correctly your suggestion involves defining a separate functor - myClass - to take the vocType's, and which I guess wraps the inner call to for_each. I had hoped for a more generic solution which doesn't involve the creation of new functors. I was hoping I could accomplish the objective of passing an algorithm into an algorithm jgenerically, just doing everything at point of call using just Boost.bind, the std::algorithms (wrapped) and using if necessary some boost.function functors to help type deduction. Are we saying this isn't possible? > Roland Bock replied: ************************************ Hi Thomas, we don't say it isn't possible :-) Here you go: // ----------------------------------------------------------- #include <boost/bind.hpp> #include <boost/bind/protect.hpp> #include <boost/function.hpp> #include <vector> #include <iostream> using namespace std; using namespace boost; int initValue = 0; class myClass { public: myClass(): mValue(initValue) {} myClass(const myClass& rhs): mValue(initValue++) { } void func() { cout << mValue << endl; } private: int mValue; }; typedef vector<myClass> vocType; typedef vector<vocType> vovType; int main() { vovType vov(10, vocType(10, myClass())); for_each(vov.begin(), vov.end(), bind(for_each< vocType::iterator, function<void (myClass&)> >, bind<vocType::iterator>(&vocType::begin, _1), bind<vocType::iterator>(&vocType::end, _1), protect(bind(&myClass::func, _1)) ) ); } // ----------------------------------------------------------- Please let me know if this is working for you. Regards, Roland ************************************************************** Thanks a lot, Roland, this looks good. I felt there must be some way to do it, but it was just beyond my grasp. Always learning! Regards, Tom.

2 1

[config] Compiler defects value-initialization
by Niels Dekker - address until 2010-10-10 19 Apr '10

19 Apr '10

The Config/trunk regression page currently shows some detailed information of various compiler defects regarding value-initialization: http://www.boost.org/development/tests/trunk/developer/config_.html If anyone wants to have a look at these results, please do so quickly! The output is from boost_no_complete_value_initialization::test(), which tests whether a specific compiler should have a new defect macro defined, BOOST_NO_COMPLETE_VALUE_INITIALIZATION. In a few days, I'm planning to add this definition to the Boost Config files of those compilers [Boost #4080], and then the test output will disappear automatically. According to the current test results, two compilers do an excellent job w.r.t. value-initialization: Intel (10.1, 11.0, 11.1) on Mac OS X, and GCC 4.4.3 (both on Linux and Windows). Compilers that don't completely do value-initialization include Microsoft Visual C++ (including msvc-10.0), Borland (including CodeGear 2010), Sun 5.10, and IBM XL V10.1. The MSVC defect was reported back in 2005 [Visual Studio #100744]. I recently reported the value-initialization defects I encountered on Embarcadero CodeGear [Embarcadero #83751, #83851] and IBM XL. The Windows version of Intel 11.1 doesn't do so well either, according to results from Huang-Vista-x86_32_intel. I still wonder why, because on Mac OS X, Intel does so well. GCC also has regression failures w.r.t. value-initialization, but those are only on earlier GCC versions, like gcc-4.2.4 and gcc-4.3.4. The last GCC bug in this area, AFAIK, [GCC #30111] was fixed for GCC 4.4. As far as I have seen, any compiler supports value-initialization of integers, floating point numbers and pointers correctly. However, problems occur for structs, classes, and arrays. Objects of those types may be left partially or entirely uninitialized, when they should have been value-initialized, depending on the compiler. I hope to have the test and the defect macro included with Boost 1.44. Please let me know if you have any comment or question about them. https://svn.boost.org/svn/boost/trunk/libs/config/test/boost_no_com_value_i… Kind regards, Niels References: [Boost #4080] "Various compilers need BOOST_NO_COMPLETE_VALUE_INITIALIZATION", https://svn.boost.org/trac/boost/ticket/4080 [Visual Studio #100744] "Value-initialization in new-expression", reported by Pavel Kuznetsov: https://connect.microsoft.com/VisualStudio/feedback/details/100744 [Embarcadero #83751, #83851] Two value-initialization bugs I recently reported: http://qc.embarcadero.com/wc/qcmain.aspx?d=83751 http://qc.embarcadero.com/wc/qcmain.aspx?d=83851 [GCC #30111] "Value-initialization of POD base class doesn't initialize members", reported by Jason Merrill: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30111 -- Niels Dekker http://www.xs4all.nl/~nd/dekkerware Scientific programmer at LKEB, Leiden University Medical Center

1 0

Re: [boost] [Bind] How do I get bind to deduce the return type offor_each?
by Thomas Jordan 19 Apr '10

19 Apr '10

Thomas Jordan wrote: > Thanks a lot for the suggestion, I did take a look at Lambda library, and > I saw that it used some extra type information in its STL > algorithm wrappers (the 'sig') to help it figure out the return types. > However, I am against using the Lambda library > for other reasons, I only want to use the bind library. I'd appreciate > some specific advice on how to get the type deduction > with the Boost.bind library. Or is this just not possible with > Boost.bind? Peter Dimov replied: ----------------- It's not. Boost.Bind only supports function objects with a specific, fixed type. There is no mechanism to tell it that the return type of struct myForEach { template <typename II, typename F> F operator()(II begin, II end, F function) const { return std::for_each(begin, end, function); } }; is the same as its third argument. In this specific case I'd just use struct myForEach { typedef void result_type; template <typename II, typename F> void operator()(II begin, II end, F function) const { std::for_each(begin, end, function); } }; -------------------- Thanks, Peter, and thanks to everyone else who replied, for their helpful suggestions. FWIW, I'm putting together a presentation for my colleagues, to show the facilities for higher-order programming in STL and Boost, and I wanted to show a couple of 'out-there' examples to illustrate their power. I'm a bit of an arriviste and my C++ is 'improving,' but I'm really impressed that you can do functional-style programming so nicely in C++. Regards, Tom.

2 1

libzeep
by Maarten L. Hekkelman 19 Apr '10

19 Apr '10

As I announced earlier, I've released a library that can be used to create SOAP servers. Since this code relies heavily on XML, I've implemented a full XML parser and XPath implementation as well. I've read a bit in the discussion on this forum regarding the implementation of XML parsers and I get the feeling some don't fully appreciate the amount of work that goes into writing a validating parser. There really is more to XML than the characters < and >. :-) If there's a DOCTYPE, the results of parsing a file can be surprising since the DTD can e.g. specify default attribute values. To test libzeep I'm using the 1808 test files provided by the w3c organisation. Of these I only test against 1490 since the others only check unicode characters that are allowed since XML version 1.1. Of the remaining 1490 only 14 produce dubious output, I'm not really sure if these tests are wrong or that my code is incorrect. Anyway, libzeep performs quite nicely. The code has not yet been profiled but I've been able to replace libxml2 in all my projects and see hardly any performance degradation and my code looks much better now. All in all, I think libzeep is quite feature complete, robust and performs nicely. I've released the code and minimal documentation at http://www.cmbi.ru.nl/libzeep Now suppose people here are interested in this library, I'm willing to spend some time to upgrade the code to boost quality standards and write more documentation. And if the boost community prefers another approach I'm willing to provide help based on my recent experience. I'm looking forward to your feedback. -maarten

9 15

[exception] [shared_ptr] ADL problem with msvc 10
by Steven Watanabe 19 Apr '10

19 Apr '10

AMDG I just tried to compile the following #include <boost/exception_ptr.hpp> void f() {} msvc 10 complains, 1>c:\boost\trunk\boost\smart_ptr\detail\sp_convertible.hpp(48): error C2660: 'f' : function does not take 1 arguments 1> c:\boost\trunk\boost\smart_ptr\detail\sp_convertible.hpp(66) : see reference to class template instantiation 'boost::detail::sp_convertible<Y,T>' being compiled 1> with 1> [ 1> Y=error_info_tag_t, 1> T=boost::exception_detail::error_info_base 1> ] 1> c:\boost\trunk\boost\exception\info.hpp(171) : see reference to class template instantiation 'boost::detail::sp_enable_if_convertible<Y,T>' being compiled 1> with 1> [ 1> Y=error_info_tag_t, 1> T=boost::exception_detail::error_info_base 1> ] 1> c:\boost\trunk\boost\exception\info.hpp(188) : see reference to function template instantiation 'const E &boost::exception_detail::set_info<E,boost::tag_original_exception_type,const type_info*>(const E &,const boost::error_info<Tag,T> &)' being compiled 1> with 1> [ 1> E=boost::unknown_exception, 1> Tag=boost::tag_original_exception_type, 1> T=const type_info * 1> ] 1> c:\boost\trunk\boost\exception\detail\exception_ptr.hpp(132) : see reference to function template instantiation 'const boost::unknown_exception &boost::operator <<<boost::unknown_exception,boost::tag_original_exception_type,const type_info*>(const E &,const boost::error_info<Tag,T> &)' being compiled 1> with 1> [ 1> E=boost::unknown_exception, 1> Tag=boost::tag_original_exception_type, 1> T=const type_info * 1> ] 1> c:\boost\trunk\boost\exception\detail\exception_ptr.hpp(111) : see reference to function template instantiation 'void boost::unknown_exception::add_original_type<std::exception>(const E &)' being compiled 1> with 1> [ 1> E=std::exception 1> ] This appears to be because type_info is defined in the global namespace, so ADL for boost::error_info<boost::tag_original_exception_type, const type_info *> picks up the global f. I don't have a fix for this yet. In Christ, Steven Watanabe

3 5

Fwd: [Boost-users] [Review] [ITL] ITL formal review results
by Joachim Faulhaber 19 Apr '10

19 Apr '10

---------- Forwarded message ---------- From: Joachim Faulhaber <afojgo(a)googlemail.com> Date: 2010/4/19 Subject: Re: [Boost-users] [Review] [ITL] ITL formal review results To: boost-users(a)lists.boost.org Hi Hartmut, list, 2010/4/18 Hartmut Kaiser <hartmut.kaiser(a)gmail.com>: > Hi all, > > The formal review of the Interval Template Library (ITL) written by Joachim > Faulhaber started February 18th and ended March 7th, 2010. We saw a lively > discussion resulting in 14 votes: 10 people voted unconditionally YES, 3 > voted conditionally YES, and 1 reviewer voted NO. > > The overwhelming majority of the votes was YES which reflects the overall > discussion and the general consensus of this library being worth to be > included into Boost. > > Based on this result and the discussions we saw the Interval Template > Library is now formally accepted into Boost. > > > Detailed results > ---------------- > > Pros: > > Almost all reviewers highlighted the general usefulness of the library. The > more experience the reviewers had with the library in real world > applications the more they emphasized its usefulness. Here are some quotes: > - "ITL solved this problem for me, in a way that honestly freed me from > having to think about a lot of the unsavory low-level details." > - " Until now, we only used the library for intervals of date-times (coded > as integers), but I'm sure, that its usefulness goes far beyond." > - " Very useful. I mentioned two projects where the library would have > helped me if it had been into Boost earlier, and I'm considering rewriting > them such that the problems make use of the library, and simplify them in > that way." > > The comments on the quality of the documentation are unanimous: "impressive > and quite complete", "I couldn't ask for more". It seemed to be generally > helpful to understand the concepts of the library and to get started. Some > people asked to add more simple quick-start examples to the documentation > and the distribution. > > Overall, the library is mature and easy to use. All reviewers actually > utilizing the ITL library for real world use cases reported they were able > to start quickly and without problems. > > All reviewers using ITL in real world applications stated that no > performance problems were encountered. This is important to note as the NO > vote was based on the current lack of a interval tree implementation, which > was considered to result in suboptimal performance for certain use cases. > > > Cons: > > Some aspects of the design have been criticized: "OO-type design decisions", > "fat 'one size fits all'-interval class template", and "incomplete > extraction of global functions" are the major points of critique. These > points have real merit. In order to make the design and interface more > flexible and more durable these have to be rectified before the final > inclusion of the library into Boost's code base. Joachim already agreed to a > list of things to change addressing those problems. > > For certain use cases, specifically for interval map of collections, the > current implementation has suboptimal complexity characteristics that leads > to O(n^2) space usage in the worst case. OTOH, for the majority of > applications of the library the worst case scenario seems to be (reportedly) > irrelevant. This issue has been discussed at length and Joachim plans to add > an implementation with a better worst case performance of the affected class > templates as later optimizations. This is not considered to be a > precondition to full inclusion into Boost's code base as it is not > anticipated to cause any interface changes. > > Last but not least people suggested to change the name of the library as > having the word template in the name does not carry any useful information. > Joachim already agreed to this. > > Regards Hartmut > Review Manager Thank you, Hartmut, for summarizing the review and declaring the results. I am of course happy to hear that my library of interval containers is now accepted. Concerning the review itself, I'd like to say that it was a very valuable experience for me. I definitely learned a lot during the process. So I'd like to thank all the reviewers and other participants in the discussion for taking so much time to examine my project and to share their knowledge and assessments. I'd like to emphasize two points: (1) For me as contributor is has been very rewarding to see, that my library has found quite a few users who not only use the ITL in real world applications but also confirm the usefulness of its concepts and patterns (e.g. aggregate on overlap), that simplify writing programs for problems that reoccur in a variety of problem domains. It was this basic feeling of usefulness that made me undertake the journey of boostifying, refactoring, documenting, polishing and submitting my code, which was much more work than I initially expected. But reading those reviews made me feel that it was worth the effort. So special thanks to my "real world"- users among the reviewers: Peter Wuttke, Eric Jonas, Michael Caisse and Jeff Flinn. (2) A review on the boost list is probably a challenge for most contributors. The important part is to encounter once own limitations and blind spots. Because these are the fields where one can learn most. We find these kinds of (at first) mostly unpleasant information within a boost review, when fellow developers examine the project closely and share their view on its flaws and problems. I have learned very much from that and I am currently really having fun applying those improvements to the library. So special thanks for sharing critique and objections to Phil Endecott, Luke Simonson, Jeff Flinn, John Reid and Barend Gehrels. And last but not least, I'd like to thank Rob Stewart who gave me feed back about some lingual pitfalls and oddities offlist. Very nice and helpful :) I have reworked the design on the interval concept already. I hope to be able to complete the discussed changes and improvements, as summarized by Hartmut above, within a few weeks after BoostCon2010. Cheers Joachim

1 0

[result_of] propose: change of maintainer
by Eric Niebler 19 Apr '10

19 Apr '10

Daniel Walker has volunteered to take over maintainer duties of utility/result_of from Doug Gregor, and Doug has agreed. Does anybody object? If not, I'll update the maintainers list. -- Eric Niebler BoostPro Computing http://www.boostpro.com

4 5

[RangeEx] Where is the current version?
by Mathias Gaunard 19 Apr '10

19 Apr '10

Where is the current version (or a fairly recent version) of RangeEx? I can't find anything on the trunk, the sandbox or the vault.

5 13

How to manage Graph Property ?
by nguyen vu tri 19 Apr '10

19 Apr '10

Hi everyone, I really need help to figure out the following problem. -------------------------------------------------------------------------------- First, I create a Vertex Property: typedef property < vertex_index_t, int> VertexProperties; Then, I create an adjacency graph type: typedef adjacency_list < vecS, vecS, directedS, VertexProperties > Graph; Now I can call: VertexProperties V1; --------------------------------------------------------------------------------- My question is: Is there anyway that I can access *VertexProperties *through * Graph* to create the same variable *V1* ?. Thanks, in advance, for your time. I appreciate all suggestions, Tri Nguyen.

3 5

Requesting permission to merge r61326 into release branch
by Jeremiah Willcock 18 Apr '10

18 Apr '10

This change is a one-line fix to a trivial bug where the wrong number of arguments was used in a function call. May I please merge it so it gets into 1.43.0? -- Jeremiah Willcock

3 12

Idea: Boost.Allocator
by joel falcou 18 Apr '10

18 Apr '10

I recently had to use Boost Iterator Facade and its relatives and found the idea great. It occured to me whiel lookign at my X different, hand written allocaotrs for various project that maybe such a system for writing std allocator could be great. Buildign a new allcoator will just be impelemnt some allocator_facade<> adn fill some small scale methods. Moreover, it could be the opportunity to add new allocator concept like allocator supporting resize calls, allcoator with state, allcoator with a allocated() method etc... and reality-check them in the boost framework. How does it sounds ? -- ___________________________________________ Joel Falcou - Assistant Professor PARALL Team - LRI - Universite Paris Sud XI Tel : (+33)1 69 15 66 35

4 5

Re: [boost] [GGL] [geometry] Inexplicable speed benefit when using Visual C++ 2010
by Stephan T. Lavavej 18 Apr '10

18 Apr '10

[Christian Buchner] > We found that GCC 4.4 on Linux was about 100% faster than Visual C++ > 2008 on Linux without modifying the code. Wow, I didn't know that VC9 could target that platform. ;-) > we attributed much of the performance difference to sub-optimal memory > heap management of Visual C++ 2008. VC's default implementation of ::operator new() calls malloc(), which calls HeapAlloc() from the Windows API. HeapAlloc()'s implementation is mostly a mystery to me, but there are a couple of things about it that you should probably be aware of. First, on WinXP and higher (note that VC9 supported targeting Win2K, but VC10 doesn't), Windows implements the Low Fragmentation Heap (LFH). The LFH services "small" allocations (definitely sub-KB; I'd have to ask around in order to figure out the precise limit) from buckets, so applications that allocate lots of small chunks of memory (like nodes) can benefit significantly from the LFH. I believe it performs other wizardry which I'm not aware of. However, on some platforms, the LFH is not enabled by default. You can request it by calling HeapSetInformation() on the CRT heap. There are two situations where the LFH is enabled by default. First, VC enables the LFH for its CRT heap when targeting x64. (For obscure reasons, we can't do this for x86.) Second, WinVista and higher automagically enable the LFH when they detect allocation patterns that would benefit from this. I've spoken to the LFH's maintainers, and they say that this automagic machinery is sufficiently smart, that enabling the LFH manually is no longer necessary (i.e. they have never seen that produce an observable benefit). > Then we tried recompiling the project with Visual C++ 2010 Ultimate > Release Candidate (RC). The speed gain of the algorithm was 900% (not > joking) and the results still appear to be correct. This greatly amuses me, as I talked about seeing order-of-magnitude performance improvements but never expected to actually see one in the real world. This is almost certainly due to rvalue references, as nothing else that we did could possibly have had so large of an effect. VC10 implemented rvalue references (v2, but not the stuff in the FCD that automatically generates move ctors/assigns), and we updated the Standard Library to take advantage of them (both by providing move ctors/assigns on Standard Library types like vector, and by taking advantage of move ctors/assigns during operations like vector reallocation). > Is anyone else seeing similar speedups in boost or in the geometry > library when compiling with Visual C++ 2010 RC (HINT: it's a free > download, so anyone can try it out until end of June 2010). Note that VC10 RC is perfectly representative of VC10 RTM. The compiler and linker are unchanged, and the Standard Library received exactly one bugfix (for obnoxious compiler errors in shared_ptr). Also note that while GCC 4.3 and higher support rvalue references (v1 in 4.3 and 4.4, v2 in 4.5), they are not enabled by default. You must compile with either -std=c++0x or -std=gnu++0x in order to activate their C++0x mode. I'd be interested to learn how VC10 fares against GCC in C++0x mode. (I'm unsure as to when and to what extent rvalue references were applied to GCC's Standard Library implementation libstdc++. As GCC 4.5 was released mere days after VC10, that would generate the most fair comparison.) About _SECURE_SCL, the worst performance penalty that I've ever seen it exact is 2x. It could have been responsible (along with allocator mumbo-jumbo) for the 100% difference you observed between GCC 4.4 and VC9, but not for the 900% difference between VC9 and VC10 (unless you have discovered a truly astounding pathological case). _SECURE_SCL (now combined with _HAS_ITERATOR_DEBUGGING into _ITERATOR_DEBUG_LEVEL) in VC10 is now disabled by default in release mode. (In debug mode, _HAS_ITERATOR_DEBUGGING, aka _ITERATOR_DEBUG_LEVEL=2, is still enabled by default - it can affect performance significantly, but provides exhaustive correctness checks, and debug performance isn't especially important unless it's 1000x slower and renders the program too slow to debug.) VC10's linker now deterministically detects when you're mixing translation units compiled with different settings of _ITERATOR_DEBUG_LEVEL, so that (combined with the new default of 0 in release mode) will put an end to the bad old days of incomprehensible ODR violations triggered by attempting to disable this machinery in some but not all libraries. Do note that mixing major compiler versions (e.g. VC9 and VC10) is still completely forbidden when you're using the C++ Standard Library, as we break binary compatibility between every major version and will continue to do so for the foreseeable future. Unfortunately, the linker's new feature (#pragma detect_mismatch) is unable to detect VC9 and VC10 mixing, so you'll just have to be careful. (The machinery is in place for us to detect VC10 and VC11 mixing.) [Barend Gehrels] > I've asked last year during BoostCon to Microsoft, present there, if > they knew this issue, but apparently they didn't, and told me it would > surprise him because the compiler basically was the same. (That was me.) > When I used after that once the VC 2008 command line compiler (so not > from Visual Studio) the problem disappeared. So it was fast. So it was > not the compiler itself, it was some setting in the IDE or VPROJ. I've > never managed to find which setting, though I studied it carefully. According to my understanding, the VS 2008 IDE had a bug when upgrading VS 2005 projects, where optimization settings would be lost. I'm unsure of what the exact symptoms of the bug looked like (I thought it was just the /O options), but your experience (that it disappeared when you used the command line) perfectly fits with this hypothesis. Alternatively, you could create a VS 2008 project from scratch. I believe that VS 2010's project system (which underwent a massive overhaul) does not suffer from this bug when upgrading either VS 2005 or VS 2008 projects, but I don't know what happens when you take a project that was damaged by the VS 2005 to VS 2008 upgrade, and then upgrade it to VS 2010. I suspect that in that case, the damage persists. My understanding of this is vague because I don't use IDE build systems. Stephan T. Lavavej Visual C++ Libraries Developer

2 1

[call-traits][param_type] why is sizeof(void*) chosen as the limit for passing by value?
by Thorsten Ottosen 17 Apr '10

17 Apr '10

Hi Boosters, It seems to me that many other slightly larger types could benefit from pass by value. For example, I rarely write foo( const double& ); but always foo( double ); So param_type<T>::type don't even follow this guideline. I tried a simple example program for the auto_buffer (vector like) class I'm implementing: #include <boost/auto_buffer/auto_buffer.hpp> int main() { boost::auto_buffer<double> buf( 2001u ); buf.push_back(42.); } When I pass by value in push_back(), the assembler is somewhat different, and as far as I can tell, better. Basically my compiler (vc9) can inline the load of 42. into push_back() whereas in the call by reference, the parameter is passes by a pointer (in a register). In the by-value version the compiler is able to optimize away completely the call to alllocate and delete memory whereas this is not so for the by-reference version. This makes me wonder why we shouldn't expect e.g. std::pair<int,int> and std::bitset<64> to be easily passable in registers. With this in mind, I think we should consider changing the limit for param_type to sizeof(long double) or even 2*sizeof(int). Of course, we should only pass types with a trivial assignment operator by value. Any thoughts? -Thorsten

4 4

Re: [boost] [Bind] How do I get bind to deduce the return type of for_each?
by Thomas Jordan 17 Apr '10

17 Apr '10

> Message: 8 > Date: Thu, 15 Apr 2010 10:51:27 +0100 > From: "Sylvester-Bradley, Gareth" > <Gareth.Sylvester-Bradley(a)eu.sony.com> > To: <boost(a)lists.boost.org> > Subject: Re: [boost] [Bind] How do I get bind to deduce the return > type offor_each? > Message-ID: > <84883B934769D3428C4AE2E403B188800A1A0F9A(a)GBISE0BASMSX02.eu.sony.com> > Content-Type: text/plain; charset="us-ascii" > >> I have been trying to use Boost.bind to create an 'STL algorithm > function >> object' to pass into another, 'higher order,' STL algorithm (e.g., to > pass >> a for_each into a for_each). However, I am struggling to get bind to >> deduce the correct return type of the for_each function object. > > The following might help: > > http://www.boost.org/doc/libs/1_42_0/doc/html/lambda/le_in_details.html# > lambda.nested_stl_algorithms > > > Best regards, > Gareth > Thanks a lot for the suggestion, I did take a look at Lambda library, and I saw that it used some extra type information in its STL algorithm wrappers (the 'sig') to help it figure out the return types. However, I am against using the Lambda library for other reasons, I only want to use the bind library. I'd appreciate some specific advice on how to get the type deduction with the Boost.bind library. Or is this just not possible with Boost.bind?

4 3

(no subject)
by Dan Jiang 16 Apr '10

16 Apr '10

Hi All, I have a question regarding CSR graph. Does anyone know if a CSR graph can be used as input to push_relabel_max_flow or edmonds_karp_max_flow algorithm in BOOST? The existing examples only use adjacency_list with the maximum flow algorithms. I need to use CSR graph with the max flow implementations, but do not know how and if it is feasible at all. If answer is yes, can anyone give a simple example? I am having trouble in setting capacity map and reverse_edge map in CSR before passing it to the max flow algorithms. -Thanks a lot for your time. Dan Jiang _________________________________________________________________ Live connected. Get Hotmail & Messenger on your phone. http://go.microsoft.com/?linkid=9724462

2 10

[xint] Question about suitability, portability, and "Boostiness"
by Chad Nelson 16 Apr '10

16 Apr '10

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Right now, the XInt library uses a pointer to a (privately defined) struct. The struct has several items, including a small array of "quick digits" and a pointer to a dynamically allocated array of digit_t types, both for containing the magnitude of the integer. While trying to find a more efficient way to store things, I came up with this: struct new_data_t { size_t used, allocated; // (other data items) digit_t digits[1]; // Last item in the struct }; It's an old C trick, apparently legitimized in the C99 standard as the "struct hack". For those not familiar with it, the idea is that I'd allocate a single array of digit_t types, of the required size plus sizeof(new_data_t), then just typecast it as a pointer of type new_data_t. Does anyone know if there's any reason not to do this? Maybe some portability or alignment problem with it? - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.10 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkvD3ZQACgkQp9x9jeZ9/wQLdQCgklN2Xcs0mDAGhsy4n3TX/Bgw JVoAoK+/YEoawXT7Yd0R3++eWLPYZhjr =Jx8O -----END PGP SIGNATURE-----

4 15

Re: [boost] How to construct a reverse_edge_map from CSR
by Dan Jiang 16 Apr '10

16 Apr '10

Hi Jeremiah, Here is the code for this error. Hope it is more readable. typedef compressed_sparse_row_graph<directedS> Traits; struct EdgeProp{ float capacity; float residual_capacity; Traits::edge_descriptor reverse_edge; }; typedef compressed_sparse_row_graph<directedS, property<vertex_index_t, DWORD32>, EdgeProp, // bundled property no_property, // Graph Property DWORD32, // Vertex Type DWORD32> // EdgeIndex Type BOOST_Graph; Errors: C:\Program Files (x86)\boost\boost_1_42\boost/graph/compressed_sparse_row_graph.hpp(1321) : error C2780: 'V boost::target(const incidence_graph_archetype<Vertex,Directed,ParallelCategory,Base>::edge_descriptor &,const boost::incidence_graph_archetype<Vertex,Directed,ParallelCategory,Base> &)' : expects 2 arguments - 1 provided C:\Program Files (x86)\boost\boost_1_42\boost/graph/graph_archetypes.hpp(64) : see declaration of 'boost::target' .\NetFlow.cpp(209) : see reference to function template instantiation 'std::pair<_Ty1,_Ty2> boost::edge<boost::directedS,boost::property<Tag,T>,EdgeProp,boost::no_property,unsigned int,DWORD32>(Vertex,Vertex,const boost::compressed_sparse_row_graph<Directed,VertexProperty,EdgeProperty,GraphProperty,Vertex,EdgeIndex> &)' being compiled with [ _Ty1=boost::detail::csr_edge_descriptor<size_t,size_t>, _Ty2=bool, Tag=boost::vertex_index_t, T=DWORD32, Vertex=unsigned int, Directed=boost::directedS, VertexProperty=boost::property<boost::vertex_index_t,DWORD32>, EdgeProperty=EdgeProp, GraphProperty=boost::no_property, EdgeIndex=DWORD32 ] C:\Program Files (x86)\boost\boost_1_42\boost/graph/compressed_sparse_row_graph.hpp(1321) : error C2780: 'Vertex boost::target(compressed_sparse_row_graph<Directed,VertexProperty,EdgeProperty,GraphProperty,Vertex,EdgeIndex>::edge_descriptor,const boost::compressed_sparse_row_graph<Directed,VertexProperty,EdgeProperty,GraphProperty,Vertex,EdgeIndex> &)' : expects 2 arguments - 1 provided Error line is: if (target(*range.first) == j) C:\Program Files (x86)\boost\boost_1_42\boost/graph/compressed_sparse_row_graph.hpp(1241) : see declaration of 'boost::target' C:\Program Files (x86)\boost\boost_1_42\boost/graph/compressed_sparse_row_graph.hpp(1321) : error C2780: 'Vertex boost::target(const boost::detail::edge_base<Directed,Vertex> &,const boost::adjacency_list<OutEdgeListS,VertexListS,DirectedS,VertexProperty,EdgeProperty,GraphProperty,EdgeListS> &)' : expects 2 arguments - 1 provided C:\Program Files (x86)\boost\boost_1_42\boost/graph/adjacency_list.hpp(530) : see declaration of 'boost::target' C:\Program Files (x86)\boost\boost_1_42\boost/graph/compressed_sparse_row_graph.hpp(1321) : error C2780: 'filtered_graph_base<G>::vertex_descriptor boost::target(filtered_graph_base<G>::edge_descriptor,const boost::filtered_graph_base<G> &)' : expects 2 arguments - 1 provided: Error line is: if (target(*range.first) == j) > > Could you please reformat your code to be more readable? What is the > exact type of your graph, and what are the definitions of the vertex and > edge bundled property classes? > > -- Jeremiah Willcock > _______________________________________________ > Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost _________________________________________________________________ Live connected. Get Hotmail & Messenger on your phone. http://go.microsoft.com/?linkid=9724462

2 1

How to construct a reverse_edge_map from CSR
by Dan Jiang 16 Apr '10

16 Apr '10

Hi All, I am having difficulty in constructing a reverse_edge_map from an existing CSR. My CSR was created as "edges_are_unsorted", I need to create a reverse_edge_map out of it? Here is my attempt:1 BGL_FORALL_EDGES(e, g, BOOST_Graph)2 {3 // Get source and target of the edge4 BOOST_Graph::vertex_descriptor src = boost::source(e, g);5 BOOST_Graph::vertex_descriptor dst = boost::target(e, g);678 // Get reverse edge9 graph_traits<BOOST_Graph>::out_edge_iterator ei, ei_end;10 for (tie(ei, ei_end) = edge_range(dst, src, g); ei != ei_end; ++ei) 11 {12 rev[*e] = *ei;13 break; // I know there is only one reverse edge in my graph14 } 15 } I got compile error on line 10: error C2784: 'std::pair<Config::out_edge_iterator,Config::out_edge_iterator> boost::edge_range(Config::vertex_descriptor,Config::vertex_descriptor,const boost::adj_list_helper<Config,Base> &)' : could not deduce template argument for 'const boost::adj_list_helper<Config,Base> &' from 'BOOST_Graph' where BOOST_Graph is a CSR graph that has been instantiated as "edges_are_unsorted" prior to the loop. Any help is appreciated. -Thanks, Dan _________________________________________________________________ Got a phone? Get Hotmail & Messenger for mobile! http://go.microsoft.com/?linkid=9724464

2 1

Re: [boost] Crypto Proposal
by Chad Seibert 16 Apr '10

16 Apr '10

Hello, > Does this mean you will be converting the source-code of Botan to Boost > standards or you are going to wrap it? > 1. If it is conversions two issues may rise: > a) License Botan is licensed under BSD license with is different from > Boost and all the code you will write for boost would not have > correct license. > b) Conversion to Boost means fork... How do you expect to synchronize > changes in two libraries and most important security updates. > This means lots of work in the live cycle of Boost.Botan I'll fork it, as stated in my proposal (which I sent sometime after the abstract). It'll be relicensed under BSL. As for synchronization, this will have to be done by hand (which I will do for some time). > Additional points: > - Botan uses GNU gmp library licensed under LGPL... Does it fit to > Boost licensing guidelines? It doesn't require gmp and is perfectly capable of working without it. It's available as a plugin, but a default implementation is already included. > - I think that you should be really specific what would be the advantage > of using Boost.Botan library over original Botan one or OpenSSL that > Boost.Asio uses. Here are some: * Tighter integration with Boost (ASIO, and possibly iostreams) * Some functions are considerable faster (such as RSA, which the maintainer purports to be several times faster than OpenSSL. SHA-1 is SSE2 optimized). * There is plugin support for OpenSSL, so ASIO would be modified to use the plugin system (which would use the default implementation or OpenSSL). > You might want to consider adding some discussion to your proposal about the > crypto library in the vault. What features are in the vault Crypto that > might be useful? That aren't useful? Why do you feel that Botan is a better > starting point. The crypto library in the vault contains mostly hash algorithms, which Botan already contains (and some of them e.g. SHA-1 have a SSE optimized version). And Botan contains better documentation and testing. Also, Botan was engineered mostly by a security expert, meaning it is likely to be more secure. It is also being maintained, so security and feature patches will be made. > Your proposal is very ambitious! IMHO, that's not doable in full over the > summer. If you trimmed it down into a more focused feature set (for instance > replacing SSL in ASIO, or adding TLS to ASIO) it would give you a more > realistic chance to finish what you are suggesting. It is very ambitious! But as I say in my draft, it'll be done in two parts. I don't think that porting is unrealistic for the summer part of the project. Many thanks for the feedback, Chad Seibert _________________________________________________________________ The New Busy is not the too busy. Combine all your e-mail accounts with Hotmail. http://www.windowslive.com/campaign/thenewbusy?tile=multiaccount&ocid=PID28…

3 6

Re: [boost] Crypto Proposal
by Chad Seibert 16 Apr '10

16 Apr '10

Here's a response to a question asked on the private review system: The design and architecture is based on dynamic polymorphism, for better or worse. In the process of porting it to Boost.Botan, it would be made static. On the mailing list, someone created a simple project that creates a certificate and the exe grew from 40kb to 1mb. Having static polymorphism would solve this problem. Also, we won't have to pay the runtime penalties for dp (especially since it's not needed - something that Boost libraries have shown time and time again). Looking at other libraries under similar licenses yielded similar results. Crypto++ also uses DP (and has even larger hierarchies) and for simple uses, the entire library get's built and included with project. For example, http://www.cryptopp.com/docs/ref/class_s_h_a1.html. SP will solve this problem, and Botan uses less DP which should make it easier to convert. I couldn't find a valid libtomcrypt homepage, so I don't know how it's structured. The interface of Botan is simple and intuitive. Looking at their sample programs (and other samples), there doesn't seem to be a simpler method to implement the various techniques and still remain flexible. Crypto++ samples seem to be a bit difficult to digest, requiring manual creation of secure memory blocks and ugly dynamic casting. More can be seen here: http://www.cryptopp.com/wiki/Diffie-Hellman. All in all, Botan has a simpler interface and a DP hierarchy that shouldn't be (as) difficult to convert to SP. I wanted to compare against libtomcrypt, but couldn't find a valid implementation. An example of how something might get ported would be the following. Botan.AES_128 has the inheritance hierarchy Botan->SymmetricAlgorithm->BlockCipher->AES->AES_128. Writing this as SP would look like the following (if I understand SP correctly): Before: class SymmetricAlgorithm { void set_key(...) } class BlockCipher: SymmetricAlgorithm { virtual void encrypt(...) virtual void decrypt(...) } class AES: BlockCipher { void encrypt(...); void decrypt(...); } class AES_128: AES { } There is no reason for AES. I'd first remove that class and have AES_128 derive from BlockCipher directly. Converting this to SP yields (sorry, I don't have a compiler to test this atm): template<class BlockCipher> struct SymmetricAlgorithm { void set_key_impl() { static_cast<*BlockCipher>(this)->set_key(); } } template <class AES_128> struct BlockCipher: SymmetricAlgorithm<BlockCipher>{ void set_key(); //More stuff } However, there is one concern. SymmetricAlgorithm is the base class of three major hierarchies: BlockCipher, MessageAuthenticationCode, and StreamCipher. If this inheritance hierarchy stays, it will mean lot's of template metaprogramming (some of which I don't know how to do). In any case, it's easier to work with than Crypto++. For example, SHA1 in Crypto++ has a hierarchy depth of 9; Botan 5. Hope this answers some questions! Glad you are interested in my work! Chad Seibert _________________________________________________________________ The New Busy is not the old busy. Search, chat and e-mail from your inbox. http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:…

4 3

space complexity of push_relabel_max_flow
by Dan Jiang 16 Apr '10

16 Apr '10

Hi All, I am a new BOOST user and like it very much. I have a question regarding space complexity of push_relabel_max_flow. The push_relabel_max_flow is very efficient compared to Edmond's and Karp. In my application, I need to deal with half a million nodes and half a billion arcs. It requires lots of ram (>= 6gb). Two questions: 1) How do I find out space used per node and per arc? 2) My network does not need any reverse edge (currently I set the capacity of reverse edge to 0), is there anyway to not supply reverse edges to save space? 3) Does push_relabel_algorithm dynamically allocates lots of memory (besides the ram required by the input graph, i.e., adjacency_list)? 4) Is it possible to implement custom file-based edge lists so that I could explicitly page to disk when not enough ram is available? How slower would it be? Thanks, Dan Jiang _________________________________________________________________ Hotmail & Messenger. Get them on your phone now. http://go.microsoft.com/?linkid=9724463

3 17

[Bind] How do I get bind to deduce the return type of for_each?
by Thomas Jordan 15 Apr '10

15 Apr '10

Hi, I have been trying to use Boost.bind to create an 'STL algorithm function object' to pass into another, 'higher order,' STL algorithm (e.g., to pass a for_each into a for_each). However, I am struggling to get bind to deduce the correct return type of the for_each function object. I include the relevant bits of the code below. class myClass { public: int func(){return mValue;} private: int mValue; }; //wrapper for STL for_each struct myForEach { template <typename II, typename F> F operator()(II begin, II end, F function) const { return std::for_each(begin, end, function); } }; typedef vector<myClass> vocType; typedef vector<vocType> vovType; //overloaded member functions vocType::begin & end typedef vocType::iterator (vocType::*fnPtr)(); typedef const vocType::iterator (vocType::*constFnPtr)() const; vovType vov(10, vocType(10, myClass())); main() { for_each(vov.begin(), vov.end(), bind< ? >(myForEach(), bind(static_cast<fnPtr>(&vocType::begin),_1), bind(static_cast<fnPtr>(&vocType::end),_1), protect(bind(&myClass::func, _1))) } I tried various things for bind<?>, but was only able to get the code to compile (eventually) on my Unix box when I substituted bind< boost::_bi::protected_bind_t<boost::_bi::bind_t<int, boost::_mfi::mf0<int, myClass>, boost::_bi::list1<boost::arg<1> (*)()> > > > for the bind<?>. I had guessed this might work from studying the compiler error messages. Obviously, this is not an ideal solution! Also, I only used the myForEach wrapper after having first attempted - and similarly failed - to bind the raw STL for_each. Is there any way I can help bind to deduce the correct return type - for either myForEach or std::for_each, or both? WIth Best Regards, Tom Jordan (Software Engineer)

3 2

Permission to merge Interprocess/Intrusive bugfixes for 1.43 in release branch?
by Ion Gaztañaga 15 Apr '10

15 Apr '10

Hi, I know it's a bit late, but I would like to ask if it's possible to merge Interprocess/Intrusive bug-fixes from trunk to release. They've been in trunk for some weeks and tests are ok. Best, Ion

5 8

[contract] with Boost.Parameter (was "Contract Programming Library")
by Lorenzo Caminiti 15 Apr '10

15 Apr '10

On Wed, Feb 17, 2010 at 4:05 AM, Andrzej Krzemienski <akrzemi1(a)gmail.com> wrote: >> > it is inevitable, etc., but.. read on. I know at least one library in >> > Boost that also spoils function declarations in order to provide >> > additional functionality: Concept Check library; they may be others >> > too (MPL?). >> > My suggestion is that if there are (or will be) libraries that require >> > spoiling function declarations, they should all provide the same >> > "spoiled" syntax. Otherwise I will be always asking "how do I declare >> > a function in this library?". It would be very convenient if Boost >> > provided one alternative function definition syntax that when used >> > would enable all its libraries to work. >> >> I agree. However, in the past I did look into harmonizing my library >> API with the ones of Boost.ConceptCheck and/or Boost.Parameter but it >> did not seem feasible... I will double check it. > > This is not only about clarity. As a super-correct programmer I may want to > apply both concept checking and pre-/post-conditions checking to my functions. > > Perhaps, if the 'compromise' syntax is possible, it requires changing > concept-checking library. I have verified that it is possible to use Boost.Parameter together with the current implementation of Boost.Contract. However, I have not yet verified compatibility with the entire set of Boost.Parameter features (template parameters, free-functions, etc). #include <boost/parameter.hpp> #include <boost/graph/depth_first_search.hpp> #include <contract.hpp> #include <iostream> namespace graphs { BOOST_PARAMETER_NAME(graph) BOOST_PARAMETER_NAME(visitor) BOOST_PARAMETER_NAME(root_vertex) BOOST_PARAMETER_NAME(index_map) BOOST_PARAMETER_NAME(color_map) struct g { CONTRACT_CLASS( (g) ) BOOST_PARAMETER_MEMBER_FUNCTION( (void), depth_first_search, tag, (required (graph, *) ) (optional (visitor, *, boost::dfs_visitor<>()) (root_vertex, *, *vertices(graph).first) (index_map, *, get(boost::vertex_index, graph)) (in_out(color_map), *, default_color_map(num_verticies(graph), index_map)) ) ) CONTRACT_FUNCTION( (public) (template)( (typename)(graph_type) (typename)(visitor_type) (typename)(root_vertex_type) (typename)(index_map_type) (typename)(color_map_type) ) (void) (depth_firt_search)( (graph_type&)(graph) (visitor_type&)(visitor) (root_vertex_type&)(root_vertex) (index_map_type&)(index_map) (copyable)(color_map_type&)(color_map) ) (postcondition) ({ CONTRACT_ASSERT( color_map == CONTRACT_OLDOF(color_map) + 10 ); }) (body) ({ color_map += 10; std::cout << "graph=" << graph << std::endl; std::cout << "visitor=" << visitor << std::endl; std::cout << "root_vertex=" << root_vertex << std::endl; std::cout << "index_map=" << index_map << std::endl; std::cout << "color_map=" << color_map << std::endl; }) ) }; } // namespace int main() { using namespace graphs; g gg; int cm = 0; gg.depth_first_search(1, 2, 3, 4, cm); std::cout << std::endl; gg.depth_first_search("1", '2', _color_map = cm, _index_map = "4", _root_vertex = "3"); return 0; } This function declaration syntax is terrible as it mixes the syntactic complexity of both Boost.Parameter and Boost.Contract... I will try to provide the following syntax instead: CONTRACT_FUNCTION( (public) (void) (depth_first_search)( // No (tag)(namespace-id) so use `tag`. // (auto) for no type requirements (preprocessor can't use `*`). (auto) (graph) // (default) for optional param. (auto) (visitor) (default)(boost::dfs_visitor<>()) (auto) (root_vertex) (vertices(graph).first) (auto) (index_map) (default)(get(boost::vertex_index, graph)) // (inout) for in-out type. (copyable)(inout)(auto) (color_map) (default) (default_color_map(num_verticies(graph), index_map)) // Plus, (deduced)( parameter-sequence ) for deduced params. ) (postcondition) ( (color_map == CONTRACT_OLDOF(color_map) + 10) ) ({ color_map += 10; std::cout << "graph=" << graph << std::endl; ... }) (IMO, this syntax looks cleaner that the original Boost.Parameter one.) -- Lorenzo

1 0

[intrusive.set] Accessing the last (largest) element.
by Andy Venikov 15 Apr '10

15 Apr '10

Since there is no "back" method for intrusive set, what's the best way to access the last (greatest) element? Is this OK:? IntrusiveSet set1; IntrusiveSet::iterator itEnd = set1.end(); //Make sure that set isn't empty. Value v = *--itEnd; ++itEnd; //will itEnd point to set1.end() after this? In general, is there anything sinister about this construct? (provided that the set isn't empty) Thanks, Andy.

2 2