Re: Accelerated C++ Exercise 3-4 Solution Question
On Apr 2, 9:08 pm, <t...@shigeru.sci.utah.edu> wrote:
You'll note that the OP's program prints both the minimum and maximum
elements.
This brings to light an issue I've myself run into. I find myself
often needing to do this kind of thing -- i.e. find the minimum and
maximum over a range -- for very large datasets. Using min_element
and max_element would require two O(n) passes over the data, which
is unacceptable in many circumstances. Thus I find myself creating
nonstd::minmax_element or whatever, with obvious semantics.
Logically, they're both iterating over the range, but have a difference
in an if-statement w/in the loop. What I'd really like is to somehow
evaluate the two operations into a single operation. Sort of like how
we bind constant values to binary_functions to create unary_functions.
Something like:
std::pair<double,double> minmax;
minmax = somesorta::iterate(range, alglist(std::min_element,
std::max_element));
std::cout << "min elem: " << minmax.first << '\n'
<< "max elem: " << minmax.second << std::endl;
I guess I really want a `reduce' which takes a variable number of
computations as input. The crux seems to be that range iteration
and data access are defined as one atomic unit in the STL at least,
preventing this kind algorithm decoupling.
Perhaps there is some sort of analogous relation between my `algorithm
list' (``alglist'', above) and `type lists'. Both ideas are known
statically at compile time. In both cases, I need to compose an
arbitrary-length list into a single entity. I don't have any more time
to think about this today...
Have others thought about this? What is [are] your solution[s]?
Using Boost, I whipped up the following in C++03. C++0x will move
almost all of the extensions and helper functions I've used in the
code below to the standard. C++0x will allow you to define functions
in-place. Until then, we have the Boost lambda libraries for C++03.
Also we'll get initialization lists in C++0x, which will lessen the
need for asVector.
The problem is that std::min_element and std::max_element are not
particularly extensible or reusable. The reason is that they couple
iterating and the algorithm applied to each element iterated over. I
use std::for_each and Boost lambda expressions instead.
#include "boost/lambda/bind.hpp"
#include "boost/lambda/if.hpp"
#include "boost/lambda/lambda.hpp"
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using namespace boost::lambda;
//helpers I use that are independent of this problem
template <size_t n, typename element_t, typename function_t>
function_t for_each(element_t (&x)[n], function_t func)
{ return for_each(x, x+n, func); }
template <typename range_t, typename function_t>
function_t for_each(range_t& range, function_t func)
{ return for_each(range.begin(), range.end(), func); }
//inspired by Java
template <size_t n, typename T>
vector<T> asVector(T (&x)[n])
{ return vector<T>(x, x+n); }
// //
void foo()
{
int x[] = {5,2,7,89,12,8};
int min = x[0], max = x[0];
for_each(x, (if_then(_1 < var(min), var(min) = _1),
if_then(var(max) < _1, var(max) = _1)));
cout << "min " << min << ", max " << max << endl;
}
void bar()
{
int x[] = {5,2,7,89,12,8};
vector<int> const y(asVector(x));
int min = y[0], max = y[0];
for_each(y, (if_then(_1 < var(min), var(min) = _1),
if_then(var(max) < _1, var(max) = _1)));
cout << "min " << min << ", max " << max << endl;
}
int main()
{ foo();
bar();
}
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]