Speed of <queue> and <vector>

This is a discussion on Speed of <queue> and <vector> within the C++ Programming forums, part of the General Programming Boards category; How is the speed of the queue and vector C++ classes compared to a normal C type class such as ...

  1. #1
    Registered User
    Join Date
    Mar 2007
    Posts
    416

    Speed of <queue> and <vector>

    How is the speed of the queue and vector C++ classes compared to a normal C type class such as a linked list or C style array. I made a couple typedef's for 3 dimensional arrays and later switched to a class with vectors of size 3 and realized the performance went way down. Is there a way to speed things up in the class by using the original typedef vec3 instead of using vectors? I tried replacing the vector with vec3 but the system fails to run and crashes, and I can't seem to find a way to manage the memory so it does not crash. I deleted and allocated the memory on almost every function, yet it still hits snags.

    Code:
    typedef float vec2[2]; //2 point vector
    typedef float vec3[3]; //3 point vector
    
    
    class Vec3{
        private:
            vector<GLfloat> vect3;
        public:
            Vec3();
            Vec3(double, double, double);
            ~Vec3();
    
            double* d_array();
            GLdouble* GLd_array();
            GLfloat* GLf_array();
            void Unit();
    
            friend Vec3 operator + (Vec3 a, Vec3 b)
            {
                Vec3 ret;
                ret.vect3[0] = a.vect3[0] + b.vect3[0];
                ret.vect3[1] = a.vect3[1] + b.vect3[1];
                ret.vect3[2] = a.vect3[2] + b.vect3[2];
    
                return ret;
            }
    
            friend Vec3 operator * (Vec3 a, double b)
            {
                Vec3 ret;
                ret.vect3[0] = a.vect3[0] * b;
                ret.vect3[1] = a.vect3[1] * b;
                ret.vect3[2] = a.vect3[2] * b;
    
                return ret;
            }
    
            Vec3 operator = (vec3 a)
            {
                vect3[0] = a[0];
                vect3[1] = a[1];
                vect3[2] = a[2];
                return *this;
            }
    
            Vec3 operator = (double* a)
            {
                vect3[0] = a[0];
                vect3[1] = a[1];
                vect3[2] = a[2];
                return *this;
            }
            
            GLfloat& operator [] (const int a)
            {
                return vect3[a];
            }
            
            GLfloat operator [] (const int a) const
            {
                return vect3[a];
            }
    
            friend Vec3 operator / (Vec3 a, double b)
            {
                Vec3 ret;
                ret.vect3[0] = a.vect3[0] / b;
                ret.vect3[1] = a.vect3[1] / b;
                ret.vect3[2] = a.vect3[2] / b;
    
                return ret;
    
            }
    
            friend Vec3 operator - (Vec3 a, Vec3 b)
            {
                Vec3 ret;
                ret.vect3[0] = a.vect3[0] - b.vect3[0];
                ret.vect3[1] = a.vect3[1] - b.vect3[1];
                ret.vect3[2] = a.vect3[2] - b.vect3[2];
    
                return ret;
            }
    
            friend Vec3 operator * (Vec3 a, Vec3 b)
            {
                Vec3 ret;
                ret.vect3[0] = a.vect3[0] * b.vect3[0];
                ret.vect3[1] = a.vect3[1] * b.vect3[1];
                ret.vect3[2] = a.vect3[2] * b.vect3[2];
    
                return ret;
            }
    
            friend Vec3 operator / (Vec3 a, Vec3 b)
            {
                Vec3 ret;
                ret.vect3[0] = a.vect3[0] / b.vect3[0];
                ret.vect3[1] = a.vect3[1] / b.vect3[1];
                ret.vect3[2] = a.vect3[2] / b.vect3[2];
    
                return ret;
            }
    
            //this is the same as the cross product
            friend Vec3 operator ^ (Vec3 a, Vec3 b)
            {
                Vec3 ret;
                ret.vect3[0] = a.vect3[1]*b.vect3[2] - a.vect3[2]*b.vect3[1];
                ret.vect3[1] = a.vect3[2]*b.vect3[0] - a.vect3[0]*b.vect3[2];
                ret.vect3[2] = a.vect3[0]*b.vect3[1] - a.vect3[1]*b.vect3[0];
    
                return ret;
            }
    };
    
    Vec3::Vec3(){
        vect3.resize(3); //allocate space for 3 elements
        return;
    }
    
    Vec3::Vec3(double x, double y, double z){
        vect3.resize(3); //allocate space for 3 elements
        vect3[0] = x;
        vect3[1] = y;
        vect3[2] = z;
        return;
    }
    
    Vec3::~Vec3(){
        vect3.clear();
    }
    
    double* Vec3::d_array(){
        double *ret = new double[3];
        ret[0] = (double)vect3[0];
        ret[1] = (double)vect3[1];
        ret[2] = (double)vect3[2];
        return ret;
    }
    
    GLdouble* Vec3::GLd_array(){
        GLdouble *ret = new GLdouble[3];
        ret[0] = (GLdouble)vect3[0];
        ret[1] = (GLdouble)vect3[1];
        ret[2] = (GLdouble)vect3[2];
        return ret;
    }
    
    GLfloat* Vec3::GLf_array(){
        GLfloat *ret = new GLfloat[3];
        ret[0] = vect3[0];
        ret[1] = vect3[1];
        ret[2] = vect3[2];
        return ret;
    }
    
    void Vec3::Unit(){
        float magn = sqrt(vect3[0]*vect3[0] + vect3[1]*vect3[1] + vect3[2]*vect3[2]);
        vect3[0] = vect3[0]*(1/magn);
        vect3[1] = vect3[1]*(1/magn);
        vect3[2] = vect3[2]*(1/magn);
    }

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I don't think data structures have a speed as such. What might be different is the complexity (and perhaps some constant overhead) of certain algorithms.

    When you want insertions in the middle, a linked list would be faster than an array or vector.
    When you want just traversal over it, anything contiguous should be faster than a linked list.
    When you want random access, a vector certainly would be faster than a linked list.
    Etc.

    Also a std::queue is a container adapter. You can pick which container to use (vector, list, deque).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,725
    Quote Originally Posted by scwizzo
    How is the speed of the queue and vector C++ classes compared to a normal C type class such as a linked list or C style array.
    The efficiency of std::queue will depend on the underlying container. The default is std::deque, which can be slower than std::vector for accesses by a constant factor. The efficiency for std::vector will be comparable to that of a C-style dynamically allocated array.

    Quote Originally Posted by scwizzo
    Is there a way to speed things up in the class by using the original typedef vec3 instead of using vectors?
    A std::tr1::array would be a better match for what you are trying to do, since you are fixed to having 3 elements in the array. However, the difference is likely to be marginal. What could be the source of your problem is if you are using a standard library implementation with checked iterators. For example, if you are using a Microsoft compiler, you could define _SCL_SECURE=0 to disable checked iterators (but this is only advisable for a release configuration, and you may face problems due to binary incompatibility).
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    However, looking at the implementation of your class, I wouldn't use dynamic allocation for 3 floats. Use a plain array of 3 GLfloats (or boost::array / tr1::array).

    Also, if you really want, you can template the vector on how many dimensions it has: Vec<2> vec2d, Vec<3> vec3d.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Some compilers like Visual Studio also have extra debug checking in their vectors, so you'd need to explicitly turn off the debug checking.
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  6. #6
    Registered User
    Join Date
    Mar 2007
    Posts
    416
    A lot of good information. Reason I was asking is I tried implementing a way to render all the objects I load (with OpenGL) with a single function. The function would loop through the objects loaded, rendering them one at a time. I noticed using queue was a lot slower in frames per second than using vector. I also noticed that switching my C-style array of float[3] to a vector<float> using resize(3) made a huge difference in the frames per second also (huge being 60-80 fps where the max before was 100 fps). After reading your comment laserlight about me having 3 fixed values I realized I could just define 3 double or float variables. That way there's no pointers, no dynamic allocation, and no vectors. The performance is about the same now using just the 3 variables instead of a 3 element C-array (which is a good thing).

    Another question, though. I get a warning upon compiling for these functions. Is there a better/more correct way to do this so there is no warning or so it follows better standards?

    Code:
    class Vec3{
        private:
            double x, y, z; //3 coordinate system
            
        public:
            Vec3();
            Vec3(double, double, double);
            ~Vec3();
    
            //the following 3 functions give the same warning
            double* d_array();
            GLdouble* GLd_array();
            GLfloat* GLf_array();
    
            void Normalize();
    
    //...rest of operator functions follow...
    };
    
    //the 3 functions are virtually the same, look at first post for other 2
    double* Vec3::d_array(){
        double ret[3];
        ret[0] = x;
        ret[1] = y;
        ret[2] = z;
        return ret;
    }
    
    warning: address of local variable `ret' returned

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,725
    Quote Originally Posted by scwizzo
    Another question, though. I get a warning upon compiling for these functions. Is there a better/more correct way to do this so there is no warning or so it follows better standards?
    The warning is pretty important: you are trying to return a pointer to a local variable, which means that the caller of the function would get a pointer that points to an object that no longer exists.

    Unfortunately, changing your implementation to have three separate variables makes a solution more difficult. I suggest that you re-consider your decision to provide these functions in the first place. Instead of trying to provide accessors to an array, perhaps you should provide accessors to the individual coordinate values.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    The optimal solution is to us a plain old array of 3 values. In this case a vector would use the same number of bytes on the stack just to track an even larger amount of space used fom the heap (considering minimum heap allocation size of 16 bytes on Windows).

    You could improve your code efficiency by passing instances of Vec3 by const-reference to function like operator + for example.

    The way you're using new, one can pretty much guarantee that your code has, or will have, memory leaks.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Class and <vector>
    By zenaphex in forum C++ Programming
    Replies: 3
    Last Post: 04-12-2004, 09:12 AM
  2. Shifting back <vector> items...
    By aker_y3k in forum C++ Programming
    Replies: 2
    Last Post: 09-16-2003, 10:30 AM
  3. Implementation of <vector> class
    By supaben34 in forum C++ Programming
    Replies: 4
    Last Post: 10-13-2002, 09:14 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21