March 2007 - Boost - lists.preview.boost.org

[sorting] Assembly language radix sort uploaded with proper c++ header file and asm file
by Sam Schetterer 21 Mar '07

21 Mar '07

I have uploaded the assembly language version of radix sort to vault, along with the appropriate header file. However, please re-write the header file as needed for proper linkage.

1 0

[sorting] Multikey quicksort terminating object
by Sam Schetterer 20 Mar '07

20 Mar '07

Hi. I am writing multikey quicksort, which is like radix quicksort except for arrays of any type. However, multikey quicksort need a terminatiing object. I am not sure whether to have users pass the terminating value and trust that it will compare low against everything else, or whether I should have users create a class that is convertible to the object type being sorted, but will always compare low no matter what. Then, users will append either the terminating value or the special object to the end of each array and sort the arrays. I would like your input so that I can get started on the documentation for multikey quicksort. Also, I have posted an example version on vault in multikey quicksort.cpp. I know that the abilities offered by multikey quicksort aren't offered by std::sort.

1 0

typo in wave/util/flex_string.hpp
by Neal Becker 20 Mar '07

20 Mar '07

Surely this is a typo: ./boost/wave/util/flex_string.hpp:1644: warning: statement has no effect flex_string& append(const value_type* s, const size_type n) { Invariant checker(*this); checker;

2 1

Review of Intrusive library begins today March 12
by Joaquín Mª López Muñoz 20 Mar '07

20 Mar '07

The review of Ion Gaztañagas's Intrusive library begins today, March 12, and extends up to March 21. * Download: Boost vault: http://boost-consulting.com/vault/ Folder: Containers File: intrusive.2007-03-04.zip * Online docs: http://ice.prohosting.com/newfunk/boost/libs/intrusive * Description: Intrusive is a library presenting some intrusive containers to the world of C++. While intrusive containers were and are widely used in C, they became more and more forgotten in C++ due to the presence of the standard containers, which don't support intrusive techniques. Intrusive not only reintroduces this technique to C++, but also encapsulates the implementation in STL-like interfaces. Hence anyone familiar with standard containers can easily use Intrusive. Like their STL-counterparts, intrusive containers use template parameters to control the stored data types and some special aspects of intrusive containers. * Compilers tested (so far): Visual 7.1/WinXP Visual 8.0/WinXP GCC 4.1.1/MinGW Intel 9.1/WinXP GCC 4.1.2/Linux * Review questions: Here are some questions you might want to answer in your review: - What is your evaluation of the design? - What is your evaluation of the implementation? - What is your evaluation of the documentation? - What is your evaluation of the potential usefulness of the library? - Did you try to use the library? With what compiler? Did you have any problems? - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? - Are you knowledgeable about the problem domain? And finally, every review should answer this question: - Do you think the library should be accepted as a Boost library? Be sure to say this explicitly so that your other comments don't obscure your overall opinion. I invite you to submit your review, either publicly to the developers or the users lists, or else, if for whatever reason you don't want to publicize it, directly to me. Thank you for investing some of your time on reviewing Ion Gaztañaga's Intrusive library. The Review Manager, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

5 8

Re: [boost] Fwd: Summer of Code Update
by Gail Banaszkiewicz 20 Mar '07

20 Mar '07

1 0

[Boost-bugs] [ boost-Patches-1684708 ] add shared_ptr< const T> support
by SourceForge.net 20 Mar '07

20 Mar '07

Patches item #1684708, was opened at 2007-03-20 22:27 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=307586&aid=1684708&group_… Please note that this message will contain a full copy of the comment thread, including the initial issue submission, for this request, not just the latest update. Category: Python Group: None Status: Open Resolution: None Priority: 5 Private: No Submitted By: Roman (roman_yakovenko) Assigned to: David Abrahams (david_abrahams) Summary: add shared_ptr< const T> support Initial Comment: This patch adds support to Boost.Python library to handle boost::shared_ptr< const T> class. The problem and solution were discussed in this thread: http://mail.python.org/pipermail/c++-sig/2006-November/011626.html ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=307586&aid=1684708&group_… ------------------------------------------------------------------------- Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys-and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV _______________________________________________ Boost-bugs mailing list Boost-bugs(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs

1 0

[libpoet] active objects library release
by Frank Mori Hess 20 Mar '07

20 Mar '07

The interface of libpoet (an active object library) has started to settle down, so I've put a tarball in the boost vault to encourage people to try it out. Download: http://www.boost-consulting.com/vault/index.php?direction=0&order=&director… Online documentation: http://www.comedi.org/projects/libpoet/index.html -- Frank

1 0

Re: [boost] [Boost-announce] Review of Intrusive library begins today
by brangdon＠cix.compulink.co.uk 20 Mar '07

20 Mar '07

In-Reply-To: <45F5011E.8484B515(a)tid.es> joaquin(a)tid.es wrote (abridged): > The review of Ion Gaztañagas's Intrusive library begins today I have spent half an hour reading the documentation. Overall I like it. I have some questions and comments. Is there any reason why Destroyers must destroy? It seems to me you could have a Destroyer which pushed the value onto another list. Is that right? If so, is it a reasonable thing to do? If so, perhaps "Destroyer" is not the best name. I'd suggest "Sink" instead. Could remove_and_destroy take a default Destroyer argument that deleted the value? I hate the name "current" for the function that turns a value into an iterator. I'd prefer "to_iterator" or "as_iterator" or similar. "Current" just doesn't seem relevant to what it does, and the core thing it does is not indicated by that name. Did you consider having pop_back() return a reference to the value popped? As I understand it, the usual reasons why this a bad thing don't apply here; returning a reference cannot throw, and the value referred to isn't deleted. Did you consider making it easier to use as a replacement for list<value*> ? The semantics are already close, but the intrusive lists use references where the non-intrusive ones use pointers. I can see me having to edit out a lot of asterixes in my existing code. I was going to ask whether it would have been a good idea to allow a value type to be in several lists of the same type, but the more I think about it the more I agree that requiring the lists to be different types is best. I agree with Tom Brinkman that the introduction page of the documentation could do more to motivate the library. The core idea of using memory in the value type to store container-specific data, which is what makes the container "intrusive", needs to be mentioned earlier. I was pleased to see you mention the typical size overheads for values and containers. It seemed to me that the overhead for containers was a bit buried. I'd recommend you draw up a little comparison table which listed typical overheads for each type of container - hopefully including a good implementation of std containers if that's not too controversial. I would also like to see some speed measurements comparing std with intrusive lists and vectors. Obviously user's milage will vary, but given that performance is a major motivation for using this library I'd like to see at least some empirical indication that it can be faster. Regardless of the above I vote that Intrusive be accepted as a boost library. I am fairly knowledgable of the domain, having spent a lot of time using intrusive lists in C 20 years ago. My current app has some rigid data-structures currently based on std::list which could probably benefit from intrusive lists, but I'm not currently in a position to try this so the above is based only on reading the online documentation. > To: boost(a)lists.boost.org, boost-users(a)lists.boost.org, > boost-announce(a)lists.boost.org > Reply-To: boost-announce(a)lists.boost.org Incidently, I tried to send this message by replying, and my mail software used the Reply-To: field and sent it to boost-announce, where it was (unsurprisingly) rejected. Maybe Reply-To: could be set to boost(a)lists.boost.org instead? -- Dave Harris, Nottingham, UK.

2 1

[intrusive] My review
by Hervé Brönnimann 20 Mar '07

20 Mar '07

Ion: I have limited time to make a review, so I'm sorry that I had to concentrate on the documentation without reviewing the code, which I will do at a later date. However, what I saw from the documentation is by-and-large how I would have done a design, no surprises there but some nice twists and a very well thought-out interface. The devil being in the detail I'm glad you validated the design with some working code. This being said, this is a first-rate and very useful library, and I vote whole-heartedly to accept it to boost. I have a few spot-comments on the documentation, to follow at the end of this message. My main criticism is with one aspect of the design: in std::set and other associative container, the key (part of the value_type that determines the order) is constant, and cannot be changed (once constructed) since the std::set interface only grants constant access to it. This makes it possible to maintain the invariant of the std::set class. It is no longer possible to guarantee this with intrusive containers. You need to mention that upfront in the doc of iset with a big warning sign! But now I must mention that this is actually a plus!!! In geometric algorithms (Fortune's sweep for Voronoi diagram, to be specific), the key is an intersection with the sweep line, and varies over time. To simplify a long story, the algorithm has discrete events at which the order can change, but the invariant is maintained by swapping two elements whose keys "cross". In order to guarantee logarithmic time per event, some kind of balanced tree is needed. Naturally one would like to use std::set, but because the key changes and the user (no longer the class) is responsible for maintaining the set invariant, one must go through hoops, and use mutable data members, etc. It gets ugly! The worse part is that one must add two nodes which are equal (at the critical sweep event, they'll get ordered as soon as the sweep line starts to move), but std::set does not allow to add the two nodes with guaranteed relative position, without performing some comparisons (which have no geometric meaning: the comparison object must be tweaked). It gets *very* ugly! For a long time, I have advocated separating the rbtree algorithms from the actual data structure, for reuse. I wrote a paper with Jyrki Katajainen (now a CPH STL report) about this. One can imagine applying rbtree algorithms, or avl_algorithms, or splay_tree_algorithms, all of them without a class; each offers a different tradeoff. In particular, I'd expect treaps to perform very well. In essence, this is exactly what your library does: it separates storage from algorithms, and thus offers the potential for reuse. This is the promise of generic programming even beyond the C+ + STL. You might add my Fortune's sweep example to the others you provide (legacy objects, etc.) I imagine kinetic data structures and some graph algorithms would be fine consumers of this approach as well. I think it is very natural, and would very much like to (but won't have the time), extend your framework with (geometric) halfedge and (combinatorial) graph-like data structures. I think it will be a great winner there, even more than standard C++ containers (one dimensional). Ultimately, because geometric algorithms typically require building several data structures on top of geometric objects, the framework here has even more value than the implementations. I would really like to see a chapter in the documentation "Guidelines for extending the framework to domain-specific containers". of course, it is not a requirement for the library, merely a suggestion but given the potential for extension, you will have questions. A graph-like example compatible with the Boost Graph Library would superbly demonstrate the power of the approach! Who knows, it could even become part of the intrusive library one day. After reading your library, I feel that this is how my generic HDSTL (half-edge data structure library) should be implemented (it remains as a half- baked research project, having been published in WAE'2001). I will take a longer look but the end of the review approaching, I feel it's best to dump this now and promise later :) Thanks for a very promising library, and regards, -- Herve Bronnimann PS: Here are the more important comments I jotted down while reading the docs: I spent about two hours doing so, so forgive the sketchiness and incompleteness of the review, but one more review is always better than nothing :) * documentation: I wanted to see, while browsing the doc and clicking on the class name, the synopsis for header, in addition to the class interface for the class (following the C++ standard). But actually, by the end of the documentation, we get the header synopsis so the physical architecture of the library is clear. * documentation: iterator and const_iterator types seems to be missing consistently for each class interface (from islist, ilist, but not from iset/imultiset.) * documentation: bool ConstantTimeSize = (default not provided in ilist and islist). * design: const/mutable value type? While it is possible to violate the invariants of a std::set, that requires willfull wrongdoing from the programmer, whereas it seems much easier to inadvertently do so with intrusive set. Must be pointed out with a big warning sign. * documentation: iterator validity guarantees for islist are part of individual functions, an overview of the iterator validity rules in the description would be welcome. * indeed, the two foremost advantages of intrusive containers are: non-invalidation rules for iunordered_set, and possibility to store derived objects in the intrusive container (without extra indirection, that is - it's possible with storing pointers to object in std containers). * combination of smart pointers + intrusive containers: the intrusive container can't use simple pointers if the object lifetimes are managed by smart pointers. Thus it appears that having managed objects actually either forces the intrusive containers to use same managed pointers, or else to use the auto-unhook feature. This is not well discussed in the relevant page (about smart pointers and intrusive containers). BTW, I don't understand the requirement on smart pointer that "It must have the same ownership semantics as a raw pointer." I don't see why a shared_ptr couldn't be used, in fact, I would find some advantages to doing so (preferable imho to the auto-unhook feature). But I haven't thought too long about it. * rbtree_algorithms: here's a great opportunity to incorporate the order-statistic tree (augmented rbtree) with additional requirements on the node traits. If there is an int to spare in the data, then you can use it. You only have to make sure you use the correct algorithms (if rotating, etc., then the node's size field must be recomputed too for the order-statistic operations to be correct). The extra field can be computed at any given time (not necessary to maintain it through the insertions/manipulation) if only needed in one section of the code, and even reclaimed later if needed. This is similar to having a singly or doubly linked list sometimes or in other situations (see page "custom valueTraits"). Here is another use for that schema of using storage and reclaiming it when no longer needed: insertion in singly linked list (which is faster) and some operations on it (e.g. move-to-front heuristic which only requires islist), then making doubly-linked list (in linear time by setting the reverse pointer) to allow more operations when that is need (e.g. entering another section of the code). Or reusing the two same list pointers for an iset if the ilist structure is no longer needed.

2 1

Ion Gaztañaga's Intrusive Library
by Tom Brinkman 20 Mar '07

20 Mar '07

I use STL now like its second nature. As the Intrusive library proposes to be an alternative to STL for some situations, I am intrigued. I have no background with intrusive containers so I'm not shur why I would use one. I scanned the documentation, and still do not feel like I would know when to use Intrusive and when to use STL. Learning STL is a huge commitement of time and energy, so I think that people might be reluctant to give Intrusive a look without a strong and clear reason why. Here is the introduction from the documentation: *"Boost.Intrusive* is a library presenting some intrusive containers to the world of C++. While intrusive containers were and are widely used in C, they became more and more forgotten in C++ due to the presence of the standard containers, which don't support intrusive techniques. *Boost.Intrusive* not only reintroduces this technique to C++, but also encapsulates the implementation in STL-like interfaces. Hence anyone familiar with standard containers can easily use *Boost.Intrusive*. Like their STL-counterparts, intrusive containers use template parameters to control the stored data types and some special aspects of intrusive containers." This is not adequate for a motivating introductory discussion about why and where I should use boost::intrusive. Give a couple of hello-world motivating examples of where STL falls short and why boost::intrusive is better. Get the reader excited about why boost::intrusive is "cool".

13 34