Storing many elements in std::vector c++

Question

For one of my applications I need to generate vector of size 2^35 (the size of my RAM is 96 GB, so this vector can easily fit into RAM).

int main ()
{
  int i;

  /* initialize random seed: */
  srand (time(NULL));

  vector<int> vec;
  do {
     i = rand() % 10 + 1;
     vec.push_back(i);
  } while ((vec.size()*sizeof(int))<pow(2,35));

  return 0;
}

However, I notice that my do while loop executes infinitely. One of the possible reasons is range of vec.size() is long unsigned int, which is very less than the number of elements inserted i.e. pow(2,35), due to which I think it goes in an infinite loop. I may be wrong. Please correct me if I am wrong. But can someone please tell how can I insert greater than pow(2,35) numbers in vec.

gcc version:4.8.2

Answer 1

I'll try to address some of your problems in a simple solution:

First problem you have is space. Since you need numbers from 1-10 only, a int8_t would serve you much better.

Second is speed. std::vector does a lot of allocations and reallocations behind the hood. Since you have a fixed size, In my opinion there's no need to use it. Knowing this, we'll use a simple array and threads to improve performance.

Here's the code:

#include <array>
#include <random>
#include <thread>
#include <cstdint>
#include <memory>
#include <chrono>

// Since you only need numbers from 1-10, a single byte will work nicely.
const uint64_t size = UINT64_C(0x800000000); // Exactly 2^35
typedef std::array<int8_t, size> vec_t;

// start is first element, end is one-past the last. This is a template so we can generate multiple functions.
template<unsigned s>
void fill(vec_t::iterator start, vec_t::iterator end) {
    static const int seed = std::chrono::system_clock::now().time_since_epoch().count()*(s+1);
    static std::default_random_engine generator(seed);
    static std::uniform_int_distribution<int8_t> distribution(1,10);
    for(auto it = start; it != end; ++it) {
        *it = distribution(generator);  // generates number in the range 1..10
    }
}

int main() {
    auto vec = std::unique_ptr<vec_t>(new vec_t());

    // Each will have its own generator and distribution.
    std::thread a(fill<0>, vec->begin(), vec->begin() + size/4);
    std::thread b(fill<1>, vec->begin() + size/4, vec->begin() + size/2);
    std::thread c(fill<2>, vec->begin() + size/2, vec->begin() + (size/4)*3);
    std::thread d(fill<3>, vec->begin() + (size/4)*3, vec->end());
    a.join();
    b.join();
    c.join();
    d.join();
    return 0;
}

Answer 2

Why can't you use constructor?

std::vector<int> vec ( number_of_elements );

That way you'll have memory reserved, then you can randomize elements using generate or something.

Answer 3

Update

As Baum mit Augen has highlighted, this post doesn't really answer the question because in his platform condition 4 doesn't hold (sizeof(std::size_t) is actually 8). However, I leave this post here to highlight an issue that might occur when porting the code.

Original post

One problem that I see is the following. Let's assume (most platforms fulfill these assumptions) that

1) vec.size returns std::size_t (not guaranteed);

2) sizeof returns std::size_t (guaranteed);

3) std::size_t is an unsigned integer type (guaranteed);

4) sizeof(std::size_t) == 4 (not guaranteed);

5) CHAR_BIT == 8 (not guaranteed).

(Recall that CHAR_BIT is the number of bits in a char.)

Therefore, the type of vec.size()*sizeof(int) is std::size_t and its maximum value is 2^(sizeof(std::size_t)*CHAR_BIT) - 1 == 2^32 - 1 < 2^32 < 2^35. Therefore, vec.size()*sizeof(int) is always smaller than 2^35.