September 2011 - Boost - lists.boost.org

[Review:Algorithms] My review of Boost.Algorithm
by Lorenzo Caminiti 30 Sep '11

30 Sep '11

Review of Boost.Algorithm 2011-09-29 - Lorenzo Caminiti ============================== Do you think the library should be accepted as a Boost library? ------------------------------ Yes, in my opinion Boost.Alrogithm should be accepted as a Boost library. Key points are: a) I would find the library usefull as is, especially for all_of_equal and for the search algorithms. b) I would like to see more algorithms supported into the library in the (near) future (IMO the "only" non-trivial algorithms currently offered are the 3 search algorithms). c) The documentation (which is clear and straightforward) should list more examples. My comments below are all numbered an marked as: [MUST] If these comments are not addressed, I would no longer recommend this library for addition to Boost. [WANT] I would like to see these comments addressed (at least replied to) but I would recommend this library for addition to Boost regardless. [NOTE] I do not feel strongly about these comments and they can be ignored. What is your evaluation of the design? ------------------------------ 1) [WANT] Could all/any/none/one_of_equal be made more general and merged with all/any/none/one_of by accepting a binary predicate via overloading? template<typename InputIterator, typename UnaryPred> bool all_of ( InputIterator first, InputIterator last, Pred p ); template<typename InputIterator, typename BinaryPred, typename V> bool all_of ( InputIterator first, InputIterator last, BinaryPred p, V const& v ); // could even overload for ternary, etc predicates bool BOOST_LOCAL_FUNCTION_PARAMS(int x) { return x > 0; } BOOST_LOCAL_FUNCTION_NAME(positive) int a[3] = {2, 2, 2}; all_of(a, a + 3, positive); // existing form all_of(a, a + 3, std::equal_to<int>(), 2); // instead of all_of_equal all_of(a, a + 3, std::less<int>(), 10); // can also do this now :) not just equal BTW, you can use Boost.Local to define the predicate functions at local scope ;) 2) [NOTE] Is there a (run-time) cost with the destruction of the tables used by Boyer-Moore and the other search algorithms? If so, is the same cost encountered by both the object and functional version of the algorithms? (BTW, it made sense to me to have both an object and function version of the algorithms.) 3) [MUST] There should be a range version for all search algorithms (unless it's not possible for some reason that I can't foresee). 4) [WANT] When using the object interface, is the caller responsible to keep the pattern in scope until the search object is destructed? Either way, this requirement should be clearly documented. 5) [NOTE] I'd be OK with any renaming of is_order based on other's opinions-- I'd follow C++11 if at all possible (is_sorted_until?). (No comment on clamp's argument ordering ;) .) What is your evaluation of the implementation? ------------------------------ 6) I very quickly read through the code. It looks clean and well organized... the iterator algorithms made sense. I did not study the search algorithm implementation close enough to comment on it. What is your evaluation of the documentation? ------------------------------ 7) [WANT] Please add more examples to the docs (you can take a few from the ones you already have in examples and tests). 8) [WANT] Always state complexity guarantees (they are mentioned in docs section but not in the code reference section). 9) [WANT] Are these examples from the docs incorrect? (What's 3, 9, etc?) one_of ( c.begin (), c.end (), 3 ) --> true one_of ( c, 3 ) --> true none_of ( c, 9 ) --> true any_of ( c.begin (), c.end (), 9 ) --> false 10) [WANT] Typos that I noted in the docs: * "are will" in "Since they have to return a place in the input sequence, input iterators are will not suffice". * check indentation of close `};` for `class boyer_moore`. * "and here are the corresponding procedural interface:" should say and "here is". 11) [WANT] Extend document of Boyer-Moore-Horspool and/or Knuth-Morris-Pratt with class code, etc to match docs of Boyer-Moore (interface is listed in the code reference section but not in the search algorithm section). What is your evaluation of the potential usefulness of the library? ------------------------------ 12) I would find the library useful as is (especially, for the handy all_of_equal and faster searches) but I would like to see more algorithms supported by the library in the near future. IMO, any/none/one/all and clamp are nice utilities, same goes for the ordered stuff, but at the end I got the sense that the search algorithms were the "only" real meat of the library. Did you try to use the library? With what compiler? Did you have any problem? ------------------------------ 13) Yes, I compiled all examples and tests on GCC 4.3.4 under Cygwin (BTW, in all_example.cpp rename all_of_val to all_of_equal). I got some warnings on MVSC 10 under Windows (see attached file). How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? ------------------------------ 14) I'd say a quick reading, I spent about 7 hours on it. I red all the docs and compiled all the examples (at least on GCC). Are you knowledgeable about the problem domain? ------------------------------ 15) Thankfully, not anymore ;) but reading the docs reminded of my class work on Boyer-Moore and variations-- it was a while ago. I'd say I am marginally familiar with the problem domain. --Lorenzo

3 3

[Review:Algorithms]
by Riccardo Marcangelo 30 Sep '11

30 Sep '11

Hi Marshall Firstly, I think the documentation is quite good. I like that there is a description of what each algorithm does, its return type and complexity. Maybe one example of each algorithm would be a nice addition. I think one_of complements the C++11 algorithms all_of, any_of and none_of well. is_increasing, is_strictly_increasing, is_decreasing and is_strictly_decreasing are useful, especially for statistical ranges. These are rolled fairly often so this is a welcome addition. is_ordered() seems to be similar to the C++11 algorithm is_sorted_until() with a comparison function. For consistency I would recommend using the behaviour of is_sorted_until() and renaming the function to is_sorted_until(). If this change were made I think there would also be a strong case for including the C++11 algorithm is_sorted(). I'm a bit sceptical on passing the arguments to clamp() by value, except for the predicate. I think (actually I'm totally convinced for myself) that clamp() should be overloaded, one version passing the arguments by const reference and the other passing the arguments by reference. Otherwise it's doing unnecessary copying in some cases. If V is large the overhead of the unneeded copies could be a lot. Another reason to not pass the arguments by value is that comparing objects should not raise any exceptions but copying usually can. The return types for the two overloaded versions would be "const V &" and "V &" respectively. Sadly, I was unable to use the search algorithms, boyer_moore_search(),boyer_moore_horspool_search() and knuth_morris_pratt_search(). All failed with a "string iterators incompatible" error during runtime using Visual C++ 2010. At first I thought it was my usage but the examples provided also had this problem. Overall, I like the library and vote "yes" for it to be included into Boost although I hope the issues I raised can be addressed. Kind regards Riccardo P.S Sorry if I haven't followed the protocol properly with this review, I'm fairly new to the Boost mailing list. -- View this message in context: http://boost.2283326.n4.nabble.com/Review-Algorithms-tp3859590p3859590.html Sent from the Boost - Dev mailing list archive at Nabble.com.

2 1

[Boost][Asio] Linker error when compiling serialization example
by jamesa 30 Sep '11

30 Sep '11

I receive a 2019 linker error when attempting to compile the asio serialization example: error LNK2019: unresolved external symbol "public: void __thiscall connection::async_read<class std::vector<struct stock,class std::allocator<struct stock> >,class boost::_bi::bind_t<void,class boost::_mfi::mf1<void,class networkConnection,class boost::system::error_code const &>,class boost::_bi::list2<class boost::_bi::value<class networkConnection *>,struct boost::arg<1> > > >(class std::vector<struct stock,class std::allocator<struct stock> > &,class boost::_bi::bind_t<void,class boost::_mfi::mf1<void,class networkConnection,class boost::system::error_code const &>,class boost::_bi::list2<class boost::_bi::value<class networkConnection *>,struct boost::arg<1> > >)" (??$async_read@V?$vector@Ustock@@V?$allocator@Ustock@@@std@@@std@@V?$bind_t@XV?$mf1@XVnetworkConnection@@ABVerror_code@system@boost@@@_mfi@boost@@V?$list2@V?$value@PAVnetworkConnection@@@_bi@boost@@U?$arg@$00@3@@_bi@3@@_bi@boost@@@connection@@QAEXAAV?$vector@Ustock@@V?$allocator@Ustock@@@std@@@std@@V?$bind_t@XV?$mf1@XVnetworkConnection@@ABVerror_code@system@boost@@@_mfi@boost@@V?$list2@V?$value@PAVnetworkConnection@@@_bi@boost@@U?$arg@$00@3@@_bi@3@@_bi@boost@@@Z) referenced in function "public: void __thiscall networkConnection::handle_connect(class boost::system::error_code const &,class boost::asio::ip::basic_resolver_iterator<class boost::asio::ip::tcp>)" (?handle_connect@networkConnection@@QAEXABVerror_code@system@boost@@V?$basic_resolver_iterator@Vtcp@ip@asio@boost@@@ip@asio@4@@Z) The client class from the example has been renamed to network connection and all the references corrected in the code, the client and stock files have not been changed and I'm still getting this error. Can anyone give me some insight has to what exactly I'm doing wrong here? using: Windows 7 64 bit Microsoft visual studio 2008 boost Ver. 1.47 -- View this message in context: http://boost.2283326.n4.nabble.com/Boost-Asio-Linker-error-when-compiling-s… Sent from the Boost - Dev mailing list archive at Nabble.com.

1 0

Re: [boost] to_string(v)
by Olaf van der Spek 30 Sep '11

30 Sep '11

Some time ago (2002) there was talk about a to_string function. Did this ever materialize? http://lists.boost.org/Archives/boost/2002/01/23585.php "to_string(5)" is a lot shorter than "lexical_cast<std::string>(5)". Likewise for "to_int("5")". Greetings, Olaf

3 5

[type_traits] copy constructor
by Lorenzo Caminiti 30 Sep '11

30 Sep '11

Hello all, What's the most portable way to detect if a type T is CopyConstructible? Actually, I would need a metafunction that is true_ iff a type T has a const-correct copy construct: T::T( T const& other) { /* copy this T from the other T */ } (I've been looking at boost::has_trivial_copy and boost::has_nothrow_copy but I wanted to double check with the ML.) Thanks a lot. --Lorenzo

4 6

Would Unicomm be interesting for Boost?
by Dmtitry Timoshenko 30 Sep '11

30 Sep '11

Hello, I finished developing the communication library based on STL, Boost. The communcation is implemented by using Boost.Asio. The library is engine that allows to build any network protocols based on TCP transport. Unicomm hides communication details and makes focus on business logic. I read the requirements for the library submission. The Unicomm is close to them. But there is still some work to make it possible it to join Boost. please, see http://libunicomm.org for details. (Smart library is also mine). So, before I start final preparations, I have the question. Would the library be interesting for Boost and compatible to it's concepts? Regards, Dmitry.

4 5

[algorithm] a unified (but unreadable?) alternative
by Lorenzo Caminiti 30 Sep '11

30 Sep '11

Hello all, I just sent my review of Boost.Algorithm. I am sending this email separately because these are just some ideas for "fun" which should not clutter the actual review of the library. I was wondering if it could be possible/useful to combine all the any/all/one/none_of and any/all/one/none_of functions into 1 single overloaded check function. Plus and minuses: - C++11 already uses all/any/none_of - Can't really read the check() code better... + I can pass any predicate, not just equal. + I can check for any count of elements that match the predicate not just for any, all, one, or none (but also for 10, etc). For example: #include <functional> #include <iostream> template< typename InIter, typename UnaryPred > // any bool check ( InIter first, InIter last, UnaryPred p ) { std::clog << "unary check count any" << std::endl; for(InIter i = first; i != last; ++i) if(p(*i)) return true; return false; } template< typename InIter, typename UnaryPred > // none/one/all/etc bool check ( unsigned count, InIter first, InIter last, UnaryPred p ) { std::clog << "unary check count " << count << std::endl; unsigned c = 0; for(InIter i = first; i != last; ++i) { if(p(*i)) c++; if(count) return false; } return c == count; } template< typename InIter, typename BinaryPred, typename V > // any bool check ( InIter first, InIter last, BinaryPred p, V const& v ) { std::clog << "binary check count any" << std::endl; for(InIter i = first; i != last; ++i) if(p(*i, v)) return true; return false; } template< typename InIter, typename BinaryPred, typename V > // none/one/all/etc bool check ( unsigned count, InIter first, InIter last, BinaryPred p, V const& v ) { std::clog << "binary check count " << count << std::endl; unsigned c = 0; for(InIter i = first; i != last; ++i) { if(p(*i, v)) c++; if(count) return false; } return c == count; } // could implement predicate ternary, etc bool less10 ( unsigned x ) { return x < 10; } int main ( ) { int a[3] = { 1, 2, 3}; int o[3] = {12, 2, 35}; int y[3] = { 1, 2, 35}; int n[3] = {10, 20, 30}; // unary predicate std::cout << check(y, y + 3, less10) << std::endl; // any std::cout << check(0, n, n + 3, less10) << std::endl; // none std::cout << check(1, o, o + 3, less10) << std::endl; // one std::cout << check(3, a, a + 3, less10) << std::endl; // all // binary predicate std::cout << check(0, a, a + 3, std::equal_to<unsigned>(), 22) // none_equal << std::endl; }; I think I can't easily understand what check() is supposed to do here... while any/one/none/all are more readable... Just some ideas :) --Lorenzo

1 0

Re: [boost] Problem static linking with boost.thread during cross-compilation
by Victor Leschuk 29 Sep '11

29 Sep '11

https://svn.boost.org/trac/boost/ticket/5964 On Wed, Sep 28, 2011 at 3:43 PM, Victor Leschuk <vleschuk(a)gmail.com> wrote: > Hello all, > > I have just met the following problem: I am cross-compiling boost 1.47 > using > > $ x86_64-w64-mingw32-g++ --version > > x86_64-w64-mingw32-g++ (GCC) 4.5.4 20110822 (prerelease) > > On Linux box with the following command: > > ./b2 -a toolset=gcc target-os=windows threading=multi threadapi=pthread > runtime-link=static --layout=versioned --build-type=complete install > > user-config.jam contains the following: > > using gcc : mingw : x86_64-w64-mingw32-g++ ; > > > After that a linkage failed when building my project. I reproduced it with > simple test program: > > #include <boost/thread.hpp> > #include <iostream> > > using namespace std; > > struct test > { > void operator()() { cout << "Called" << endl; } > }; > > int main() > { > test test_obj; > boost::thread thr(test_obj); > thr.join(); > } > > The output looks like > > $ x86_64-w64-mingw32-g++ -Wall test_boost.cpp -I ./3rdparty/boost/include/boost-1_47 -L ./3rdparty/boost/lib -lboost_thread-mgw-mt-s-1_47 -o test_boost.exe > In file included from ./3rdparty/boost/include/boost-1_47/boost/thread/win32/thread_data.hpp:12:0, > from ./3rdparty/boost/include/boost-1_47/boost/thread/thread.hpp:15, > from ./3rdparty/boost/include/boost-1_47/boost/thread.hpp:13, > from test_boost.cpp:2: > ./3rdparty/boost/include/boost-1_47/boost/thread/win32/thread_heap_alloc.hpp:59:40: warning: inline function ‘void* boost::detail::allocate_raw_heap_memory(unsigned int)’ declared as dllimport: attribute ignored > ./3rdparty/boost/include/boost-1_47/boost/thread/win32/thread_heap_alloc.hpp:69:39: warning: inline function ‘void boost::detail::free_raw_heap_memory(void*)’ declared as dllimport: attribute ignored > /tmp/ccSmsBnO.o:test_boost.cpp:(.text+0xde): undefined reference to `__imp__ZN5boost6thread4joinEv' > /tmp/ccSmsBnO.o:test_boost.cpp:(.text+0xfb): undefined reference to `__imp__ZN5boost6threadD1Ev' > /tmp/ccSmsBnO.o:test_boost.cpp:(.text+0x1c3): undefined reference to `__imp__ZN5boost6threadD1Ev' > /tmp/ccSmsBnO.o:test_boost.cpp:(.text$_ZN5boost6threadC1I4testEET_NS_10disable_ifINS_14is_convertibleIRS3_NS_6detail13thread_move_tIS3_EEEEPNS0_5dummyEE4typeE[boost::thread::thread<test>(test, boost::disable_if<boost::is_convertible<test&, boost::detail::thread_move_t<test> >, boost::thread::dummy*>::type)]+0xd5): undefined reference to `__imp__ZN5boost6thread12start_threadEv' > collect2: ld returned 1 exit status > > The same scenario works fine when linking with dynamic libboost_thread. > Both static and dynamic builds work fine for Linux. > > What could be the cause of the problem and where to look? Does it worse > posting a defect in bug-tracker? > > Thanks! > -- > Victor > > > > > >

1 0

Reminder: Algorithms library review ends Saturday
by Dave Abrahams 29 Sep '11

29 Sep '11

The official end date of the review of the proposed Boost.Algorithms is this coming Saturday, October 1st. Please submit your review by then, and please vote on its acceptance! Thanks, Dave ,----[ Important Notes ] | - Please do not post your review or discussion as a reply to this ...<schnipp 1>... | message. | - Please begin your review's subject line with "[Review:Algorithms]" | - Please feel free to note any individual issues in the GitHub issue | tracker and make reference to them from your review. | - Please see below for *further* important notes `---- You can find the library at https://github.com/mclow/Boost.Algorithm. If you don't want to use Git, you can get a .zip or tarball snapshot at https://github.com/mclow/Boost.Algorithm/archives/master Description =========== The Boost Algorithms library is a work in progress; it is not meant to be a complete set of general purpose algorithms for C++ programming; but rather a small collection of useful algorithms, and a structure for adding more over time. The algorithms here fall into three basic categories: 1. Searching - Boyer-Moore Search - Boyer-Moore-Horspool Search - Knuth-Morris-Pratt search 2. Sequence properties - Tests to see if a sequence is ordered - Tests for the elements of a sequence 3. Miscellaneous - Constrain a value between two 'boundaries' (minmax) Potential Interactions with Existing Boost Libraries ==================================================== This submission potentially interacts with all of the following existing Boost libraries: * foreach - http://boost.org/libs/foreach * minmax - http://boost.org/libs/algorithm/minmax * range - http://boost.org/libs/range * string_algo - http://boost.org/libs/algorithm/string_algo Reviewers should consider these potential interactions. What to include in Review Comments ================================== - Keep your criticism constructive. Constructive criticism usually comes with specific suggestions for improvement. - If you identify problems along the way, please note if they are minor, serious, or showstoppers. - Please *do* vote on whether the library should be accepted. Everyone who takes the time to look at the library is qualified to vote, and every vote is valuable. - Other questions you might want to answer in your review: * What is your evaluation of the design? * What is your evaluation of the implementation? * What is your evaluation of the documentation? * What is your evaluation of the potential usefulness of the library? * Did you try to use the library? With what compiler? Did you have any problems? * How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? * Are you knowledgeable about the problem domain? -- Dave Abrahams BoostPro Computing http://www.boostpro.com

1 0

[contract] extra type requirements for contracts
by lcaminiti 29 Sep '11

29 Sep '11

Hello all, Andrzej and I have been discussing off-line the following issue: How to program contract assertions without adding extra type requirements. I would like to get Boosters' input on possible solutions for this problem. THE PROBLEM Consider the following contract for vector::push_back: CONTRACT_CLASS( template( typename T ) class (myvector) ) { ... CONTRACT_FUNCTION_TPL( public void (push_back) ( (const T&) value ) precondition( size() < max_size(), ) postcondition( auto old_size = CONTRACT_OLDOF size(), auto old_capacity = CONTRACT_OLDOF capacity(), back() == value, // (1) size() == old_size + 1, capacity() >= old_capacity, ) ) ; }; Postcondition (1) introduces the extra requirement EqualityComparable<T>. This is not ideal because this requirement is only needed to check the contract but not to implement the push_back functionality (body). For example: struct pod {}; // not EqualityComparable std::vector<pod> v; v.push_back(pod()); // ok, does not require EqualityComparable<pod> myvector<pod> w; w.push_back(pod()); // complier-error, can't find operator== for type pod... Because of postcondition (1), myvector cannot be used on pod while the std::vector can! This is a general issue with contracts. In general, an arbitrary complex (const) expression can be used to assert preconditions, postconditions, or invariants. Such a complex assertion might introduce an arbitray set of extra requirements on the types used, requirements that might not be necessary to implement the function body. The extra type requirements introduced by the contracts are especially problematic when programming templates because the used types are generic and it is not know a priori to the function programmer if the generic types will or not satisfy the requirements. POSSIBLE SOLUTIONS A possible solution is to specify the type requirements that a given assertion introduces. If the type requirements are met, the assertion will be compiled and checked at run-time. If the type requirements are not met, the assertion will not be compiled (so not compiler-error "missing operator== for type ...") and not checked at run-time for that specific type. For example: CONTRACT_FUNCTION_TPL( // Option 1 public void (push_back) ( (const T&) value ) precondition( size() < max_size(), requires has_less<size_type>::value ) postcondition( auto old_size = CONTRACT_OLDOF size(), requires const_copy_constructor<size_type>::value auto old_capacity = CONTRACT_OLDOF capacity(), requires const_copy_constructor<size_type>::value back() == value, requires has_equal_to<T>::value // assertion type requirements size() == old_size + 1, requires has_equal_to<size_type>::value && has_plus<size_type>::value capacity() >= old_capacity, requires has_greater_equal<size_type>::value ) ) ; Here I have specified assertion type requirements using `requires` for each assertion. However, size_type is known a priori to be essentially an unsigned int for which all these type requirements will always be met so the type requirements on size_type could have been omitted. That said, you can easily imagine an example for a different template class or function where size_type is also a generic type for which const copy constructor, +, ==, etc might not always be available. Another option would be would be to specify the type requirements for precondition/postcondition instead than for each assertion: CONTRACT_FUNCTION_TPL( // Option 2. public void (push_back) ( (const T&) value ) precondition( size() < max_size(), ) requires has_less<size_type>::value // pre/postcondition type requirements postcondition( auto old_size = CONTRACT_OLDOF size(), auto old_capacity = CONTRACT_OLDOF capacity(), back() == value, size() == old_size + 1, capacity() >= old_capacity, ) requires const_copy_constructor<size_type>::value && has_equal_to<T>::value && has_plus<size_type>::value && has_greater_equal<size_type>::value ) ; Options 2 is less verbose and it does not specify the same type requirements multiple time for the different assertions. However, I prefer Option 1 because if T is not equality comparable, only the postcondition `back() == value` is not checked but all the other postconditions are still checked. With Option 2 if one type requirement is not met, then all preconditions/postconditions are not checked causing more bugs to go unobserved. If the re-use of the preprocessor "keyword" `requires` was found confusing because of its different semantics when used with concepts, a different preprocessor "keyword" like `unless` could be used instead: CONTRACT_FUNCTION( // Option 3 template( typename InIter1, typename InIter2, typename OutIter, typename BinOp ) requires( boost::InputIterator<InIter1>, boost::InputIterator<InIter2>, typename CONTRACT_IDENTITY_TYPE(( boost::OutputIterator<OutIter, typename boost::InputIterator<InIter1>::value_type > )), typename CONTRACT_IDENTITY_TYPE(( boost::BinaryFunction<BinOp, typename boost::InputIterator<InIter1>::value_type, typename boost::InputIterator<InIter1>::value_type, typename boost::InputIterator<InIter2>::value_type> )) ) (OutIter) (mytransform) ( (InIter1) first1, (InIter1) last1, (InIter2) first2, (OutIter) result, (BinOp) op ) precondition( contract::trivial::range(first1, last1).valid() ) postcondition( auto return_value = return, return_value == result, unless !has_equal_to<T>::value // use unless ) ) { return std::transform(first1, last1, first2, result, op); } Reflections: a) All these solutions require extensive type traits support to write the contract type requirements (I cannot use concepts because they greedily generate compiler-errors when they are not met). However, I see no way around this: I must be able to check the type requirements (extensively using type traits) in order to disable the assertion compilation and their run-time check. b) All these solutions leave the assertions in the contracts so the contract code retains its self-documentation value even then the assertion checking is disabled because the type requirements are not met. c) N1962, Eiffel, D, A++, and all other Contract Programming references that I have seen do not address the issue of the extra type requirements. I am not sure why... Eiffel has generic types but you can always compare them for equality, for non Void, etc. d) In practice, this might not be a big deal because most of the times old-of is applied to counters (int) and postconditions are the ones introducing the extra requirement but only of EqualityComparable. However, in general I think I need to provide a solution for this issue. What do you think? Thanks a lot! --Lorenzo -- View this message in context: http://boost.2283326.n4.nabble.com/boost-contract-extra-type-requirements-f… Sent from the Boost - Dev mailing list archive at Nabble.com.

6 12