[LLVMdev] Removing std::vector from APIs (was Re: Mutating the elements of a ConstantArray)

[Gordon Henriksen]

On 2009-05-15, at 07:26, David Greene wrote:

> On Friday 15 May 2009 05:50, Jay Foad wrote:
>>
>
>>> The one major thing to be aware of is that it isn't safe to use  
>>> &V[0] when V is an empty std::vector
>>
>> Oh dear. That's a bit of a flaw in the plan. I suppose the solution  
>> is to switch to SmallVector whenever this might be a problem.
>
> Or use iterators.  That's why they're there.

The reason to use the pointer-length pair in preference to iterators  
is that iterators make templates of everything, causing code bloat. In  
my code, rather than pass the separate parameters I use a range<Iter>  
class something like this:

template<typename Iter>
class range {
   Iter Begin, End;

public:
   range() : Begin(), End() { }

   template<typename ConvertibleToRange>
   range(T &seq) : Begin(seq.begin()), End(seq.end()) { }

   Iter begin() { return Begin; }
   Iter end() { return End; }
   // ... other Sequence methods ...
};

And encapsulate the logic to deal with the empty sequence problem in a  
function:

template<typename ConvertibleToRange>
range<typename ConvertibleToRange::value_type*>
ptr_range(ConvertibleToRange &seq) {
   typename ConvertibleToRange::iterator i = seq.begin(), e = seq.end();
   if (i == e)
     return range<typename ConvertibleToRange::value_type*>();
   return range<typename ConvertibleToRange::value_type*>(&*i, &*i +  
(e - i));
};

So that:

StructType::get(v.empty()? 0 : &v[0], v.empty()? 0 : &v[0] + v.size());
// becomes
StructType::get(ptr_range(v));


Two important refinements… First, the above can be made safer so that  
ptr_range will reject e.g. std::list with a bit of metaprogramming:

template<typename T> struct is_ptr { enum { value = false }; };
template<typename T> struct is_ptr<T*> { enum { value = true }; };

template<typename T>
struct is_contiguous_sequence { enum { value =  
is_ptr<T::iterator>::value }; };
template<typename T, typename Alloc>
struct is_contiguous_sequence<std::vector<T,Alloc> > { enum { value =  
true }; };
template<typename T, typename Ch, typename Alloc>
struct is_contiguous_sequence<std::basic_string<T,Ch,Alloc> > { enum  
{ value = true }; };

template<typename T, bool True> struct type_if { typedef T type; }
template<typename T> struct type_if<T,false> { /* cause substitution  
failure */ }

// New prototype for ptr_range.
template<typename ConvertibleRange>
typename type_if<
   range<typename T::value_type*>,
   is_contiguous_sequence<T>::value
 >::type ptr_range(ConvertibleRange &seq);

And secondly, range<T*> can be extended to convert from arrays in  
addition to objects with begin()/end() methods by (1) providing a  
partial specialization on T* which adds a template constructor:

template<typename T>
template<size_t N>
range<T*>::range<T*>(T (&arr)[N]) : Begin(arr), End(arr + N) { }

or by (2a) using a traits type to look up ConvertibleToRange::iterator  
& -::value_type

template<typename T>
struct range_traits {
   typedef typename T::value_type value_type;
   typedef typename T::iterator iterator;
   // .. etc ...
};

template<typename T, size_t N>
struct range_traits<T[N]> {
   typedef T value_type;
   typedef T *iterator;
   // .. etc ...
};

and by (2b) indirecting calls to seq.begin() and seq.end() through  
template functions:

template<typename ConvertibleToRange>
typename range_traits<T>::iterator beginof(T &seq) { seq.begin(); }
template<typename ConvertibleToRange, size_t N>
typename range_traits<T[N]>::iterator beginof(T (&seq)[N]) { return  
seq; }

template<typename ConvertibleToRange>
typename range_traits<T>::iterator endof(T &seq) { seq.begin(); }
template<typename ConvertibleToRange, size_t N>
typename range_traits<T[N]>::iterator endof(T (&seq)[N]) { return seq  
+ N; }

This refines StructType::get(arr, arr + sizeof(arr) / sizeof(arr[0]));
to just StructType::get(arr);

— Gordon