Re: Author of Visual C++ 2005 STL ???

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

I made such a claim on a discussion list that just happened to include some of the more brilliant minds at Microsoft, including the developer responsible for maintaining the STL. It was my long-held belief that it was better to allocate elements and simply put pointers into structures such as lists and maps. After making this claim, however, I got "taken to school" on the subject. Here are some excerpts:

"Putting raw pointers into an STL collection is also a bad idea (some might say "epic fail" or something similar). Use smart pointers [see shared_ptr of TR1], always. If you throw an exception, and the stl collection gets destroyed without you deleting the pointers it holds you will leak. For small objects the STL is pretty efficient anyway. In fact I've found in the past that std::vector of objects outperforms std::vector of raw pointers (before a learned how bad this was) by quite a lot. I assume this is due to improved locality - everything is contiguous in memory instead of hopping about all over the place, so the memory manager and the CPU cache can do a much better job of making sure that everything you need is ready when you need it. It also uses less memory - a collection of pointers will add (at least) the size of the pointer in the collection, plus the heap goop either side of the object you allocated.


Of course things change for really big or particularly expensive to copy objects"

and "The performance thing surprised me when I first figured it out. In my case I was using std::map to hold a dictionary that was being searched on a hot code path. Changing it to an ordered vector had an enourmous impact on the performance (orders of magnitude) and cost me virtually nothing - adding things to the dictionary was very unusual once the system had been up and running for a bit. The big problem in my case was page faults, the map had many small nodes allocated all over memory, and it was a very memory hungry app so these nodes were getting paged out and I was incurring page faults all the time. Sticking it in a vector made the whole thing fit into three or four consecutive pages, which stayed in memory all the time. The memory manager, CPU and cache are all much better at understanding sequential access to things than random access"

"Joseph M. Newcomer" <newcomer@xxxxxxxxxxxx> wrote in message news:s4q4t498s92d9v26d4tgr48trdmqfb2p8k@xxxxxxxxxx
Well, strictly speaking it only needs to call the copy constructor if it has to copy the
object (such as when it reallocates the vector). So if the built-in preallocation (which
is how STL avoids the exponential-time problem) is working, you will get one or two calls
on the copy constructor (e.g., as shown below, there is one when the parameter x is copied
as part of the call and one when the object is placed in the vector).

But note that if you add something into the vector, and the vector has 1000 elements, if
you add something at position 50 you will get 952 calls on the copy constructor.

This is one of the reasons that vectors of pointers are often a better choice than vectors
of objects, because the pointers can be trivially copied.
joe

On Tue, 31 Mar 2009 10:32:00 -0500, "AliR \(VC++ MVP\)" <AliR@xxxxxxxxxxxxx> wrote:

It is not a bug.

say you have

class CMyObject
{
....
};

vector<CMyObject> MyVector;

MyVector.push_back(x); //this will call the copy constructor twice
MyVector.push_back(x); //this will call it 3 times.
// and so on and so forth.

It is just how vector allocates and moves things around when new items are
added. When it is empty and an item is added, it first allocates the space
for it which calls the copy constructor of the template item, then it
actually copies it in there, which again calls the copy constructor.

AliR.


"Giovanni Dicanio" <giovanniDOTdicanio@xxxxxxxxxxxxxxxxx> wrote in message
news:uVTNrQhsJHA.4324@xxxxxxxxxxxxxxxxxxxxxxx

"PeteOlcott" <PeteOlcott@xxxxxxxxx> ha scritto nel messaggio
news:1b82dda9-f64e-4cec-8330-63117d664a0f@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
There is an issue with std::vector::push_back() calling the object's
copy constructor twice. I want to see if this can be resolved.

I don't have VS2005 on this machine (I have VS2008), but I'm curious...
std::vector::push_back is a very common method, and it would seem strange
to me that such a common method have a similar bug.

Could you please post some compilable code so we could analyze it?

Thanks,
Giovanni



Joseph M. Newcomer [MVP]
email: newcomer@xxxxxxxxxxxx
Web: http://www.flounder.com
MVP Tips: http://www.flounder.com/mvp_tips.htm

.

Relevant Pages

  • How java passes object references?
    ... + as a language that passes by reference for the sake of my questions. ... does it do it in memory? ... Allocates memory for the newly create Human object and changes the ... how pointers work in memory. ...
    (comp.lang.java.programmer)
  • Re: malloc and pointer hell
    ... >array (pointers to pointers). ... This allocates space for only one pointer. ... place is an int**. ... you no longer have access to the memory that was ...
    (comp.lang.c)
  • Re: malloc/free aimple question!
    ... If you have pointers 'p' and 'x', ... free that memory, *ALL* pointers pointing to that block of memory must ... When I go from the first winProc to the second ... memory -- you should know who allocates it, ...
    (microsoft.public.vc.language)
  • Re: malloc and pointer hell
    ... >>array (pointers to pointers). ... >This allocates space for only one pointer. ... >allocated memory in the int* pointed to by digit. ... The value of digit is modified in the loop. ...
    (comp.lang.c)
  • Re: Function with two int parameters
    ... Even if the array index was in bounds, say 15, all ... I understand now the error in my constructor, ... But the memory can be ... I would ask myself why I am using only pointers. ...
    (alt.comp.lang.learn.c-cpp)