Sign in to follow this  
Gumgo

Multimap .first, .second?

Recommended Posts

I was looking at this tutorial on multimaps and I noticed that near the bottom, there is this:
cout << (*it).first << " => " << (*it).second << endl;
Where it is an iterator. But where is this .first and .second coming from? I don't see it anywhere if I push ctrl+space in VC++, but the strange thing is it seems to work. I think that it get the "key" and "value" from the map but I can't be sure. I'm storing a pointer as the value in a multimap, and when I do this:
(*iter).second->Update();
It runs the "Update" function in the object. But if I do this:
if ((*iter).second)
{
...
It always seems to return true (I'm trying to check if the pointer is valid). I can't seem to find anything in the tutorial actually defining the "second" function, or telling why it is there or where it is "from". I can't find it in other tutorials either. What is this about? What could I use to check if an iterator in a multimap "points" to a valid pointer (if that makes sense)? Thanks

Share this post


Link to post
Share on other sites
Map/Multimap are actally sets/multisets of std::pair, keyed off of the first element.


std::pair<int, int> intPair(3, 4);
int x = intPair.first; // 3
int y = intPair.second; // 4


So when you iterate over them, you can refer to
iter->first
(the key) and
iter->second
(the value).

Share this post


Link to post
Share on other sites
map and multimap store objects of type std::pair<KeyType,ValueType>. std::pair is a simple aggregate that exposes two member fields: first and second. In the given context, first is the key and second is the value (a pointer in your case).

'(*iter).second' should evaluate to false if the specified pointer is null. If this doesn't seem to be working, you might try displaying the value of the pointer before testing it for nullity (maybe the pointers you think are null are not actually null).

Also, I personally find it->first to be a little easier to read than (*it).first, but that's just personal preference.

Share this post


Link to post
Share on other sites
Thanks for clarifying. Now that I know what they do I'll probably be able to figure out what is wrong.

EDIT: This doesn't seem to work...

if (iter->second)

It always returns true, even if I deleted the object that the pointer points to.

[Edited by - Gumgo on May 4, 2007 10:44:42 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Replicon
I don't believe 'delete' is required to assign NULL, so if(iter->second) would still point at the (now free) memory1.


Okay I believe it might even be explicitly required not to by the standard -- I certainly know of no implementation that does assign a pointer to NULL. Note that such a change would only affect one copy of the pointer -- and if you've only got one pointer, one has to wonder why you were using pointers in the first place. An object that has been deleted and a pointer which points at nothing (e.g. "point at NULL") are unrelated, orthogonal concepts.

Gumgo: Your noteworthy options are:

1) NULL the pointer yourself.
2) Remove the entry from the multimap.
3) Use a boost::weak_ptr (in conjunction with boost::smart_ptr).


[1] Terminology: This is known as a "dangling pointer".

Share this post


Link to post
Share on other sites
I think I know what I'm going to do then in this case. Rather than delete the object, I'm going to set a variable in the object (maybe "DELETE_ME") that gets set when I want to delete it. Then, all the containers that have a pointer to that object will detect if DELETE_ME is true and if so, rather than updating the object, it will be removed from the container (I have several different containers). Then after all the updating has been done, I'll run another function to "clean up", which will delete all objects with DELETE_ME set to true.

That sound like it will work? :)

EDIT: Hehe, just noticed that "DELETE_ME" is actually taken...

Aaargh! This is getting really irritating! I can't get ANY of this to work!


if ((iter->second)->DEL_ME == true)


iter is an iterator in a multimap. The multimap contains objects with the variable DEL_ME. This keeps returning an exception!

What I'm confused about is how do you access the FUNCTIONS and VARIABLES of an object using an iterator.

[Edited by - Gumgo on May 5, 2007 3:33:12 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Gumgo
That sound like it will work? :)

As long as you keep one pointer of the object around to do the actual delete with somewhere.

Quote:

if ((iter->second)->DEL_ME == true)


iter is an iterator in a multimap. The multimap contains objects with the variable DEL_ME. This keeps returning an exception!

What I'm confused about is how do you access the FUNCTIONS and VARIABLES of an object using an iterator.


... You're accessing the variable in that above snippet just fine, syntaxically. For that to have problems, either:

1) iter is an invalid iterator
2) iter->second is an invalid pointer

Note that removing elements from containers typically invalidates iterators (not necessairly just the ones that reference the object(s) removed, although I think that may be the case for multimap at least). Dangling pointers (as mentioned earlier) are also, of course, invalid.

In conclusion: Paste more source code. And pasting exact error messages never hurts either.

Share this post


Link to post
Share on other sites
Quote:
Hehe, just noticed that "DELETE_ME" is actually taken...
By whom? Also, why all caps?
Quote:

if ((iter->second)->DEL_ME == true)
There's no need to compare to true here. Just write:
if (iter->second->DEL_ME)
Quote:
iter is an iterator in a multimap. The multimap contains objects with the variable DEL_ME. This keeps returning an exception!
You'll need to be more specific about the errors you're encountering. If you mean an exception is being thrown, then you need to post the message (if any) associated with the exception, and/or its type (if you know it). If it's an assertion failure, show the actual code that fails. If it's a compile-time error, post the error message along with the code that generates it. If your program is crashing, use the debugger to find out where and why. If it's simply not behaving correctly, describe the incorrect behavior and post the relevant code. And so on.
Quote:
What I'm confused about is how do you access the FUNCTIONS and VARIABLES of an object using an iterator.
If the value type of your map is a pointer, then:
iter->second->my_function_or_variable
Is correct.

As for your 'delete me' flag, it's probably not a good idea (at least not as you described it). It's very brittle, and will likely lead to dangling pointers and various other unpleasantries.

An appropriate solution will most likely involve using smart pointers in some way, as mentioned previously. If you want more specific feedback, you may need to provide more information (such as why it's necessary to store the same object in multiple containers, and what these various containers are used for).

Share this post


Link to post
Share on other sites
Sorry. I seem to have a problem with not providing enough code...

Quote:

By whom? Also, why all caps?

I'm not sure, but I just noticed that it was on the list when I hit "ctrl+shift" already (#define DELETE_ME). But that isn't important cause I changed it.

Anyways, the reason of doing this is because I want to delete objects only when they are removed from ALL loops that may need to access them (or have a pointer to them). There is a render loop and updating loop, and if I delete one from the updating loop and delete the pointer to it from the loop as well, the pointer in the render loop may point to something different by the time it comes along.

Anyways, here's the code:

class ObjectClass
{
public:
bool DEL_ME;
int depth;
virtual void Update() = 0; // abstract base
virtual void Draw() = 0; // abstract base
};

...

class GameLoopClass
{
public:
DWORD ObjectNumber; // don't bother telling me to just check the size of the multimap, I'll delete this (it was from something from before)
std::multimap<int, ObjectClass*> ObjHolder; // int = depth
GameLoopClass();
void AddObj( ObjectClass * object );
void Update();
};

...

GameLoopClass::GameLoopClass()
{
ObjectNumber = 0; // yes I know it is pointless I'll take it out
}

void GameLoopClass::AddObj( ObjectClass * object )
{
ObjHolder.insert( std::pair<int, ObjectClass*>( object->depth, object ) );
ObjectNumber++;
}

void GameLoopClass::Update()
{
std::multimap<int, ObjectClass*>::iterator iter;
for (iter = ObjHolder.begin(); iter != ObjHolder.end(); iter++)
{
if (iter->second->DEL_ME != true)
iter->second->Update();
}
// reason for two loops is that I want all the updating to happen
// and then I want to get rid of the pointers. The reason is,
// say I had OBJECT1 get updated. Then OBJECT2 gets updated, and in
// its updated code, it sets DEL_ME to true for OBJECT1. OBJECT1 would
// have already been updated but would have been set to be deleted
// AFTER that, and the pointer to it would not be deleted from the
// multimap
for (iter = ObjHolder.begin(); iter != ObjHolder.end();)
{
if (iter->second->DEL_ME)
{
ObjHolder.erase( iter );
ObjectNumber--; // one less object
}
else
iter++;
}
}




There is my complete code (it is very similar in the Render loop, and also the "clean up" loop that I run afterwards to actually delete the objects.

Share this post


Link to post
Share on other sites
In your last for loop, you need to have
		if (iter->second->DEL_ME)
{
iter = ObjHolder.erase( iter );
ObjectNumber--; // one less object
}
else
iter++;
Note that when the element is erased, a new iterator is returned. The old iterator has been invalidated. If you try to use this old iterator, you'll only end up having problems of one sort or another. This may be the problem you're currently experiencing.

Share this post


Link to post
Share on other sites
Quote:
Original post by MaulingMonkey
Quote:
Original post by Replicon
I don't believe 'delete' is required to assign NULL, so if(iter->second) would still point at the (now free) memory1.


I believe it might even be explicitly required not to by the standard -- I certainly know of no implementation that does assign a pointer to NULL. Note that such a change would only affect one copy of the pointer -- and if you've only got one pointer, one has to wonder why you were using pointers in the first place. An object that has been deleted and a pointer which points at nothing (e.g. "point at NULL") are unrelated, orthogonal concepts.


I think it's explicitly allowed to assign NULL to the pointer (provided it is an lvalue) - I think I read a quote from Stroustrup saying he was very disappointed that nobody has chosen to implement this.

Share this post


Link to post
Share on other sites
Quote:

Note that when the element is erased, a new iterator is returned. The old iterator has been invalidated. If you try to use this old iterator, you'll only end up having problems of one sort or another. This may be the problem you're currently experiencing.


Yay! That fixed everything! Seems to work fine now. Thanks for all your help. MaulingMonkey, you're right, you did mention that earlier but I wasn't sure what you meant by it (didn't know that the iterator became invalid).

Again thanks for all your help.

Share this post


Link to post
Share on other sites
Quote:
Original post by Agony
In your last for loop, you need to have*** Source Snippet Removed ***Note that when the element is erased, a new iterator is returned. The old iterator has been invalidated. If you try to use this old iterator, you'll only end up having problems of one sort or another. This may be the problem you're currently experiencing.

No. None of the standard erase mechanisms on associative containers return iterators. Since I'll assume he's using VS2k5EE, his standard library implementation does, but it's a non-standard extension. mymap.erase(it++); would work however.

Share this post


Link to post
Share on other sites
Quote:
Original post by ZQJ
Quote:
Original post by MaulingMonkey
Quote:
Original post by Replicon
I don't believe 'delete' is required to assign NULL, so if(iter->second) would still point at the (now free) memory1.


I believe it might even be explicitly required not to by the standard -- I certainly know of no implementation that does assign a pointer to NULL. Note that such a change would only affect one copy of the pointer -- and if you've only got one pointer, one has to wonder why you were using pointers in the first place. An object that has been deleted and a pointer which points at nothing (e.g. "point at NULL") are unrelated, orthogonal concepts.


I think it's explicitly allowed to assign NULL to the pointer (provided it is an lvalue) - I think I read a quote from Stroustrup saying he was very disappointed that nobody has chosen to implement this.


Hmm Now that you mention it, I vaugely remember a quote to that effect too. A quick google turns up this:

Quote:
From http://www.research.att.com/~bs/bs_faq2.html#delete-zero:

C++ explicitly allows an implementation of delete to zero out an lvalue operand, and I had hoped that implementations would do that, but that idea doesn't seem to have become popular with implementers.

(where http://www.research.att.com/~bs/ is of course Bjarne Stroustrup's website)

Quote:
From #gamedev:

<Washu> MaulingMonkey: [Note: the value of a pointer that refers to deallocated storage is indeterminate.]
<Washu> furthermore, multimap does not have an erase operation that returns an iterator.


Microsoft's implementation of multimap does provide one IIRC (which would be confirmed if the original snippet from Agony works), but to avoid depending on this extension to the standard library and stick to the standard... standard library... you'll want:

if (iter->second->DEL_ME) {
temp = iter++;
ObjHolder.erase( temp );
ObjectNumber--; // one less object
} else {
++iter;
}


Note: The iterator increment must come before the erase, so we can't just move that out of the conditional)

Share this post


Link to post
Share on other sites
Quote:
Original post by Washu
Quote:
Original post by Agony
In your last for loop, you need to have*** Source Snippet Removed ***Note that when the element is erased, a new iterator is returned. The old iterator has been invalidated. If you try to use this old iterator, you'll only end up having problems of one sort or another. This may be the problem you're currently experiencing.

No. None of the standard erase mechanisms on associative containers return iterators. Since I'll assume he's using VS2k5EE, his standard library implementation does, but it's a non-standard extension. mymap.erase(it++); would work however.

Oh. I see. I'm actually rather surprised. Do you know if this is something that is likely to change in the next standard? Because it seems like a rather useful and obvious thing to include. Is there some negative side of this that I'm not seeing? Or just the cost of returning a value? Even for associative containers, the elements have a particular ordering (how else would iterators work), so every eraseable iterator is guaranteed to have another iterator after it. Why are associative containers treated differently in this regard? To discourage linearly iterating over them?

Share this post


Link to post
Share on other sites
Quote:
Original post by Agony
Quote:
Original post by Washu
Quote:
Original post by Agony
In your last for loop, you need to have*** Source Snippet Removed ***Note that when the element is erased, a new iterator is returned. The old iterator has been invalidated. If you try to use this old iterator, you'll only end up having problems of one sort or another. This may be the problem you're currently experiencing.

No. None of the standard erase mechanisms on associative containers return iterators. Since I'll assume he's using VS2k5EE, his standard library implementation does, but it's a non-standard extension. mymap.erase(it++); would work however.

Oh. I see. I'm actually rather surprised. Do you know if this is something that is likely to change in the next standard? Because it seems like a rather useful and obvious thing to include. Is there some negative side of this that I'm not seeing? Or just the cost of returning a value? Even for associative containers, the elements have a particular ordering (how else would iterators work), so every eraseable iterator is guaranteed to have another iterator after it. Why are associative containers treated differently in this regard? To discourage linearly iterating over them?

Actually, unordered containers are likely to have their iterator return type removed as well (it's an active defect report). The reason being: cont.erase(it); is supposed to run in ammortized constant time. Requiring a return iterator actually makes it logarithmic (think tree traversal for an example). Unordered containers, like unordered_map, will also likely have their return types on erase(it) changed to void as well, since it also changes the ammortized time to be logarithmic.

Share this post


Link to post
Share on other sites
Quote:
Original post by Washu
Actually, unordered containers are likely to have their iterator return type removed as well (it's an active defect report). The reason being: cont.erase(it); is supposed to run in ammortized constant time. Requiring a return iterator actually makes it logarithmic (think tree traversal for an example). Unordered containers, like unordered_map, will also likely have their return types on erase(it) changed to void as well, since it also changes the ammortized time to be logarithmic.


Not sure I follow. Why would an *unordered*_map need to do a tree traversal to create an iterator? Presumably it's using a hashing system of some sort? Although then I guess you have to linear-search the buckets to find the "next" iterator to return from .erase()... blech.

Anyway, seems you are correct about .erase(it++); we don't need a temporary (just pointing this out to MaulingMonkey ;) ) because the operator++ implicitly creates a copy (which is passed to .erase(), while the original has already been incremented). Although I guess we could also save to a temporary unconditionally, and then conditionally pass it to erase ;) And it seems to me that this actually lets us write a "normal" loop again - almost :)


typedef std::multimap<int, ObjectClass*> container;
for (container::iterator it = ObjHolder.begin(), it2 = ObjHolder.end();
it != ObjHolder.end(); it2 = it++) {
if (it2 == ObjHolder.end()) { continue; }
if (it2->second->DEL_ME) {
ObjHolder.erase(it2);
}
}


Although I really don't know that that's an improvement.

To the OP:

- You really should consider the object ownership more carefully.
- You really should think about why an object might be allowed to trigger the "death" of another object, and whether this is really necessary.
- Tagging a class name with "Class" really doesn't add any information. It's used as a type name, and it isn't built in to the language, so it could be a class, struct or typedef; but there isn't a reason that the person writing the code should *care* - what that person cares about, at the time of writing the code, is the *interface* provided.
- Once you get rid of the ObjectNumber business, you won't need a constructor for the GameLoop at all. :)
- Any base class defining virtual functions should have a virtual destructor as well. (The body can normally be empty, and you don't necessarily have to add any code to any derived classes - unless they require cleanup of specific things). Otherwise, you will have problems doing the deallocation (no matter "who" is responsible for it).
- It's probably cleaner to check DEL_ME from within Update(), rather than explicitly in the updating loop. That way, other code that needs to update individual objects (say you reuse them for another project that doesn't keep them in a GameLoop) can't possibly forget the check.




Also, why don't these associative containers provide const_iterators over keys, or iterators over values? That would bypass the messy "this is not a const_iterator but also not a Mutable Iterator" business.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Quote:
Original post by Washu
Actually, unordered containers are likely to have their iterator return type removed as well (it's an active defect report). The reason being: cont.erase(it); is supposed to run in ammortized constant time. Requiring a return iterator actually makes it logarithmic (think tree traversal for an example). Unordered containers, like unordered_map, will also likely have their return types on erase(it) changed to void as well, since it also changes the ammortized time to be logarithmic.


Not sure I follow. Why would an *unordered*_map need to do a tree traversal to create an iterator? Presumably it's using a hashing system of some sort? Although then I guess you have to linear-search the buckets to find the "next" iterator to return from .erase()... blech.

Because the next element may not be in the current bucket, you may end up requiring a traversal to the next bucket. See: N2023 for more information.
Quote:
Also, why don't these associative containers provide const_iterators over keys, or iterators over values? That would bypass the messy "this is not a const_iterator but also not a Mutable Iterator" business.

Because this is C++, not .NET [grin]. Also I should note that there is work on getting the associative erase member functions to return iterators. The amortized constant time is...well to quote them "Only 'amortized constant' in special circumstances, and we believe that's implementable. That is: doing this N times will be O(N), not O(log N)."

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Anyway, seems you are correct about .erase(it++); we don't need a temporary (just pointing this out to MaulingMonkey ;) ) because the operator++ implicitly creates a copy (which is passed to .erase(), while the original has already been incremented).


Stabby? Indeed (here, anyways). I actually wrote it that way the first goaround, but it was giving me the screaming heebie-jeebies -- and my instincts know better than to get into a sword fight with C++ over what could (for all I know) be undefined behavior. But as you point out, postfix operator++ is going to return a copy1 (which I knew -- leaving everything kosher there), and I can't think of any other reason to justify my paranoia.

[1] Ignoring monsterously mallicious abuse of expression templates at any rate

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this