Thread: std::map question.

I would recommend against using std::map, at least under MS STL. There is a lot going on in std::map and it's not as straightforward as one might think. With a vector there is minimal lookup time if you code it correctly because you can use the array access operator to get to your data. Out of all the containers in the MS STL the only few that I can actually bear to suggest are the different queues, stack, and vector.

However if you insert a lot and/or remove a lot a vector is not what you want. To gain the exact functionality you want you will have to create a custom container that's either a mix of two STL containers or a collection of your own design. In general, I do not recommend using MS STL for any of your containers and would go with STL Port. Also if you are multi-threaded keep in mind that the more that happens inside the container the more of a window you are creating for things to go horribly wrong. I normally wrap all access to containers in critical sections. You must be extremely careful with any STL container a multi-threaded environment. MS STL containers are nearly impossible to debug and even a book from Microsoft Press urges people not to use it. It's very hard to debug your code when you can't even see what's in the container. MS IDE only shows the first element of an STL container. With map and list you can navigate your way to more objects but it's a pain. Also what Daved says is very true. You will not get efficient use of the map if you just dole out sequential ID's.

You will find that STL Port complemented with the nice boost shared pointers will give you some very nice containers. You still have to protect all access in a multi-threaded system but boost makes your life a lot easier.

I'm not against the STL and I use it but there is nothing keeping you from coding your own custom container to suit your specific needs in this instance. You may mix two STL containers or mix two other containers and create a container that is specific to what you need.

I have a templated container that may do exactly what you want. It uses an array and a stack, has constant lookup, constant removal, and constant insertion. The size of the collection does not affect removal or insertion and it does not invalidate indices upon removal. It has all the benefits of a std::vector including array access but does not suffer from the issues that vector does. The only downside of the container is that you must specify a size beforehand. You cannot just add and then expect it to resize. So you allocate it just like an array and then use it just like a vector from that point on.

Originally Posted by Bubba

You must be extremely careful with any STL container a multi-threaded environment. MS STL containers are nearly impossible to debug and even a book from Microsoft Press urges people not to use it. It's very hard to debug your code when you can't even see what's in the container. MS IDE only shows the first element of an STL container. With map and list you can navigate your way to more objects but it's a pain. Also what Daved says is very true. You will not get efficient use of the map if you just dole out sequential ID's.

That is no longer true. the IDE shows all elements of containers such as map just fine as of at least VS2008, and debugging is a piece of cake. Sure, giving out sequential IDs will always result in the most unbalanced tree possible, but that doesn't change its big O performance guarantees, and if it's enough difference to care about, you should probably be using a container that hashes instead anyway.

Also, just store objects in the map, not pointers. If you're worried about the overhead of copying the Texture object into the map, then simply provide a specialisation of std::swap that swaps the two member variables, and use swap(collection[index], myTexture);
Then you can happily have an assignment operator that deep copies.