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

[multi-index] Complex searches, multiple predicates, foreign keys
by dv 07 Jun '11

07 Jun '11

Hi, I stumbled upon this multi-index example: http://www.boost.org/doc/libs/1_46_1/libs/multi_index/doc/examples.html#exa… and I do not understand the gains in the second step. To sum up, the example wants to apply two predicates to the search - select elements with the given manufacturer, and select elements that fall in a certain price range. It does so by using one predicate in a first search (for example, finding all elements with the given manufacturer), then taking the range of search results, and copy it to another multi-index container (using pointers to avoid unnecessary deep copying of the elements). Then it performs a second search using the other predicate (in this example, the price range) to further narrow down the range of results. It is this copying and creating of the 2nd container that bugs me. Isn't this unnecessary? It implies O(n) steps to insert the search results, n being the number of results from the 1st search. Then, why use a second multi-index container? Why shouldn't I just use remove_copy_if() instead? it would make sense if copying the subset into a new multi-index container were faster than O(n), but I doubt that. What do you think? regards

2 1

BGL metric_tsp_approx time complexity?
by Anders Wallin 07 Jun '11

07 Jun '11

Hi all, I ran metric_tsp_approx on a number of TSPLIB problems and got the following graph: http://goo.gl/iGYsH This would indicate the time-complexity is V^2 (V is the number of cities/vertices). However the documentation [1] says O(E log V). A complete graph has O(V^2) edges, so the documentation would indicate metric_tsp_approx is O( V^2 log V ) (?) The heavy lifting in metric_tsp_approx is done by prim_minimum_spanning_tree, which the documentation [3] also lists as O(E log V). However I then go to [4] and see that for an adjacency matrix prim's algorithm runs in V^2. Confused, Anders [1] http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/metric_tsp_approx.html [2] http://www.boost.org/doc/libs/1_46_1/libs/graph/test/metric_tsp_approx.cpp [3] http://www.boost.org/doc/libs/1_46_1/libs/graph/doc/prim_minimum_spanning_t… [4] http://en.wikipedia.org/wiki/Prim%27s_algorithm

2 3

Ranges to Collections
by John M. Dlugosz 07 Jun '11

07 Jun '11

I like "ranges". When I first read the introduction to the ideas that would become STL, I did not like the use of begin/end iterators. Primarily, there is a possibility of getting them mixed up and the proposed library was explicitly not robust in the face of being passed bad parameters, such as not belonging to the same collection or not having the end after the begin. This was in direct contrast to the code I was promoting, which stressed API design that prevented errors from being possible, and strongly checking for everything else. The fact that they are not "functional" was harder to grasp exactly at the time, but it bothered me "in my gut". When I read about the Boost Range library and the C++0x adoption of the range concept, I felt this to be a long sought improvement and would dramatically improve my use of STL. Suffice to say, I'm a fan of Ranges. In new work, and in refactoring and improving code, I expect ranges to be one of the pillars of improvement. I'm sad to see that the draft standard dropped most of the range stuff (presumably it needs Concepts) but left in the intrinsic for-each loop. Anyway, the concrete compiler I have to work with, Visual Studio 2010, doesn't include it. So Boost.Range to the rescue! Except... the standard containers like vector don't have constructors that take ranges. Consider something like: vector<string> retval (rangefunc | rangefilter); It really gets in the way to introduce a temporary variable of "some range type", but I see that the 'auto' feature comes to the rescue. I'm not used to having that available, so perhaps I'm over reacting. But, is there a way to bridge the gap? I take it patching the STL headers to add the missing constructors is frowned upon. But some syntactic sugar might get pretty close to that. First of all, what are people doing now? Maybe this has all be gone over before? I can see creating a derived class from each STL container. The sole purpose of that class is to have the range constructor, and then the resulting instance is used as the base class, passed somewhere or copied. So you might write, for the previous example: range_vector retval (rangefunc | rangefilter); and other code won't care about your derived class since it only existed district from the base class in order to add a constructor. In fact, a template might systematically do this to any class that has a constructor that takes two iterators: rangeit<vector<string>> retval (rangefunc | rangefilter); This is less than desirable in cases where you were not going to state the type. Say, a return statement or parameter, where you would ideally have an implicit conversion from a range to the collection: return (rangefunc | rangefilter); // give a "range" where collection is expected Could a helper template be written that has a simple name and doesn't need to be told the types involved? return range_to_collection (rangefunc | rangefilter); Perhaps this produces a temporary object that supports a templatized conversion operator, so it can continue when that is told the type desired. I can see a few approaches, depending on what the compiler would swallow. But, has anyone already done this? —John

2 3

Re: [Boost-users] Ranges to Collections
by 乔志强 07 Jun '11

07 Jun '11

Maybe you want make_vector() , make_list(). #include <vector> #include <list> #include <boost/range/algorithm.hpp> #include <boost/range/algorithm_ext/push_back.hpp> #include <boost/range/adaptor/reversed.hpp> // for test template<class T, class SinglePassRange> T make_container(const SinglePassRange& from) { T c; boost::push_back(c, from); return move(c); } template<class SinglePassRange> std::vector<typename SinglePassRange::value_type> make_vector(const SinglePassRange& from) { return make_container<std::vector<typename SinglePassRange::value_type>>(from); } template<class SinglePassRange> std::list<typename SinglePassRange::value_type> make_list(const SinglePassRange& from) { return make_container<std::list<typename SinglePassRange::value_type>>(from); } int main(int argc, _TCHAR* argv[]) { std::vector<char> vector1; vector1.push_back(1); vector1.push_back(2); vector1.push_back(3); std::list<char> list1; list1.push_back(1); list1.push_back(2); list1.push_back(3); auto vector2 = make_container<std::vector<char>>(vector1 | boost::adaptors::reversed); auto vector3 = make_vector(vector1 | boost::adaptors::reversed); auto vector4 = make_vector(vector1); auto list2 = make_container<std::list<char>>(list1 | boost::adaptors::reversed); auto list3 = make_list(list1 | boost::adaptors::reversed); auto list4 = make_list(list1); return 0; } > ------------------------------ > > Message: 2 > Date: Mon, 06 Jun 2011 11:00:29 -0500 > From: "John M. Dlugosz" <mpbecey7gu(a)snkmail.com> > To: boost-users(a)lists.boost.org > Subject: [Boost-users] Ranges to Collections > Message-ID: <15775-1307376032-823667(a)sneakemail.com> > Content-Type: text/plain; charset=UTF-8; format=flowed > > I like "ranges". When I first read the introduction to the ideas that would > become STL, I > did not like the use of begin/end iterators. Primarily, there is a possibility > of getting > them mixed up and the proposed library was explicitly not robust in the face > of being > passed bad parameters, such as not belonging to the same collection or not > having the end > after the begin. This was in direct contrast to the code I was promoting, which > stressed > API design that prevented errors from being possible, and strongly checking > for everything > else. The fact that they are not "functional" was harder to grasp exactly at > the time, > but it bothered me "in my gut". > > When I read about the Boost Range library and the C++0x adoption of the range > concept, I > felt this to be a long sought improvement and would dramatically improve my > use of STL. > > Suffice to say, I'm a fan of Ranges. In new work, and in refactoring and > improving code, > I expect ranges to be one of the pillars of improvement. I'm sad to see that > the draft > standard dropped most of the range stuff (presumably it needs Concepts) but > left in the > intrinsic for-each loop. Anyway, the concrete compiler I have to work with, > Visual Studio > 2010, doesn't include it. So Boost.Range to the rescue! Except... the > standard > containers like vector don't have constructors that take ranges. > > Consider something like: > vector<string> retval (rangefunc | rangefilter); > > It really gets in the way to introduce a temporary variable of "some range type", > but I > see that the 'auto' feature comes to the rescue. I'm not used to having that > available, > so perhaps I'm over reacting. > > But, is there a way to bridge the gap? > > I take it patching the STL headers to add the missing constructors is frowned > upon. But > some syntactic sugar might get pretty close to that. First of all, what are > people doing > now? Maybe this has all be gone over before? > > I can see creating a derived class from each STL container. The sole purpose > of that > class is to have the range constructor, and then the resulting instance is used > as the > base class, passed somewhere or copied. So you might write, for the previous > example: > range_vector retval (rangefunc | rangefilter); > > and other code won't care about your derived class since it only existed > district from the > base class in order to add a constructor. In fact, a template might > systematically do > this to any class that has a constructor that takes two iterators: > rangeit<vector<string>> retval (rangefunc | rangefilter); > > This is less than desirable in cases where you were not going to state the type. > Say, a > return statement or parameter, where you would ideally have an implicit > conversion from a > range to the collection: > return (rangefunc | rangefilter); // give a "range" where collection is > expected > > Could a helper template be written that has a simple name and doesn't need to > be told the > types involved? > return range_to_collection (rangefunc | rangefilter); > > Perhaps this produces a temporary object that supports a templatized conversion > operator, > so it can continue when that is told the type desired. I can see a few > approaches, > depending on what the compiler would swallow. But, has anyone already done > this? > > ?John > > >

4 6

C++ thread in BOOST
by Claude 06 Jun '11

06 Jun '11

Hi! I would like to use some c++2011 thread library functions in VC + + using BOOST thread. What is the equivalent of try_lock_for() (c++ timed_mutex) in BOOST timed_mutex? -- View this message in context: http://boost.2283326.n4.nabble.com/C-thread-in-BOOST-tp3577969p3577969.html Sent from the Boost - Users mailing list archive at Nabble.com.

2 1

Using boost::asio
by Ram Sundar 06 Jun '11

06 Jun '11

Hi, I am trying to use boost::asio for a project where we currently use ACE. The way it currently works, the data that is passed between the server and client is preceded by a header with the data length. Currently with ACE when data is ready to be read at the socket, the handler function is invoked, and we invoke a ioctl with FIONREAD to read the number of bytes ready to be read and then allocate a buffer of that length to read the data. The reason we do this way is because the data may be sent in chunks. Internally we keep track of how much data we have received etc. I am at a loss to know how to do this using boost::asio. All the read methods expect a buffer where data will be read and it also needs the size of the buffer. Is there a way we get notified when data is ready to be read, and do similar operation. ie read the number of bytes available to read and then allocate buffers to read the data? Are there any other methods to accomplish the same? Thanks, Ram

4 4

"WinSock.h has already been included" : problem with asio and VC++2010
by Claude 06 Jun '11

06 Jun '11

Hi! I use a boost asio library in my program. When I compile with Visual C++ obtain this error: [...]\boost_1_45_0\boost\asio\detail\socket_types.hpp(22): fatal error C1189: #error : WinSock.h has already been included How can I fix this error? -- View this message in context: http://boost.2283326.n4.nabble.com/WinSock-h-has-already-been-included-prob… Sent from the Boost - Users mailing list archive at Nabble.com.

3 3

Boost MSM: Can not get out of the submachine
by gauravk 06 Jun '11

06 Jun '11

Hi, I have been playing around with the boost MSM libraries, to know more about them. I am creating a vending machine simulation with a sub-machine for accepting payment from the user. The vending machine has 3 states: waiting (where the machine just waits for the user to start processing), selection (where user selects a product. The machine makes a transition to this state from "waiting" state if the event "key_press" occurs and if the key pressed is the start button (checked by a guard condition).). After a product is selected the machine goes in payment state, which is a submachine that accepts payment in quarters. After the payment is received (it is fixed $1 for all products, just to make it simple) the machine again goes in the waiting state dispensing the product (action: dispatch_item). The submachine Payment has 4 states: Payment_init which just displays a message and then makes an immediate automatic transition to the next state "Paying". In this state the machine just waits for the "coin_insert" event to occur (which represents inserting a quarter). Once the "coin_insert" event occurs it makes a transition to "check_payment" state which checks if sufficient amount was paid. If not it again makes an automatic transition to "Paying" state, else it moves to the "Payment_done" state which is the last state in the submachine. This state generates an event "last_state" which is an indicator that the payment has been made and should cause a transition from the submachine "Payment" to waiting state (which I am not observing). The transition tables for both the machines are: (btw I am using the functors as the front end.) Table for vending machine: // +---------------------+-----------------------+----------------------+---------------------+------- Row < waiting, key_press, selection, none, is_start>, /// If start button pressed, go to selection state Row < waiting, key_press, waiting, none, is_cancel>, // If cancel pressed stay in the waiting state Row < selection, key_press, Payment, none, is_number>, //If a product number pressed go to payment Row < selection, key_press, waiting, none, is_cancel>, // If cancel pressed go to Row < Payment, key_press, waiting, none, is_cancel>, Row < Payment, last_state, waiting, dispatch_item, none> //the last_state event is generated in the // "payment_done" state of the Payment submachine // +---------+-------------+---------+---------------------+----------------------+ Table for Payment machine: // +---------------------+-----------------------+----------------------+---------------------+------- Row < Payment_init, none, Paying, none, none >, // Just make an auto transition after displaying a msg Row < Paying, coin_insert, check_payment, none, none>, Row < check_payment, none, Paying, none, is_not_paid>, //If enough money received Row < check_payment, none, payment_done, none, is_paid> // +---------+-------------+---------+---------------------+----------------------+ The code for payment_done state is: struct payment_done: public msm::front::state { template<class Event, class FSM> void on_entry(Event const &, FSM &fsm) { cout << "---------------" << endl; cout << "Payment_done" << endl; fsm.process_event(last_state()); } }; The events that I gave as an input to the state machine are: Event inputs: //vm = vending machine vm->start(); vm->process_event(key_press(START)); //press start vm->process_event(key_press('5')); // select a product vm->process_event(coin_insert(0.25)); // Make payment in quarters and "50 cents"! vm->process_event(coin_insert(0.25)); vm->process_event(coin_insert(0.5)); I am printing out the event/state/action/guard condition name on entry. Here is the output: Output: Trying out the Boost Meta State Machine --------------- waiting Please press start button --------------- Event key_press Entered key: s // s = start --------------- Guard condition is_cancel --------------- Guard condition is_start --------------- selection Select a product: --------------- Event key_press Entered key: 5 --------------- Guard condition is_cancel --------------- Guard condition is_number entering: Payment // submachine --------------- Payment_Init --------------- Paying template Insert coins: //msg displayed in the state //plz ignore the word "template" in the line --------------- Event coin_insert Inserted $0.25 --------------- check_payment Checking if full payment made in check_payment. --------------- Guard condition is_paid //check if full payment received --------------- Guard condition is_not_paid //check if full payment not received (in which case move to Paying state) --------------- Paying template Insert coins: //msg displayed in the state //plz ignore the word "template" in the line --------------- Event coin_insert Inserted $0.25 --------------- check_payment Checking if full payment made in check_payment. --------------- Guard condition is_paid //check if full payment received --------------- Guard condition is_not_paid //check if full payment not received (in which case move to Paying state) --------------- Paying template Insert coins: //msg displayed in the state //plz ignore the word "template" in the line --------------- Event coin_insert Inserted $0.5 --------------- check_payment Checking if full payment made in check_payment. --------------- Guard condition is_paid //check if full payment received (which is, in this case. so move the payment_done state) --------------- Payment_done --------------- Event last state //The event occurs but the transition does not As you can see the event "last_state" is occurring in the payment_done state but the transition is not taking place. I can post the entire code is someone is interested but I am just playing around with the libraries so the code (and some logic too) is not sophisticated at all. Still I can post it if someone wants to take a look at it. Thanks! -- View this message in context: http://boost.2283326.n4.nabble.com/Boost-MSM-Can-not-get-out-of-the-submach… Sent from the Boost - Users mailing list archive at Nabble.com.

2 5

Fwd: boost::range : sliced vs copied
by Rafaël Fourquet 06 Jun '11

06 Jun '11

What is the difference between the two boost::adaptors functions sliced and copied? Looking at the code, one can see that copied uses sliced, but I am not sure if there is a subtle difference. Maybe it could be explained in the docs. Moreover, the docs say that sliced returns "make_range(rng, n, m)", but I could not find the documentation for make_range (and only found a function with this name in the range_detail namespace, but which does not correspond). Thanks!

1 0

ICL library usage for interval map
by Dave Schwartz 06 Jun '11

06 Jun '11

Hi Users, I am trying to use the new ICL (interval container library) for a project that requires some interval based calculations. I have a question on using the joining interval_map. For example, below I have a conceptual 30 minute window divided into three 10 minute intervals. I want to do some aggregates in my 10 minute windows. { [0,10], (10, 20], (20, 30) } Now say, I have 2 clients shopping in the first interval (0, 10) and their shopping time window interval is [2, 5] and [4, 9] minutes respectively. When I add the 2 interval, value pairs to my interval_map, I see that the interval map gets splited from [0, 10] to { [0,2], [2, 4], [5,9], [9,10] }. How do I make sure the interval still remains from [0, 10]. My question is how do I make sure my original interval of 10 minutes is preserved. The samples mentioned do mention about joining interval_map but I cannot seem to figure out an example for my requirement. Thank you for your help Dece

3 3