Iterator Question for map of ints to set of ints

[uclamathguy]

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

[Mark P]

uc*********@gma il.com 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_p arameters_>::it erator and the
result of dereferencing such an iterator is
map<_template_p arameters_>::va lue_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.

[uclamathguy]

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<in t> >), 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>::i terator findValueInSet( int value,map<int,s et<int>

::iterator iter1,map<int,s et<int> >::iterator iter2)

{
while (iter1 != iter2)
{
if (((*iter1).seco nd).find(value) != ((*iter1).secon d).end())
break;
iter1++;
}

if (iter1 != iter2)
**** return ((*iter1).secon d); //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

[Mark P]

uc*********@gma il.com 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<in t> >), 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>::i terator findValueInSet( int value,map<int,s et<int>

::iterator iter1,map<int,s et<int> >::iterator iter2)

{
while (iter1 != iter2)
{
if (((*iter1).seco nd).find(value) != ((*iter1).secon d).end())
break;
iter1++;
}

if (iter1 != iter2)
**** return ((*iter1).secon d); //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>::itera tor 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(va lue)) != 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