i need bigger string array

[TheMummy]

hello,

i need a bigger string array to hold strings .


string str[1000]; // is this ok ?

can i get more than this ? so that memory problem does not occur.

[Paul McKenzie]

Why not use a vector, so that you can expand the array at runtime if you need more room?

#include <vector>
#include <string>

typedef std::vector<std::string> StringArray;

int main()
{
  StringArray a(1000); // a thousand strings

  // if I need more strings
  int n = 3000;
  a.resize( n ); // now I have room for 3,000 strings.
}

Regards,

Paul McKenzie

[Rabelo]

This aproach work very well for this purpose but is necessary remember that each resize will have cost since all members on the old vector array will be moved to the new one. So if you will make many resizes you better think about a set (or multiset) or even a map(or multimap).

Regards

Rabelo

[TheMummy]

// if I need more strings
int n = 3000;
a.resize( n ); // now I have room for 3,000 strings.

but if i dont know how much memory do i need beforehand how can i resize that ?

is there anyway so that program will allocate memory as much it needs.

something like below.

a.resize(as_much _the _program _needed).


how can i do so that program automatically resizes upto how much it needs ?

[Assmaster]

You can just skip the resize and use the push_back member-function of the vector class to add each string you create in your app to the end of the vector.

Note that if you add thousands of strings, this might be slow since a lot of reallocation can occur. In that case the std:equeue or std::list containers would be a better choice.

[Guysl]

how can i do so that program automatically resizes upto how much it needs ?

Thats exactly what dynamic allocation is for (and data structures
that use dynamic allocation).
If you know, as the programmer, the amount of memory
from the beginning - then use static allocation.
if you don't know, you should resize your data structure either
using a data structure that supports the resize- or implement the resize by yourself.

[DevLip]

another option is to address the array dynamically

//here's a ptr to our array
string * theArray;
int numElements = 4;
theArray = new string[numElements];

of course if you want to resize this you will need to create a new larger array and copy all the elements over and then delete the old one

[Paul McKenzie]

Originally posted by TheMummy
but if i dont know how much memory do i need beforehand how can i resize that ?

Well at some point in your program, you do know how much memory you need (either you read the amount from a file, the user entered something, whatever). Once you know the memory amount, then you call resize with that amount. The argument to resize can be any expression, just like you wrote it:

int as_mas_much _the _program _needed;

// compute the as_much _the _program _needed somewhere
//...
a.resize(as_much _the _program _needed).

So you answered your own question.

Regards,

Paul McKenzie

[Paul McKenzie]

Originally posted by DevLip
another option is to address the array dynamically

Vector does all this for you, including the resizing. In C++, you try to stay away from naked pointers and "new"/"delete" as much as possible until it is absolutely necessary.

Regards,

Paul McKenzie

[Paul McKenzie]

Originally posted by Assmaster
You can just skip the resize and use the push_back member-function of the vector class to add each string you create in your app to the end of the vector.

Note that if you add thousands of strings, this might be slow since a lot of reallocation can occur. In that case the std:equeue or std::list containers would be a better choice.

Or calll std::vector::reserve, which allocates the memory up front so that reallocations don't occur.

Regards,

Paul McKenzie

[Rabelo]

Reserve can avoid you from exeeded realocations. But now you have another problem: how many itens to reserve?. As much acurated is this number less memory will the program use and more fast it will run.
to achieve this, try to answer these questions: (ask the users)
how will you vector grow up?
if from a file what is the medium size of these files?
if from a connection or such things what is the speed of this connection?
how many registers are coming per hour?
will your program work in a batch or a in line process?
With this informations you can find a magic number that will define your reserve, try 1/10 from the medium size, or you can even postphone this problem until the program run, parametrizing this item, like
ask the user for : "type the growing tax for this Data". So based on these number you define you reservation.

if you don´t now nothing about this I think that vector is not the apropriated structure to use. since vector is more apropriated to static structures that don´t change much in size.

Regards

Rabelo

[HeartBreakKid]

Additon to a vector using push_back() is very fast, fast enough that it won't matter to you (unless you need lots of strings, ie > 100000 and up).

Don't code for performance... Only look at performance when you know there is a bottleneck...

[Rabelo]

The push back has a lineartime O(n). So it´s time is proportional to the number of itens on the array.
So at the beginning it is fast but its time is proportional to the vector size.
It means that for a 200n size the time for push back is the double of 100n, being n the time for 1 item.
So no matter the time for one item, at 100000th item the time will be 100000 x n. On set the medium time for insert log2n.

supouse your array will have 100000 itens so the medium time is 50000 X nv, on a set this time will be log2(100000) X ns being nc the vector time and ns the set time.

to make the 100000th push back on this vector you´ll spend 100000 nv.
to make the 100000th on this set you´ll spend 20ns.

nc is not equal to ns so let´s supouse that ns is 2 times slower than nv, (what is an absurd). even so the set will be 40nv, 2500X faster.

I think that you may consider this when desing data structures.

I think that if you don´t code aiming performance you will miss the best of the C++.

Regards,

Rabelo

[MrViggy]

I think your time argument is incorrect here. Putting things into a set is slower then putting things into a vector (ignoring resizing for a moment), because you have to search then insert for a set! In a vector, you just push_back at the end (which, presumably, the vector class has that information cached).

Pushing back into a vector is *not* O(n); it's O(1).

Now, resizing... The vector class (and I beleive that the standard does say this somewhere) will resize it self to double it's current capacity. This means that the more you put into it, the less resizing occurs. However, if you know (or can make an educated guess) the total number of items in your vector; you call the vector's reserve function first; then all of your push_backs are executed in O(1) time.

Viggy

PS. I just wanted to add, resizing the vector is an O(n) operation.

[Rabelo]

Without resizing, push_back acts like operator[] that has a constant time k . Then, on this case, push_back has a constant time no matter the item order is being pushed. But with resizing the push back time is linear, not constant. The STL algorithm for push_back has an embedged resize. that prealloc n itens, previewing nexts push_back. This is named "amortized time". This amortized time causes constant time insertion, when there is no resizing and linear time insertion when there is resizing. It is very fast . But we need to know the price that we´re paying for this funcionality. Most of the cases the allocated memory is, as you said, 2 times the used memory. If memory is not a big deal, it is ok, but if the program runs on a memory shared machine, or if it work with a houge amount of data it can cause a big loss of performance.

Regards,

Rabelo