Re: container design (Was: std::complex design (Was: N-Dimensional array))

From: rwgk (rwgk_at_[hidden])
Date: 2002-03-08 01:19:08

--- In boost_at_y..., "David Abrahams" <david.abrahams_at_r...> wrote:
> Suppose you're writing a generic function which has to work for all
> kinds of numeric T:
>
> double, complex<float>, and array_with_shared_semantics<double> are
> examples
>
> You need to create a huge vector<T> at the beginning of the 
function,
> and you want to initialize it piecemeal during the function's 
execution
> by assigning values into it. You don't want to pay for 
initialization if
> you don't have to. Note that you do have to initialize
> array_with_shared_semantics<double>, because its assignment operator
> inspects the current contents. How do you write this?

That was a little exercise. I am happy to present my result,
but I will not fight a battle for this :-)

The basic idea follows the procedure executed by this constructor:

      vector(size_t n)
      {
        // allocator is called here
        std::uninitialized_fill_n(begin(), n, T());
        size_ = n;
      }

Instead of std::uninitialized_fill_n() we have any function
that produces a result of type T, or more generally, a result
that is convertible to a T.

Here is one example (current version of shared_algebra.h):

  template<typename ElementType1, typename ElementType2>
  inline
  shared<
    typename binary_operator_traits<
        ElementType1, ElementType2>::arithmetic>
  operator+(
    const shared<ElementType1>& a1,
    const shared<ElementType2>& a2) {
    typedef shared<
      typename binary_operator_traits<
          ElementType1, ElementType2>::arithmetic>
    result_array_type;
    typedef typename result_array_type::value_type 
return_element_type;
    if (a1.size() != a2.size()) throw_range_error();
    result_array_type result(a1.size(), reserve_flag());
    array_operation_binary_a_a(functor_plus<
        return_element_type,
        ElementType1,
        ElementType2>(),
      a1.begin(), a2.begin(), result.begin(), a1.size(),
      has_trivial_destructor<return_element_type>::value());
    result.set_size_back_door(a1.size());
    return result;
  }

has_trivial_destructor will eventually be replaced by some other
trait (see previous posting).

result_array_type result(a1.size(), reserve_flag());

is a desperate attempt to reduce the notational overhead
a little bit and equivalent to:

result_array_type result;
result.reserve(a1.size());

There are two implementations of array_operation_binary_a_a
which are selected via tag dispatching (has_trivial_destructor
is something like int2type<boost::has_trivial_destructor<T>::value>):

array_operation_binary_a_a for non-POD types (roughly speaking)
resembles std::uninitialized_fill_n():

  template <typename BinaryFunctorType,
            typename ElementType1,
            typename ElementType2,
            typename ElementTypeResult>
  void // not inline
  array_operation_binary_a_a(
    const BinaryFunctorType& ftor,
    const ElementType1* a1,
    const ElementType2* a2,
    ElementTypeResult* result,
    const std::size_t& sz,
    false_type) // non-POD result type
  {
    ElementTypeResult* result_start = result;
    try {
      ElementTypeResult* result_end = result + sz;
      for(;result != result_end; a1++, a2++, result++) {
        new (result) ElementTypeResult(ftor(*a1, *a2));
      }
    }
    catch (...) {
      cctbx::af::detail::destroy_array_elements(result_start, result,
        false_type());
      throw;
    }
  }

The other array_operation_binary_a_a() is much simpler (and inlined):

  template <typename BinaryFunctorType,
            typename ElementType1,
            typename ElementType2,
            typename ElementTypeResult>
  inline void
  array_operation_binary_a_a(
    const BinaryFunctorType& ftor,
    const ElementType1* a1,
    const ElementType2* a2,
    ElementTypeResult* result,
    const std::size_t& sz,
    true_type) // POD result type
  {
    ElementTypeResult* result_end = result + sz;
    for(;result != result_end; a1++, a2++, result++) {
      *result = ftor(*a1, *a2);
    }
  }

Here is the essential secret weapon (and finally the answer
to David's question):

    result.set_size_back_door(a1.size());

Without this back door only friend functions could use the
mechanism that I just explained. I have no clue how the
same effect could be achieved without violating the
principle of encapsulation. Personally I have no problem
with this pragmatic approach, but as I said, I am not going
to argue the case with respect to a standard container.

Ralf