- Boost - lists.boost.org

[sorting] What are the most complicated sorting problems?
by Sam Schetterer 20 Mar '07

20 Mar '07

Hi. Since people want the sorting library to have something that the standard library sorts do not offer, I would like to know the most complicated sorting situations that user have encountered (like sort by name, and then first three digits of phone number, and if the sum of the first three digits of the phone number is less than 10, sort by the second 4 digits of the phone number). I ask this because radixsort and radix quicksort are able to do those sorts, but I need input from users to add features. Also, even if you do not have any complicated sorts, ideas in general would help.

5 6

[regex] format_perl conundrum
by Eric Niebler 20 Mar '07

20 Mar '07

I have a question and a bug report regarding the format_perl flag. First the question ... I see that, when you specify format_perl, match_results::format() recognizes the escape sequences \l \L \u and \U, which do uppercasing or lowercasing. These are necessarily locale-dependent character transformations, but match_results does not have a Traits parameter. How should the transformations be done? I note that the basic_regex<> class template has a traits parameter, and that match_results<>::format() can only be called after a successful regex match. One reasonable approach is that match_results<> holds a (shared) pointer to the regex object's traits. It would have to be a polymorphic base pointer, since match_results can't know the exact type of the traits object at the time format() is called. That doesn't exactly work because the RegexTraits concept doesn't have toupper() and tolower() functions. I suggest adding them. This isn't only a problem for format_perl, strictly speaking. match_results::format() also needs to know how to turn characters into integers (eg. to parse format strings like "$1"). That is the reason for RegexTraits::value()'s existence, so match_results<>::format() should use it. (Incidentally, I just implemented all this in xpressive, so I can confirm that this strategy works. It incurs a virtual call for each tolower(), toupper(), and value(), but there doesn't seem to be any other way without changing the interface in a non-TR1 compatible way.) Finally, a bug report. Consider the following code: std::string str ("fOO bAr BaZ"); regex rx ("\\w+"); str = regex_replace( str, rx, "\\L\\u$&", format_perl ); std::cout << str << std::endl; This prints: FOO BAr BaZ However, the equivalent perl: $str= 'fOO bAr BaZ'; $str =~ s/\w+/\L\u$&/g; print "$str\n"; Prints this: Foo Bar Baz Looks like in boost::regex, the \u is stomping the \L rather than merely overriding it for the next character. -- Eric Niebler Boost Consulting www.boost-consulting.com

2 3

Proposed Boost Exception updated
by Emil Dotchevski 20 Mar '07

20 Mar '07

Documentation, source code and tests available for online browsing here: http://www.revergestudios.com/boost-exception/boost-exception.htm Everything is also available as a single .zip file download: http://www.revergestudios.com/boost-exception/boost-exception.zip This update includes only a minor change in how boost::exception::what() deduces the string representation of objects stored in a boost::exception. See http://www.revergestudios.com/boost-exception/boost-exception.htm#logging for details. Comments/feedback much appreciated. Emil Dotchevski _________________________________________________________________ Watch free concerts with Pink, Rod Stewart, Oasis and more. Visit MSN Presents today. http://music.msn.com/presents?icid=ncmsnpresentstagline&ocid=T002MSN03A07001

1 0

Summer of Code Update
by Gail Banaszkiewicz 20 Mar '07

20 Mar '07

Hi everyone, After some careful consideration, I have decided not to put forward an application to Boost for Summer of Code. Instead I will be concentrating my efforts on proposals for Inkscape. My reasoning for this is that there seems to be less desire for the projects I was interested in (Computational Geometry), and because I will not have time to put together a really killer proposal (especially since I have not used Boost a whole lot yet as it is). I just wanted to thank those of you who wrote me with encouragement, and who told me about the many opportunities in computational geometry elsewhere as well. I wish all the students who are applying to Boost good luck, and perhaps I will look into contributing sometime in the near future outside of SoC! Cheers, Gail

2 1

[SoC] Interest of a plugin library
by Mariano Consoni 20 Mar '07

20 Mar '07

Hi! I'm a Msc. student. Last years, I've been using boost for a lot of tasks, and I liked too much its philosophy. Aside from that, I've worked some time creating some kind of library/code to support the need of plugins in applications. The development went through different approaches over the time... and I think that now I have good ideas to do a good implementation (using .dll/.so and a framework of callback to initialize/destroy plugins and implement the interfaces). At least, I think that it works well in Windows and Linux (so maybe it will work well in most unices) because I tried some prototypes and I think that it could be a great tool for the opensource community (because as far as I know, there isn't a library that does this job). So I'm writing this email because I want to know if there is interest in the community of a project of this type, because I want to participe in Boost/SoC and if it isn't interesting I will try to find some other idea. I know that "new library" projects maybe are bad seen for SoC, but I think that this could be a very concrete project, with short-term useful deliverables. Thanks! ps: apart from that, other idea that i've for SoC is a timer pool library, similar to SDL's but using boost::threads.

9 19

GSoC proposal
by Mauricio Hollando 20 Mar '07

20 Mar '07

Hello! I have created a page to keep track of my GSoC applications. I have recently sent a proposal to Boost C++ and I have added it to my page. It would be great if you come by and leave any comments you may have so I can improve my project or answer any of your questions. Thank you for your help and interest. Oh! The site URL is http://mime.ac.labf.usb.ve/mauricio/ Mauricio Hollando Dubuc

2 1

[sorting] Assembly language extensions to the algorithms
by Sam Schetterer 20 Mar '07

20 Mar '07

Lewis Hyatt wrote: > Are you sure about the quicksort speed difference? That seems like a huge > difference. Did you have inlining enabled? Also, the current versions are > not the final forms. I am implementing random-access iterators and > user-provided functions. Yes, this was on cygwin compiled with g++ -O3. One thing to keep in mind is that your routines are competing with the standard library, which can be highly optimized for whatever target platform the compiler was written for. Unless you have a dramatically improved algorithm, it is unlikely that your sorting routines will beat std::sort in general, even if they do on some platforms. As an example, suppose your goal was to write an equivalent of std::bitset which beat the standard implementation. It is unlikely that you could exceed the performance of std::bitset::count(), for instance, because most implementations use native assembly instructions to do this whenever possible. (e.g., gcc uses its built-in popcount function on platforms where it is available.) On the other hand, if you hand-coded a version with the best algorithm you could find, it might beat a few poor implementations, but in general it would be inferior. The only way to make it better in general would be to implement all these optimizations yourself for each target platform, but at that point, it's just not worth the time. I don't think it's true that std::sort, std::stable_sort, and std::partial_sort are the end of the story, but I think any work in a sorting library should focus on needs which are not already met. So far, only radix sort appears to fall in that category, but you would also need to demonstrate a case in which radix sort is preferable to std::sort. -lewis I think that you are right that each compiler's version of the stl has the advantage of assembly language. Since I know both that speed and features are important to developers, what would people think if I uploaded to vault x86 assembly language extensions to the algorithm for users to download. The whole algorithm will not be coded in assembly language(only the tight inner loop), but it could only be used on built in types. Would you use the extensions if they were supplied?

1 0

Re: [boost] [Intrusive] - Adapting existing intrusive classes
by Michael Fawcett 20 Mar '07

20 Mar '07

On 3/19/07, Ion Gaztañaga <igaztanaga(a)gmail.com> wrote: > The same happens with Intrusive. The user derives or stores a hook to > make the class intrusive-friendly. The hook contains a minimum generic > node that just stores pointers. All the low-level (link, unlink, > rebalance...) algorithms operate with these minimal nodes to avoid > instantiating algorithms for all user types. Ion, does this version of Intrusive have functionality that would allow me to adapt existing classes (i.e. a non-intrusive way to provide Boost.Intrusive functionality)? I think this could be accomplished using a mechanism similar to iterator traits classes. A user would simply need to specialize a boost::intrusive::list::node_traits class. This was how I went about it when I coded an intrusive n-ary tree. It looked something like (simplified): template <typename T> struct nary_treenode_traits { static T *&parent(T &node); static T *&prev(T &node); static T *&next(T &node); static T *&first_child(T &node); static T *&last_child(T &node); // const versions too... }; And then all of my node operations went through the traits class. E.g. template <typename T> T *&parent_node(T &node) { typedef nary_treenode_traits<T> traits_type; return traits_type::parent(node); } This allows implementations where the user takes advantage of platform specific knowledge to store extra information within one pointer (linked list with next/prev pointer in the same pointer with xor to extract), as well as more commonly, existing pointers that might simply be named something different than what the generic algorithm expected. It appears that my implementation, yours, and the Generic Tree GSoC project from last year all had similar goals in trying to provide generic algorithms that only rely on certain capabilities of the input type (e.g. must have next/prev to be used as a linked list node, or must have parent to be a tree node). --Michael Fawcett

2 2

[sorting] Big endian and Little endian radix sort
by Sam Schetterer 19 Mar '07

19 Mar '07

Hello. I am not sure whether my radix sort code will work on both big endian and lttle endian platforms. If anybody has access to both big endian and little endian platforms, could they please test radixsort on both of them, because I do not have access to both big endian and little endian platforms. That would be very helpful to the development of this library.

1 0

[sorting] Multikey quicksort - is it wanted?
by Sam Schetterer 19 Mar '07

19 Mar '07

Hello. I am planning to implement a multikey quicksort, which is basically the same thing as normal radix quicksort except it is adapted to work for arrays of any one type. However, it is used for arrays of arrays, and the arrays in the array are sorted using the same method that is used on strings. However, to use it, one must pass the function a terminating object, operator== and operator< must be defined for the objects in the arrays in the big array, each array must be of one type (multikey quicksort won't work well for arrays of objects that have polymorphic compare functions). Also, I don't encounter the array within array situation very much, but if you do, I am pretty sure that multikey quicksort will help a lot if you do the work required of you, because you won't have to worry about whether keys are the same length like you would for normal radixsort. However, if multikey quicksort will not be of any help to you, please post, because I don't want to adouble the size of the radix quicksort header for something that will not be used.

1 0