- Boost - lists.boost.org

Container optimized for "insert once"
by Stefan Slapeta 08 Sep '04

08 Sep '04

Hi all, I'm looking for an associative container which is optimized for one-time insertion and avoids much of the overhead of std::map therefore. IIRC Andrei once published something like this: a vector of pairs that was sorted once and accessed by binary search. Is there something similar in boost? Stefan

6 7

Challenge: Implement a state machine compiler as a Cpp macro using Order
by Vesa Karvonen 08 Sep '04

08 Sep '04

Hi, During the summer, I have been designing and implementing a metalanguage for C preprocessor metaprogramming named Order. The Order language is a *complete* high-level functional programming language with features such as - lexical scoping, - first-class functions, - anonymous functions, - partial application of functions (currying), - intuitive call-by-value semantics, and - tail-recursion optimization. The Order prelude supports, among other things, - arithmetic on arbitrary precision natural numbers and small literals {0,...,100}, - sequences (with many higher-order functions), - tuples, and - so called token strings/sequences. The Order interpreter, which is implemented using the C preprocessor macro mechanism, can be used to generate arbitrary sequences of preprocessing tokens (read: code). The intepreter also provides a debug mode that checks for many kinds of programming errors (syntax-errors, run-time type errors and user assertions). The Order language has been designed to transform the feel of C preprocessor metaprogramming from "learning lots of tricky, low-level Cpp specific idioms" to "thinking in an intuitive high-level language". Here is a short example of Order code that generates the complete lyrics to the song "99 Bottles of Beer on the Wall": #define GEN_phrase(N_bottles, N_minus_1_bottles) \ N_bottles of beer on the wall, \ N_bottles of beer, take one down, pass it around, \ N_minus_1_bottles of beer on the wall. #define ORDER_PP_DEF_8bottles \ ORDER_PP_FN(8fn(8N, \ 8cond((8greater(8N, 1), \ 8separate(8N, 8quote(bottles))) \ (8equal(8N, 1), \ 8quote(1 bottle)) \ (8else, \ 8quote(no more bottles))))) ORDER_PP(8for_each_in_range (8fn(8N, 8emit(8quote(GEN_phrase), 8tuple(8bottles(8N), 8bottles(8dec(8N))))), 100, 1)) (The above is an extract from a completely documented example.) There are two known caveats. First of all, the Order interpreter requires standard C variadic macros and placemarkers, which aren't standard C++, yet. The second caveat is that the Order interpreter currently requires a standards conforming preprocessor. The interpreter has been developed on the GNU CPP (3.x). Theoretically, the interpreter should be quite portable to less conforming preprocessors, because the interpreter is a "closed system of macros", but I personally don't have the preprocessors nor the time, though I would be happy to assist in such porting work by providing information on the interpreter. I'm currently working on the Order programming manual. I have already written several completely documented examples for the programming manual, which should be enough to get one started in using the Order interpreter, but one example I'd like to have would be a state machine compiler (SMC). Instead of implementing and documenting a SMC myself, I'd like to challenge *you* to write such a SMC example to be included in the forthcoming manual. Knowing that the documentation is still unfinished, I will be happy to assist people writing such a compiler (or some other kind of code generator) through e-mail (I might setup a mailing list). This might also help me to identify specific issues (e.g. sources of confusion, important design heuristics) that need to be addressed in the forthcoming programming manual. If you are interested in seeing the future of C preprocessor metaprogramming by trying out the Order intepreter and implement a state machine compiler (or some other program generator), please contact me at vesa_karvonen(a)hotmail.com. Note that you won't need previous Boost.Preprocessr library experience. Learning to use the Order interpreter should be an order of magnitude easier than learning to use the Boost.Preprecessor library. After I've completed the Order programming manual, I will release the Order interpreter (independently) and submit it to Boost if there is enough interest. Regards, Vesa Karvonen _________________________________________________________________ STOP MORE SPAM with the new MSN 8 and get 2 months FREE* http://join.msn.com/?page=features/junkmail

1 0

[string_algo] split suggestion
by Vladimir Prus 08 Sep '04

08 Sep '04

Hello, suppose I have a string "module.foo1.port" and want to get the second dot-separated element. I think I can use the 'split' algorithm, but it does not look very convenient, I need to declare container, then call split and then obtain the result. In Qt, there's QString::section method, which allows to do this in one line. Here's example from the docs: QString csv( "forename,middlename,surname,phone" ); QString s = csv.section( ',', 2, 2 ); // s == "surname" And the complete docs are at: http://doc.trolltech.com/3.3/qstring.html#section Maybe, something like this can be added? - Volodya

2 3

RE: [boost] Re: RFI: RMI in C++
by Schalk_Cronje＠McAfee.com 08 Sep '04

08 Sep '04

In a related vein, I have been working on a generic functionality to launch asynchronous functions be it in another thread, another process or even out-of-box. The key is the definition of a set of asynchronous function traits allowing a number of free functions such as run_task() wait_task() and task_result() to be presented. One might for instance have something like to run a task on a different thread // Assuming boost::threader is defined and != boost:thread // The following line will launch a function on a separate thread using boost:thread. task_id<boost::threader> id= run_task( boost::threader(), boost::bind( my_dns_request, "www.boost.org" ) ); // do some work here { } // and some time later wait for request to finish wait_task( id ); By specialising the asynchronous function traits it can allow for requests to performed on another host via SOAP or in a RMI-lie fashion for instance. Would anyone be interested in something like this?

1 0

Re: [boost] [serialization] request: low-level info about order of serialization
by Robert Ramey 08 Sep '04

08 Sep '04

>I'm slowly designing the addition of serialization support to >Boost.MultiIndex, and come up with a need that, AFAIK, the >current serialization library does not cover: >The serialization of a multi_index_container should ensure that >the order in which elements appear is preserved for all indices >of the container. Appear? >This implies serializing the elements and then >recording the appropriate rearrangements in each index. I'm >writing the code for serializing these rearrangements in >an efficient manner as some sort of "diff" sequences, using >an algorithm called "longest increasing subsequence" (LIS). >The algorithm would greatly benefit for some low-level API >by the serialization lib that, given an object reference, would >return the order in which that object was serialized. I guess this >information is already available internally, as the lib must keep >track of previously saved objects. >If this requirement is deemed too exotic to provide to the >general user, well, I can write something myself without aid from >the lib, but I thought I should ask at least :) It seems too exotic to me. The focus of the serialization library is to re-create exactly that which was there before. So far, that has already been possible with the API provided. Some containers (e.g. slist) required a little bit of special handling to preserve sequence but this did not require any change in the basic API. All of this special handling is part of the implementation of the container in question. I'm really not sure what your doing, so without knowing more its hard for me to comment. Robert Ramey

2 1

Re:[boost] Boost serialization: release configuration linker errors
by Robert Ramey 08 Sep '04

08 Sep '04

Andy Favell >Thanks for the info, actually yes, I am using version 1_31. Is that a >mistake by me? Personally I would recommend using 1.31 until 1.32 is released. >Can you tell me where the CVS tree is, thanks, www.boost.org main page has a link to the main cvs tree. Robert Ramey

1 0

boost::generic_pool ??
by Rohit Joshi 08 Sep '04

08 Sep '04

boost::pool is specific to memory pool. boost doesn't have library to support generic pool which can be used for connection pooling, thread pool or any generic object pooling. Look at this article : "Generic Pool : Policy based design (http://www.codeproject.com/library/Generic_Pool_Design.asp) I like the concept and let's make it as part of boost library. What's your opinion???

1 0

IOStreams basic_newline_filter convenience request
by Jonathan Graehl 08 Sep '04

08 Sep '04

For basic_newline_filter (great idea; I hadn't even realized Macintosh had yet ANOTHER newline convention), it would be nice to be able to get the current line number and possibly even the character number on that line, for reporting errors in input. I realize this should be possible as a separate filter counting '\n' and non-'\n' characters, which handles the output of basic_newline_filter, but I don't think the cost of maintaining one or two counters would be too much a burden for those who don't need it (or if it is, provide versions with and without). Even nicer would be a call that extracts up to the previous N already consumed characters, for even more helpful context (I have already made a practice of showing the next N characters to be read in case of a fatal error, when the input is a file and not interactive). Obviously this could be a filter in its own right, and really has nothing to do with basic_newline_filter.

2 1

possible conflict with new mpl
by Pavol Droba 07 Sep '04

07 Sep '04

Hi, After merging the new MPL version, an error popped out in vc7 tests of string_algo lib. http://tinyurl.com/3t6zc It seems that std::distance is conflicting with something else. I'm using both "using namespace std;" and "using namespace boost;" in the tests. This problem do not appear with other compilers. I can possibly fix it with the explicit qualification, but it may just hide some other problem. Any suggestions? Regards, Pavol

3 4

IOStreams Formal review -- Guide for Reviewers
by Jonathan Turkanis 07 Sep '04

07 Sep '04

Dear All, I've been very pleased with the discussion of the iostreams library so far. I'd like to thank all those who have posted review and comments. One thing that has been lacking, to a large extent, is a detailed examination of the source code. I understand that this may seem a daunting task, since the library is quite large. Therefore, I would like to point out the relatively small bits of the source which contain the core implementation. I'll also give a brief description of the filtering framework, to make it easier to answer the questions raised by Carlo Wood that large amounts of data are being copied needlessly. Finally -- the easiest part -- I'll mention what I think are the most important outstanding issues about the library interface. ----------------------------------------------------- Part I: Overview of the source. Even if you only look at one of the following three sections, I'd be very happy :-) A. Filter and resource support. This provides the infrastructure for the generic i/o operations read, write, close, etc. It contains no definitions of stream or stream buffers: <boost/io/categories.hpp> <boost/io/concepts.hpp> <boost/io/operations.hpp> <boost/io/io_traits.hpp> <boost/io/detail/ios_traits.hpp> <boost/io/detail/wrap_unwrap.hpp> B. Policy-based streams and stream buffers. This provides the implementation of the fundamental library component streambuf_facade: <boost/io/detail/adapters/filter_adapter.hpp> <boost/io/detail/adapters/resource_adapter.hpp> <boost/io/detail/streambufs/direct_streambuf.hpp> <boost/io/detail/streambufs/indirect_streambuf.hpp> <boost/io/streambuf_facade.hpp> C. Filtering streams and stream buffers. This provides the infrastructure for chaining filters. <boost/io/detail/chain.hpp> <boost/io/detail/streambufs/chainbuf.hpp> <boost/io/filtering_streambuf.hpp> ----------------------------------------------------- Part II. Implementation of filter chains. The following diagram should be viewed with a fixed-width font: streambuf1 streambuf2 streambuf3 filter1 -> filter2 -> resource [------------] [------------] [------------] buf1 (size n1) buf2 (size n2) buf3 (size n3) ^ | | filtering_stream Here the end user write to the filtering_stream at the bottom of the diagram, and the data is passed through streambuf1, streambuf2 and streambuf3, each of which contains a character buffer and either a filter or a resource. The end user, through the filtering stream functions and operatiors, writes *directly* to buf1. When buf1 is full, the buffer's contents are passed to filter1 as follows: filter1.write(streambuf2, buf1, buf1 + n1); This writes *directly* to buf2. When buf2 is full, filter2 is called filter2.write(streambuf3, buf2, buf2 + n2); This writes *directly* to buf3. When buf3 is full, resource is called: resource.write(buf3, buf3 + n3); In the general case, data is copied no more than absolutely necessary. There are some special cases where the copying is wasteful, though. For instance: 1. If filter1 is just a passive observer, simply counting the number of occurences of '\n', or copying the data to a logging stream, then the end user should really be writing directly to buf2. Filter1 could process the data using the same buffer as filter2. 2. Same as above, but filter1 also modifies the data in-place, making character-by-character modifications. (E.g., a toupper filter). This can be handled the same way. 3. If 'resource' is a stream or stream buffer, it could be assumed to do its own buffering. In that case, filter2 should be writing directly to resource, instead of to streambuf3: filter2.write(resource, buf2, buf2+ n2). These three cases can be handled easily by modifying the existing framework. I didn't add special treatment because it occurred to me rather late in development. There is another class of cases in which the current setup is wasteful, but I think it is rather domain-specific: 4. Most filters in the chain modify only small parts of character sequences, leaving big chunks unchanged. For example, a web server might have a chain of filters which add headers to an HTTP message, but leave the body unchanged. In this case, it might be better to allow the filters to send the body through the chain simply as a pointer to a file or memory block. If at some point a filter needs to modify the body, it will read the actual data, modify it, and send it to the next filter as a sequence of characters rather than a pointer to a file or memory block. To optimize case 4 would require a major library extension. My feeling is that it is not necessary at this point, but I'd like to know what others think. ----------------------------------------------------- Part III: Interface questions: 1. How to handle read and write requests which return fewer characters than requested, though there has been no error, and EOF has not been reached. I think some answer to this question is necessary to allow the library to be extended later to handle models orther than ordinary blocking i/o. I mention three possibilties here, http://tinyurl.com/6r8p2, but only two are realistic. I'm interested to know how important pople think this issues is, and what is the best way to resolve it. 2. The stack interface. Is the interface to the underlying filter chains rich enoguh? Originally is was similar to std::list, so that you could disconnect chains at arbitrary points, store them, and reattach them later. I decided there wasn't much use for this, so I simplified the interface. 3. Exceptions. James Kanze has argued repeatedly that protected stream buffer functions should not throw exceptions (http://tinyurl.com/5o34x) I try to make the case for exceptions here: http://tinyurl.com/6r8p2. What do people think? 4. Closable. Many output filters need to write additional information to a stream as soon as it is about to close. For instance, a gzip_compressor needs to write a checksum and message length. This is one of the motivations for the 'Closable' concept (http://tinyurl.com/3pg5j) Sometimes, however, the beginning -- rather than the end -- of a character sequence requires special treatment. For instance, a gzip_compressor must write the gzip header before the compressed data is written. Currently this has to be implemented using a 'first-time switch'. So the question is: Should an open() function be added to the closable interface, to eliminate the need for first-time switches? Alternatively, should there be a separate Openable concept? ----------------------------------------------------- Best Regards, Jonathan

1 0