std::map question.

I have the following class that basically just holds a texture handle, and manages the memory of the texture.

Code:

---

#ifndef XTEXTURE_H
#define XTEXTURE_H

#include <hge.h>

namespace Varia
{
    class Texture
    {
    public:
        Texture():mTexture(0)
        {
            mHge = hgeCreate(HGE_VERSION);
        };
        ~Texture()
        {
            if ( mTexture != 0 )
                mHge->Texture_Free(mTexture);
            //Release the HGE pointer
            mHge->Release();
        };

        //This will not allow you to overwrite the existing texture
        HTEXTURE CreateTexture(const char* filename, bool mipmap)
        {
            if ( mHge != NULL )
            {
                if (mTexture!=NULL)
                    return (mTexture);

                mTexture = mHge->Texture_Load(filename,0,mipmap);
                return (mTexture);
            }
            return 0;
        };

        HTEXTURE  DeleteTexture()
        {
            if ( mHge != NULL )
            {
                mHge->Texture_Free(mTexture);
                (mTexture=0);
            }
        };

        HTEXTURE GetTexture()
        {
            return (mTexture);
        };

    private:
        HGE* mHge;
        HTEXTURE mTexture;
    };
};

#endif//XTEXTURE_H

---

I also have two other classes that are capable of holding data. One is a template class for internal stuff (user can't modify), and one that contains std::maps that I hope will allow me to implement my script system more easily.
Really it is just a question of speed in indirection. Also if indirection is worth all the extra code required.
basicly I have either

Code:

---

std::map<size_t, Varia::Texture> mTextures;
//Or
std::map<size_t, Varia::Texture*> mTextures;

---

I want to use std::map, but I hear that it is substantially slower than std::vector(although with map you don't have to manage the indexes).

Thank you greatly for any assistance.

Quote:

---

Originally Posted by Raigne

I want to use std::map, but I hear that it is substantially slower than std::vector(although with map you don't have to manage the indexes).

---

If you think a linear search through a vector is going to be more efficient than a logarithmic search in a map, then you have quite a bit of studying to do...

Instead of hypothesizing some imaginary performance problems, just write it the way that makes the most sense and see if it's fast enough. If not, you might consider specific optimizations. The difference in performance between holding objects and holding pointers to objects is going to be dwarfed by the time needed to traverse the map or vector, in any case.

Thank you brewbuck, but still I am going to make the assumption that at any given time, the size of these map and/or vectors will not exceed 100, so the searching I don't think will matter anyhow. I am more looking for access time.

Quote:

---

Originally Posted by Raigne

Thank you brewbuck, but still I am going to make the assumption that at any given time, the size of these map and/or vectors will not exceed 100, so the searching I don't think will matter anyhow. I am more looking for access time.

---

I still think you are imagining the problem. Try it with the map, and if things are slow, profile it. The containers are not usually the problem.

What does the key to the maps represent? Are they numbers that start from 0 and always increment by 1? Do they jump around randomly? Will you be filling your map once, then accessing it many times without inserting or deleting?

I agree with brewbuck, this is probably not going to be a problem. However, if the key is just a number starting 0 or 1 that goes up sequentially, then a vector probably makes sense. If the numbers are sparsely populated within a range, then maybe not.

Another common solution for sparsely populated numbers if you insert them all once in the beginning is to add them to the vector then sort, and when you want to access an element use binary_search. However, that will still be logarithmic lookup time, and will only potentially optimize the constant factors.

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.

>> I would recommend against using std::map, at least under MS STL.

I use std::map from the MS standard library all the time and it works great.

There were issues with older versions of the library (like the one for VC++ 6.0 and the one called SXL), but those are so old you probably shouldn't be using them anyway.

There's no reason to switch to a custom container unless you are working in an area that has very specific functional and performance requirements that aren't met by the standard containers. In the case of a key/value pairing, a map is the logical choice, and only in some instances (like those I mentioned) does it make sense to use something else.

BTW, Bubba, have you looked at using std::tr1::array in your custom container? It is like vector but is a fixed size array specified at compile time and so it has performance advantages of statically sized arrays over dynamic ones.

Quote:

---

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.