CODEWITHSUNDEEP
c++stl
Nitin
Nitin

Reputation: 2874

Maximum number of stl::list objects

The problem is to find periodic graph patterns in a dataset. So I have 1000 timesteps with a graph(encoded as integers) in each timestep. So, there are 999 possible periods in which the graph can occur. Also I define a phase offset defined as (timestep mod period). For a graph which was first seen in the 5th timestep with period 2, the phase offset is 1.

I am trying to create a bidimensional array of lists in C++. Each cell contains a list containing graphs having a specified period and phase offset. I keep inserting graphs in the corresponding lists. 

list<ListNode> A[timesteps][phase offsets]

ListNode is a class with 4 integer variables.

This gives me Segmentation fault. Using 500 for the size runs fine. Is this due to lack of memory or some other issue?

Thanks.

Upvotes: 2

Views: 1401

Answers (4)

Anders Johansson
Anders Johansson

Reputation: 4006

Sounds like you're running out of stack space. Try allocating it on the heap, e.g. through std::vector, and wrap in try ... catch to see out of memory errors instead of crashing.

(Edit: Don't use std::array since it also allocates on the stack.)

try {
   std::vector<std::list<ListNode> > a(1000000);   // create 1000*1000 lists
   // index a by e.g. [index1 * 1000 + index2]
   a[42 * 1000 + 18].size(); // size of that list

   // or if you really want double subscripting without a wrapper function:
   std::vector<std::vector<std::list<ListNode> > > a(1000);
   for (size_t i = 0; i < 1000; ++i) {   // do 1000 times:
       a[i].resize(1000);                // default-create and create 1000 in each
   }
   a[42][18].size(); // size of that list

} catch (std::exception const& e) {
    std::cerr << "Caught " << typeid(e).name() << ": " << e.what() << std::endl;
}

Upvotes: 1

Jerry Coffin
Jerry Coffin

Reputation: 490148

Probably due to limited stack size.

You're creating an array of 1000x1000 = 1000000 objects that are almost certainly at least 4 bytes apiece, so roughly 4 megabytes at a minimum. Assuming that's inside a function, it'll be auto storage class, which normally translates to being allocated on the stack. Typical stack sizes are around 1 to 4 megabytes.

Try something like: std::vector<ListNode> A(1000*1000); (and, if necessary, create a wrapper to make it look 2-dimensional).

Edit: The wrapper would overload an operator to give you 2D addressing:

template <class T>
class array_2D { 
    std::vector<T> data;
    size_t cols;
public:
    array_2D(size_t x, size_t y) : cols(x), data(x*y) {}

    T &operator()(size_t x, size_t y) { return data[y*cols+x]; }
};

You may want to embellish that (e.g., with bounds checking) but that's the general idea. Addressing it would use (), as in:

array_2d<int> x(1000, 1000);

x(100, 3) = 2;

y = x(20, 20);

Upvotes: 6

Matteo Italia
Matteo Italia

Reputation: 126797

In libstdc++ on a 32 bit system a std::list object weights 8 bytes (only the object itself, not counting the allocations it may make), and even in other implementations I don't think it will be much different; so, you are allocating about 8 MB of data, which isn't much per se on a regular computer, but, if you are putting that declaration in a function it will be a local variable, thus allocated on the stack, which is quite limited in size (few MBs at most).

You should allocate that thing on the heap, e.g. using new, or, even better using a std::vector.

By the way, it doesn't seem right that you need a 1000x1000 array of std::list, could you specify exactly what you are trying to achieve? Probably there are data structures that better fit your needs.

Upvotes: 1

Mark Ransom
Mark Ransom

Reputation: 308206

You're declaring a two-dimensional array [1000]x[1000] of list<ListNode>. I don't think that's what you intended.

The segmentation fault is probably from trying to use elements of the list that aren't valid.

Upvotes: 0

Related Questions