Alex - There are some notes which libraries need compilation on the Wiki at: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?InstallingBoo...

Jeremy Siek <jsiek@cs.indiana.edu> a écrit : Do you need to use the graphviz file reader/writer? If not then you don't need to build anything.

Jeremy are you saying that the graphviz feature is a "non-header" feature requiring an actual build of graph into a lib? Jeff

Thanks a lot, I understand why the sample works now, it's written at the url you given me: Note that only a few libraries require a library compilation step using Boost.Jam. These are: thread, regex and python. The other Boost libraries are contained completely within header files. Next Boost.Jam is also used for generating all test programs and running all tests. Jeff Garland <jeff@crystalclearsoftware.com> a écrit : Alex - There are some notes which libraries need compilation on the Wiki at: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?InstallingBoo...

Jeremy Siek <jsiek@cs.indiana.edu> a écrit : Do you need to use the graphviz file reader/writer? If not then you don't need to build anything.

Jeremy are you saying that the graphviz feature is a "non-header" feature requiring an actual build of graph into a lib? Jeff Yahoo! Groups SponsorADVERTISEMENT Info: <http://www.boost.org> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl> Unsubscribe: <mailto:boost-users-unsubscribe@yahoogroups.com> Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service. --------------------------------- Yahoo! Courrier -- Une adresse @yahoo.fr gratuite et en français ! [Non-text portions of this message have been removed]

The book "Introduction to Algorithms" by Cormen, et all covers basic graph theory. http://www.mhhe.com/catalogs/0070131511.mhtml Also, some graph theory will be covered in the BGL book due to be published in December: http://cseng.awl.com/book/0,3828,0201729148,00.html Cheers, Jeremy On Fri, 30 Nov 2001, Ihsan Ali Al Darhi wrote: iad929> Can someone of you point me to a good book or URL on graph iad929> theory? Ineed this to understand the BGL. Please. iad929> iad929> Mo iad929> iad929> iad929> Info: <http://www.boost.org> iad929> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl> iad929> Unsubscribe: <mailto:boost-users-unsubscribe@yahoogroups.com> iad929> iad929> iad929> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ iad929> iad929> ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------

On Saturday 01 December 2001 10:41 am, you wrote:

I want to make this explanation short so I will skip details. In a nutshell, during destruction or resize, a destructor is explicitly called from a loop for each element which has been constructed. Obviously this is desireable much of the time, but it is true even if the element type has an *empty* destructor. This can take a lot of unecessary time, like 10's or even a few 100 milliseconds, which can make a big difference in, say, inspection software used in an industrial production line.

This isn't really a problem with the specification of std::vector, but is a quality-of-implementation issue. If one knows that the destructor is trivial, one can compile a version of the destruction/resize code that does not contain a destruction loop.

I wrote a replacement vector class which uses delete[] internally but otherwise acts like std::vector just to get around this problem. There are some drawbacks and limitations during resizing, but there are times when this behavior is essential.

Does it meet the criteria for std::vector with respect to reserve(n)? It seems that would present a problem... In any case, I believe the solution is this: template<bool> truth_type {}; template<typename InputIterator> inline void destruct_elements_in_range( InputIterator first, InputIterator last, truth_type<true>) { // The elements in the range have trivial destructors, so do nothing } template<typename InputIterator> inline void destruct_elements_in_range( InputIterator first, InputIterator last, truth_type<false>) { typedef typename std::iterator_traits<InputIterator>::value_type T; for(; first != last; ++first) { T* victim = &(*first); victim->~T(); } } template<typename T> class vector { private: void destruct_elements() { destruct_elements_in_range(begin(), end(), truth_type<boost::has_trivial_destructor<T>::value>()); } }; The user will generally need to add a specialization for any type with a trivial destructor (or some compilers may support this, eventually).

Unfortunately, containers like the graph boost library use std::vector as containers and that is hardcoded. So the destructor for a graph might take 100 or 200 ms, when it should take almost nothing because there is nothing dangerous which really needs to be cleaned up.

Most Boost libraries that use containers allow you to supply your own container. Doug

Thanks for replying. Douglas Gregor wrote:

On Saturday 01 December 2001 10:41 am, you wrote:

...

I want to make this explanation short so I will skip details. In a nutshell, during destruction or resize, a destructor is explicitly called from a loop for each element which has been constructed. Obviously this is desireable much of the time, but it is true even if the element type has an *empty* destructor. This can take a lot of unecessary time, like 10's or even a few 100 milliseconds, which can make a big difference in, say, inspection software used in an industrial production line.

This isn't really a problem with the specification of std::vector, but is a quality-of-implementation issue. If one knows that the destructor is trivial, one can compile a version of the destruction/resize code that does not contain a destruction loop.

In any case, I believe the solution is this:

template<bool> truth_type {};

template<typename InputIterator> inline void destruct_elements_in_range( InputIterator first, InputIterator last, truth_type<true>) { // The elements in the range have trivial destructors, so do nothing }

template<typename InputIterator> inline void destruct_elements_in_range( InputIterator first, InputIterator last, truth_type<false>) { typedef typename std::iterator_traits<InputIterator>::value_type T; for(; first != last; ++first) { T* victim = &(*first); victim->~T(); } }

template<typename T> class vector { private: void destruct_elements() { destruct_elements_in_range(begin(), end(), truth_type<boost::has_trivial_destructor<T>::value>()); } };

The user will generally need to add a specialization for any type with a trivial destructor (or some compilers may support this, eventually).

Having read about traits recently, I wonder if it shouldn't look like this: // default class struct ctor_types { struct empty {}; // no tor called, no code executed; can optimize struct trivial {}; // default constructor can be called for single element, and that can be copied struct volatile {}; // default constructor must be called seperately for each element // and destructor should not be called after container internal copy operation (e.g. vector resize) }; Note that STL currently defaults to ctor_type::trivial, whereas a call to new T[n] preforms what is indicated by volatile. Because of this, some classes are not safe to use with STL. struct dtor_types { struct empty {}; // no tor called, no code executed; can optimize struct volatile {}; // default desstructor must be called seperately for each element }; Note that STL currently defaults to dtor_type::volatile // default class_tor_triaits using current STL defaults template <class T> class_tor_triaits { typedef ctor_types::trivial ctor_type; typedef dtor_types::volatile dtor_type; }; // specializations template <int> class_tor_triaits { typedef tor_type::empty ctor_type; typedef tor_type::empty dtor_type; }; etc. .... (These must be a less coding intensive way to do this) Finally in the user code template <MyClass> class_tor_triaits { typedef ctor_types::volatile ctor_type; typedef dtor_types::empty dtor_type; }; template <MyOtherClass> class_tor_triaits { typedef ctor_types::empty ctor_type; typedef dtor_type::empty dtor_type; }; Now containers for class T can query class_tor_traits<T> to decide how to proceed with initialization and destruction. If this were implemented, not only would optimization become possible, but some classes which are not currently STL safe would also become compatible with STL by defining ctor_type as ctor_types::volatile. (Such classes allocate memory to pointers on construction and simply copy the pointers during a copy operation. Obviously STL uncouth but common in practice, no?) Cheers Craig Hicks Engineer, KGK Tokyo [Non-text portions of this message have been removed]

Douglas Gregor wrote:

On Sunday 09 December 2001 09:22 am, hicks wrote:

...

Having read about traits recently, I wonder if it shouldn't look like this:

// default class

struct ctor_types { struct empty {}; // no tor called, no code executed; can optimize struct trivial {}; // default constructor can be called for single element, and that can be copied struct volatile {}; // default constructor must be called seperately for each element // and destructor should not be called after container internal copy operation (e.g. vector resize) }; Note that STL currently defaults to ctor_type::trivial, whereas a call to new T[n] preforms what is indicated by volatile. Because of this, some classes are not safe to use with STL.

This is explicitly stated as part of the CopyConstructable requirements. Besides, if one has a user-defined type with such a strange copy constructor, vector resizing, for instance, would be impossible.

I think it is possible to be more specific about the kind (can't use the word class here) of class I intend to represent by volatile. It contains only values by member, and pointers to memory which it has allocated on construction or in an explicit "init (or open, or allocate)" type of call, which are explicitly freed in its destructor, or in an explicit "destroy (or close, or free)" type of call. It has only the default copy operator. A struct with no member functions, which contains pointers to allocated memory, and for which there exist helper functions to allocate and delete the memory associated with the pointers, fits this description, and is exactly what is found in a lot C style programming. I think that being able to use STL in a shop full of C style programs and programmers is a good thing. It lowers the threshold for entry into the STL and C++ style of programming. Its not only code, but human back-compatability which must be considered. Vector resizing is not impossible for such a structure. How to: Default copy is made (exactly copy of values and pointers) and no destructor is called afterwards. That's what I meant when I said "destructor should not be called after copy operation". /I'm not sure this is a good thing; classes that aren't CopyConstructable are /strange beasts, and one must be _extremely_ cautious in their use. For /instance, they can't be returned or passed by value, can never be safely held /in a std::vector, and generally cause migraines because they _look_ like they /are CopyConstructable but they don't _act_ like it. The fact that they can't be held safely in std::vector is exactly the problem I wanted to address.

As a side note, the mapping between your vocabulary here and the SGI standard template library is: Yours <-> SGI empty <-> trivial trivial <-> CopyConstructible volatile <-> no equivalent SGI term

...

(These must be a less coding intensive way to do this)

Not that I've found, unfortunately; however, one can often lump traits together into larger concepts, and arrange the concepts in a concept lattice to minimize the typing required.

Does SGI or Boost have a trait assigned for all predefined types? struct predefined_type_true {}; struct predefined_type_false {}; // default template <class T> struct predefined_type_traits { typedef predefined_type_false predfined_type; }; // the predefines char, unsigned char, int, long, etc. template <int> struct predefined_type_traits { typedef predefined_type_true predfined_type; }; etc ...

In this case, the compiler can sometimes fill in the traits. For instance, if a constructor or destructor does nothing, the "empty" (or SGI "trivial") property can be asserted; however, the compiler cannot generally tell whether a constructor meets your "trivial" or "volatile" requirement, so it must assume the worst.

This is quite true. "volatile" would require a manual assignment of trait.

...

but some classes which are not currently STL safe would also become compatible with STL by defining ctor_type as ctor_types::volatile. (Such classes allocate memory to pointers on construction and simply copy the pointers during a copy operation. Obviously STL uncouth but common in practice, no?)

I'm not sure this is a good thing; classes that aren't CopyConstructable are strange beasts, and one must be _extremely_ cautious in their use. For instance, they can't be returned or passed by value, can never be safely held in a std::vector, and generally cause migraines because they _look_ like they are CopyConstructable but they don't _act_ like it.

I'd be happy to see this type of object go gently into that good night. I'm a big fan of the "a type must be either CopyConstructable or Noncopyable." If my name was Scott Meyers, I'd put that in a book :)

I think that is the correct conclusion ... given infinte dealines and a universal desire to adopt STL programming in a single gulp. Only if we live in a less than ideal world is there any reason to do otherwise.

Doug

Info: <http://www.boost.org> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl> Unsubscribe: <mailto:boost-users-unsubscribe@yahoogroups.com>

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

[Non-text portions of this message have been removed]

Douglas Gregor wrote:

On Wednesday 12 December 2001 03:49 am, you wrote:

...

I think it is possible to be more specific about the kind (can't use the word class here) of class I intend to represent by volatile. It contains only values by member, and pointers to memory which it has allocated on construction or in an explicit "init (or open, or allocate)" type of call, which are explicitly freed in its destructor, or in an explicit "destroy (or close, or free)" type of call. It has only the default copy operator.

There's a big difference between these two: if they allocate in the constructor and deallocate in the destructor, but don't copy the resources then there is a serious design flaw here. The fix is not to change std::vector, but to either: 1) Make the copy constructor/copy assignment operator do the right thing 2) Make the class explicitly noncopyable (pass pointers around instead) 3) Make the class a lightweight "handle" (basically a boost::shared_ptr) to the actual resources allocated.

All cases allow some form of usage in std::vector; 1 & 3 allow direct usage, whereas 2 requires that the object be explicitly allocated. All cases also avoid the ability to shoot oneself in the foot, and don't require changes to std::vector.

...

A struct with no member functions, which contains pointers to allocated memory, and for which there exist helper functions to allocate and delete the memory associated with the pointers, fits this description, and is exactly what is found in a lot C style programming.

... and there is no reason why such a class would not be safely CopyConstructable. Something like this is already usable in std::vector, you just have to deal with allocation/deallocation on your own.

...

I think that being able to use STL in a shop full of C style programs and programmers is a good thing.

Perhaps.

...

It lowers the threshold for entry into the STL and C++ style of programming.

I disagree with this completely. If a programmer new to C++ has to deal with objects whose destructors should not be called, they _will_ be confused. One of the basic tenets of C++ is that destructors will be called on all deallocated objects.

...

Vector resizing is not impossible for such a structure. How to: Default copy is made (exactly copy of values and pointers) and no destructor is called afterwards.

That's what I meant when I said "destructor should not be called after copy operation".

Again, one has to essentially subvert the C++ type system to make this possible, and break with C++ traditions. A class type that requires this behavior can't be passed as an argument to a function, or can't be returned (unless the return-value optimization is supported: do you really want your object's behavior to differ depending on a legal optimization?)

...

Does SGI or Boost have a trait assigned for all predefined types?

boost::is_fundamental<T>::value

...

...

I'd be happy to see this type of object go gently into that good night. I'm a big fan of the "a type must be either CopyConstructable or Noncopyable." If my name was Scott Meyers, I'd put that in a book :)

I think that is the correct conclusion ... given infinte dealines and a universal desire to adopt STL programming in a single gulp. Only if we live in a less than ideal world is there any reason to do otherwise.

It's not really an STL issue, however. If we're going from C, which has no notion of construction or destruction, to C++, which has both construction and automatic destruction, we need to watch out for "half-breeds." The kinds of types we were talking about earlier, where the constructor allocates, destructor deallocates, but the copy constructor doesn't copy fall into this category. They aren't C structures, because they have constructors; however, they aren't safe C++ classes, because they can easily be used in ways that will break.

Wouldn't it take longer for programmers not familiar with C++ semantics to figure out why they can't now pass these structures as arguments that it would just to fix the structures themselves? One quick fix: make all of the raw pointers into boost::shared_ptrs. Then the default copy constructor/copy assignment operator will handle reference-counting automatically.

Using boost::shared_ptrs is a very good idea. It relieves the need for any modification, which in some cases is more work than not using std::vector, but some other mechanism instead. Thanks for your very useful advice and comments. Hicks

Doug

Doug

Info: <http://www.boost.org> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl> Unsubscribe: <mailto:boost-users-unsubscribe@yahoogroups.com>

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/

[Non-text portions of this message have been removed]