Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Iterator Question for map of ints to set of ints

Reply
Thread Tools

Iterator Question for map of ints to set of ints

 
 
uclamathguy@gmail.com
Guest
Posts: n/a
 
      04-02-2005
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

 
Reply With Quote
 
 
 
 
Mark P
Guest
Posts: n/a
 
      04-02-2005
http://www.velocityreviews.com/forums/(E-Mail Removed) 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.
 
Reply With Quote
 
 
 
 
uclamathguy@gmail.com
Guest
Posts: n/a
 
      04-02-2005
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

 
Reply With Quote
 
Mark P
Guest
Posts: n/a
 
      04-03-2005
(E-Mail Removed) 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
will an iterator to a map becomes invalid when an element is inserted into the map wolverine C++ 3 07-31-2006 12:24 PM
Difference between Java iterator and iterator in Gang of Four Hendrik Maryns Java 18 12-22-2005 05:14 AM
How to loop in a vector (set, map, etc) from iterator i to iteratorj Tony Young C++ 4 04-09-2005 12:59 AM
ints ints ints and ints Skybuck Flying C Programming 24 07-10-2004 04:48 AM
Iterator doubts, Decision on Iterator usage greg C++ 6 07-17-2003 01:26 PM



Advertisments