Variable sized char array with minimizing calls to new?

Question

I need a char array that will dynamically change in size. I do not know how big it can get so preallocating is not an option. It could never get any bigger than 20 bytes 1 time, the next time it may get up to 5kb...

I want the allocation to be like a std vector.

I thought of using a std vector < char > but all those push backs seem like they waste time:

strVec.clear();
for(size_t i = 0; i < varLen; ++i)
{
   strVec.push_back(0);
}

Is this the best I can do or is there a way to add a bunch of items to a vector at once? Or maybe a better way to do this.

Thanks

See [here](http://www.cplusplus.com/reference/stl/vector/resize/) — Shahbaz, May 11 '12 at 23:57
`std::vector` has a method `reserve` for exactly this purpose. — AJG85, May 12 '12 at 00:01
I'm taking a packet, and encrypting or decrypting it using an xor cipher. — jmasterx, May 12 '12 at 00:01
@Milo resize is the correct function to call, reserve just increases its capacity, you need actual elements, so resize it. — johnathan, May 12 '12 at 00:03
@Milo, resize the vector, and write to it with std::copy or what ever you need to do it with. — johnathan, May 12 '12 at 00:05
look this one, http://stackoverflow.com/questions/18444318/how-to-create-a-variable-size-char-array-in-vc — ANjaNA, Jul 20 '15 at 05:12

score 3 · Accepted Answer · answered May 12 '12 at 00:02

3

std::vector doesn't allocate memory every time you call push_back, but only when the size becomes bigger than the capacity

answered May 12 '12 at 00:02

Ruggero Turra

16,929
16
85
141

score 2 · Answer 2 · answered May 12 '12 at 04:28

First, don't optimize until you've profiled your code and determined that there is a bottleneck. Consider the costs to readability, accessibility, and maintainability by doing something clever. Make sure any plan you take won't preclude you from working with Unicode in future. Still here? Alright.

As others have mentioned, vectors reserve more memory than they use initially, and push_back usually is very cheap.

There are cases when using push_back reallocates memory more than is necessary, however. For example, one million calls to myvector.push_back() might trigger 10 or 20 reallocations of myvector. On the other hand, inserting into a vector at its end will cause at most 1 reallocation of myvector*. I generally prefer the insertion idiom to the reserve / push_back idiom for both speed and readability reasons.

myvector.insert(myvector.end(), inputBegin, inputEnd)

If you do not know the size of your string in advance and cannot tolerate the hiccups caused by reallocations, perhaps because of hard real-time constraints, then maybe you should use a linked list. A linked list will have consistent performance at the price of much worse average performance.

If all of this isn't enough for your purposes, consider other data structures such as a rope or post back with more specifics about your case.

From Scott Meyer's Effective STL, IIRC

score 1 · Answer 3 · answered May 11 '12 at 23:57

1

You can use the resize member function to add a bunch. However, I would not expect that push_back would be slow, especially if the vector's internal capacity is already non-trivial.

answered May 11 '12 at 23:57

Puppy

144,682
38
256
465

Considering it's pretty much a constant time operation, push_back is fine, The only time I set a containers size before adding elements is when i have to use some C api that writes to a buffer. Good answer +1 – johnathan May 12 '12 at 00:01

score 1 · Answer 4 · answered May 12 '12 at 04:50

Is this the best I can do or is there a way to add a bunch of items to a vector at once? Or maybe a better way to do this.

push_back isn't very slow, it just compares the size to the current capacity and reallocates if necessary. The comparison may work out to essentially zero time because of branch prediction and superscalar execution on the CPU. The reallocation is performed O(log N) times, so the vector uses up to twice as much memory as needed but time spent on reallocation seldom adds up to anything.

To insert several items at once, use insert. There are a few overloads, the only trick is that you need to explicitly pass end.

my_vec.insert( my_vec.end(), num_to_add, initial_value );
my_vec.insert( my_vec.end(), first, last ); // iterators or pointers

For the second form, you could put the values in an array first and then copy the array to the end of the vector. But this might add as much complexity as it removes. That's how it goes with micro-optimization. Only attempt to optimize if you know there's a measurable gain to be had.

Variable sized char array with minimizing calls to new?

4 Answers4