Iterator Question for map of ints to set of ints

Discussion in 'C++' started by uclamathguy@gmail.com, Apr 2, 2005.

  1. Guest

    I am working on connected component analysis, but that is irrelevant. I
    have a mapping containing ints as the keys and sets of ints as the
    "values."

    Given an integer, I need to iterate through the map, which means I must
    iterate through all of the sets in the map. I need an iterator that
    points to the set where the integer was found. How can I do this? What
    will the type of this iterator be? Can you help me with a code snippet?


    Thanks in Adv.
    Ryan
     
    , Apr 2, 2005
    #1
    1. Advertising

  2. Mark P Guest

    wrote:
    > I am working on connected component analysis, but that is irrelevant. I
    > have a mapping containing ints as the keys and sets of ints as the
    > "values."
    >
    > Given an integer, I need to iterate through the map, which means I must
    > iterate through all of the sets in the map. I need an iterator that
    > points to the set where the integer was found. How can I do this? What
    > will the type of this iterator be? Can you help me with a code snippet?
    >
    >
    > Thanks in Adv.
    > Ryan
    >


    Look at http://www.sgi.com/tech/stl/Map.html

    You haven't provided a very clear description of what you need to do.
    "Given an integer" suggests that you have a (necessarily) unique Key of
    the map in which case there is only one corresponding Data value (a set
    of ints, in your case). So what range do you want to iterate?

    find(const key_type& k) will return an interator pointing to the
    appropriate value_type element in the map, if one exists. You can then
    iterate forward from there. You could also use begin() or rbegin() to
    iterate front to back or back to front through the whole map.

    The types involved are all explained at the site above. In particular
    the iterator is of type map<_template_parameters_>::iterator and the
    result of dereferencing such an iterator is
    map<_template_parameters_>::value_type, which is in fact of type
    pair<const key_type, data_type>. You can access the key and data values
    via the .first and .second members of pair<>. A few typedefs will
    simplify your life here.
     
    Mark P, Apr 2, 2005
    #2
    1. Advertising

  3. Guest

    Thanks for the help. I have written the following function that should
    do the trick, but I am confused about the 2 starred lines.

    I would like to return an iterator to the set that contains the value
    for which I am searching. Since this set is the value of an std::map
    (map<int,set<int> >), how can I return an iterator that points to this
    specific set (2nd starred line)? Once I have that iterator, I can then
    insert the value into that specific set. What is confusing me is that
    this set is contained within an std::map if that makes sense.

    And, what would the iterator type even be (first starred line)?

    ****set<int>::iterator findValueInSet(int value,map<int,set<int>
    >::iterator iter1,map<int,set<int> >::iterator iter2)

    {
    while (iter1 != iter2)
    {
    if (((*iter1).second).find(value) != ((*iter1).second).end())
    break;
    iter1++;
    }

    if (iter1 != iter2)
    **** return ((*iter1).second); //right now I am returning a set, but
    I want to return an iterator to this set, not the set itself.
    return NULL;
    }

    Thanks in Adv.
    Ryan
     
    , Apr 2, 2005
    #3
  4. Mark P Guest

    wrote:
    > Thanks for the help. I have written the following function that should
    > do the trick, but I am confused about the 2 starred lines.
    >
    > I would like to return an iterator to the set that contains the value
    > for which I am searching. Since this set is the value of an std::map
    > (map<int,set<int> >), how can I return an iterator that points to this
    > specific set (2nd starred line)? Once I have that iterator, I can then
    > insert the value into that specific set. What is confusing me is that
    > this set is contained within an std::map if that makes sense.
    >
    > And, what would the iterator type even be (first starred line)?
    >
    > ****set<int>::iterator findValueInSet(int value,map<int,set<int>
    >
    >>::iterator iter1,map<int,set<int> >::iterator iter2)

    >
    > {
    > while (iter1 != iter2)
    > {
    > if (((*iter1).second).find(value) != ((*iter1).second).end())
    > break;
    > iter1++;
    > }
    >
    > if (iter1 != iter2)
    > **** return ((*iter1).second); //right now I am returning a set, but
    > I want to return an iterator to this set, not the set itself.
    > return NULL;
    > }
    >


    If you're returning a set and want instead an interator into the set,
    you need a member function of the set that returns an iterator. In
    addition to begin() and end(), there's find(int) which you in fact
    already use in your if condition. So why not remember that result when
    you use it? Consider the following simplifications of your code, along
    with a (mostly-- see below) correct return type:

    typedef set<int>::iterator setIter;
    typedef map<int,set<int>>::iterator mapIter;

    // untest code - not guaranteed to work :)
    setIter findValueInSet(int value, mapIter iter1, mapIter iter2)
    {
    setIter result;
    while (iter1 != iter2)
    {
    if ((result = iter1->second.find(value)) != iter1->second.end())
    resturn result;
    ++iter1;
    }

    // Uh oh, what do we return if the value is never found?
    }

    Notice that the iterator is stored in result and if it's not end() it is
    returned. But what do you do if value is never found? You can't return
    NULL as you did above (assuming NULL = 0) since NULL is not a setIter
    (btw, note the greatly improved readability which follows from a couple
    typedefs.) This is a design decision that you'll have to make on your own.

    What may be more approriate for you, rather than using sets nested
    within a map, is to use a multimap. This is like a map, but every int
    key can be associated with multiple int values, obviating the need for
    set (unless it's important to you that the values in the set be sorted).
    This also simplifies the return type issue since there's only one
    type of iter and a unique end() iter to indicate a value not found. Look
    at the SGI STL documentation for details of the multimap.

    -Mark
     
    Mark P, Apr 3, 2005
    #4
    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. Tony Young
    Replies:
    4
    Views:
    846
    Mark P
    Apr 9, 2005
  2. Skybuck Flying

    ints ints ints and ints

    Skybuck Flying, Jul 8, 2004, in forum: C Programming
    Replies:
    24
    Views:
    870
    Jack Klein
    Jul 10, 2004
  3. wolverine
    Replies:
    3
    Views:
    1,113
    Chris
    Jul 31, 2006
  4. Vikram Karandikar
    Replies:
    1
    Views:
    234
    Vikram Karandikar
    Oct 25, 2013
  5. Jim Anderson

    problem with iterator (map iterator)

    Jim Anderson, Jan 10, 2014, in forum: C++
    Replies:
    3
    Views:
    159
    Luca Risolia
    Jan 13, 2014
Loading...

Share This Page