- Boost - lists.boost.org

Cyclic Queue Requirements and Description
by Sasha Goldshtein 21 Feb '04

21 Feb '04

Good day, Assume the following requirements from a container: - O(logn) find operation - O(1) random access operation - O(logn) insert, O(logn) delete of a block of SEVERAL elements at a random position in the container This container can be described as a cyclic queue - a queue that you push items at its back and remove items from its front, but retaining the ability to randomly access any element in the container according to its index. The cyclic nature of the queue is in that if gaps are created due to element removal, then the inserts will first attempt filling those gaps (and expanding the queue IN THE MIDDLE if necessary) prior to moving to the back of the queue, enlarging it and copying the elements. The following 'diagram' demonstrates the idea: x x x x x x x x x x x x x x x x x x x (1) (2) (3) (1) - elements are normally removed from here. (2) - a gap that was created due to removal of two elements from the middle of the container. (3) - elements are normally inserted here, unless there are gaps in the container. Now if we want to insert two elements, we can just put them instead of (2) and we're done. But what if we want three? The requirement is to expand the queue to fill the gap and make room for the elements - i.e. insert at (2) but make room, at (2), for another element. I hope the requirements are clear :) Anyhow, I've had an idea of implementing this as a linked list of blocks, each being moved to the free pool when fully deallocated and pushed at the end of the queue from the free pool if all end blocks are full, if needed. Is there any interest in this sort of container? Is there any existing / pending library in Boost or elsewhere that provides an implementation of a similar concept? Have you any ideas that can make the whole problem go away by using some combination of the standard containers? Thanks in advance to all, Sasha Goldshtein.

3 3

Future of Boost.Thread part II
by Michael Glassford 21 Feb '04

21 Feb '04

In the "Future of Boost.Thread" thread, Jeff Garland said: > I believe exception propagation can be a useful model at times, <snip> > But as I believe I said earlier I hardly believe it is the > most important capability that should be added to Boost threads. In another post he said: > There are lots of other things that boost.threads lacks > when stacked up against more comprehensive solutions > which are probably more important than cross-thread exceptions... In yet another post, Matt Hurd said: > I do need to set thread priorities however. > This is more important to me than cancellation. This leads me to ask, while the interest sparked by the "Future of Boost.Thread" thread is still hot: what are the most important things, in your opinion, that Boost.Thread lacks? Mike

8 14

unique_type
by Jody Hagins 21 Feb '04

21 Feb '04

This code is extremely simple, but it begs several questions, and I hope this forum is appropriate for discussion: 1. Is there something similar in boost already? 2. Are nested anonymous namespaces portable across most common implementations? 3. Does anyone know of a better way of doing this, especially overcoming the problem with having multiple declarations on the same line? 4. Does anyone know of a way to create a unique object id constant that does not require something like using the address of a static variable -- this would require memory for each instance of the object id? 5. Any other comments about this snippet, or related issues? Thanks!! #ifndef wjh__unique_type__hpp_ #define wjh__unique_type__hpp_ // Some of my meta-programming tasks require a completely // unique type. I am sure there is a better way, but this // is what I currently have. // // Simply use the macro WJH_UNIQUE_TYPE in any source file, // and a unique type will be defined. // // This depends on: // __LINE__ providing the line number of the source from which // the macro is called. // // The nested anonymous namespace is specific to the compilation // unit. So, each unit can have a type created with the same // line number, but the two types will still be unique. // // Note that it "breaks" if you put more than one WJH_UNIQUE_TYPE // on a single line of code. // // I tried to create an OID at compile time, but was unsuccessful. // This would certainly make the job of creating a unique type // a lot easier. // // I almost always use the macro directly: // wjh::typemap<std::string, WJH_UNIQUE_TYPE> // but there may be reasons for: // typedef WJH_UNIQUE_TYPE type_x; namespace wjh { namespace detail { namespace { template <int v> struct unique_type_helper { }; } // end anonymous namespace } // end detail namespace } // end wjh namespace // Construct a "unique" type #ifdef WJH_UNIQUE_TYPE #warning WJH_UNIQUE_TYPE is already defined! #else #define WJH_UNIQUE_TYPE wjh::detail::unique_type_helper< __LINE__ > #endif #endif // wjh__unique_type__hpp_ -- Jody Hagins Some men are born mediocre, some men achieve mediocrity, and some men have mediocrity thrust upon them. -- Joseph Heller, "Catch-22"

2 1

FC++ formal review extended through 3/1/04
by Mat Marcus 21 Feb '04

21 Feb '04

I have received several requests to add time to the formal review period for the FC++ library. This library presents a new paradigm for many C++ programmers and requires a healthy investment of time to review properly. In addition, interesting relationships exist between FC++ and existing boost components. So far, there have been relatively few reviews. For these reasons I am extending the review period through the end of Monday, 3/1/2004. Please try to find time to post your review next week if you haven't already. Even if you don't have time for a full review, simple questions that may promote discussion about the intent of the library, its relation to other components, the ease of understanding for typical boost users, etc. are very welcome. But most of all, deeper reviews by the boost community will serve as essential aids to help me decide whether this library is ready to become a part of boost. If you are interested in FC++, now is the time to come forward. Thanks in advance for you time/volunteering, Mat ### original notice reproduced below for your convenience The formal review of fcpp by Brian McNamara and Yannis Smaragdakis is now in progress, running from Friday February 13th at 12 noon, PST and and run to Monday, February 23rd, 12 noon PST. The library is currently available at <http://www.cc.gatech.edu/~yannis/fc++/boostpaper/> Here is a brief introduction to the library: FC++ is a library for doing functional programming in C++. The library provides a general framework to support various functional programming aspects, such as higher-order polymorphic functions, currying, lazy evaluation, and lambda. In addition to the framework, FC++ also provides a large library of useful functions and data types. The main utility of the library comes from its ability to implement functional programming designs, especially those which use higher-order polymorphic functions or lazy evaluation in significant ways. The library also contains a number of ancillary components that implement features like currying and lambda for function objects; these features are also useful in their own right. For information about submitting a Formal Review, see <http://www.boost.org/more/formal_review_process.htm> Please try out the library and read the documentation and say whether or not you think the library should be accepted by Boost and why. Compiler notes: This library has been tested with icc7 and with gcc-3.1.1 (and various other gcc-3.x.y versions) on Solaris and Linux. The library is also likely to compile on VC++7.1 and Comeau (prior versions of the library succeeded with these compilers, but this particular snapshot has not been tested with them). The library covers a great deal of the C++ language and thus requires a high degree of standard conformance; compilers like gcc-2.95.x and VC++6 will not be able to compile the library. Getting started: The web page http://www.cc.gatech.edu/~yannis/fc++/boostpaper/ mentions all the basics: The zip file will expand into these subdirectories: fcpp/fcpp/ # the library (.hpp) files fcpp/fcpp_clients/ # the example (.cpp) files Running the examples just involves invoking the complier with the right #include paths; for example, # in the fcpp_clients directory g++ -I/path/to/boost -I../fcpp some_example.cpp There is also a gnu-style Makefile included with the clients (examples), which will compile all of the examples in batch (you will have to edit a tiny bit at the top of the Makefile). The examples in the clients directory are a mix of both (regression-type) tests cases which cover the features of the library and example applications which demonstrate some of the library's utility. The README file in the client directory gives a short explanation of some of the more interesting clients. The documentation at http://www.cc.gatech.edu/~yannis/fc++/boostpaper/ provides a walkthrough and reference for most of the main features of the library. There are also some pointers out to other papers and documentation on the main FC++ web site: http://www.cc.gatech.edu/~yannis/fc++/ Conformance to Boost guidelines: The library meets most of the requirements described at http://www.boost.org/more/lib_guide.htm Here are a few notable exceptions: - the current library headers are too "monolithic"; you #include "prelude.hpp" and suck in all of the library - some of the lambda internals should be rewritten to use MPL rather than hand-rolled metaprogramming code - only a few of the example programs utilize the Boost testing framework (to automate regression testing) Should the library be accepted into Boost, Brian will remedy these deficiencies. (If you notice other major problems along these lines, please bring them to Brian's attention during the review.) The Formal Review manager is Mat Marcus.

2 1

RE: [boost] Re: [Threads] Simple active object wrapper, take 2
by Darryl Green 21 Feb '04

21 Feb '04

Hi Matty, > -----Original Message----- > From: Matthew Vogt [mailto:mvogt@juptech.com] > Subject: [boost] Re: [Threads] Simple active object wrapper, take 2 > > Actually, the paper does note that for performance reasons, > the thread could > be replaced with a thread pool. This requires support, > however, in that the > Method Request needs to be able to lock the resources needed > to perform the > task prior to doing so. I haven't read the paper you mentioned, but I do have POSA volume 2 by Schmidt et al in front of me. Based on the description in it, your code definitely does (very cleanly) provide a way to implement the active object pattern. > > In terms of my wrapper, the object wrapped needs to have > 'hooks' for locking > its resources, and the active<> wrapper class would need to > have a policy > class to perform the 'Scheduler' role, which knew enough to > use the resource > locking hooks. I don't see a great deal of use for the thread-pool based active object variant briefly described in the book, where the active object has a whole thread-pool to itself and the object needs its own internal locking. This seems to me to be an implementation detail of the object itself - nothing to do with the active object model. Further I have real difficulty imagining a circumstance in which I'd want all those threads sitting around dedicated to one AO (like I can talk...). However, it sounds like you are describing something different. I can (if I try hard enough) imagine that I'd like to specify the level of concurrency allowed between methods of an object and have a scheduler clever enough to order the execution of those methods efficiently based on this (and probably request priority as well) on a (shared by multiple such AOs) thread pool. A dynamic thread pool could then scale the number of threads used based on the actual observed/required concurrency. However, I suspect that the above isn't going to fly, if only because it is likely to make the scheduler a bottleneck. Anyway, nobody seems to want to give me a box with enough processors and I/O to make this much fun - and I can't think of anything (useful) to run on it :-) Is that anything like what you had in mind? Does anyone actually re-use some of the more exotic veriations of these patterns often enough that they consider a framework for implementing them is actually anything more than a (fun?) excercise? Regards Darryl. ########################################################################## This e-mail is for the use of the intended recipient(s) only. If you have received this e-mail in error, please notify the sender immediately and then delete it. If you are not the intended recipient, you must not use, disclose or distribute this e-mail without the author's prior permission. We have taken precautions to minimise the risk of transmitting software viruses, but we advise you to carry out your own virus checks on any attachment to this message. We cannot accept liability for any loss or damage caused by software viruses. ##########################################################################

3 2

status of wchar_t support in filesystem::path?
by Paul Miller 20 Feb '04

20 Feb '04

I just started using boost recently and it seems excellent so far. One of the first classes I started using is filesystem::path, with the intention to use it portably on Windows, OS X, and Linux. On Windows and OS X, you can work with paths in Unicode. Presumably Linux still works with multi-byte characters. Is there progres toward a wchar_t-aware path? Is there an existing strategy for storing my Unicode Windows/Mac paths as UTF-8 with the existing path? I notice the existing posix checks would fail horribly in this case. Is a UTF-8 checker in order?

8 25

[MPL] insert_range bug with empty sequences
by Jonathan Turkanis 20 Feb '04

20 Feb '04

I have found that applying insert_range to append elements to an empty sequence has no effect. E.g., the following compiles without error on every compiler I have tried (VC7.1, GCC 3.2, Intel 7.1 and CW8.0). typedef mpl::insert_range< mpl::list0<>, mpl::end< mpl::list0<> >::type, mpl::list<int> >::type result; BOOST_STATIC_ASSERT((size<result>::type::value == 0)); I get the same result if I use vectors instead of lists. This looks like a bug to me. Jonathan

2 2

RE: [boost] Re: algorithms namespace
by Reece Dunn 20 Feb '04

20 Feb '04

Stefan Slapeta wrote: >Pavol Droba wrote: > >>It is not really reasonable to await from >> a user to always type boost::algorithm::string::trim. >> > >Maybe it could help a little bit to replace 'algorithm' by 'algo' and >'string' by 'str'. > >IMHO, also shorter namespaces like 'boost::filesystem' have the problem of >beeing too long to be used on every access. Long typenames like >boost::filesystem::directory_iterator have a very high capability to make >the code unreadable very quickly. why not use: namespace sa = boost::algorithm::string; sa::trim( ... ); or namespace fs = boost::filesystem; fs::directory_iterator di = ...; Surely this gives you what you are after (shorter namespace names) without modifying the namespace currently used by the library (which will break existing code that uses the libraries). This is what namespace aliases are for and is used for the filesystem library in the regression test implementation. Regards, Reece _________________________________________________________________ It's fast, it's easy and it's free. Get MSN Messenger today! http://www.msn.co.uk/messenger

8 14

Re: [boost] [Filesystem] behaviour of branch_path
by Beman Dawes 20 Feb '04

20 Feb '04

At 10:48 PM 1/25/2004, Gustavo Guerra wrote: >Why does branch_path return path("") with simple paths like "file.ext"? >Would'nt it make more sense to return path(".")? At least that was I was >expecting. I had to go carefully see at documentation to discover it wasn't >like that, because in other place in the docs its writen "A non-empty path >is specified as a precondition because an empty path is almost certainly an >error". > >This way, for example, if I have some code that gets the parent directory >of a path and then uses that in other path operations, I'm forced to make >special cases checking for has_branch_path, when if it returned "." it >would work better for most cases... In thinking more about this need, it seems to me that changing path::branch_path() may not be the best approach. Class path member functions work only on the lexical representation of a path, regardless of the actual state of the external filesystem. The use cases I can think of usually need to look at the external filesystem. Also, The decomposition functions return elements of the path. It seems a bit surprising for a decomposition function to return "." when it is not an element of the path. Perhaps the use cases you are running into would be better dealt with by new operational functions which do look at filesystem state. Two possible functions come to mind (subject to better naming): path directory_path_of_file( const path & ph ); Throws: !exists(ph) || is_directory(ph) Returns: branch_path(ph).empty() ? path(".") : branch_path(ph) path directory_path( const path & ph ); Throws: !exists(ph) Returns: is_directory(ph) ? ph : directory_path_of_file(ph) Thoughts? --Beman

1 0

RE: [boost] Re: Re: full functoids
by Rozental, Gennadiy 20 Feb '04

20 Feb '04

> > (BTW it would really help for the whole > > library review, if you could provide a little introduction what is a > > "functional programming" in a first place; how it differ from other > > programming styles and what is the place of your library in > this - I mean > > what purpose does it serve, what solution does it provide). > > I think this is way out of scope for the library. Functional > programming has > been around for ages, and it shouldn't be up to Brian to > introduce and > explain all of it in his introduction. I merely need just few starting pointers and if possibly couple links. Also explanation what does this library provide exactly would be helpful. > > If I need to include boost/fcpp/plus.hpp separately from > boost/fcpp/minus.hpp, > I'm going to very, very unhappy. I agree with breaking up > large components > intro multiple headers, but when we get 20 headers with 10 > lines of code in > them each, all related, we've gone too far. > > Doug Well. It's the matter of taste. I believe we both could be happy if structure would include separate headers in boost/function directory and one boost/functional.hpp that include them all. Gennadiy.

2 1