- Boost - lists.boost.org

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

Re: [boost] boost::multi_index::key_extractors status
by JOAQUIN LOPEZ MU?Z 27 Feb '05

27 Feb '05

----- Mensaje original ----- De: Loïc Joly <loic.actarus.joly(a)wanadoo.fr> Fecha: Domingo, Febrero 27, 2005 7:04 pm Asunto: [boost] boost::multi_index::key_extractors status > Hello everybody, > > I'm discovering boost::multi_index, and something strikes me: I've > been > dreaming of something like boost::multi_index key extractors (and > especially member) for most of my std::set or std::sort uses. > > I therefore think that this part of boost::multi_index does not > belong > in this library, but is more general purpose, and deserves a > library of > its own, along with a way to get a suitable less predicate from > the > result of those. All the arguments that make such a framework > usefull > for boost::multi_index can equally be applied to STL containers > and > algorithms. > > I wonder if such a proposal has already been made (maybe it even > already > exists, boost has so many parts that I may be unaware of this), > and in > the positive case what were the arguments in favor or in > opposition of it. > This issue was considered during the review, and those who gave an opinion about it thought it was better to leave like it is now. Anyway, there's nothing preventing you from using the key extraction sublib for your own purposes, as it is headerwise separate from the rest. You'll only need some compose classes to plug key extractors into comparison predicates, something like this: template<typename KeyFromValue> struct key_less { typedef result_type bool; template <typename Arg> bool operator()(const Arg& x,const Arg& y) { return key(x)<key(y); } private: KeyFromValue key; }; ... typedef std::set< employee, key_less<member<employee,std::string,&employee::name> > > employee_set; HTH Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

1 0

boost::multi_index::key_extractors status
by Loïc Joly 27 Feb '05

27 Feb '05

Hello everybody, I'm discovering boost::multi_index, and something strikes me: I've been dreaming of something like boost::multi_index key extractors (and especially member) for most of my std::set or std::sort uses. I therefore think that this part of boost::multi_index does not belong in this library, but is more general purpose, and deserves a library of its own, along with a way to get a suitable less predicate from the result of those. All the arguments that make such a framework usefull for boost::multi_index can equally be applied to STL containers and algorithms. I wonder if such a proposal has already been made (maybe it even already exists, boost has so many parts that I may be unaware of this), and in the positive case what were the arguments in favor or in opposition of it. Best regards, -- Loïc

1 0

Reading the contents of a directory
by Dark Haruka 27 Feb '05

27 Feb '05

Hello :) I'm searching a library for C/C++ which can access directorys. I have read that the boost library can it. So I have downloaded and installed it. But I'm searching a function with which I can look up which files are in a directory. I'd like to say a directory to scan to the function. The function should return the names of the files in that directory and if possible the name of subdirs. Does anyone know this function? Thank you in advance :)

2 1

Object-oriented preprocessor programming :-)
by Arkadiy Vertleyb 27 Feb '05

27 Feb '05

Hi all, If one needs to manage a lot of PP code, some code structuring technique might be helpful. So, how about the OO? The example below demonstrates this techinique with the canonical shapes example. An object is represented as a PP sequence of properties. The head of the sequence contains the "class name" and is used for dispatching. I believe this proved very useful in the BOOST_TYPEOF project where we polymorphicaly treat type, integral, and template template parameters. Comments? Regards, Arkadiy -- #include <boost/preprocessor/seq/transform.hpp> #include <boost/preprocessor/seq/enum.hpp> #include <boost/preprocessor/seq/cat.hpp> #include <boost/lambda/lambda.hpp> #include <algorithm> #include <iostream> // #define VIRTUAL(Fname, This) BOOST_PP_SEQ_CAT(\ (BOOST_PP_SEQ_HEAD(This))(_)(Fname)) // #define CIRCLE(r) (CIRCLE)(r) #define CIRCLE_RADIUS(This)\ BOOST_PP_SEQ_ELEM(1, This) #define CIRCLE_AREA(This)\ 2 * 3.14159 * CIRCLE_RADIUS(This) // #define RECTANGLE(h, w) (RECTANGLE)(h)(w) #define RECTANGLE_HIGHT(This)\ BOOST_PP_SEQ_ELEM(1, This) #define RECTANGLE_WIDTH(This)\ BOOST_PP_SEQ_ELEM(2, This) #define RECTANGLE_AREA(This)\ RECTANGLE_HIGHT(This) * RECTANGLE_WIDTH(This) // #define SQUARE(x) (SQUARE)(x) #define SQUARE_SIDE(This)\ BOOST_PP_SEQ_ELEM(1, This) #define SQUARE_AREA(This)\ SQUARE_SIDE(This) * SQUARE_SIDE(This) // #define MY_SHAPES\ (CIRCLE(5))\ (RECTANGLE(3, 4))\ (CIRCLE(3))\ (SQUARE(3))\ (SQUARE(5))\ (RECTANGLE(2, 6)) #define ENUM_AREAS(shapes)\ BOOST_PP_SEQ_ENUM(BOOST_PP_SEQ_TRANSFORM(OP, ~, shapes)) #define OP(s, data, elem)\ VIRTUAL(AREA, elem)(elem) double MyAreas[] = { ENUM_AREAS(MY_SHAPES) }; // int main() { using namespace std; using namespace boost::lambda; for_each( MyAreas, MyAreas + sizeof(MyAreas)/sizeof(MyAreas[0]), cout << _1 << "\n"); return 0; }

1 0