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()(const pair<A, B>& p) { return p.first; }
};

template<class A, class B>
struct AccumulatePairFirsts : 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.begin(), m.end(), 0,
AccumulatePairFirsts<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 AccumulatePairFirsts - 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.

 

[Alf P. Steinbach]

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

Yes, it's called a for-loop.

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()(const pair<A, B>& p) { return p.first; }
};

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

I don't understand the purpose of FirstOfPair, why not just
write "p->first" instead of "FirstOfPari<A,B>()(p)", which is both
simpler and possibly (depending on compiler) much more efficient?

int sumKeys(const map<int, string>& m) {
return accumulate(m.begin(), m.end(), 0,
AccumulatePairFirsts<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 AccumulatePairFirsts - couldnt I bind (or
compose?) with plus<int>() here?

Calling any gurus, please help!

Sorry, I'm no guru on the standard template classes.

But I suggest less template "magic". It requires both analysis and
knowledge of particulars (of library classes). Instead, use e.g.


template< typename Key, typename Value >
Key sumOfKeys( std::map<Key, Value> const& aMap )
{
std::map<Key, Value>::const_iterator it;
Key sum = 0;

for( it = aMap.begin(); it != aMap.end(); ++it ){ sum += it->first; }
return sum;
}

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'.

A simple for-loop is very consistent with "the way".

 

[Roger Willcocks]

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()(const pair<A, B>& p) { return p.first; }
};

template<class A, class B>
struct AccumulatePairFirsts : public binary_function<A, const pair<A, B>, A> {
A operator()(A a, const pair<A, B>& p) { return a +

};

int sumKeys(const map<int, string>& m) {
return accumulate(m.begin(), m.end(), 0,
AccumulatePairFirsts<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 AccumulatePairFirsts - 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'.

---snip---

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

struct accumulate {
int& total;
accumulate(int& total_) : total(total_) { }
void operator()(const std:air<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.begin(), foo.end(), accumulate(total));

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

---snip---

 

[tom_usenet]

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()(const pair<A, B>& p) { return p.first; }
};

template<class A, class B>
struct AccumulatePairFirsts : 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.begin(), m.end(), 0,
AccumulatePairFirsts<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 AccumulatePairFirsts - 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'.

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::first, _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]

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 worth
making, I just wanted to push a little harder toward StlStyle to see if
we could come up something nicer.

2) Don't use std::accumulate() to do your accumulation, use std::for_each()
and a bespoke functor. A neat solution I agree but it bugs me not to use
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.begin(), m.end(), 0,
someBinding(plus<int>,
mem_fun_ref(&pair<int, string>::first))
);
}

Because it seems more expressive of intent. It says

return the *accumulation* of *m* *adding up* the *first* of each element.

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 stuff
in the second version?

Obviously I am biased here, perhaps someone else would like to write out the
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 what
someBinder() is in my solution . That's what I'm posting to find out I guess!

Because (as you pointed out in your original post) std:air 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:air<int, std::string>&
p) {
return acc + p.first;
}
}

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

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

---snip---

 

[Paul MG]

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_type == BinOp::second_argument_type
template<class BinOp, class UnOp>
class MyBinder2nd : public
binary_function<typename BinOp::first_argument_type,
typename UnOp::argument_type,
typename BinOp::result_type> {
protected:
BinOp binOp;
UnOp unOp;
public:
MyBinder2nd(const 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<BinOp, UnOp> MyBind2nd(const BinOp& b,
const UnOp& u)
{
return MyBinder2nd<BinOp, 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.begin(), 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 counterarguments.

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.