Thread: Vector Size

I need a large string vector for file content manipulation.

v1.max_size() gives me 153 391 689.

But if I make a test by looping a vector pushing back strings it crashes around 16 - 26 000 000 though I still have a lot of ram (1GB left).

How come and why isn't vector size limited by ram instead?

myvector.max_size() "Returns the maximum number of elements that the vector can hold."

Post your test program.
What are you actually storing in the vector?
Is your system 32 or 64 bit?

x64 machine x86 program.
Storing words in the vector.
This is the test program.

Code:

int count=0;

int main ()
{
    vector<string>v;

    while(1)
    {
        v.push_back("a");
        count++;
    }

    return 0;
}

Notes:
- Not all strings are equal in size; therefore, the maximum elements cannot be guaranteed as a maximum limit. Each string eats memory too.
- In 32-bit programs, you are limited to around 2 GB of ram. If you don't want that, create a 64-bit program.

I also seriously wonder if you need all that ram. Can you get away with less? Process it in chunks instead of reading all at once.

Not all strings are equal in size; therefore, the maximum elements cannot be guaranteed as a maximum limit. Each string eats memory too.

In my test program I only push back "a"s and it crashes around 26 000 000.

I cannot process it in chunks because I want to remove duplicates.

Originally Posted by Ducky

How come and why isn't vector size limited by ram instead?

It is.

When you compile program for a 32-bit machine, the highest possible address is usually 0xFFFFFFFF (4294967295). Assuming that your std::string implementation needs (at least) 28 bytes for each string instance, this gives a theoretical maximum of 4294967295 / 28 = 153391689 strings.

EDIT:

Vector implementations have one drawback (which can also be an advantage) - they allocate memory contiguously. Each vector holds a preallocated storage which grows exponentially, usually by a factor between 1.5 - 2 (google its allocation strategy if you want to know more). This means that when your vector reaches the size of 2GB, next time it reallocates the memory, it attempts to find a contiguous chunk of 4GB (or 3), and it fails because it already occupies 2. This leaves you with a big chunk of free memory.

You can try calling reserve() before you push anything, or try using a different container, e.g., std::deque.

Originally Posted by Ducky

I cannot process it in chunks because I want to remove duplicates.

Do you require the removal of consecutive duplicates only? Must ordering be maintained?

If you just want to process the strings and get unique strings in any order, then perhaps you can process it in chunks using std::set<std::string>, assuming that the number of unique strings is sufficiently small.

Consecutive duplicates? Any duplicate in the file.

The strings are small but I would need ordering, yes.

I will try to use a different container then or maybe a multidimensional char or compile it in x64.

Originally Posted by Ducky

The strings are small

It then stands to reason that the number of unique strings is also small.

Originally Posted by Ducky

I would need ordering, yes.

That is rather ambiguous: do you mean to say that you need the strings to be ordered say, lexicographically, or do you mean to say that the order as given by the the first of each unique string must be maintained? A std::set is appropriate for the former, but for the latter it may either be impossible with std::set or be more complicated.

Sorry, meant to say ordered lexicographically.