STL map

Quote:

Original post by tneva82 Found out this rather nifty container and now I'm wondering wether I should switch from vector to this. Problem: I need access to creature based on creatures ID. Creatures get added and deleted a lot. There could potentially be thousands of of creatures.

Maps are a natural way to handle this sort of thing, if you don't mind removing the ID from the Creature structure. Otherwise you duplicate the data. An alternative, if you want to leave the ID in the Creature for some reason, is to use std::set with a custom comparator. The resulting code can get a little tricky/subtle, though.

Quote:

First I thought I would sort vector with STL-algorithm after creating(and deleting) all the creatures that are going to be created/deleted and when needing creature with ID of x some search algorithm that takes advantage of the fact list is sorted so that smallest ID is first and largest last gives me right vector index. Should be faster than looping through all the creatures every time I need certain creature right?

Yes. The standard library (BTW, please don't say "STL"; that hasn't been a relevant term for many years) provides that algorithm, too: check out std::binary_search and std::lower_bound/upper_bound.

Quote:

However since that requires sort everytime creatures are added(atleast this can be done once per logic round)

Not if you're smart about how you generate IDs. :)

Quote:

plus search everytime

Not if you just want to process every Creature in turn. How often do you really need to refer to a specific Creature by its ID? Are you really even sure you need to assign IDs to Creatures? If you are, you should have no problem explaining to me why? :)

Quote:

I wondered wasn't there alternative way and came upon map. Don't know how it's implemented

Wikipedia has a good article on that.

Quote:

but would this be faster(or atleast not meaningfully slower) than STL sort+some sort of search algorithm(binary is current thinking unless I find even better)?

It will be on the same order of complexity for most operations. It will be faster in the order of complexity sense for inserting new elements (because inserting into the middle of a std::vector requires shifting down every element past the insertion point). Constant factor-wise, you can probably expect it to be on the order of 2-4 times slower. Usually this doesn't matter very much.

Quote:

And I could do it like: map myCreatures; And then do like map[myCreature.getId()]=myCreature; right? (assuming myCreature is valid object of course)

Yes; but see above about duplicating information.

Quote:

Anything else I would need to know? I would like to know potential pitfalls before switching from vectors to maps for everything that needs something like this.

Maps don't store things sequentially in memory (that's actually unique to vector, out of the standard library containers), and thus don't provide random-access iterators. A map's iterators iterate over key-value pairs. You are not allowed to change the 'key' part, even through a non-const iterator, although this isn't (AFAIK) enforceable by the compiler - it just blows everything up at runtime (because the map has no way to know about your changes and take things into account). If you want to change a creature's ID, remove it from the map first and then reinsert it with the new ID.

Quote:

Original post by Zahlman Maps are a natural way to handle this sort of thing, if you don't mind removing the ID from the Creature structure. Otherwise you duplicate the data.

Can you get the id from the map then if you need to send the ID forward?

Say I have creature with ID x. Player A attacks creature with that id. I use map to get access to creature so I can reduce hitpoints. Creature dies. Now I need to send every player who cares about this(players on the other side of the world for example hardly have need to know about this ;-) gets notified that creature with id 'x' died. Can I pull that x from the map? Ie reverse-map. I have the creature, now I need to find out id.

It's just one int. Yeah might be wasted memory a bit but that shouldn't kill me if it results in cleaner&faster code(I rather sacrifice memory than speed).

Quote:

Not if you just want to process every Creature in turn. How often do you really need to refer to a specific Creature by its ID? Are you really even sure you need to assign IDs to Creatures? If you are, you should have no problem explaining to me why? :)

If you don't have ID how you are going to point which creature creature X interacts with? Attacks, Gives items, checks stats or something etc. Not just within this program but through network. Client A sends "I want to attack this creature". What other ways server has to know which specific creature client A wants to attack if not for ID? Preferably something that is quick to send via network. So storing pointer to target creature isn't for example going to work. Pointers don't really move around well across network...Plus I would like to reduce number of pointers in use. Not increase it ;-)

Maybe there's some fancy way to do that but ID is only one I have figured out.

Quote:

If you want to change a creature's ID, remove it from the map first and then reinsert it with the new ID.

Well I don't see why creatures ID would need to change. You create it when creature is born and then that's how you are identified with.