C++ STL Multimap issue

[scootermaster]

So here's the situation:

*** if you're interested ***
I'm dealing with a dataflow graph, and I'm building a map of symbols (of the form symbolName => graphNodeNumber). I use a multimap because there can multiple entries of the same symbol in the map. So when I encounter a new symbol, I want to check the map, see if it exists, if it doesn't, add it (actually, I add it regardless) and then manipulate the previous entries in the map (i.e. I use the symbolName to get access to the other nodes in the graph that have that symbol, and then manipulate those nodes).
*** /if you're interested ***

So here's the question: technically, I only need to edit the "last" node I saw, assuming that the multimap entry returns the "last" one entered. Ya dig? So, it'd go like this:

1. See symbol "a" at node 4. Search map, return null. Add to map (entry 1)
2. See symbol "a" at node 5. Search map, return entry 1. Edit entry 1. Add to map (entry 2).
3. See symbol "a" at node 8. Search map, return entry 2. Edit entry 2. Add to map (entry 3).
etc
etc

Otherwise, I need to return an iterator (or, actually, 2 iterators) with a range of entries, and then edit them all. Or, actually, I'll only need to edit one of them, but I'm not sure which one it'll be that I'll need to edit.

So can I just use a find operation on the multimap and it'll give me the one I want?

Any other datastructures I should be using? I do know there's a million ways to do this.

 

[iCyborg]

find() will return an iterator to the first key in the map, and because the multimap is sorted, the others with the same value will follow, and you can just ++ the iterator to track them all down. so I think multimap is a good choice, but I'm not sure I understand completely your problem, what does "seeing" a symbol mean, what are you editing etc...

 

[scootermaster]

Originally posted by: iCyborg
find() will return an iterator to the first key in the map, and because the multimap is sorted, the others with the same value will follow, and you can just ++ the iterator to track them all down. so I think multimap is a good choice, but I'm not sure I understand completely your problem, what does "seeing" a symbol mean, what are you editing etc...

Thanks for the reply. Yeah, it's kind of confusing. I'm building a Dataflow graph from a flattened abstract syntax tree. So, pretty much what this means is every time I have a store (i.e. a write, or an l-value) I need to make sure that all the other nodes in the graph that correspond to the same symbol are flagged as a) no longer being live, and b) as no longer being outputs to the graph.

The thing is, I don't really need to do this for "all" of them. I just need to do it to the "last" one, as long as there's some ordering when they're added/retrieved. Does that make sense? As long as I mark the last node dead, and not an output, each time I encounter the symbol again, it'll work. (The point maybe I didn't mention here is that only one node corresponding to a symbol can be live, and therefore an output).

So it'd seem to me to be a shame to have to look at each of the matching nodes, when in reality it's only one that I need to deal with. It's not the end of the world though. Marking the other nodes as dead/non output over and over isn't going to hurt any thing, it's just a waste of time.

 

[iCyborg]

I see. The elements are only sorted according to the keys, so I don't think you can avoid looking at all of them (with the same key) in the worst case. You can use equal_range() to get the first and the one beyond last. The iterators are bidirectional so you can get the last one, but I don't think there's any guarantee that insertion will put the new pair at some particular place (like first or last) among the ones having the same key.

You could always write your own container similar to multimap where you would always order the key-value pairs the way you like, say always putting the 'live' nodes in front of all dead ones, but unless you expect that you'll often have more than a couple of keys with the same value, I'd say it's not worth it.

 

[scootermaster]

Yeah I'll just use equal range, iterate through until I find one that's live, and tweak it. I'm guessing it'll end up being the first one, but I'd rather not chance it (the graph itself is built bottom up...or, actually, sort of inside out, and since it's recursive it's hard to tell what happens before what, so it's best not to chance it).

Thanks for the help.