Re: [Boost-Users] Re: graph destructor and resizing in general

From: Douglas Gregor (gregod_at_[hidden])
Date: 2001-12-01 11:05:17

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