February 2013 - Boost - lists.preview.boost.org

[thread] synchronized_value: value and move semantics
by Vicente J. Botet Escriba 24 Sep '13

24 Sep '13

Hi, boost::synchronized_value (not released yet [1][2][3]) is based on [4]. See below part of this paper adapted to the Boost.Thread interface. Currently boost::synchronized_value is in addition Copyable and Swappable. I was wondering if it is worth adding value and move semantics to synchronized_value. Making it EqualityComparable, LessThanComparable and Movable if the underlying type satisfy these requirements will allow to store them on a Boost.Container/C++11 container. Do you see something completely wrong with this addition? Has some of you had a need for this? Could you share the context? Best, Vicente [1] https://svn.boost.org/svn/boost/trunk/boost/thread/synchronized_value.hpp [2] https://svn.boost.org/svn/boost/trunk/libs/thread/example/synchronized_valu… [3] https://svn.boost.org/svn/boost/trunk/libs/thread/example/synchronized_pers… [4] "Enforcing Correct Mutex Usage with Synchronized Values" by Anthony Williams http://www.drdobbs.com/cpp/enforcing-correct-mutex-usage-with-synch/2252002… ------------- [section The Problem with Mutexes] The key problem with protecting shared data with a mutex is that there is no easy way to associate the mutex with the data. It is thus relatively easy to accidentally write code that fails to lock the right mutex - or even locks the wrong mutex - and the compiler will not help you. std::mutex m1; int value1; std::mutex m2; int value2; int readValue1() { boost::lock_guard<boost::mutex> lk(m1); return value1; } int readValue2() { boost::lock_guard<boost::mutex> lk(m1); // oops: wrong mutex return value2; } Moreover, managing the mutex lock also clutters the source code, making it harder to see what is really going on. The use of synchronized_value solves both these problems - the mutex is intimately tied to the value, so you cannot access it without a lock, and yet access semantics are still straightforward. For simple accesses, synchronized_value behaves like a pointer-to-T; for example: boost::synchronized_value<std::string> value3; std::string readValue3() { return *value3; } void setValue3(std::string const& newVal) { *value3=newVal; } void appendToValue3(std::string const& extra) { value3->append(extra); } Both forms of pointer dereference return a proxy object rather than a real reference, to ensure that the lock on the mutex is held across the assignment or method call, but this is transparent to the user. [endsect] [/The Problem with Mutexes] [section Beyond Simple Accesses] The pointer-like semantics work very well for simple accesses such as assignment and calls to member functions. However, sometimes you need to perform an operation that requires multiple accesses under protection of the same lock, and that's what the synchronize() method provides. By calling synchronize() you obtain an strict_lock_ptr object that holds a lock on the mutex protecting the data, and which can be used to access the protected data. The lock is held until the strict_lock_ptr object is destroyed, so you can safely perform multi-part operations. The strict_lock_ptr object also acts as a pointer-to-T, just like synchronized_value does, but this time the lock is already held. For example, the following function adds a trailing slash to a path held in a synchronized_value. The use of the strict_lock_ptr object ensures that the string hasn't changed in between the query and the update. void addTrailingSlashIfMissing(boost::synchronized_value<std::string> & path) { boost::strict_lock_ptr<std::string> u=path.synchronize(); if(u->empty() || (*u->rbegin()!='/')) { *u+='/'; } } [endsect] [/Beyond Simple Accesses] [section Operations Across Multiple Objects] Though synchronized_value works very well for protecting a single object of type T, nothing that we've seen so far solves the problem of operations that require atomic access to multiple objects unless those objects can be combined within a single structure protected by a single mutex. One way to protect access to two synchronized_value objects is to construct a strict_lock_ptr for each object and use those to access the respective protected values; for instance: synchronized_value<std::queue<MessageType> > q1,q2; void transferMessage() { strict_lock_ptr<std::queue<MessageType> > u1 = q1.synchronize(); strict_lock_ptr<std::queue<MessageType> > u2 = q2.synchronize(); if(!u1->empty()) { u2->push_back(u1->front()); u1->pop_front(); } } This works well in some scenarios, but not all - if the same two objects are updated together in different sections of code then you need to take care to ensure that the strict_lock_ptr objects are constructed in the same sequence in all cases, otherwise you have the potential for deadlock. This is just the same as when acquiring any two mutexes. In order to be able to use the dead-lock free lock algorithms we need to use instead unique_lock_ptr, which is Lockable. synchronized_value<std::queue<MessageType> > q1,q2; void transferMessage() { unique_lock_ptr<std::queue<MessageType> > u1 = q1.unique_synchronize(boost::defer_lock); unique_lock_ptr<std::queue<MessageType> > u2 = q2.unique_synchronize(boost::defer_lock); boost::lock(u1,u2); // dead-lock free algorithm if(!u1->empty()) { u2->push_back(u1->front()); u1->pop_front(); } } [endsect] [/Operations Across Multiple Objects]

1 0

[asio] Randomly having problems reading from the socket
by Torben Wiggerich 29 Jul '13

29 Jul '13

Hi all, I have some problems using the boost.asio.read for a TCP-socket. So far it works fine, but it randomly stops the transfer for at least 5 seconds. To resolve the error I used a simple synchronous server and client from the boost examples and modified it too send a larger amount of data. (307400 Bytes; this size comes from the program I'm trying to get run). On the client side I also changed the reading from the socket to read the complete data with boost.asio.read and transfer_all as argument. Both, server and client, measure the time for sending and reading to the socket and will give an error if it needs more than 1 second. Here is the sourcecode for the server: #include <iostream> #include <string> #include <boost/asio.hpp> #include <boost/date_time/posix_time/posix_time.hpp> using boost::asio::ip::tcp; using namespace boost::posix_time; int main() { try { boost::asio::io_service io_service; tcp::acceptor acceptor(io_service, tcp::endpoint(tcp::v4(), 8002)); tcp::socket socket(io_service); acceptor.accept(socket); unsigned char * array = new unsigned char[307400]; for (;;) { boost::system::error_code ignored_error; ptime startTime = microsec_clock::universal_time(); boost::asio::write(socket, boost::asio::buffer( array, 307400 ), boost::asio::transfer_all(), ignored_error); time_duration neededTime = microsec_clock::universal_time() - startTime; if ( neededTime.total_milliseconds() > 1000 ) { std::cout << "ERROR needed too much time: " << neededTime.total_milliseconds() << "ms" << std::endl; } } } catch (std::exception& e) { std::cerr << e.what() << std::endl; } return 0; } My client sourcecode: #include <iostream> #include <boost/array.hpp> #include <boost/asio.hpp> #include <boost/date_time/posix_time/posix_time.hpp> using boost::asio::ip::tcp; using namespace boost::posix_time; int main(int argc, char* argv[]) { try { if (argc != 2) { std::cerr << "Usage: client <host>" << std::endl; return 1; } boost::asio::io_service io_service; boost::asio::ip::tcp::endpoint endpoint( boost::asio::ip::address::from_string( argv[1] ), 8002 ); tcp::socket socket(io_service); boost::system::error_code error = boost::asio::error::host_not_found; socket.connect( endpoint, error ); if (error) throw boost::system::system_error(error); int counter = 0; unsigned char* array = new unsigned char[307400]; for (;;) { boost::system::error_code error; ptime startTime = microsec_clock::universal_time(); size_t len = boost::asio::read( socket, boost::asio::buffer( array, 307400 ), boost::asio::transfer_all(), error ); time_duration neededTime = microsec_clock::universal_time() - startTime; if ( error ) { printf( "body read error %s\n", error.message().c_str() ); } if ( counter % 5000 == 0 ) { std::cout << "passed: " << counter << "\r"; } ++counter; if ( neededTime.total_milliseconds() > 1000 ) { std::cout << "ERROR needed too much time: " << neededTime.total_milliseconds() << "ms" << std::endl; } } } catch (std::exception& e) { std::cerr << e.what() << std::endl; } return 0; } To reproduce the error just let it run for a while. It can take up to 30 minutes or even more... After a while it will produce the line: "ERROR needed too much time: 5007ms". Maybe with slightly different times, but all around 5 seconds. I tested it on different machines with Windows Vista and Seven. So am I'm doing sth. wrong? Is the reading from the socket correct? I'm using boost version 1.44. Kind regards Torben Wiggerich

6 11

A more convenient Variant visitation syntax
by Kevin Wu Won 19 Jul '13

19 Jul '13

While Boost Variant is a wonderful library that fills a genuine hole in the C++ language, it is not as nice to use as it could be. The "correct" way to unwrap a variant is to apply a static visitor, but this method carries a high syntactic burden because it needs the user to define a class (probably somewhere far away) just so they can "switch" on the type of the object stored in the variant. I came up with a solution where the handler functions can be specified inline with C++11 lambdas. Here's an example: boost::variant< int, std::string > u("hello world"); int result = match(u, [](int i) -> int { return i; }, [](const std::string & str) -> int { return str.length(); }); The `match` function accepts the variant followed by the handler functions. The functions can be specified in any order. It will fail to compile if the functions do not match the types of the variant, if the return types are not all the same, or if a non-unary function is supplied. This is C++11 only because it's quite pointless without lambda functions. I've tested it with gcc 4.7. It doesn't work on gcc 4.6, which can't handle the variadic templates. Here's the code: https://github.com/exclipy/inline_variant_visitor What do you think? This started out for me as an exercise to learn template metaprogramming and C++11, but hopefully, it can actually evolve into something useful.

7 8

Static initialization of boost shared objects question
by Juan Carlos Franzoy 02 Jul '13

02 Jul '13

Hello. Thanks for reading my question. I fell into a deadlock in static initialization of boost shared objects. The deadlock occurs in a reentrant call to a function which contains a definition of a static variable. Apparenlty gcc protects the initialization of such variables with a condition variable. Looking at the c++ code nothing at all make anybody suspect about reentrancy. My "interpretation of the fact" may be titled 'something in gcc, ld, ld.so, c++language made the call to be reentrant' - There is a function boost::system::generic_category() that has a static variable V - V type is boost::system::annonymous-namespace::generic_error_category - boost::system::annonymous-namespace::generic_error_category is subclass of boost::system::error_category. - boost::system::annonymous-namespace::generic_error_category has no declared/defined constructor as well as all its superclasses - The compilation process generate the constructor boost::system::error_category::error_category() as a weak symbol inside every shared object that uses it. - There is a static variable boost::system::posix_category in one of the shared objects that is initialized calling boost::system::generic_category(). - when the static initialization of a shared object boost::system::posix_category get initialized - which calls boost::system::generic_category() - Inside boost::system::generic_category() starts the initialization of V which calls boost::system::error_category::error_category() - It may happend that the runtime calls an instance of boost::system::error_category::error_category() that resides in a shared object that is still not loaded - So that .so get loaded and it is called its own static initialization - which can call boost::system::generic_category() - BOOM I would love if you can confirm of refute my humble "interpretation". Details follows ------------------- boost version: 1-52-0 Operating system: uname -a SunOS bcpp-solaris10 5.10 Generic_147441-25 i86pc i386 i86pc $ gcc -v Using built-in specs. COLLECT_GCC=gcc COLLECT_LTO_WRAPPER=/export/home/local/gcc-4.6.2/libexec/gcc/i386-pc-solaris2.10/4.6.2/lto-wrapper Target: i386-pc-solaris2.10 Configured with: ../src/gcc-4.6.2/configure --prefix=/export/home/local/gcc-4.6.2 --with-gmp=/export/home/local/gcc-4.6.2/gmp-4.3.2 --with-mpfr=/export/home/local/gcc-4.6.2/mpfr-3.0.0 --with-mpc=/export/home/local/gcc-4.6.2/mpc-0.8.2 --with-libelf=/export/home/local/gcc-4.6.2/libelf-0.8.12 --enable-shared --enable-threads=posix --enable-checking=release --with-system-zlib --enable-__cxa_atexit --enable-languages=c,c++ --with-as=/usr/local/bin/as --with-gnu-as --with-ld=/usr/ccs/bin/ld --without-gnu-ld --enable-plugin --enable-multilib --enable-version-specific-runtime-libs --enable-bootstrap --enable-ssp --enable-libssp --with-included-gettext --enable-lto --host=i386-pc-solaris2.10 --build=i386-pc-solaris2.10 Thread model: posix gcc version 4.6.2 (GCC) Callstack backtrace (lines begining with = are my comments): = = deadlock here: the threads is waiting itself = #0 0xfd459019 in __lwp_park () from /lib/libc.so.1 #1 0xfd45365e in cond_sleep_queue () from /lib/libc.so.1 #2 0xfd453817 in cond_wait_queue () from /lib/libc.so.1 #3 0xfd453b94 in cond_wait_common () from /lib/libc.so.1 #4 0xfd453d02 in _cond_wait () from /lib/libc.so.1 #5 0xfd453d2d in cond_wait () from /lib/libc.so.1 #6 0xfd453d66 in pthread_cond_wait () from /lib/libc.so.1 #7 0xfd632898 in __gthread_cond_wait (g=0xfd822ea8) at ...build-gcc/out/i386-pc-solaris2.10/libstdc++-v3/include/i386-pc-solaris2.10/bits/gthr-default.h:846 #8 __gthread_cond_wait_recursive (g=0xfd822ea8) at ...work/build-gcc/out/i386-pc-solaris2.10/libstdc++-v3/include/i386-pc-solaris2.10/bits/gthr-default.h:860 #9 __gnu_cxx::__cond::wait_recursive (g=0xfd822ea8) at ...build-gcc/out/i386-pc-solaris2.10/libstdc++-v3/include/ext/concurrence.h:377 #10 __cxa_guard_acquire (g=0xfd822ea8) at .../src/gcc-4.6.2/libstdc++-v3/libsupc++/guard.cc:289 = = Reentrant call to boost::system::generic_category() = #11 0xfd812313 in boost::system::generic_category () at libs/system/src/error_code.cpp:425 #12 0xfe85cd38 in __static_initialization_and_destruction_0(__initialize_p=1, __priority=65535) at ./boost/system/error_code.hpp:214 #13 0xfe85d05f in _GLOBAL__sub_I_instantiate_re2c_lexer_str.cpp () at libs/wave/src/instantiate_re2c_lexer_str.cpp:56 = = static initization of boost.wave library = #14 0xfe8868fd in __do_global_ctors_aux () from ...boost/lib/libboost_wave-gcc46-mt-d-32-SOLARIS-X86-1_52.so.1.52.0 #15 0xfe88692a in _init () from ...boost/lib/libboost_wave-gcc46-mt-d-32-SOLARIS-X86-1_52.so.1.52.0 #16 0xfefce37e in call_init () from /usr/lib/ld.so.1 #17 0xfefce1cf in is_dep_init () from /usr/lib/ld.so.1 #18 0xfefdaa4b in elf_bndr () from /usr/lib/ld.so.1 #19 0xfefc2ab4 in elf_rtbndr () from /usr/lib/ld.so.1 #20 0xfee60688 in ?? () #21 0xfee0c8f6 in boost::exception_detail::get_static_exception_object<boost::exception_detail::bad_alloc_>() at ./boost/exception/detail/exception_ptr.hpp:119 #22 0xfee0c0d2 in __static_initialization_and_destruction_0(__initialize_p=1, __priority=65535) at ./boost/exception/detail/exception_ptr.hpp:138 #23 0xfee0c271 in _GLOBAL__sub_I_future.cpp () at libs/thread/src/future.cpp:60 = = static initization of boost.thread library = #24 0xfee0d98d in __do_global_ctors_aux () from ...boost/lib/libboost_thread-gcc46-mt-d-32-SOLARIS-X86-1_52.so.1.52.0 #25 0xfee0d9ba in _init () from ...boost/lib/libboost_thread-gcc46-mt-d-32-SOLARIS-X86-1_52.so.1.52.0 #26 0xfefce37e in call_init () from /usr/lib/ld.so.1 #27 0xfefce1cf in is_dep_init () from /usr/lib/ld.so.1 #28 0xfefdaa4b in elf_bndr () from /usr/lib/ld.so.1 #29 0xfefc2ab4 in elf_rtbndr () from /usr/lib/ld.so.1 #30 0xfdce0688 in ?? () = = First calll to boost::system::generic_category() = #31 0xfd81232a in boost::system::generic_category () at libs/system/src/error_code.cpp:425 #32 0xfd812386 in __static_initialization_and_destruction_0(__initialize_p=1, __priority=65535) at ./boost/system/error_code.hpp:214 #33 0xfd8123ed in _GLOBAL__sub_I_error_code.cpp () at libs/system/src/error_code.cpp:430 = = static initialization of boost.system = #34 0xfd8126ed in __do_global_ctors_aux () from ...boost/lib/libboost_system-gcc46-mt-d-32-SOLARIS-X86-1_52.so.1.52.0 #35 0xfd81271a in _init () from ...boost/lib/libboost_system-gcc46-mt-d-32-SOLARIS-X86-1_52.so.1.52.0 #36 0xfefce37e in call_init () from /usr/lib/ld.so.1 #37 0xfefcd7d5 in setup () from /usr/lib/ld.so.1 #38 0xfefdba3e in _setup () from /usr/lib/ld.so.1 #39 0xfefc299c in _rt_boot () from /usr/lib/ld.so.1 #40 0x08047540 in ?? () #41 0x08047670 in ?? () More thanks for reading all.

3 4

De Bruijn Bind (alternate bind syntax) Interest?
by David Sankel 24 Jun '13

24 Jun '13

Hello all, I've been working on an alternate bind syntax based on De Bruijn indices[1]. The syntax is very simple, yet the terms are very powerful. Here is an example of a function const that takes in an argument c and returns another function that, for all input, returns c: //λx.λy.x = λλ1 with De Bruijn indices. auto const_ = abs<1>( abs<1>( var<1,0>() ) ); More examples, further explanation, and an implementation are available here[2]. I'm thinking that this library could also be useful as a core for more syntax heavy bind variations. David [1] http://en.wikipedia.org/wiki/De_Bruijn_index [2] http://bitbucket.org/camior/de-bruijn-bind/ -- David Sankel Sankel Software www.sankelsoftware.com 585 617 4748 (Office)

11 73

[TypeErasure] references
by Chapman, Alec 10 May '13

10 May '13

Hi Steven, I have a somewhat-generic type erasure class that I would like to switch to yours. The main difficulty I can see is in the way capturing by reference is handled. The approach I take in my class is to pass a boost::reference_wrapper to the constructor: typedef mpl::vector<copy_constructible<>, type_id_<>, incrementable<> > requirements; int i = 0; any<requirements> x(boost::ref(i)); // capture i by reference ++x; // i == 1 any<requirements> y(x); // makes a copy of i ++y; // i == 1, any_cast<int>(y) == 2 My motivation is that I have a bunch of template functions already written that I often call directly, but in other cases I need to compile them separately by instantiating them with any<...>: ---------------------- module 1 ------------------------- // some long algorithm that I don't want to modify to be aware of any<...> template<class T> void f(T& t) { ++t; T t2 = t; ++t2; // do something with t2 } // make a type-erased version for separate compilation void any_f(any<requirements>& x) { return f(x); } -------------------- module 2 ---------------------------- // provide a thin wrapper that applies type erasure before calling any_f template<class T> void f_fwd(T& t) { any<requirements> x(boost::ref(t)); any_f(x); } // some function that needs to call f void g(int& i) { // do something with i... // then pass it to f f_fwd(i); } Is something like this possible with your method? Are there advantages that I'm not seeing to having the type signature contain information about whether the object is held by reference? Thanks, Alec

3 6

[GSOC] Are we going to participate?
by Antony Polukhin 02 May '13

02 May '13

Hi all, Today starts Google Summer of Code. Is Boost community will become one of the mentoring organizations? What project ideas are we proposing? (As for me, I'd love to see unique_ptr+unique_array implemented using Boost.Move; C++11 features support for MPL, Fusion, Graph, Bind, Optional; BTree library; library for getting system info) -- Best regards, Antony Polukhin

16 24

What Should we do About Boost.Test?
by Dave Abrahams 16 Apr '13

16 Apr '13

Hi All, I was just going through Boost.Test to try to figure out how to teach it, and while it looks to have substantial value, it is also in quite a mess. It contains loads of features that are exercised in the examples/ directory but neither included in any of the tests nor documented. There are facilities for command-line argument parsing! There are "decorators" that turn on/off features for test cases. There is support for mock objects! These are cool and sometimes necessary features, but who knew? The third tutorial page (http://www.boost.org/doc/libs/1_51_0/libs/test/doc/html/tutorials/new-year-…) has a glaring typo in the code examples: "BOOST_AUTO_EST_CASE". There's no reference manual at all. There are nearly-identical files in the examples/ directory called "est_example1.cpp" and "test_example1.cpp" (Did the "t" key on someone's keyboard break?) I could go on, but where would I stop? I don't know what to do about this. Because of the lack of redundancy (i.e. tests and documentation), it's hard to tell whether this library is correct or even to define what "correct" should mean. It seems like, as long as the code is incompletely / incorrectly documented and tested, it's just someone's personal coding project that we happen to keep shipping with Boost, and not really a library for general use. This situation reflects poorly on Boost as a whole and the fact that it centers around a _testing_ library, which is concerned with robustness... well, let's just say that the irony isn't lost on me. I don't mean this posting as an attack on Gennadiy in any way, but I think the situation is unacceptable and therefore am opening a discussion about what should happen. As a straw man, I'll make this suggestion: - Boost.Test is officially deprecated in the next release - Its documentation, such as it is, is removed from the release after that - Meanwhile, other tests in Boost that use this library are rewritten to use a different mechanism - The code is removed from Boost thereafter I am not at all attached to removing Boost.Test from Boost, but IMO rescuing it would require a significant new investment of time and energy from people who are committed to bringing the library up to par with the rest of what we do. (I seriously thought about volunteering for this myself, but realistically speaking, I don't have the time, and volunteering for something you can't actually do is worse than not volunteering at all.) Even if volunteers show up, I'd suggest proceeding with the plan above, subject to reversal at any time the work actually gets done. Thoughts? -- Dave Abrahams BoostPro Computing Software Development Training http://www.boostpro.com Clang/LLVM/EDG Compilers C++ Boost

34 85

future<>::then() Error returning future<void> (on trunk)
by Fernando Pelliccioni 07 Apr '13

07 Apr '13

Hi Vicente, hi all, I noticed that in the trunk there is a implementation of future<>::then(). Thank you very much for your efforts to implement it! The following example, compiles OK boost::future<int> f1 = boost::async([]() { return 123; }); f1.then([](boost::future<int> const& f) { return std::string(""); }); But this one fails to compile: boost::future<int> f1 = boost::async([]() { return 123; }); f1.then([](boost::future<int> const& f) { }); Here future<>::then() have to returns future<void> like ... boost::async([]() { }); Am I right? On the other hand, have you taken into account the following paper? http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3451.pdf Regards, Fernando Pelliccioni.

3 5

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