S
swivelhead
I just wanted to check and make sure that it is cool with this group's
rules.
Thanks.
rules.
Thanks.
Ask away.
V
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.
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;
}
[snip]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.
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:
[snip]
vector<ReturnType> tempSet((origSize / 2) + 1);
// fill in the temporary container while sorting
std:artial_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];
[snip]
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.
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:artial_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.
If using (origSize / 2) + 1 with origSize==1, thentempSet.end());
DiffType midPoint = tempSet.size() - 1;
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.
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++.
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.