- Boost - lists.preview.boost.org

Review managers wanted for augmented data structures
by Vadim Stadnik 06 Apr '13

06 Apr '13

Hi all, At present, neither Boost library nor STL provides containers using augmented data structures. I suggest that the Boost community consider solving the challenging problem – how to extend STL by integrating advanced data structures. Is there an alternative of not integrating advanced data structures into STL? IMO, no, since it is equivalent to “STL must go”. C++ cannot ignore performance benefits provided by these data structures. On the other hand, advanced data structures can be implemented in many programming languages and this will make C++ less competitive. Augmented red-black trees could have been included in the very first version of STL. Why is it difficult and has not been done yet? The major obstacle for the integration is the C++ standard specification of computational complexities of single operations for containers and iterators. Augmented trees are non-standard due to different performance guarantees. At the same these data structures are beneficial for complex algorithms, since they offer a wider set of more efficient operations compared to standard containers. The typical performance improvement for one operation is O(log N) against O(N). For less efficient operations these trees normally provide running time O(log N) against O(1), which is good enough for many applications. The C++ STL will be under pressure as long as there are new data structures that offer better running time for user algorithms. Asymptotically, the main parameter that determines the running time of an algorithm is the total computational cost (to simplify the discussion we omit the effect of locality of reference). By definition, the total computational cost is the sum of costs of single operations multiplied by their frequencies. For a general purpose library, such as STL, it is impossible at the design stage to know frequencies of all container and iterator operations required in all possible user algorithms. A more reasonable and practical approach to STL would be to provide a wide set of interchangeable containers and data structures with different performance guarantees and allow programmers to make decisions about the most suitable containers for specific applications. Relatively small frequencies of inefficient operations do not have significant effect on the total computational cost of an algorithm. Thus, in principle, containers and iterators can provide even inefficient operation in order to support more unified interfaces and to improve the generality. The replacement of interchangeable containers offers the advantage of low development cost solutions to performance bottlenecks that arise due to enhancement requests and/or an increase in the number of elements processed by a user algorithm. Also, I’d like to note that the representation of sequences using augmented trees is a frequent point of confusion and probably the fact that was overlooked in the development of previous versions of STL. The general description of the method of augmenting data structures is given in the section 14.2 of this book T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, 2nd Edition, MIT Press and McGraw-Hill, 2001. The specific application of this method is provided for order statistic trees and interval trees. Unfortunately, there is no example of a sequence that stores unordered elements. Probably for this reason augmented red-black trees are often considered to be an improvement of search trees only. The efficient representation of sequences by the described red-black trees follows from the fact that augmenting by the counter of children nodes supports efficient mapping from non-negative integers into container elements. It works both for ordered and unordered containers with unique and multiple elements or keys. There are two libraries in the Boost review schedule: http://www.boost.org/community/review_schedule.html "STL Extensions" and "Countertree". None of them has as yet a review manager. The order of the reviews may not be significant. It is more important that at least one library pass the review. This would help integrating other advanced data structures. Are there Boost experts who could volunteer to take responsibility of review manager for any of these two libraries? Regards, Vadim Stadnik

2 4

[any] C++11 support
by Antony Polukhin 06 Apr '13

06 Apr '13

Hi, There is a patch for Boost.Any, that adds rvalue references support (via Boost.Move) and noexcepts (see ticket #6999 any.patch). It also includes a set of tests, and they pass well. Previous maintainers of the library are away for a long time, so if there will be no objections till the end of next weekend, I'll apply the patch. -- Best regards, Antony Polukhin

1 0

Scope Tracer or General Scope Function with parameter or variable values
by Anlin Zhang 06 Apr '13

06 Apr '13

Hi, I'm wondering if a "Scope Tracer" or a "General Scope Function" can be easily implemented with existing boost libraries now. One example use case is to log variable or parameter values or any program state when entering or leaving a scope, but it can do more than just logging, it can, for example, lock/unlock mutex, or prepare/teardown test cases, etc. For logging requirement, to give you an idea, the expected log message looks like this: >04/10/09 05:29:12:210257 entering func foo with parameter a=10, b=1.5, d.x=10, d.y=[string], global d=2, filename:test.cpp>04/10/09 05:29:12:210257 entering while() a=10, b=1.5, d.x=10>04/10/09 05:29:12:210257 leaving while() a=9, b=1.5, d.x=9>04/10/09 05:29:12:210257 entering while() a=9, b=1.5, d.x=9>04/10/09 05:29:12:210257 leaving while() a=8, b=1.5, d.x=8>...>04/10/09 05:29:12:210257 entering while() a=2, b=1.5, d.x=2>04/10/09 05:29:12:210257 leaving while() a=1, b=1.5, d.x=1>04/10/09 05:29:12:210257 entering while() a=1, b=1.5, d.x=1>04/10/09 05:29:12:210257 leaving while() a=0, b=1.5, d.x=0>04/10/09 05:29:12:210257 leaving function foo with parameter a=0, b=1.5, d.x=0, d.y=[string], global d=2, filename:test.cpp It does not have to be logging, it can do any general processing when entering/leaving a scope. I implemented a small library to do so in 2008 mainly for tracing, it worked fine for me and I never revisited it again until recently. Wondering if boost has libraries to support such a requirment. My implementation has a template class logger_class which can manage the log-level at runtime and send the log message to standard-output or other places. Application code use a macro to invoke the library, the macro can be disabled at compile time, or weakened to only log scope without variables. Example of the macro definition: #ifdef ENABLE_ONLY_SCOPE_TRACER #define SCOPE_TRACER(logger_class, logger, args, level, scope) \ scope_tracer<logger_class> tracer_obj(logger, __FUNCTION__, __FILE__, __LINE__); \ if (logger.get_level() >= level){ \ tracer_obj.init(level, scope).noMore(); \ } #else #ifdef DISABLE_SCOPE_VAR_TRACER #define SCOPE_TRACER(logger_class, logger, args, level, scope) #else #define SCOPE_TRACER(logger_class, logger, args, level, scope) \ scope_tracer<loggerClass> tracer_obj(logger, __FUNCTION__, __FILE__, __LINE__); \ if (logger.get_level() >= level){ \ tracer_obj.init(level, scope) << args; \ tracer_obj.noMore(); \ } #endif#endif Application code example: int globalVar; void MyClass::func1( A a, B&b, C* c, int d, std::string & s){ SCOPE_TRACER(MyLogger, test_logger, a<<b<<c<<d<<s<<globalVar, LOG_LEVEL_TRACE, "func1"); ... int localVar; while(x){ SCOPE_TRACER(MyLogger, test_logger, x<<a<<b<<c<<d<<s<<globalVar<<localVar, LOG_LEVEL_TRACE, "while(x)"); ... } ... } As you see, "<<" operator is being used. But it does not have to be only "<<" operator. Basically any C++ operator can be supported between the logger class and logged type. And the logger_class is not limited to just do tracing, it can virtuall do anything. I can attach the code if needed. The code was compiled with GCC on linux and VisualStudio on Windows. If the above functionality can be easily achieved using existing boot library, please advise how. Otherwise is it worth to request such a feature in boost? Thanks,Anlin

2 1

Regression tests crashing
by Tom Kent 03 Apr '13

03 Apr '13

Sometime yesterday most of the regression tests that I run (not the incremental ones?) started crashing and not sending any results. The screen output is the general error: "No such file or directory: '/home/tomkent/teeks99-02/a/results/boost/bin.v2/libs/any/test/any_test.test'" Looking at the tail of the results/bjam.log file shows this: error: at /home/tomkent/teeks99-02/a/tools_bb/kernel/modules.jam:107 error: Unable to find file or target named error: 'has_float128.cpp' error: referred to from project at error: '../libs/multiprecision/config' That was on Ubuntu 12.04, running the gcc-4.6 tests, but the others (including windows) have the same error. I don't believe anything else changed on the machines that were running the regression tests. You can still see the previous results on the regression results page. Tom Kent

1 0

[utility]result_of - erroneous result type from a C++11 lambda
by Vicente J. Botet Escriba 03 Apr '13

03 Apr '13

Hi, I've started to use C++11 lambda functions with Boost.Thread. The following works with clang-3.2 boost::future<int> f1 = boost::async( []() -> int {return 123;} ); But it fails with gcc-4.6.2, 4.7.2 and 4.8.0 ../example/lambda_future.cpp:25:91: erreur: conversion from ‘boost::future<void>’ to non-scalar type ‘boost::future<int>’ requested boost::future<int> f1 = boost::async( []() -> int {return 123;} ); The current implementation of boost::async uses boost::result_of to get the result type of the callable parameter. Is this a know bug on boost::result_of or gcc compiler? Best, Vicente

9 15

generate algorithm
by Fabian Bösch 02 Apr '13

02 Apr '13

Dear Boost community I am developing a library which extends the STL generate algorithm. It's aim is to improve performance for highly optimized (e.g. vectorized) generation mechanisms while it retains the same interface. This is especially useful when dealing with random number generation as there are several libraries (e.g. Intel MKL or AMD ACML) which provide means to generate a block of random values at once. However, the current STL generate algorithm is not able to cope with such "range generation". Is there any interest in a such a library for Boost? Cheers, Fabian Bösch

4 5

[boost.lockfree] Lockfree on Windows?
by Philip Bennefall 02 Apr '13

02 Apr '13

Hello, I am in need of a lock free fifo for my current project so I looked into lockfree. However, in the documentation I see: boost.lockfree has been tested on the following platforms: a.. g++ 4.4, 4.5 and 4.6, linux, x86 & x86_64 b.. clang++ 3.0, linux, x86 & x86_64 My question is what the status is on Windows? The documentation for boost.atomic says that Windows has been tested, so is there a reason why lockfree might have platform specific issues? When I run the example provided for the single producer/single consumer queue, I get the expected results so it does seem to work. It also states that the queue is lock free. Is it safe to use on Windows at present? Thanks in advance for any information. Kind regards, Philip Bennefall

2 3

[extension] library under construction status
by Lorenzo Caminiti 02 Apr '13

02 Apr '13

Hello all, What's the status of Jeremy Pack's library under construction Boost.Extension? P.S. I read the docs and I have a couple of comments: 1. shared_library as RAII Why isn't shared_library an RAII object? If there's a good reason for that, a RAII object should also be provided scoped_library that will open at construction and automatically close at destruction. 2. get should use function type syntax get<result_type, arg1_type, arg2_type, ...> should be changed to get<result_type (arg1_type, arg2_type, ...)> 3. type_map purpose/name The introduction of type_map seems arbitrary... some rationale needs to be provided as soon as it's introduced in Tutorial 2. Is there a better name than type_map? That name tells me little about what it is.. maybe, factory_map given that it's a map strings to factories? 4. call(type_map) lib.call(type_map) the name call is too generic, it should be changed to set or even better get_factories: type_map types; if(!lib.call(types)) ... Changed to: factory_map factories; if(!lib.get_factories(factories)) ... 5. type_map doesn't allow for multiple constructors type_map doesn't allow for derived classes to have constructors with different signatures than the base class. It also doesn't allow for classes (derived or base) to have multiple constructors. In any case, the syntax should use member function types, changing the current syntax: std::map<std::string, factory<animal, int> >... to: std::map<std::string, factory<void (*::animal)(int)> 6. I didn't understand parameter_map purpose, usage, etc :( Thanks. --Lorenzo

3 3

Building ThreadPool with boost::function in boost::lockfree::queue
by Ryan Fogarty 01 Apr '13

01 Apr '13

I am having trouble typedef-ing a lockfree::queue with boost::function as the element for a ThreadPool class I am writing. TestJobQueue1 below compiles fine while TestJobQueue2 compile fails. I am using gcc 4.7.2 and boost_1_53_0. void doSomething() { std::cout << "Called doSomething\n"; } typedef boost::function<void ()> FunctionType; class TestJobQueue1 { public: typedef std::vector<FunctionType> FunctionArray; TestJobQueue1() { std::cout << sizeof(FunctionType) << std::endl; FunctionType f(&doSomething); FunctionArray funcArray; funcArray.push_back(f); std::cout << funcArray.size() << std::endl; } }; class TestJobQueue2 { public: typedef boost::lockfree::queue<FunctionType> QueueType; TestJobQueue2() { std::cout << sizeof(FunctionType) << std::endl; FunctionType f(&doSomething); QueueType funcQueue; funcQueue.push(f); } }; >> g++ -c -I/usr/local/boost_1_53_0/include TestFunctionCompleteness.cpp produces: In file included from TestFunctionCompleteness.cpp:11:0: /usr/local/boost_1_53_0/include/boost/lockfree/queue.hpp: In instantiation of ‘class boost::lockfree::queue<boost::function<void()> >’: TestFunctionCompleteness.cpp:42:17: required from here /usr/local/boost_1_53_0/include/boost/lockfree/queue.hpp:79:1: error: invalid application of ‘sizeof’ to incomplete type ‘boost::STATIC_ASSERTION_FAILURE<false>’ /usr/local/boost_1_53_0/include/boost/lockfree/queue.hpp:83:1: error: invalid application of ‘sizeof’ to incomplete type ‘boost::STATIC_ASSERTION_FAILURE<false>’ >> g++ -c --std=c++0x -I/usr/local/boost_1_53_0/include TestFunctionCompleteness.cpp produces: In file included from TestFunctionCompleteness.cpp:11:0: /usr/local/boost_1_53_0/include/boost/lockfree/queue.hpp: In instantiation of ‘class boost::lockfree::queue<boost::function<void()> >’: TestFunctionCompleteness.cpp:42:17: required from here /usr/local/boost_1_53_0/include/boost/lockfree/queue.hpp:79:5: error: static assertion failed: (boost::has_trivial_destructor<T>::value) /usr/local/boost_1_53_0/include/boost/lockfree/queue.hpp:83:5: error: static assertion failed: (boost::has_trivial_assign<T>::value) Is boost::function somehow an incomplete type and not expected to work in boost::lockfree::queue or is this a bug in the queue implementation? Can anyone suggest a simple workaround? Thank you, Ryan Fogarty

2 3

traits classes vs. metafunctions
by Stefan Strasser 01 Apr '13

01 Apr '13

Hi everyone, are there any guidelines for boost libraries on when to use traits classes and when to use a metafunction for each member of a would-be traits class? I've seen both in boost libraries. c++11 uses traits classes (iterator_traits, pointer traits, ...), but Abrahams and Gurtovoy [1] argue that traits classes ("traits blobs") should be avoided "at all costs" because they are an unnecessary concatenation of multiple metafunctions into one metafunction with multiple return values. in practice, this means that if a single 'traits class member' aka 'metafunction result' ought to differ from the defaults, the entire traits class has to be reimplemented by the user, not only the metafunction whose result ought to differ from the default. on the other hand, asking a user to implement 5 or more metafunctions is much more tedious than implementing a traits class. possibility 1) template<...> struct property1 : mpl::bool_<...>{}; template<...> struct property2 : mpl::bool_<...>{}; template<...> struct property3 : mpl::bool_<...>{}; 2) template<...> struct ..._traits{ typedef mpl::bool_<...> property1; typedef mpl::bool_<...> property2; typedef mpl::bool_<...> property3; }; you could provide both, but in which "direction"? does a traits class refer to metafunctions, or do metafunctions refer to a traits class? a) template<...> struct ..._traits{ typedef typename property1<...>::type property1; typedef typename property2<...>::type property2; typedef typename property3<...>::type property3; }; b) template<...> struct property1 : ..._traits<...>::property1{} template<...> struct property2 : ..._traits<...>::property2{} template<...> struct property3 : ..._traits<...>::property3{} which is accessed when "calling" the metafunction? it seems to me that metafunctions are better for the "caller" and traits classes are better for the implementor of the traits/metafunctions. in my case, the caller is a library and the implementor is the user, so you might choose a traits class over metafunctions. but what if a new member is added that wasn't there before (like "property4"). the implementor of an (old) traits class could not have known about the new member, so accessing the new member (by the library) will result in an error, while a new metafunction "property4" could simply return a default. should new properties of traits classes only be accessed after making sure they exist, using SFINAE? there isn't a precedent for this in c++11. only new traits classes were introduced, but no new members of already existing traits classes. should metafunctions always be preferred? why did c++11 choose traits classes over metafunctions, even though the concept of a metafunction was introduced in c++11 (<type_traits>). Thanks [1] Abrahams; Gurtovoy: C++ Template Metaprogramming, 2.2 Metafunctions

7 14