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

S

swivelhead

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

Thanks.
 
S

swivelhead

Ask away.

V

Thanks Victor.

This question deals with exercises 10-2 and 10-3.
10-2.
Rewrite the median function from $8.11/140 so that we can call it with
either a vector or a built-in array. The function should allow
containers of any arithmetic type.
10-3.
Write a test program to verify that the median function operates
correctly. Ensure that calling median does not change the order of the
elements in the container.

I will leave out the $8.11/140 example for now, but will post it if
anyone wants. Here is my shot at the median function. (Note, anyone
who has seen the book/examples will see that I added an insertion sort
where the generic sort function would be. I actually made it a
template function also, but the vector container kept passing by value
and not sorting:)

template<typename ReturnType, typename ContainerType>
ReturnType median(ContainerType set, size_t elementTotal) {
if (elementTotal == 0)
throw std::domain_error("median of an empty set");

ReturnType check;

std::cout << "The element total is " << elementTotal << endl;

// perform insertion sort
for(int i = 0; i < elementTotal; i++) {
// grab element value
check = set;

// while there is a element to the left that is greater than check
for(int j = i; j > 0 && (set[j - 1] > check); --j) {
// swap the two element values
set[j] = set[j - 1];
set[j - 1] = check;
}
}

// recheck order
std::cout << "rechecking order" << std::endl;
for(size_t index = 0;
index < elementTotal;
++index)
{
std::cout << set[index] << std::endl;
}

// sort<ReturnType, ContainerType>(set, elementTotal);

size_t mid = elementTotal / 2;

return elementTotal % 2 == 0 ? (set[mid] + set[mid - 1]) / 2 :
set[mid];
}

Here's my problem. The vector is passing by value and the array
(pointer) is passing by reference, so even though it finds a median in
both cases, it is altering the order of my array.

This is how I'm calling them from my test program.
vector<int> set1;
...
// set1 is filled
...
cout << "the median is "
<< median<int, vector<int> >(set1, set1.size()) << endl;

const size_t maxint = set1.size();
int *set2 = new int[maxint];
// set2 is filled
cout << "the median is "
<< median<int, int[]>(set2, maxint) << endl;

What are some strategies for accepting both indexed containers by
value?

Thanks.
 
S

swivelhead

Thanks Daniel. That's good advice. Here's the final result.

I still have the RetrunType template parameter, but I don't know how
to get the type of a container's elements consistently for STL
container or built-in arrays alike.

template<typename ReturnType, typename InputIterator>
ReturnType median2(InputIterator first, InputIterator last)
{
size_t elementTotal = last - first;

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

std::cout << "The element total is " << elementTotal << endl;

// built the temporary container
ReturnType *tempSet = new int[elementTotal];

// perform insertion sort
for(int i = 0; i < elementTotal; i++)
{
tempSet = first;
}

// perform insertion sort
for(int i = 0; i < elementTotal; i++)
{
// grab element value
ReturnType check = tempSet;

// while there is a element to the left that is greater than check
for(int j = i; j > 0 && (tempSet[j - 1] > check); --j)
{
// swap the two element values
tempSet[j] = tempSet[j - 1];
tempSet[j - 1] = check;
}
}

// recheck order
std::cout << "rechecking order" << std::endl;
for(size_t index = 0;
index < elementTotal;
++index)
{
std::cout << tempSet[index] << std::endl;
}

// sort<ReturnType, ContainerType>(set, elementTotal);

size_t mid = elementTotal / 2;

ReturnType returnValue =
elementTotal % 2 == 0 ? (tempSet[mid] + tempSet[mid - 1]) / 2 :
tempSet[mid];

delete[] tempSet;

return returnValue;
}
 
D

Daniel T.

swivelhead said:
Thanks Daniel. That's good advice. Here's the final result.

I still have the RetrunType template parameter, but I don't know how
to get the type of a container's elements consistently for STL
container or built-in arrays alike.

Check out "iterator_traits" in your best reference. Two of my
favorites are:
http://www.dinkumware.com/manuals/ and
http://www.sgi.com/tech/stl/

Do you remember Comp 1 in college? What you have below is a first
draft. Now that your function works, it's time to refine it.
template<typename ReturnType, typename InputIterator>
ReturnType median2(InputIterator first, InputIterator last)
{
size_t elementTotal = last - first;

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

std::cout << "The element total is " << elementTotal << endl;

// built the temporary container
ReturnType *tempSet = new int[elementTotal];

Get out of the habit of using raw memory. The above can be replaced
with a vector.
// perform insertion sort
for(int i = 0; i < elementTotal; i++)
{
tempSet = first;
}

// perform insertion sort
for(int i = 0; i < elementTotal; i++)
{
// grab element value
ReturnType check = tempSet;

// while there is a element to the left that is greater than check
for(int j = i; j > 0 && (tempSet[j - 1] > check); --j)
{
// swap the two element values
tempSet[j] = tempSet[j - 1];
tempSet[j - 1] = check;
}
}


Get out of the habit of writing that which already exists in the
language...
You don't need to sort the whole container in order to find out what
the middle one or two would be if it were sorted. Look up
"partial_sort" in your favorite reference.
// recheck order
std::cout << "rechecking order" << std::endl;
for(size_t index = 0;
index < elementTotal;
++index)
{
std::cout << tempSet[index] << std::endl;
}

The above (and the other couts in this function) are inapproprate. If
you feel the need to put them in, then you should make a seperate
function that creates the output you want to examine.
In other words, if you find yourself wanting to double check the
results of an algorithm you wrote, then you should wrap that algoritm
in its own function that returns the results. Don't put debug couts in
the middle of functions.
// sort<ReturnType, ContainerType>(set, elementTotal);

size_t mid = elementTotal / 2;

ReturnType returnValue =
elementTotal % 2 == 0 ? (tempSet[mid] + tempSet[mid - 1]) / 2 :
tempSet[mid];

delete[] tempSet;

return returnValue;
}
 
S

swivelhead

That was challenging, but do-able and I learned a heck of a lot in the
process.
It's one thing to learn the capabilities of a language, but quite
another to learn the best practices.

Thanks for the nice suggestions, Daniel!

I did some minor manual tests, but it looks like it works according to
the original excercises.

Here's what I came up with:

// median.h
#ifndef GUARD_MEDIAN_H
#define GUARD_MEDIAN_H

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

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");

// built the temporary container
vector<ReturnType> tempSet;

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

DiffType halfElementTotal = elementTotal / 2;

// The 1 is added on the end because partial sort's second argument
should be
// the middle point "to" which the sort is performed, not "through"
which.
// Therefore, it goes one past no matter if there are an even or odd
amount
// of elements, specifically because we are looking for a median
value.
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;

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

return median;
}

#endif GUARD_MEDIAN_H
// end of median.h

// chap1003.cpp
#include <iostream>
#include <vector>
#include "median.h"

using std::cout;
using std::cin;
using std::endl;
using std::vector;

int main()
{
typedef double ArithmeticType;

ArithmeticType number;

cout << "Please enter some numbers: " << endl;

vector<ArithmeticType> set1;

while(cin >> number)
{
set1.push_back(number);
}

cout << "Get the median using a vector of these numbers:" << endl;

// print set
for(vector<ArithmeticType>::iterator intiter = set1.begin();
intiter != set1.end();
++intiter)
{
cout << *intiter << endl;
}

size_t vec_len = set1.size();

cout << "the median is "
<< median2(set1.begin(), set1.end()) << endl;

for(vector<ArithmeticType>::iterator intiter = set1.begin();
intiter != set1.end();
++intiter)
{
cout << *intiter << endl;
}

cout << "Get the median using an array of these numbers:" << endl;
const size_t maxint = set1.size();
ArithmeticType *set2 = new ArithmeticType[maxint];

// get the array contents
for(size_t j = 0;
j < maxint;
++j)
{
set2[j] = set1[j] * 2;
}

// print set
for(size_t j = 0;
j < maxint;
++j)
{
cout << set2[j] << endl;
}

cout << "the median is "
<< median2(set2, set2 + maxint) << endl;

cout << "verify that the order did not change" << endl;

// print set
for(size_t j = 0;
j < maxint;
++j)
{
cout << set2[j] << endl;
}

delete[] set2;

return 0;
}
// end of chap1003.cpp
 
M

Michael DOUBEZ

Daniel T. a écrit :
template<typename InputIterator>
typename std::iterator_traits<InputIterator>::value_type
median(InputIterator first, InputIterator last)
{ [snip]
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.
[snip]

And 'last - first' doesn't necessarily give you the number of elements.
If you relly need to compute the number of elements you should use
std::iterator_traits<>::distance().

Note that in your case, you need a ForwardIterator in order to determine
if the range is empty. The best way would be to avoid doing this check
but, as Daniel T. said, use partial_sort_copy() and determine afterward
if the set is empty.
 
S

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_type DiffType;

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

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

vector<ReturnType> tempSet((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;
}
 
M

Michael DOUBEZ

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

No. Perhaps you could rename InputIterator to ForwardIterator in order
to avoid confusion - if anybody is going to read your code.

However, since you are using std::distance(), your algorithm requires
ForwardIterator and it makes sense for computing a median value.

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

No. midPoint should be of type size_t.
Here's the results:
[snip]
vector<ReturnType> tempSet((origSize / 2) + 1);

Use:
vector<ReturnType> tempSet( (origSize+1) / 2 );

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.
ReturnType median =
origSize % 2 == 0 ?
(tempSet[midPoint] + tempSet[midPoint - 1]) / 2 :
tempSet[midPoint];
[snip]
 
S

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<ReturnType> tempSet((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;
}
 
J

joseph cook

Here's the results:
[snip]
  vector<ReturnType> tempSet((origSize / 2) + 1);

Use:
vector<ReturnType> tempSet( (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
 
M

Michael DOUBEZ

joseph cook a écrit :
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.

Indeed I did.
 
S

swivelhead

How?   (1/2) + 1 will equal 1, so tempSet.size() will equal 1.
Indeed I did.

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

vector<ReturnType> tempSet((origSize + 2) / 2);

seems to work, like my original statement:

vector<ReturnType> tempSet((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++.
 
S

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!
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top