January 2005 - Boost - lists.boost.org

[rangelib]RFE: iterable range tuple to flatten tree?
by Larry Evans 13 Jan '05

13 Jan '05

A recent thread in c.l.c++.m: http://groups-beta.google.com/group/comp.lang.c++.moderated/browse_frm/thre… illustrates the general problem of flattening a tree-like structure to iterate over the leaves. Could iterable ranges be extended to do this sort of thing. I'm thinking that if the depth of the tree, D, were known in advance, then a tuple of iterator ranges could be used. i.e. for tuple, t, t.get<0> is a range over leaves of the tree, and t.get<1> is a range over the next level branch in the tree, until t.get<D-1> is the iterator over the branches in the root of the tree. I've currently a need for this; hence, I would be interested in knowing if there any plans for extending rangelib in this direction.

1 1

Access to protected member functions
by Alexander Nasonov 12 Jan '05

12 Jan '05

Hello Boosters, I know it's really BAD idea but sometimes ... especially if you ABSOLUTELY sure ... you may access protected member functions of an object without touching a class of that object. Two steps are required. First, at global scope in .cpp file (never in a header!) you should declare all functions you want to access later in this file: DECLARE_ACCESS_PROTECTED_FUNCTIONS( (foo)(bar) ) and, then you can access them: X x; // you want to access x's protected function bar. No problem: long r1 = ACCESS_PROTECTED_FUNCTION(X, x, bar, (4, 5, 6) ); Please, don't use if you're not sure. You've been warned! -- Alexander Nasonov

1 0

Re: Patterns (was Singleton)
by Dave Handley 12 Jan '05

12 Jan '05

During the recent discussions on Jason's Singleton implementation, I mentioned that I had some other code for patterns available. I have just put my composite implementation up on a web-server for people to have a look at, the following links lead to the code: http://dah.me.uk/pattern_tl/Composite.h http://dah.me.uk/pattern_tl/CompositeShallowIterator.h http://dah.me.uk/pattern_tl/CompositeDeepIterator.h http://dah.me.uk/pattern_tl/CompositeTypedShallowIterator.h http://dah.me.uk/pattern_tl/CompositeTypedDeepIterator.h http://dah.me.uk/pattern_tl/CompositeFunctorIterator.h Usage of the code is pretty simple. A composite is created using CRTP - for example class node: public class pattern_tl::composite<node>; You are required to implement a Clone function since this is used for tree duplication. There is a basic set of functions to add entries to the tree (for example push_back), remove entries from the tree, and navigate up the tree. Then there are a whole bunch of iterators to use in getting around the tree. The shallow iterators just iterate over direct descendents of a node, the deep iterators iterate over the entire tree below a node (including the start node), the typed iterators use RTTI to allow you to shallow/deep iterator over the tree picking out nodes of a particular type; and the functor iterator applies a functor to each node to decide whether to return it in an iteration (note that there are no const versions of the functor iterators). If you don't include either CompositeTypedShallowIterator.h or CompositeTypedDeepIterator.h then you don't need to build with RTTI. I'm pretty sure that there is scope for improvement, and I would appreciate any constructive feedback. Plus I would be interested in the general view about creating a "pattern_tl" library within Boost to contain, for example, this code, plus other generic design pattern implementations including singletons and visitors etc. Finally, I know that for submission to Boost I would need to do some tidying up, changes to naming standards etc, plus I would need to write a test suite - but I'm just interested in general opinions at the moment, and suggestions for improvements. Dave Handley

1 0

Re: Singleton
by Dave Handley 12 Jan '05

12 Jan '05

Jason, I just want to clarify a couple of points in your last post: <snip> > > Since my revision, the singleton is not forced to be created > statically. Singleton A will only be created statically if client code > creates a static dependency on A, or if another singleton B has a static > lifetime and depends upon A. If the actual method of allocation (new) > should be made more flexible, would adding a template allocator > parameter similar to that used by stl containers be sufficient? > I've just looked at your code again, and I actually note that the only creation policy you use is effectively the CreateUsingNew policy of Loki. The singleton is always created using a new in the AddDependency function. Providing an allocator template is essentially what is done in Loki so that would suffice to resolve this particular difference. >> ...a single lifetime policy (dependencies) > > Again, because I removed the enforced static dependency that was in the > original code, my singleton should allow multiple lifetime types based > on where and how dependencies are used. > Sorry, I think you have misunderstood me. I know that the dependencies method can be used in different ways, but it is still only a single policy. The reason for providing completely different policies for the lifetime policy is just that different projects require different solutions. I know for example that the dependencies model would fall down very quickly in the system I code in at present. We have a singleton that is the root of the tree that contains all the data in the system. Everyone uses this singleton, but doesn't tend to hold out references (dependencies). Under your dependency model, we would be almost forced to place a dependency in the main function - but here lies the problem. We actually have a number of different products which share the code base, but provide different main functions (and a few key interface classes) - this would mean we are coupling the main singleton to loads of places in the code. Using lifetimes, we can trivially make sure that this is the last singleton to come down. > > Doesn't the same potential problem exist with ref-counted smart > pointers? Wouldn't it be accurate to say that it should be illegal to > create singletons with cyclic dependencies in the first place? With my > current design, just getting a pointer to the singleton introduces a > dependency. Thus, if a singleton B requires access to a singleton A for > only certain function calls, it should simply get access to the pointer > to A's instance at the beginning of those function calls. A singleton > should only own a dependency to another singleton if it actually > requires it for its entire lifetime, so cyclic dependencies simply don't > make sense to write. There is exactly the same problem with reference counted smart pointers. That is why the boost smart pointer library includes the weak_ptr. If you (for example) write a composite tree, and use smart pointers in both directions, the tree will never be destroyed - so you normally make the parent pointer a weak pointer. You are absolutely right in saying that it makes no sense to have a cyclic singleton dependency - but I can guarantee that in a big enough system, someone would make the mistake and put one in - especially since you don't explicitly check for cyclic dependencies (something that is hard to do anyway). > > Hard coding a longevity number for each singleton seems dangerous to me, > because it is difficult to see what order all the singletons would be > created in without tracking each down and looking at it. Any time a new > singleton is added, many of the numbers might need to be shuffled. > Explicitly owning a dependency or getting the instance seems more > intuitive to me as to document what the singleton actually requires. > Generally, if I use longevities, I place the longevity numbers in a header file. Either explicitly creating a longevity number for every singleton in there, or creating a set of longevity numbers that every singleton uses (possibly sharing numbers when there are no dependencies). I'm not saying dependencies are wrong - I'm just saying that a generic implementation should really provide the choice. I prefer to use longevities - you clearly prefer the dependencies - other people prefer to use Phoenix Singletons (singletons that re-create themselves from their own ashes if they are re-accessed after destruction). Even though I prefer longevities, there are some systems where I would probably use a different lifetime policy because it made sense to do so there. I would personally recommend having a read of Alexandrescu's book, especially the sections on the lifetime policies, then browsing the Loki code. If you implemented the allocation policy, used CRTP, implemented a threading policy, and also looked at integrating some different lifetime policies, then I personally think that you would have an ideal library to put forward for inclusion in Boost. Dave

5 13

anfa-regex performance
by Vladimir Pozdyayev 12 Jan '05

12 Jan '05

Some time ago Eric Niebler wrote: >You commented on the algorithmic complexity, but have you >benchmarked against Boost.regex? I'd be very curious to see how your >back-end stacks up performance-wise. I have done some benchmarking of ANFA-regex versus Boost.Regex, and it revealed the following (quite expected) trends. For very simple match problems ANFA-regex is by about an order of magnitude slower. Moreover, the slowdown noticeably increases with the number of capturing parentheses. For real-world-like match problems, like finding paragraphs of "libs/libraries.htm" by matching it against ".*?(<p>.*?</p>)", the slowdown drops to about 1.5x--2x. However, in this case the "regex_search" function of Boost.Regex performs much faster than "regex_match" (thanks to Knuth-Morris-Pratt algorithm, AFAICS). For complex / pathological problems ANFA-regex performs much faster (any number of orders of magnitude, depending on the problem) than Boost.Regex---the linear complexity pays off. Both Boost.Regex and ANFA-regex have linear complexity for simple regexes. Highly optimized nature of Boost.Regex allows its complexity to have much lower time constant than that of ANFA-regex, resulting in much better performance. However, for more involved regexes Boost.Regex gets nonlinear complexity, with respective consequences. The most obvious way of speeding up is to optimize the actual code (or help the compiler to optimize it). The problem is, the ANFA simulation algorithm is quite simple and straightforward, so there's not much room for improvement. On the other hand, there's a whole new story in optimizing the algorithm itself. Two main slowdown factors are (1) excessive tag copying and (2) nondeterminism. I can name two ways to reduce (1). The factor (2) is all about ANFA to ADFA conversion. These optimizations are subject to additional research. And, of course, there are additional speed reserves in KMP for search problems. (A side note. An ANFA version used for benchmarking is not the version I uploaded into yahoo groups recently---I actually managed to double its speed, or something like that.) -- Best regards, Vladimir Pozdyayev.

3 2

Typeof library: formal review request
by Arkadiy Vertleyb 12 Jan '05

12 Jan '05

Dear Boosters, Peder and I believe that our combined Typeof library reached a stable condition. Considering the fact that, during preliminary submisions, a number of people expresed certain interest in the library, we are asking for the formal review. The library has been tested with the following compilers: VC6.5 / 7.0 / 7.1 GCC 3.4.2 (forcing the typeof emulation) Also, during the discussion, a few people were able to successfully build the tests with Intel and como. Although we cannot garantee the library is compatible with these compilers right now (we don't have access to these compilers), we have a reason to believe that porting to them would be quite easy. The library is located at: http://groups.yahoo.com/group/boost/files/typeof.zip Regards, Arkadiy

3 2

Any interest in a decimal and money class?
by Martin 12 Jan '05

12 Jan '05

(I know that "Currency" received 0 votes at the OOPSALA conference but maybe someone is interested anyway) I have implemented a type for handling decimal math and a type specialized for monetary values. decimal64 type ------------- The type stores a decimal value with specified numberof decimals exactly and also performs all arithmetic operations (+,-,*,/) using decimal math. (Internally the type stores the value as an int64 value which gives 18 DECIMAL digits precision. Multiply and divide uses a 128 bit temporay to avoid rounding errors) - All std rounding modes are available plus a few extra such as round_to_even. - Construction of a decimal64 can be made from int, double, string literal (e.g. "1.234") and other decimal64 values. - Operations can be made on decimal64 objects with different number of decimals and/or different rounding policy. Result of a binary operation on two decimal64 values will have the number of decimals and rounding policy of the left operand. - Streaming works the same way as floating point values but the scientific format is ignored. There are 2 decimal64 types defined: - decimal64 - all constructors requires specification of number of decimals and optionally rounding mode. decimal64(3.1415, 4, round_to_nearest); - decimal64_spec - a template version of decimal64 where number of decimals and rounding mode are specified as template parameters which allows a default constructor. typedef decimal64_spec<3, round_to_even> decimal3; decimal3 x(3.14), y; The decimal value can be converted into another at any time if a calculation needs to be performed at a higher precision or with another rounding policy. decimal64 x(1.2, 1, round_to_nearest); // calculate x*PI/2 using 5 decimals // result is stored in x with 1 decimal, // rounded with round_to_nearest policy x = x.as_decimal(5) * decimal64(3.14159, 5) / 2; Some things I would specificly like to have comments on: 1. Operations are not allowed on doubles. Double values always need to be converted into a decimal value first. e.g. x * decimal64(3.14, 2). Is this something that is needed? 2. No overflow detection or +inf etc. Just like with the integer types there is no checking for overflow on operations. Money type ----------- The money type uses a decimal type to store a monetary value. The functionality is the same as for the decimal64 type with the following exception: 1. Operations are more limited to detect errors. The limitations are: - Money * Money is not allowed. (Money * Decimal is allowed) - Money / Money is allowed but the result is a Decimal (not money) - Money + Decimal is not allowed (Money + Money is allowed). (The same applies to - and all comparison operators) Integers works as both money and decimal so Money*2 and Money+1 is always allowed. 2. Streaming uses locale moneypunct for formatting and parsing. As with the decimal type two money classes are defined - money_base - construction always requires number of decimals and optionally rounding policy typedef money_base<decimal64> money64; money64 x(100,2,round_toward_infinity); - money_spec - number of decimals and rounding policy are template parameters. typedef money_spec<decimal64, 4, round_toward_neg_infinity> money4; money4 x("9.99"), y; locale library -------------- Some time ago implemented helper classes for locale but I never got around submitting it to boost. I needed it for testing the decimal64/money streaming so I cleaned it up and it is included in the package. Building -------- A jam file for building decimal library is included. I have compiled all files and testcases with VS2002 (VC70) and "g++ (GCC) 3.4.2 (mingw-special)". Couldn't get the boost test jam file to work but command line g++ works fine. g++ libs/decimal/test/decimal64_test.cpp libs/decimal/src/decimal64.cpp g++ libs/decimal/test/money_test.cpp libs/decimal/src/decimal64.cpp libs/decimal/src/money.cpp g++ libs/locale/test/locale_test.cpp libs/decimal/src/decimal64.cpp libs/decimal/src/money.cpp There are some differences in streaming which causes a few test errors for money: - VC70 only inserts spaces in the money format if the "internal" adjustment flag and width is set. g++ always inserts 1 space when specifed in the format. I assumed g++ was right so VC70 fails this test. - The default locale with g++ seem to miss a '-' sign for the money format so it fails tests with negative numbers. Library is available here http://web.telia.com/~u84606172/Boost/ Documentation is available in the download as well.

10 30

program_options: compilation fixes
by Graham Bennett 12 Jan '05

12 Jan '05

Hi, parsers.cpp and value_semantic.cpp in 1.32.0 both use 'tolower' without including <cctype>, which on my platform is not included as a side-effect of one of the other headers. I have attached patches which make it compile cleanly for me. Thanks, Graham. -- Graham Bennett

2 1

[serialization] and filesystem::path
by Russell Hind 12 Jan '05

12 Jan '05

Are there plans to add serialization support to filesystem::path? Thannks Russell

1 0

lambda problem (VC7.0 and GNU Dev-C++)
by Sergey Pisarchik 12 Jan '05

12 Jan '05

Hello All, Problem is: what the difference between "type" in such cases? 1) class type{}; and 2) class type1{}; typedef type1 type; I think, they are equal. But... look code. ///////////////////////////////////// //// Begin of code ///////////////////////////////////// #include <boost\mpl\apply.hpp> #include <boost\mpl\lambda.hpp> #include <boost\mpl\placeholders.hpp> namespace mpl = boost::mpl; struct CClass{ void Init(int& i){i--;};}; namespace impl { template<typename TBase> struct CClass0:public TBase { public: void Init(int& i){i--; TBase::Init(i);}; }; template<typename TBase> struct CClass1:public TBase { public: void Init(int& i){i--; TBase::Init(i);} ;}; } typedef mpl::lambda<impl::CClass0<mpl::_> >::type CClass0; typedef mpl::lambda<impl::CClass1<mpl::_> >::type CClass1; template <typename T1, typename T2> struct CMetaFunction1 { struct type1: public mpl::apply<T1, T2>::type{}; typedef type1 type; }; template <typename T1, typename T2> struct CMetaFunction2 { struct type: public mpl::apply<T1, T2>::type{}; }; class CBase { CBase(void) { { CMetaFunction1<CClass1, CMetaFunction1<CClass0, CClass>::type >::type g; int i=5; g.Init(i); } { CMetaFunction2<CClass1, CMetaFunction2<CClass0, CClass>::type >::type g; int i=5; g.Init(i); } } }; /////////////////////////////////////////////// end of code ////////////////////////////////////////////// Explanation: Want impl::CClass1<impl::CClass0<CClass> >; and running g.Init(); CClass1::Init(); CClass0::Init(); CClass::Init(); using CMetaFunction1 everything is OK. but CMetaFunction2 gives CClass0::Init(); CClass::Init(); WHY ??? Tested on VC++7.0 and GNU Dev-C++ P.S. when use my own lamda function Both variants works OK. /////////////////////////////////////////////// template <template <typename> class TBase> struct lambda { template <typename T> struct apply { typedef TBase<T> type; }; }; typedef lambda<impl::CClass0> CClass0; typedef lambda<impl::CClass1> CClass1; /////////////////////////////////////////////// --Sincerely Yours,-- --\ SergeY /-- --<>\\\ PisarchiK ///<>-- --<>()<>--Never surrendeR--<>()<>-- mailto:Sergey_pisarchiK@tut.by

2 1