May 2009 - Boost - lists.boost.org

minmax_element and sorted data
by Steven Ross 29 May '09

29 May '09

I've noticed that minmax_element makes roughly 3n/2 comparisons, though n - 1 comparisons are all that is required to see if data is sorted, and if it is, the minimum and maximum are known. Sorted data is a relatively common special-case, and I think minmax_element might be better optimized to take advantage of sorted data when it is provided. Also, it would be nice to have a version of it that returns the minimum, maximum, and whether the data is sorted. Also worth considering is whether minmax_element can work more efficiently with long chains of sorted (or reverse-sorted) data, by taking advantage of the fact that the maximum and minimum of sorted data is known, and it takes n - 1 comparisons to tell whether a list of n items is sorted. An example of how sorting can be tested without hurting overall runtime for unsorted data is how I find the minimum and maximum for integer_sort. Note that when the data is sorted, it returns with max and min being identical; a boolean could provide that information in a more general method. Source: //Find the minimum and maximum using < template <class RandomAccessIter> inline void find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min) { min = max = current; //It is assumed we have more than 1 element; there are multiple checks for this while(!(*(current + 1) < *current)) { //If everything is in sorted order, return if(++current == last - 1) return; } //The maximum is the last sorted element max = current; //Now that we know it isn't sorted, doing an efficient max/min find std::pair<RandomAccessIter, RandomAccessIter> vals = minmax_element(++current, last); if(*(vals.first) < *min) min = vals.first; if(*max < *(vals.second)) max = vals.second; }

1 0

Re: [boost] [parameter] Testing for existence of a parameter, building ArgumentPacks, more lazy return types
by Jeremiah Willcock 29 May '09

29 May '09

(reposting because of no response) >> I have a few questions about the parameter library. Please note that I am >> using >> argument packs directly, since I am creating them from another data >> structure. >> >> 1. Is there a way to build Boost.Parameter ArgumentPacks from a >> program? > > Yes, and it's documented. Have you read through the documentation, or > do you mean something else? Are you talking about section 3.2.1? I also need to get the types of the resulting ArgumentPacks. >> I am currently using many internal data structures of Boost.Parameter >> (empty_arg_list and such). > > That doesn't sound like a public interface to me, but maybe it should > be. Yes, that is the issue. I could use the operators in 3.2.1 but need a way to get the type of the result. >> 2. Is there a way to tell at compile-time whether a particular >> parameter exists in an ArgumentPack? I currently have a metafunction >> that uses a special default type and tests for that; is there a more >> "official" way? > > Nope, that's the way we recommend. OK. I guess I would prefer an explicit metafunction for that. >> 3. I have a case where the default type for a named parameter cannot >> be instantiated in some cases where that parameter is given >> explicitly. The operator||() lazy defaults don't seem to work for >> that because they get the result_type member from my default right >> away, even if it won't be used. > > Ouch. It would be nice to have a fix for that one. > >> I currently have a hack to work around this using my parameter_exists >> test and some metaprogramming. >> >> The reason I am working on this low of a level is that I am playing >> with converting Boost.Graph named parameter structures into >> ArgumentPacks > > About time! I know. I just started playing with it over the weekend. >> to have access to Boost.Parameter's nicer capabilities >> and syntax. I thus need to build all of the argument data structures >> and such within another function and then access them later. > > I'm not sure what you're saying here, Jeremiah. Are you talking about > building the backward-compatibility interface for the old syntax, here? > The generation macros should be enough to handle all the new-syntax > cases. Yes -- I am starting with keeping the old external interfaces (only) and translating the implementation to use Boost.Parameter internally. This means that users will not see any changes and yet the internals of BGL can use Boost.Parameter default computation and such. Later, once that's working, the external interfaces can be switched. One more question -- I have a situation where I'd like to declare an extra variable only when a certain parameter is not specified, and the type of that variable may not even be valid when the parameter is specified. In more detail, I'd like to write something like (pseudocode): if parameter color_map is specified { auto color_map = color_map parameter } else { std::vector<default_color_type> color_data; auto color_map = f(color_data); } I can stand having something like a dummy int as the default case for color_data, but the type of color_map changes based on whether the parameter was specified or not. Is there an easy way to do that? You can also look at the bottom of boost/graph/named_function_params.hpp and in boost/graph/depth_first_search.hpp (the one file I've tried to convert) to see the ways I'm doing things now and what I'm trying to do. Thank you. -- Jeremiah Willcock

1 0

[Signal] Variadic template implementation of signal/slot
by Kevin Brandon 29 May '09

29 May '09

Would anyone be interested in seeing my implementation of Signals/Slots that uses the variadic template capability that will be a part of c++0x standard? It seemed to me a natural evolution for the current library that is Signal\Signal2. I did not baseline from the current boost code; but, if the interest exists, I would love to submit my code for formal review and equally try to integrate and respect the design decisions that already fostered the growth for the other two versions. Regards, Kevin Brandon

5 7

[fusion] adding infinite sequences to fusion
by Stjepan Rajko 29 May '09

29 May '09

Hi all, There's been some off-list discussion between Dan Marsden, Joel de Guzman and myself on how to address infinite sequences in fusion. Joel suggested to bring the discussion back to the list for more feedback: On Wed, Apr 15, 2009 at 6:21 PM, Joel de Guzman <djowel(a)gmail.com> wrote: > Stjepan Rajko wrote: >> >> Here is a list and description of all of the concepts that might be >> relevant: >> >> >> Forward Sequence >> begin(s) - returns a Forward Iterator >> empty(s) - returns a bool >> front(s) - any type >> >> Finite Forward Sequence >> refines Forward Sequence >> end(s) - returns a Forward Iterator >> size(s) - MPL integral constant >> >> Infinite Forward Sequence >> refines Forward Sequence >> empty(s) - returns false >> size(s) - infinity >> >> Bidirectional Sequence >> refines Forward Sequence >> begin(s) - returns a Bidirectional Iterator >> >> Finite Bidirectional Sequence >> refines Bidirectional Sequence, Finite Forward Sequence >> end(s) - returns a Bidirectional Iterator >> back(s) - any type >> >> Infinite Bidirectional Sequence >> refines Bidirectional Sequence, Infinite Forward Sequence >> >> Random Access Sequence >> refines Bidirectional Sequence >> begin(s) - returns a Random Access Iterator >> >> Finite Random Access Sequence >> refines Random Access Sequence, Finite Bidirectional Sequence >> end(s) - returns a Random Access Iterator >> >> Infinite Random Access Sequence >> refines Random Access Sequence, Infinite Bidirectional Sequence >> >> >> How does that look? > > I'd suggest posting that to the Boost list to get more feedback. > I have a feeling that infinity is a separate concept orthogonal > to traversal. But I'm not sure. > The above layout is almost orthogonal, with Infinite Forward Sequence and Finite Forward Sequence serving as "base" concepts related to Finite / Infinite. I suppose you could have less refined Infinite Sequence and Finite Sequence concepts, but I'm not sure how useful they would be (AFAICT, they could only describe `size` and `empty`). Things aren't perfectly orthogonal because Finite + Bidirectional require `back`, but Finite + Forward do not, and neither do Infinite + Bidirectional. Best, Stjepan > Regards, > -- > Joel de Guzman > http://www.boostpro.com > http://spirit.sf.net >

2 2

[MultiIndex] Recursive data structure with MultiIndex
by Sebastian Redl 29 May '09

29 May '09

Hi, I'm trying to implement property_tree in terms of multi_index, but have run into a problem. The old implementation boiled down to this (using no templates for clarity): class ptree { typedef std::pair<std::string, ptree> value_type; typedef std::list<value_type> list_type; list_type m_children; }; This is undefined behavior, because at the point where the list is instantiated, ptree is incomplete, so the pair cannot be fully instantiated. However, apparently it worked on enough compilers. Now I want to use MultiIndex instead, so that I can have both the order of children preserved and offer O(log(N)) lookup of children. (The old code was O(N), but claimed to be O(log(N)).) But MultiIndex actually fails to instantiate with the incomplete type. More concretely, what fails to instantiate is the key retriever, a member<value_type, std::string, &value_type::first>. This is because the member access into the pair requires pair to be fully instantiated, and the instantiation fails as the ptree is incomplete. I'm not very fond of the idea of storing pointers, especially as there is no ptr_multi_index_container. But is there any other way, really? Sebastian

2 4

Trac policy on "won't fix" issue
by Vladimir Prus 29 May '09

29 May '09

Suppose there's an issue in Trac about program_options library. The issue is such that I personally have no hope of *ever* fixing it. What should be done to such issue: 1. Close it as won't fix. 2. Keep it open. (1) has the advantage that the issue won't show up in my searched, making life easier for me, but it reduces chances that somebody else will accidentally see and fix it. OTOH, the chances of such fix are also pretty low. So, I personally prefer (1), but I also think we should have a single consistent meaning of what open issue in Trac means, and under what cases an issue that is not actually fixed can be closed. Any comments? - Volodya

9 12

[asio] Bug in allocation of timer
by puzirev＠gmail.com 28 May '09

28 May '09

Wrong allocation of timer in timer_queue.hpp: template <typename Handler> bool enqueue_timer(const time_type& time, Handler handler, void* token) { ... // Create a new timer object. std::auto_ptr<timer<Handler> > new_timer( new timer<Handler>(time, handler, token)); // <-- ATTENTION ... new timer<Handler>(...) later will be dealocated with asio_handler_deallocate Solution: allocate new timers with asio_handler_allocate // Create a new timer object. typedef timer<Handler> timer_type; typedef handler_alloc_traits<Handler, timer_type> alloc_traits; raw_handler_ptr<alloc_traits> raw_ptr(handler); handler_ptr<alloc_traits> new_timer(raw_ptr, time, handler, token);

1 0

bug in boost::asio
by puzirev＠gmail.com 28 May '09

28 May '09

Wrong allocation of timer in timer_queue.hpp: template <typename Handler> bool enqueue_timer(const time_type& time, Handler handler, void* token) { // Ensure that there is space for the timer in the heap. We reserve here so // that the push_back below will not throw due to a reallocation failure. heap_.reserve(heap_.size() + 1); // Create a new timer object. std::auto_ptr<timer<Handler> > new_timer( new timer<Handler>(time, handler, token)); // <-- ATTENTION ... new timer<Handler>(...) later will be dealocated with asio_handler_deallocate Solution: allocate new timers with asio_handler_allocate // Create a new timer object. typedef timer<Handler> timer_type; typedef handler_alloc_traits<Handler, timer_type> alloc_traits; raw_handler_ptr<alloc_traits> raw_ptr(handler); handler_ptr<alloc_traits> new_timer(raw_ptr, time, handler, token);

1 0

Re: [boost] Second call: The Boost Bug Sprint is coming!!
by Stjepan Rajko 28 May '09

28 May '09

On Tue, May 26, 2009 at 6:10 AM, Marshall Clow <marshall(a)idio.com> wrote: > The boost bug sprint is coming! It starts _this_ Friday, May 28th, and runs > through Sunday June 7th. > Thanks for organizing this. I just started going through fusion tickets, so I guess sign me up :-) Best, Stjepan

1 0

Re: [boost] Spirit Not Parsing
by Aston 28 May '09

28 May '09

ooppss...my bad mistake is in parse_conf_file() below line is incorrect, wrong grammar rule<> conf_lines = l_root | *l_params | l_end; correct line is rule<> conf_lines = l_root >> *l_params >> l_end; sorry for pollution ________________________________ From: Aston <blackapache512-ticket(a)yahoo.com> To: boost(a)lists.boost.org Sent: Thursday, 28 May, 2009 10:18:16 AM Subject: Spirit Not Parsing Hello, I am evaluating Boot.Spirit for parsing a custom format. I have presented the code below and config file as well. I expect numUsers to be 2 but it is zero, indicating that integer_action() was not call at all. I tried with assign_d as well, it also didn't help. I guess I am missing something, and I cannot figure out that since parse() returns 0. can anybody point that out ? thanks, Aston ============ src file begin ============ #include <iostream> #include <fstream> #include <string> #include <boost/spirit.hpp> using namespace boost::spirit; int numUsers = 0; void integer_action( const int& var) { numUsers = var; }; int parse_conf_file( char* buffer) { rule<> l_root = str_p("FakeRC") >> *blank_p >> *alpha_p >> eol_p; rule<> l_params = *blank_p >> *alpha_p >> *blank_p >> str_p("Integer") >> *blank_p >> *int_p[&integer_action] >> eol_p; rule<> l_end = str_p("end") >> eol_p; rule<> conf_lines = l_root | *l_params | l_end; return parse( buffer, conf_lines).full; } int main( int argc, char** argv) { std::ifstream conf(".fakerc", std::ios::binary); conf.seekg( 0, std::ios::beg); int start = conf.tellg(); conf.seekg( 0, std::ios::end); int end = conf.tellg(); int size = end - start; conf.seekg( 0, std::ios::beg); char* buffer = new char[size]; std::fill( buffer, buffer + size, 0); conf.read( buffer, size); buffer[size - 1] = 0; int err_code = parse_conf_file( buffer); std::cout << ( err_code == 0 ? "success" : "failed"); std::cout << ": " << err_code << std::endl; std::cout << "numUsers: " << numUsers << std::endl; delete[] buffer; conf.close(); return 0; } ============ src file end ============ ============ .fakerc contents ============ FakeRC FakeRC_Name Users Integer 2 end ============ end .fakerc ============ ________________________________ Explore and discover exciting holidays and getaways with Yahoo! India Travel Click here! Bollywood news, movie reviews, film trailers and more! Go to http://in.movies.yahoo.com/

2 1