STL vector performance

Question

STL vector class stores a copy of the object using copy constructor each time I call push_back. Wouldn't it slow down the program? I can have a custom linkedlist kind of class which deals with pointers to objects. Though it would not have some benefits of STL but still should be faster.

See this code below:

#include <vector>
#include <iostream>  
#include <cstring>

using namespace std;

class myclass
{
    public:
        char* text;

        myclass(const char* val)
        {
           text = new char[10]; 
           strcpy(text, val);
        }

        myclass(const myclass& v)
        {
            cout << "copy\n";
            //copy data
        }
};

int main()
{
    vector<myclass> list;
    myclass m1("first");
    myclass m2("second");

    cout << "adding first...";
    list.push_back(m1);

    cout << "adding second...";
    list.push_back(m2);

    cout << "returning...";
    myclass& ret1 = list.at(0);
    cout << ret1.text << endl;

    return 0;
}

its output comes out as:

adding first...copy
adding second...copy
copy

The output shows the copy constructor is called both times when adding and when retrieving the value even then. Does it have any effect on performance esp when we have larger objects?

Answer 1

You should choose a container that has the best performance characteristics for your use case. Your use case looks like you need to add items to the back of the container. With a vector, you will sometimes get reallocation and a performance hit unless you know in advance the maximum number of members and can afford to reserve in advance.

If instead you use a deque then you are guaranteed constant time insertion at the back (or front) of the container while still retaining useful features such as random access.

If you want something that is semantically a container of objects changing to a vector of pointers purely for performance reasons would not be my recommendation, indeed it may not be a performance gain as every object needs a separate memory allocation unlike using a container of objects where memory for multiple objects may be allocated in advance.

Answer 2

Copying objects can have unforseen side-effects. The reality is C++ classes are often not written to be copied and this could therefore cause errors... the idealist will argue "they should write their classes properly" but I prefer to deal in reality, it's not even going to be that rare this happens. Not to mention any logging your class does of creation/destruction is going to happen a lot.

Fundamentally it's not what the coder meant to happen, that a copy is made. That alone means it's a bad plan for non-trivial types. For simple cases it's fine (say a Point2D class) but be careful and in general if the class is not carrying a small amount of data, store pointers (or use smart pointers).

Answer 3

You may not believe it, but the vector (and better still the deque) are the fastest containers the STL has to offer for most tasks.

You may worry about copying your object, but unless it extremely huge or the Copy Constructor is somewhat complex, it costs less to copy the object that allocating it on the heap.

Heap allocation and the result cache misses are much more of a penalty than a simple copy.

But let's not frolick in idle talk: benchmark your container against the vector and see which comes on top, and by which order of magnitude, I bet you'll be surprised.

And if really your class is huge or prohibitive to copy, there is always boost::ptr_vector, though unless you use a pool you're obviously throwing cache locality by the window ;)

Answer 4

Something the other posters haven't mentioned is that you can use vector::reserve to preallocate the region of memory for the vector if you have an idea how many elements are needed in your vector. This should speed things up especially if you're using push_back to store objects by value because the vector class won't have to keep reallocating a new contiguous block of memory when it hits whatever the capacity limit within the loop.

Answer 5

On the note of C++0x, std::vector and friends will get emplace_back() which will place an element in place to the end of the vector.

http://msdn.microsoft.com/en-us/library/dd647620.aspx

Answer 6

Unless you are storing basic types, it is recommended to use pointers as your vector elements instead of the actual objects themselves. And in many cases, better use smart pointers instead.
Copy ctor would still be called - not that of your class, but of the smart pointer class.

Answer 7

It all depends on how large your object is.. But I'd say for most of the time it's better to use value semantics (copy the whole objects) and it should be performant enough. It saves you from having to think about memory management associated with pointers.

ONLY if you find that the performance is not enough should you consider using pointers and then deal carefully with memory management.

And if you need pointers, just use vector<myclass*> rather than rolling out your own collection class. That's the beauty of STL being generic =)

Answer 8

Copying will have some impact on performance. For small objects, just store them by value and profiling will tell you if you need to reconsider. For larger objects you could store a smart pointer in the container to mitigate some of the concerns. Again, if it's natural to store the object by value, do it that way unless profiling indicates it's a significant bottleneck.

Also note that I don't believe the return is in fact making a copy. What you're seeing is that "adding second" probably makes two copies: First, it has to expand the vector from 1 to (probably) 2, and copy the old element from its previous location to the new one, then copy element 2 into its place.

Answer 9

Firstly Its recommended to use Pointers Instead, when using your own class in vector. However here as the data text is stored as pointer. Its (the text attribute's value) not copied twice.So in this application there is no major performance problem.

Answer 10

Yes it does. This is one of the main reasons we'll be getting rvalue references in C++0x.

Answer 11

Copying will affect performance. If you keep large objects in standard containers it will be a good idea to use smart pointers instead of objects itself.