Re: arrays/vectors/templates

From: Dave Moore (dtmoore_at_email.unc.edu)
Date: 01/17/05 

Date: Mon, 17 Jan 2005 15:25:42 +0100

"Dave W" <davewatson2002@NOSPAMhotmail.com> wrote in message
news:cs9clv$jbs$1@hercules.btinternet.com...
>
> "Mike Wahler" <mkwahler@mkwahler.net> wrote in message
> news:tiBFd.6555$Ii4.6438@newsread3.news.pas.earthlink.net...
> >
> > "Dave W" <davewatson2002@NOSPAMhotmail.com> wrote in message
> > news:cs6khh$6pp$1@hercules.btinternet.com...
> > > How can I define a template function which can take either a vector or
> an
> > > array as a parameter? I can do one or the other, but not both......
> > >
> > > Thanks
> >
> > Iterators are your friend. Pointers qualify as
> > (random access) iterators. The 'display_container()'
> > function below should work with any type of iterator
> > (thus can iterate through any container or array).
> >
> >
> >
> > -Mike
> >
> >
>
> Thanks for that. I've used your example to write the code below. I got it
to
> work mainly through trial and error, as I don't completely understand
what's
> going on.
>
>
> template<class T, class U> U median(T beg, T end, U x)
> {
> if (x == 0)
> throw std::domain_error("Median of an empty container");
>
> sort(beg, end);
>
> U mid = x/2;
> return x % 2 == 0 ? (*(beg+mid) + *(beg+(mid-1))) / 2 :*(beg+mid);
>
> }
>
>
> int main()
> {
>
> vector<double> testVec;
> testVec.push_back(55);
> testVec.push_back(66);
> testVec.push_back(77);
> testVec.push_back(44);
> testVec.push_back(22);
>
> std::vector<double>::size_type vec_sz = testVec.size();
>
> double testArr[] = {55, 66, 77, 44, 22};
> size_t length = sizeof(testArr)/sizeof(*testArr);
>
> cout << "Vector median..." << median(testVec.begin(), testVec.end(),
> vec_sz) << endl;
> cout << "Array median... " << median(testArr, testArr+length, length)
> << endl;
>
> return 0;
> }
>
> The bit I don't understand is that, as I understand it, in my median
> function the third parameter has the same type as the return value ('U').
Is
> this correct?
>
> If so, does that not mean that the value of :
>
> return x % 2 == 0 ? (*(beg+mid) + *(beg+(mid-1))) / 2 :*(beg+mid);
>
> has the same type as the value of the size of the array/vector (i.e. the
3rd
> parameter in my median function)? This doesn't really makes sense to me.
Can
> anyone shed any light on what's happening?
>
 Your analysis above is exactly correct, what you seem to be missing is that
you have the power to specify the return type another way.

Since you have designed your function to use iterators, it makes sense to
define the return type to be the same as that of the value_type of the
iterators. IOW, you can declare the function as:

// note more meaningful parameter names .. always a good idea
template <class iter, class size_t>
typename std::iter::value_type
median(iter beg, iter end, size_t length);

and it will now return the correct value type with exactly the same
definition. Note also that improper use of the function (for example if the
beg and end types are not STL iterators) will cause a compile-time error
when the function is instantiated. However, this version will not be
instantiated for pointer types, since then the expression iter::value_type
will be meaningless.

You can make it work for pointers as well, however, using the
std::iterator_traits template from the STL. This also allows you to get rid
of the second template parameter, since the length of the range pointed to
can be determined from the iterator arguments. For example:

#include <iterator>
#include <algorithm>

template <class iter>
typename std::iterator_traits<iter>::value_type
median(iter beg, iter end)
{
  if (! (end > beg) ) // note broader error checking
    throw std::domain_error("Median of empty range.");

  sort(beg, end);
  typename std::iterator_traits<iter>::difference_type len=(end-beg);
  iter mid = beg+len/2;

  return ( len % 2 == 0) // IMO line breaks enhance readability here
    ? (*mid + *(mid-1))/2
    : *mid;
}

    This will now compile for any STL-derived iterator for which operator-,
operator+ and operator > are defined, or for any raw pointer type, provided
that the results of deferencing the iterators or pointers can be used in the
mathematical operations specified in the function. However, for pointers
the function will not run properly unless the pointer arguments point to
contiguous storage (i.e. end must be "reachable" from beg in the parlance of
the C++ Standard). The danger is that you will at some point use the
function with raw pointers into non-contiguous storage, which will silently
yield undefined behavior.
    However you had the same danger with the previous version of median as
well. Furthermore, this is always a danger when passing simple pointers to
functions designed to take iterators. Although the STL provides the
mechanism to allow use of bare pointers as iterators using the pointer
specialization of std::iterator_traits, it is always assumed that they point
to contiguous storage, and this can never be checked at compile time or run
time. So, you should always keep this potential drawback in mind ... it is
one of the better reasons to always use STL containers, as opposed to
built-in arrays and pointers, with STL algorithms.

HTH,

Dave Moore

Relevant Pages

  • Re: std::vector : begin, end and insert - Using Objects instead of ints
    ... vector< CPoint> vec; ... lists, which only have iterators. ... "overloaded pointers", and it is better to say that iterators are "an ... iterator approach to a loop. ...
    (microsoft.public.vc.mfc)
  • Re: Bug in my code or compiler?
    ... >> as pointing before the element, it ought to make equal sense to see ... >> than your suggestion re. thinking about iterators could save. ... When you say "pointers point ...
    (alt.comp.lang.learn.c-cpp)
  • abstract containers: does such a thing exist, conceptually?
    ... code implementing that pattern? ... behaviour by the additional pointers. ... trigger adding- or removing-operations of other iterators... ... 2)graph = list of lists: The same as above but with its own allocator ...
    (comp.object)
  • Re: Pointer To A Vector Elements While Still Adding
    ... No. list iterators (and you really should be using iterators, not pointers, ... Well that's a problem for vectors, but not for lists. ... lists do not (each node stores the address of the ...
    (comp.lang.cpp)
  • Re: Problem Based Passing Vectors Elements As Arguments
    ... > loop using the vector iterators. ... > Ok well fcalls another function, and i want to pass pointers to the ... > Well i know that the iterator class is basically just a pointer ... template<class ItX, class ItY> void f{ ...
    (comp.lang.cpp)