Re: Is it okay to ask questions about Accelerated C++ exercises here?

From:

"Daniel T." <daniel_t@earthlink.net>

Newsgroups:

comp.lang.c++

Date:

Sat, 21 Jun 2008 11:58:24 -0400

Message-ID:

<daniel_t-EF2040.11582321062008@earthlink.vsrv-sjc.supernews.net>

swivelhead <jetimms@gmail.com> wrote:

Wow! You did a lot of research and this is a much better second draft.
Now for the final draft... :-)

First, look up 'distance' in your reference so your algorithm will work
with lists as well as vectors and deques.

// median.h
#ifndef GUARD_MEDIAN_H
#define GUARD_MEDIAN_H

#include <algorithm>
#include <cstring>
#include <iostream>
#include <iterator>
#include <stdexcept>

#include <vector>

template<typename InputIterator>
typename std::iterator_traits<InputIterator>::value_type
median(InputIterator first, InputIterator last)
{
  typedef typename
    std::iterator_traits<InputIterator>::value_type ReturnType;
  typedef typename
    std::iterator_traits<InputIterator>::difference_type DiffType;

  DiffType elementTotal = last - first;

  if (elementTotal == 0)
    throw std::domain_error("median of an empty set");

Another way to do the above... if (first == last)... You don't need
elementTotal.

// built the temporary container

std::vector<ReturnType> tempSet;

// fill in the temporary container
copy(first, last, back_inserter(tempSet));

Instead of making the vector, then copying it, then sorting it. Look
into using partial_sort_copy. Only copy the half of the input that you
need.

At this point, tempSet.size() == elementTotal... You don't need both
variables, they are the same. So remove elementTotal.

DiffType halfElementTotal = elementTotal / 2;

typename std::vector<ReturnType>::iterator throughMedianIter =

    tempSet.begin() + halfElementTotal + 1;

  // sort the temporary container through (one passed) the midpoint
  std::partial_sort(
      tempSet.begin(),
      throughMedianIter,
      tempSet.end());

  bool hasEvenElements = elementTotal % 2 == 0;
  DiffType midPoint = halfElementTotal;

midPoint == halfElementTotal... You don't need both variables, they are
the same.

  ReturnType median =
    hasEvenElements ?
    (tempSet[midPoint] + tempSet[midPoint - 1]) / 2 :
    tempSet[midPoint];

  return median;
}

#endif GUARD_MEDIAN_H
// end of median.h