getting keys out of a map

Discussion in 'C++' started by Paul MG, Jul 24, 2003.

  1. Paul MG

    Paul MG Guest

    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.
     
    Paul MG, Jul 24, 2003
    #1
    1. Advertising

  2. On 24 Jul 2003 14:16:41 -0700, (Paul MG) wrote:

    >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".
     
    Alf P. Steinbach, Jul 24, 2003
    #2
    1. Advertising

  3. "Paul MG" <> wrote in message
    news:...
    > 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'.
    >


    ---snip---

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

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

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

    ---snip---

    > Cheers
    >
    > Paul.


    --
    Roger
     
    Roger Willcocks, Jul 25, 2003
    #3
  4. Paul MG

    tom_usenet Guest

    On 24 Jul 2003 14:16:41 -0700, (Paul MG)
    wrote:

    >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
     
    tom_usenet, Jul 25, 2003
    #4
  5. "Paul MG" <> wrote in message
    news:...
    > 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::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---

    > thanx for feedback,
    >
    > paul.


    --
    Roger
     
    Roger Willcocks, Jul 25, 2003
    #5
  6. Paul MG

    Paul MG Guest

    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.
     
    Paul MG, Jul 25, 2003
    #6
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Erik Arner
    Replies:
    0
    Views:
    1,320
    Erik Arner
    Nov 2, 2004
  2. Norman Shelley
    Replies:
    0
    Views:
    281
    Norman Shelley
    Oct 11, 2003
  3. Angus
    Replies:
    12
    Views:
    688
    James Kanze
    Oct 2, 2007
  4. alan
    Replies:
    3
    Views:
    374
    Victor Bazarov
    Nov 28, 2007
  5. Chris Riesbeck

    JSTL: getting a map's keys

    Chris Riesbeck, Mar 19, 2012, in forum: Java
    Replies:
    19
    Views:
    5,273
    Chris Riesbeck
    Mar 26, 2012
Loading...

Share This Page