getting keys out of a map

[Paul MG]

Hi

Is there a simple general way of getting the keys out of a map? Or a vector of
pairs?

My problem seems to be that the pair<> type returned by iterating through either
has no methods to bind to to get the .first or .second elements. That seems to
me to be a major oversight - so I am assuming I must be making one!

For instance, imagine I want to use eg accumulate, to add up all the keys in a
map:


template<class A, class B>
struct FirstOfPair : public unary_function< const pair<A, B>, A> {
A operator()(cons t pair<A, B>& p) { return p.first; }
};

template<class A, class B>
struct AccumulatePairF irsts : public binary_function <A, const pair<A, B>, A> {
A operator()(A a, const pair<A, B>& p) { return a + FirstOfPair<A,B >()(p); }
};

int sumKeys(const map<int, string>& m) {
return accumulate(m.be gin(), m.end(), 0,
AccumulatePairF irsts<int, string>());
}


This is pretty horrendous! It took me about 20 goes to get this all right. Also
I am not happy that I had to define AccumulatePairF irsts - couldnt I bind (or
compose?) with plus<int>() here?

Calling any gurus, please help!

I have a not-totally-weak functional background btw; I just often find it hard
to see how to do simple things using C++'s 'way'.

Cheers

Paul.

[Roger Willcocks]

Re: getting keys out of a map


"Paul MG" <paulmg@digital brain.com> wrote in message
news:265e380f.0 307240544.88075 68@posting.goog le.com...[color=blue]
> Hi
>
> Is there a simple general way of getting the keys out of a map? Or a[/color]
vector of[color=blue]
> pairs?
>
> My problem seems to be that the pair<> type returned by iterating through[/color]
either[color=blue]
> has no methods to bind to to get the .first or .second elements. That[/color]
seems to[color=blue]
> me to be a major oversight - so I am assuming I must be making one!
>
> For instance, imagine I want to use eg accumulate, to add up all the keys[/color]
in a[color=blue]
> map:
>
>
> template<class A, class B>
> struct FirstOfPair : public unary_function< const pair<A, B>, A> {
> A operator()(cons t pair<A, B>& p) { return p.first; }
> };
>
> template<class A, class B>
> struct AccumulatePairF irsts : public binary_function <A, const pair<A,[/color]
B>, A> {[color=blue]
> A operator()(A a, const pair<A, B>& p) { return a +[/color]
FirstOfPair<A,B >()(p); }[color=blue]
> };
>
> int sumKeys(const map<int, string>& m) {
> return accumulate(m.be gin(), m.end(), 0,
> AccumulatePairF irsts<int, string>());
> }
>
>
> This is pretty horrendous! It took me about 20 goes to get this all right.[/color]
Also[color=blue]
> I am not happy that I had to define AccumulatePairF irsts - couldnt I bind[/color]
(or[color=blue]
> compose?) with plus<int>() here?
>
> Calling any gurus, please help!
>
> I have a not-totally-weak functional background btw; I just often find it[/color]
hard[color=blue]
> to see how to do simple things using C++'s 'way'.
>[/color]

---snip---

#include <iostream>
#include <algorithm>
#include <string>
#include <map>

struct accumulate {
int& total;
accumulate(int& total_) : total(total_) { }
void operator()(cons t std::pair<int, std::string> &p) { total +=
p.first; }
};

int main(int argc, char* argv[])
{
std::map<int, std::string> foo;

foo[3] = "hello";
foo[6] = "world";

int total = 0;
for_each(foo.be gin(), foo.end(), accumulate(tota l));

std::cout << "key total = " << total << std::endl;
return 0;
}

---snip---
[color=blue]
> Cheers
>
> Paul.[/color]

--
Roger

[tom_usenet]

Re: getting keys out of a map

On 24 Jul 2003 14:16:41 -0700, paulmg@digitalb rain.com (Paul MG)
wrote:
[color=blue]
>Hi
>
>Is there a simple general way of getting the keys out of a map? Or a vector of
>pairs?
>
>My problem seems to be that the pair<> type returned by iterating through either
>has no methods to bind to to get the .first or .second elements. That seems to
>me to be a major oversight - so I am assuming I must be making one!
>
>For instance, imagine I want to use eg accumulate, to add up all the keys in a
>map:
>
>
> template<class A, class B>
> struct FirstOfPair : public unary_function< const pair<A, B>, A> {
> A operator()(cons t pair<A, B>& p) { return p.first; }
> };
>
> template<class A, class B>
> struct AccumulatePairF irsts : public binary_function <A, const pair<A, B>, A> {
> A operator()(A a, const pair<A, B>& p) { return a + FirstOfPair<A,B >()(p); }
> };
>
> int sumKeys(const map<int, string>& m) {
> return accumulate(m.be gin(), m.end(), 0,
> AccumulatePairF irsts<int, string>());
> }
>
>
>This is pretty horrendous! It took me about 20 goes to get this all right. Also
>I am not happy that I had to define AccumulatePairF irsts - couldnt I bind (or
>compose?) with plus<int>() here?
>
>Calling any gurus, please help!
>
>I have a not-totally-weak functional background btw; I just often find it hard
>to see how to do simple things using C++'s 'way'.[/color]

If you must use algorithms, then you should either use iterator
adaptors or lambda functions. e.g.

To write an iterator adaptor that projects an iterator onto the first
member of a pair (or use the projection iterator with a suitable
functor):

http://www.boost.org/libs/utility/iterator_adaptors.htm

Using boost.lambda: http://www.boost.org/libs/lambda/doc/index.html

#include <map>
#include <string>
#include <numeric>
#include <iostream>
#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>

int main()
{

using namespace boost::lambda;
typedef std::map<int, std::string> m_t;
typedef m_t::value_type pair_t;
m_t m;
m[4] = "Foo";
m[2] = "Bar";
int result = std::accumulate (
m.begin(),
m.end(),
0,
_1 + bind(&pair_t::f irst, _2)
);
std::cout << result << '\n';
}

Without a toolkit like boost.lambda handy, the for loop definitely
wins in cases like this, and even with boost.lambda, the increase in
compile times might not be worth it.

Tom

[Roger Willcocks]

Re: getting keys out of a map


"Paul MG" <paulmg@digital brain.com> wrote in message
news:265e380f.0 307250256.588e0 7d0@posting.goo gle.com...[color=blue]
> Thanks for your thoughts guys.
>
> There seem to be two major threads of response:
>
> 1) Use C (ie explicit loops). I realise that this can be a tradeoff[/color]
worth[color=blue]
> making, I just wanted to push a little harder toward StlStyle to see[/color]
if[color=blue]
> we could come up something nicer.
>
> 2) Don't use std::accumulate () to do your accumulation, use[/color]
std::for_each()[color=blue]
> and a bespoke functor. A neat solution I agree but it bugs me not to[/color]
use[color=blue]
> std::accumulate () to accumulate a range.
>
> What I think I want to be able to do though, is something like:
>
> int sumKeys(const map<int, string>& m) {
> return accumulate(m.be gin(), m.end(), 0,
> someBinding(plu s<int>,
> mem_fun_ref(&pa ir<int,[/color]
string>::first) )[color=blue]
> );
> }
>
> Because it seems more expressive of intent. It says
>
> return the *accumulation* of *m* *adding up* the *first* of each[/color]
element.[color=blue]
>
> Rather than
>
> initialize an accumulator variable to zero
> initialize an iterator to the first element of *m*
> while that iterator is not at the last element of *m*
> add the *first* of the pointed-at element to my accumulator variable
> increment that iterator
> return the value of my accumulator variable
>
> See how sparse the actual algorithm core is amongst all the surrounding[/color]
stuff[color=blue]
> in the second version?
>
> Obviously I am biased here, perhaps someone else would like to write out[/color]
the[color=blue]
> two 'scripts' and somehow show that an alternative to my version is more
> expressive?
>
> Of course, there is the slight problem that I haven't quite worked out[/color]
what[color=blue]
> someBinder() is in my solution ;). That's what I'm posting to find out I[/color]
guess![color=blue]
>[/color]

Because (as you pointed out in your original post) std::pair doesn't define
member functions to access
its member variables, the mem_fun and mem_fun_ref helpers don't help, so I
don't think this can be
done as a one-liner.

Once you've defined the symantics of adding a pair<int, string> to an int,
however, it's all rather easy:

---snip---

namespace std {
inline int operator+(const int& acc, const std::pair<int, std::string>&
p) {
return acc + p.first;
}
}

std::map<int, std::string> foo;

int total = std::accumulate (foo.begin(), foo.end(), 0);

---snip---
[color=blue]
> thanx for feedback,
>
> paul.[/color]

--
Roger

[Paul MG]

Re: getting keys out of a map

Thanks tom_usenet, it was interesting to see the solution using
boost::lambda.

I am currently perusing boost's iterator adaptor library too. Thanks
for the link.

I have since realised what I 'need' to solve my original problem as
stated:

1) pair<> to have functions for first and second which you can
bind against

2) arbitrary function compose()rs which can build a 'tree' of
functions, leading from args to return type, rather than
just the 'pipeline' provided by compose1() etc.

In reference to (1), are there good justifications for why these don't
exist? It just makes you write your own functors FirstOfPair<> and
SecondOfPair<> to do it. I have always accepted that 'public data is
evil, prefer private data and public accessors'; can anybody explain
why this is an exceptional case?

In reference to (2)... Well, possibly I am just barking up the wrong
tree entirely. I think that is what the general feel of the feedback
has been!

But I managed to create a sort of tree-like compose(), to do what I
want. Here it is:

// Constraint: UnOp::result_ty pe == BinOp::second_a rgument_type
template<class BinOp, class UnOp>
class MyBinder2nd : public
binary_function <typename BinOp::first_ar gument_type,
typename UnOp::argument_ type,
typename BinOp::result_t ype> {
protected:
BinOp binOp;
UnOp unOp;
public:
MyBinder2nd(con st BinOp& b, const UnOp& u)
: binOp(b), unOp(u) {}

result_type operator() (
const first_argument_ type& x,
const second_argument _type& y)
{
return binOp(x, unOp(y));
}
};

template<class BinOp, class UnOp>
MyBinder2nd<Bin Op, UnOp> MyBind2nd(const BinOp& b,
const UnOp& u)
{
return MyBinder2nd<Bin Op, UnOp>(b, u);
}

I feel I could enforce that 'Constraint' somehow using template
templates (could I?)

My main problem is that I couldn't think of a sensible name.
TreeCompose is just silly. MyBind2nd is cos it is like bind2nd but
takes a unary_function instead of a fixed value to bind against the
second arg.

A secondary problem is that this seems to be very specific: what about
building arbitrary trees of function calls? is that hard? impossible?
(given the non-availability of variable-length template-arg lists).

Anyway, my client code now looks like this:

int f(const map<int, string>& m) {
return accumulate(m.be gin(), m.end(), 0,
MyBind2nd(plus< int>(),
FirstOfPair<int , string>()));
}

which is acceptable I think? Tho it seems a pain that I have to
declare all those template params, is there any way they could be
inferred?

------------

I am surprised no-one has said this yet, so I will say it myself:
"trying to program Lisp/Haskell in C++ is just stupid."

I accept that initially, what I have trouble with is when it is
sensible to use a functional, declarative style in solving a problem
in C++, and when to revert to an imperative, procedural style. The
literature appears to draw the line 'when it looks messy'. But this is
too subjective - many people think even a simple use of for_each more
'messy' than a simple for-loop. If declarative is good, surely it
should be good all the way up?

Another way of formulating my point is,

1. There exist some arguments which justify preferring a
for_each call over a simple for loop.
2. Some people reject those arguments with counterargument s.

Therefore if you reject my attempts to use STL rather than a loop in
this case, using the arguments from (2), can I not just respond with
the arguments from (1)? How is the situation different?

Any illuminating thoughts here would be much appreciated. :)

Thanks for your help,

Paul.