CArray and memory pre-allocation

Question

I'm working with the code in a MFC project that uses CArray class to work with dynamic arrays. It works as such:

CArray<CUSTOM_STRUCT> arr;
while(some_criteria)
{
    CUSTOM_STRUCT cs;
    add.add(cs);
}

This approach works, but becomes really slow with a large number of additions to dynamic array. So I was curious, is there a way to preallocate memory in CArray before I begin calling the add() method?

There's one caveat though. I can only estimate approximately the resulting number of elements in the array before I go into my while() loop.

PS. I cannot use any other arrays than CArray.

PS2. Due to complexity of this prokect, I would prefer to keep additions to the array via the add() method.

score 1 · Accepted Answer · answered Mar 19 '15 at 20:06

1

Really, really consider swapping out for a std::vector. It is surprisingly easy.

This is an attempt to make CArray follow a std::vector-like growth policy, instead of by 1 each time:

CArray<CUSTOM_STRUCT> arr;
while(some_criteria) {
  CUSTOM_STRUCT cs;
  arr.SetSize( arr.GetSize(), 1 + arr.GetSize()/2 );
  arr.add(cs);
}

When I run into this problem, I replace the CArray with a std::vector, so I haven't tested the above. Reading the docs, it should work. Test it and see if you get a massive performance increase (it should go from O(n^2) down to O(n) amortized)).

answered Mar 19 '15 at 20:06

Yakk - Adam Nevraumont

262,606
27
330
524

Thanks for the info. Just from curiosity, why is that `std::vector` is so much better than `CArray`? PS. I'm still on Visual Studio 2008. – c00000fd Mar 19 '15 at 20:11
@c00000fd As an example, if you did the above operation with `std::vector` it would just work, and you wouldn't have a performance problem. I am no `CArray` expert, I just know enough to be able to remove it from a code base when I need to (usually for maintenance (we find `std::vector` easier to work with) or performance reasons). – Yakk - Adam Nevraumont Mar 19 '15 at 20:22
Is it still available for older compilers/IDEs, i.e. VS 2008? – c00000fd Mar 19 '15 at 20:30
@c00000fd `#include `. It is worth learning but your first use of it should not be replacing CArray with it, I will admit. (it is not a drop-in replacement). – Yakk - Adam Nevraumont Mar 19 '15 at 20:52
Hey, one last question. Do you know if MFC's `CString` is also affected by the same memory allocation issue? – c00000fd Mar 23 '15 at 00:34
@c00000fd no, I do not know. A quick google says that it has a [linear growth policy](http://msgroups.net/microsoft.public.vc.mfc/cstring-concatenation-advice-pls/551364). [Another link talks about exponential to 1k, then linear](http://msgroups.net/microsoft.public.vc.mfc/cstring-addition-of-large-strings/555069), but that is also a decade old. – Yakk - Adam Nevraumont Mar 23 '15 at 02:18

score 0 · Answer 2 · answered Mar 23 '15 at 11:20

0

Use CArray::SetSize() method to preallocate the memory.

Please note if the memory is preallocated you should use CArray::operator[] instead of CArray::Add method.

answered Mar 23 '15 at 11:20

Andrew Komiagin

6,446
1
13
23

CArray and memory pre-allocation

2 Answers2