QVector::remove(int i, int count) performance when removing from the first

Question

I want to use a QVector like a queue. That's because i want to access a raw pointer to data in vector and QVector puts data contiguously. So i append data in my QVector in a thread and in another thread read count elements from the first and remove them.

When you remove from the middle of a QVector the data is rearranged and many copies take place. I want to know whether data is copied when removing count elements from the begging of QVector or it have little overhead? Is there any better method for doing this?

Answer 1

You can use this class to check QVector::remove performance:

#include <QDebug>

class Dummy
{
public:
    Dummy()
    {
        qDebug() << "dummy ctor" << ++c1;
    }

    Dummy(const Dummy &d)
    {
        qDebug() << "dummy copy ctor" << ++c2;
    }

    Dummy &operator=(const Dummy &d)
    {
        qDebug() << "dummy asign" << ++c3;
    }

    static int c1, c2, c3;
};

int Dummy::c1 = 0;
int Dummy::c2 = 0;
int Dummy::c3 = 0;

The test itself:

int main(int argc, char *argv[])
{
    QVector<Dummy> v;

    for (int i = 0; i < 100; ++i)
    {
        v.append(Dummy());
    }

    qDebug() << "adding finished";

    v.remove(0);
    v.remove(v.size() - 1);

    qDebug() << "end";

        return 0;
}

In this example Dummy assign operator is called 99 times when you remove the first element, and it's not called at all when you remove the last one.

Anyway, I suppose you have some design problems if you need to access container raw data. As JKSH said in comments, you can dynamically allocate memory for you data elements and then put those pointers into a container.

Answer 2

The problem is that you are looking for a data structure where the data is stored contiguously and, at the same time, you need to rearrange the data (i.e. remove element from the front). Unless you are removing all the elements in the vector, this operation will always require moving data to keep the vector contiguous.

One approach I can suggest to optimize the performance of your design (other than using lists instead of vectors and giving up on access-by-pointer) is to write a custom vector where removing the first element simply increments the front pointer and does not rearrange the data. This will have the same effect as removing the first element, but without the performance penalty. You will also have to implement a cleanup routine that will compact the vector once a certain threshold of removed elements is reached, but you can control when this cleanup is executed rather than having it execute on every removal from the queue.