- Boost - lists.boost.org

Filesystem efficiency- search sample
by Terence Wilson 28 Feb '05

28 Feb '05

I'm interested in using the filesystem library, however, I was disappointed by the performance test I ran. I wrote a simple recursive find file function using win32 to compare its speed with the find_file sample in the 2 minute tutorial, I found Boost to be 2-3 times slower on average. Does anyone have any thoughts on where the slowdown may be? Terence Wilson

2 1

Re: [boost] Re: Type of Review for UnorderedAssociativeContainers&HashFunctions
by JOAQUIN LOPEZ MU?Z 28 Feb '05

28 Feb '05

----- Mensaje original ----- De: Daniel James <daniel(a)calamity.org.uk> Fecha: Sábado, Febrero 26, 2005 5:40 pm Asunto: [boost] Re: Type of Review for UnorderedAssociativeContainers&HashFunctions > Thorsten Ottosen wrote: > > I think tr components should be allowed special status. What's > the point in > > putting tr components through a normal review, when there can be > no interface > > changes? > > > > If the definition of fast-track review is not suitable for tr > components, then > > let us call it a > > tr review. The important aspect of such a review is that it > should be fast. > > Fast as in soon? Or just spending less time on the review? I don't > mind > waiting in the review queue so unless anyone really wants to see > this in > Boost as soon as possible, I guess that Boost.Hash should be fast > tracked, Boost.Unordered should go in the queue, maybe for a > shorter > than normal review. Is that okay with everyone? > Is perfect with me at least :) I guess the review wizard should allocate a period for fasttrack reviewing Boost.Hash (which, if I understand it OK, can run in paralel with other regular reviews.) Tom? As for my negative vote to accepting Boost.Unordered for fasttrack, my main concern is that other authors are patiently standing in line for their own reviews, and the size and scope of this library does not justify for a fasttrack treatment, in my humble opinion. Other than that I think the lib is needed and will eventually make it into Boost. Best, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

3 2

[program options] optional/required options
by Stefan Slapeta 28 Feb '05

28 Feb '05

Hi, I don't know if this has been answered yet, but is there any concept of optional/required options in the program option library? Currently, only "allowed options" can be defined, no? I would be great if you could define different sets of required option groups (because it's possible that a+b _or_ a+c are required) and provide some validatation for that. Otherwise, you have to do that by hand again and again. Stefan

2 3

Boost library inclusion: generic tree containers?
by Justin Gottschlich 28 Feb '05

28 Feb '05

Dear Boost library members - My name is Justin Gottschlich and have just recently joined the boost mailing list. Since this is my first post, I would first like to apologize in advance for any e-mail inequities I manage to include in this e-mail. I'm e-mailing is to ask if there may be interest in a generic tree container for addition to Boost. I have created four generic tree libraries which I am currently using in my online game (Nodeka). Additionally, my former company began using them in a rather small scope in 2002 and has since requested additional use of the libraries throughout their product (QuarkXPress) and my current company is now showing interest in using them and will begin using them within the next couple weeks (Raytheon Company). Due to the increased interest of the tree libraries, I am now bringing them to your attention in case you feel they may be of interest for Boost library inclusion. The four containers I have written are: core::tree - creates a generic tree that follows std::set functionality per tree level core::multitree - creates a generic tree that follows std::multiset functionality per tree level core::tree_pair - creates a key/value generic tree that follows std::map functionality per tree level core::multitree_pair - creates a key/value generic tree that follows std::multimap functionality per tree level In addition, I have four iterators for each tree container. The containers are written in an extremely general manner so while they have ordered behavior through "insert" functionality (like set and map), they can also achieve unordered element behavior through "push_back" and "push_front" behavior. The reason for this is so the generic tree containers can be used as a basic framework to build additional, algorithm or purpose driven behavior (nested sets, compiler based control trees). The containers are by no means up to "standards" quality - so much work would be needed there. =) I have written two articles on my tree containers (one published on gamedev.net) and the second article in the process for publication on gamedev.net that is currently being reviewed. I have posted both articles on my site for review (if you're interested in reading them): http://nodeka.com/TreePart1.pdf http://nodeka.com/TreePart2.pdf The second article really explains the design thoughts behind the tree containers. The first article simple shows how I've seen C++ programmers build trees using maps and why that's bad. =) If you are interested in the reasoning of my design for the trees, I would recommend reading the second article (http://nodeka.com/TreePart2.pdf) The current header source code can be seen here: http://nodeka.com/tree.h http://nodeka.com/multitree.h The core::tree_pair and core::multitree_pair are undergoing some changes so I haven't posted them just yet. If you feel generic tree containers are not suitable for Boost, I will completely understand and my feelings won't be hurt by your honesty. =) Thanks for your time and consideration, Justin Gottschlich ( <mailto:justin@nodeka.com> justin(a)nodeka.com, jgottschlich(a)runbox.com)

16 48

Welcome to Jeff Garland as a new Boost moderator!
by Beman Dawes 28 Feb '05

28 Feb '05

Jeff Garland is now a Boost moderator. Jeff is a Boost contributor (Date-Time library), runs the Wiki, and has been generally helping out for a long time. Adding an additional moderator gives us a bit more depth. Welcome to Jeff! --Beman

3 2

Re: Boost library inclusion: generic tree containers?
by Dan Rosen 28 Feb '05

28 Feb '05

Hi all, This is my first posting to the Boost mailing list, so apologies in advance for any gaffes. I wanted to jump into the fray a bit on the tree container discussion with a couple little thoughts I had on the topic. There's been some excellent points made, reviewing the thread thus far, about separating the concerns of tree structure from tree iteration. I agree that it's very appropriate to consider designing the fundamental structure and operations on a tree a distinct exercise from designing how the data might be accessed, traversed or mutated by standard algorithms. Talking first in terms of concepts such as TreeContainer, which behave similarly to (or refine) the existing standard library Container, seems like the right approach. But there has also been some mention of more refined concepts such as AVL Tree, Red-Black Tree, Splay Tree, BTree, etc. which have some intrinsic algorithmic properties that distinguish them from what I'd call a "basic" tree for lack of a better term. I believe that an AVL tree, for example, is not actually a refinement of the basic tree concept, because you can not treat an AVL tree polymorphically as a basic tree. Inserting into one of these types of specialized trees, for example, may invalidate iterators or violate other ordering assumptions that are safe to make in a basic tree. I'm picturing a particularly hairy instance where you have iterators marking a range in, say, a red-black tree, and you call std::transform() on that range in-place. In other words, I think the only tree structures that are appropriate to consider are the basic TreeContainer and strict refinements thereof. Taking my own argument to an extreme, I'm not even entirely convinced that binary or k-ary trees should be considered, since they aren't strictly substitutable for basic trees... That aside, the real idea I wanted to offer was this: If we want to provide the type of behavior that one of these various self-balancing search trees, etc. would offer (which I certainly think we should), it should take much the same form as the heap algorithms present in the standard library do today. The operations push_heap(), pop_heap(), make_heap(), sort_heap() and is_heap() operate with typical, characteristic cleverness on a sequential range of RandomAccessIterators, imposing an ordering more specific than that offered by the RandomAccessContainer storing the data. Similarly, operations such as is_k_ary_tree(int), is_avl_tree(), avl_balance(), etc. would serve to impose and maintain a useful, more specific structure on top of TreeContainer, and would avoid having to make a messy hierarchy of structural concepts. So, this is all just to say: if we adopt the approach of further separating the concern of specialized tree structures, then I believe the exercise of formulating good concepts for basic tree structures becomes simpler. Furthermore, I'm guessing that also makes things easier when we do get to the step of worrying about standard iterators and interoperability with standard library algorithms. Hope this is a useful contribution! Cheers, dr

2 1

[range?] Re: Partial specialization matching
by David Abrahams 27 Feb '05

27 Feb '05

The following message is a courtesy copy of an article that has been posted to comp.lang.c++.moderated as well. [I'm Cc'ing this to Boost because IIRC some people were struggling with a similar issue recently. Of course it may not apply ;-)] "Nicolas" <nicolas.tisserand(a)gmail.com> writes: > Ben Hutchings wrote: > > [snip] >> I believe it was considered unreasonable to require implementers to >> do that kind of analysis, given that it could involve checking for >> specialisations across the whole program. > > Got that. Thanks :) > > In the code I posted, I was trying to specialize a class template > (IteratorTraits) according to the relationship between an Iterator and > its Container. > For instance, I wanted to be able to produce a specialization of > IteratorTraits for what std::vector<T, Alloc> advertises as being its > iterator type. It's fundamentally impossible [unless the core language was to make exceptions based on special knowledge about certain standard library components]. Forget everything you know about vectors, and now consider: template <class Iterator> struct IteratorTraits; template <class T> struct vector { typedef char* iterator; }; // This would be the syntax, if it were legal. template <class T> struct iterator_traits<vector<T>::iterator> { // What is T? }; It's illegal because there's no way for the compiler to deduce T. > Is there a way to do that without having to examine a given STL > implementation and find out what the exact type of std::vector<T, > Alloc>::iterator is? Technically, no. *If* you're willing to assume that std::vector<T,A>::iterator is the same type for any A (which is not quite correct in any real implementation because of vector<bool>), you could do this: template <class Iterator, class Enable = void> struct IteratorTraits; template <class Iterator> struct IteratorTraits< Iterator , boost::enable_if< boost::is_same< Iterator , typename std::vector< typename std::iterator_traits<Iterator>::value_type >::iterator > >::type > { // whatever you want here. }; This specialization of IteratorTraits applies iff the iterator type of a vector of the argument's value_type is the same as the argument. I'm sure you can figure out how to deal with the vector<bool> anomaly. See http://www.boost.org/libs/utility/enable_if.html for information about how enable_if works with class template specializations. HTH, -- Dave Abrahams Boost Consulting www.boost-consulting.com

3 5

RE: [boost] Re: IoStreams Question: How do I get "tee" functionality
by Brian Braatz 27 Feb '05

27 Feb '05

-----Original Message----- From: boost-bounces(a)lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Jonathan Turkanis Sent: Sunday, February 27, 2005 12:20 PM To: boost(a)lists.boost.org Subject: [boost] Re: IoStreams Question: How do I get "tee" functionality Jonathan Turkanis Wrote: <<<<<<<<<<<<<<<<<<<<< I apparently didn't test that code, because it contained two errors (write takes a const char* instead of a char*, and only multi-character filters implement write() instead of put()). At the end of this message is an updated and tested version. I plan to include a tee filter in the first released version of the library. It should be slightly more efficient than the example. Jonathan <<<<<<<<<<<<<<<<<<<<< BRIAN BRAATZ WRITES: THANK YOU !

1 0

lazy exact arithmetic
by Brandon Kohn 27 Feb '05

27 Feb '05

Hello, I was just posting to see if there is any interest in developing a library to help with exact arithmetic using the lazy arithmetic strategy? I've been working for the last couple of years with computational geometry algorithms, and have found that such a library is really essential to overcoming problems due to floating point precision/round off errors in most computational geometry algorithms with non-brute force complexity. The idea behind the lazy paradigm is that exact computation (using rational arithmetic with arbitrary sized integers) is too costly to be used all the time. So the exact computations are delayed until such a time as you cannot reliably make decisions with the information you have from the 'lazy' filters. The lazy filters are implemented as a layer of calculation that uses interval arithmetic to compare numerical quantities. If the intervals being compared are non-overlapping, the result is considered to be sufficient and exact computation is avoided. If the intervals do overlap, exact computation is required to unambiguously decide how the quantities compare. This is just a rough outline of how the method works, and I'm sure there will be plenty of kinks to work out (my background is in physics and computer science... so perhaps a mathematician in the group would step up to help guide my efforts :). A library such as this one exists in the CGAL kernel library which is available under the LGPL. I find that while the LGPL can be useful in cases where the library is already organized as a single DLL/shared object library, it is generally difficult to implement into commercial solutions due to the dynamic linking constraints imposed by the library. Further, I think that this type of algorithm (which solves a very big problem with floating point arithmetic in computing) is really something that should be standardized and freely available. Sorry for the long post :) What do you guys think? Kind regards, Brandon

5 6

IoStreams Question: How do I get "tee" functionality
by Brian Braatz 27 Feb '05

27 Feb '05

However, I am NOT (yet) an expert in the Iostreams library so please excuse me if I am missing something obvious. I add 2 sinks filtering_ostream out; out.push(file_sink("Report.txt")); out.push(cout); I get an exception thrown on the second one (regardless of which one goes in first) In searching the archives, I noticed this mail: http://tinyurl.com/6soeb where Johnathon Turkis writes: "For this we need to define an OutputFilter which stores a reference to an ostream and has a member function 'write' which forwards all characters to the stored ostream as well as to the downstream sink (you don't need to understand the following code -- the point is that it's just a few lines): struct tee : boost::io::output_filter { tee(std::ostream& dest) : dest(dest) { } template<typename Sink> void write(Sink& snk, char* s, std::streamsize n) { // Write to the downstream Sink boost::io::write(snk, s, n); // Write to the stored ostream: dest.write(s, n); } std::ostream& dest; }; We use the tee as follows. Given two ostreams ostream first; ostream second; we define a filtering_ostream which passes data through the tee to both streams: filtering_ostream out; out.push(tee(first)); out.push(second); out << "this gets written to both ostreams\n"; " Which looks "good" except I suspect the library has changed since the above is not compiling for me under VC71. (it complains about wanting a Put() instead of a write()).. Any help appreciated- and also - a request- if "tee" functionality could be officially implemented in the streaming lib for output sinks. OR if it already is, I request that how do to it be spelled out more clearly in the documentation. Thanks Brian Braatz

2 1