Thread: 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);
}

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).

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.

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).

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.

Some compilers like Visual Studio also have extra debug checking in their vectors, so you'd need to explicitly turn off the debug checking.

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

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.

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.