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

[swivelhead]

I just wanted to check and make sure that it is cool with this group's
rules.

Thanks.

[Victor Bazarov]

swivelhead wrote:

I just wanted to check and make sure that it is cool with this group's
rules.

Ask away.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Daniel T.]

swivelhead <je*****@gmail.comwrote:

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_ty pe 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<ReturnTypetempSet;

>
// 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

[swivelhead]

Thanks again Daniel and Michael. This has been an interesting
exercise.

I did a check for first == last and left it at the top in my latest
draft. Does that disqualify it from using lists?

Also, does midPoint need to be of the type
std::iterator_traits<vector<ReturnType>::iterator> ::difference_type?

Here's the results:

template<typename InputIterator>
typename std::iterator_traits<InputIterator>::value_type
median(InputIterator first, InputIterator last)
{
if (first == last)
throw std::domain_error("median of an empty set");

// built the temporary container big enough to do a partial sort of
one more
// of one more than half the size of the input container (odd or
even) to
// accomadate the median
typedef typename
std::iterator_traits<InputIterator>::difference_ty pe DiffType;

DiffType origSize = std::distance(first, last);

typedef typename
std::iterator_traits<InputIterator>::value_type ReturnType;

vector<ReturnTypetempSet((origSize / 2) + 1);

// fill in the temporary container while sorting
std::partial_sort_copy(
first,
last,
tempSet.begin(),
tempSet.end());

DiffType midPoint = tempSet.size() - 1;

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

return median;
}

[Daniel T.]

swivelhead <je*****@gmail.comwrote:

Thanks again Daniel and Michael. This has been an interesting
exercise.

I did a check for first == last and left it at the top in my latest
draft. Does that disqualify it from using lists?

Also, does midPoint need to be of the type
std::iterator_traits<vector<ReturnType>::iterator> ::difference_type?

No, it should be the same type as vector<ReturnType>::size()'s return
type. Which for all vectors is vector<T>::size_type. (Which is
convertible to size_t hence Michael's response is acceptable.)

Here's the results:

After applying Michael's final changes, compare the end result with your
first draft and be amazed... It calls to mind Blaise Pascal's quote:
"...my letters were not wont... to be so prolix... Want of time must
plead my excuse..."

It takes time to make code succinct.

Personally, I would have eliminated 'median', 'midPoint' as well. The
information in those variables is redundant.

template<typename InputIterator>
typename std::iterator_traits<InputIterator>::value_type
median(InputIterator first, InputIterator last)
{
if (first == last)
throw std::domain_error("median of an empty set");

// built the temporary container big enough to do a partial sort of
one more
// of one more than half the size of the input container (odd or
even) to
// accomadate the median
typedef typename
std::iterator_traits<InputIterator>::difference_ty pe DiffType;

DiffType origSize = std::distance(first, last);

typedef typename
std::iterator_traits<InputIterator>::value_type ReturnType;

vector<ReturnTypetempSet((origSize / 2) + 1);

// fill in the temporary container while sorting
std::partial_sort_copy(
first,
last,
tempSet.begin(),
tempSet.end());

DiffType midPoint = tempSet.size() - 1;

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

return median;
}

[swivelhead]

>

After applying Michael's final changes, compare the end result with your
first draft and be amazed... It calls to mind Blaise Pascal's quote:
"...my letters were not wont... to be so prolix... Want of time must
plead my excuse..."

It takes time to make code succinct.

Personally, I would have eliminated 'median', 'midPoint' as well. The
information in those variables is redundant.

The differences are crystal clear. My next step is two do some tests
with other container types and numeric types.

Thanks for the incredible information!

BTW: I kept the median/midPoint variables just for readability's sake.
I'm a verbose programmer and like things laid out and obvious because,
frankly, I don't remember much about the code I wrote last month.
Also, I don't like returning from an operator statement.

Here's my final, final, (final?) draft:

template<typename ForwardIterator>
typename std::iterator_traits<ForwardIterator>::value_type
median(ForwardIterator first, ForwardIterator last)
{
if (first == last)
throw std::domain_error("median of an empty set");

// built the temporary container big enough to do a partial sort of
one more
// of one more than half the size of the input container (odd or
even) to
// accomadate the median
typedef typename
std::iterator_traits<ForwardIterator>::difference_ type DiffType;

DiffType origSize = std::distance(first, last);

typedef typename
std::iterator_traits<ForwardIterator>::value_type ReturnType;

vector<ReturnTypetempSet((origSize + 2) / 2);

// fill in the temporary container while sorting
std::partial_sort_copy(
first,
last,
tempSet.begin(),
tempSet.end());

vector<ReturnType>::size_type midPoint = tempSet.size() - 1;

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

return median;
}

[joseph cook]

Here's the results:
[snip]
* vector<ReturnTypetempSet((origSize / 2) + 1);

Use:
vector<ReturnTypetempSet( (origSize+1) / 2 );

Um.. See Below

>
It computes the exact value and avoids the UB you would have hereafter
in the case of the border effect (origSize==1).

* // fill in the temporary container while sorting
* std::partial_sort_copy(
* * * first,
* * * last,
* * * tempSet.begin(),
* * * tempSet.end());

* DiffType midPoint = tempSet.size() - 1;

If using (origSize / 2) + 1 with origSize==1, then
* * tempSet.size()=2 =midPoint=1;
But tempSet[midpoint] is not set.

How? (1/2) + 1 will equal 1, so tempSet.size() will equal 1.
The problem is when origSize is even, say '2'; then your tempSet size
will only end up being '1' big. The original poster had it right; I
think you've introduced a bug.

Joe Cook

[swivelhead]

How? * (1/2) + 1 will equal 1, so tempSet.size() will equal 1.

The problem is when origSize is even, say '2'; then your tempSet size
will only end up being '1' big. * The original poster had it right; I
think you've introduced a bug.

Indeed I did.

I tested it out and adding 2 instead of 1, as in:

vector<ReturnTypetempSet((origSize + 2) / 2);

seems to work, like my original statement:

vector<ReturnTypetempSet((origSize / 2) + 1);

Here's some quick examples of how they match:
((origSize / 2) + 1)
origSize tempSet.size()
1 1
2 2
3 2
4 3
5 3
6 4
11 6

((origSize + 2) / 2)
origSize tempSet.size()
1 1
2 2
3 2
4 3
5 3
6 4
11 6

I originally thought it would affect a different calculation for
median, therefore, I changed it. However, it was intesting finding
out that both calculations were equivalent because of the "division of
an odd int" characteristic in C++.

[swivelhead]

I originally thought it would affect a different calculation for

median, therefore, I changed it. *However, it was intesting finding
out that both calculations were equivalent because of the "division of
an odd int" characteristic in C++.

Wait a minute, they would be equivalent in normal division too. I
should have recognized that. I think I need some more sleep!