array/pointer access of different-sized sets?

[dshillady]

Hello all.

Let me start by saying that there have been similar questions and answers on this forum to mine, but I feel that my question is significantly different enough to justify a new post. It deals with dynamic arrays, but in this case the array elements are not of uniform size.

I am trying to port/translate a java program to C++ that I wrote and completed for my Master's Degree thesis.

I am a relative beginner with C++, but I do know quite a bit about programming in general.

The current issue I am having is due to the fact that java and C++ handle arrays differently (if I understand correctly).

Anyways, what I am trying to do is to create a *dynamic* 3-dimensional array of STL sets, of different "sizes" (different number of elements), to be passed to a function to be processed.

A standard way I learned of passing C++ arrays is to pass the name (pointer) as a parameter along with its dimensions as parameters, and then access the array elements by pointer arithmetic or the [] operator with loops within the function.

My question is, will the [] or dereferencing operators "know" how to separate the memory "boundaries" of individual sets in the array if they are of different and variable sizes?

I understand that I can use vectors, such as vector<vector<vector<set> > >, but the whole point of my thesis is to analyze the runtime complexity and efficiency of two algorithms, so I would like to access, store, and manipulate the data in the sets as efficiently as possible.

I'm hoping to avoid as much overhead and computation as can be, so vectors are not my first choice, but I'll use them if I have to.

The only alternative to using vectors that I can see is to create a class to implement a "linked array", much like a linked list but with an array of its own class instead of just a single instance, and a set, as data members.

This still seems to me to be a very roundabout and slow-performance solution.

Is my understanding of the situation correct?

What would anyone recommend that I do?

Thank you in advance.

[Athar]

vectors are the way to go.
They don't have the overhead that you think they have. A self-made solution using raw pointers and dynamic allocations wouldn't be any faster (in Release mode).

[R0mai]

I agree with Athar, use vectors, they will be faster then your hand-made solution. To make it even faster I recommend making a class which from the outside looks like a 3D array, but inside it's only uses one single allocation of memory.

[dshillady]

Thanks Athar and R0mai, but now that I think about it a bit more, I think my original question runs deeper than I had originally anticipated.

Aside from my original situation, I'd like to know if any array of different sized containers is even possible to use at all, dynamic or static.

For example, if this code is used to create such an array:

set<int> set_array[10];

for (int i=0; i<10; i++) {

    set_array[i] = createRandomSizedSet(someVariable);

}

will the system (or even the compiler) be able to handle the following task, without getting mixed up?

for (int j=0; j<10; j++) {

    outputSet(set_array[j]);

}

It looks simple, but think about it--the sets are of different sizes.

I was taught that arrays are contiguous blocks of memory pointed to by the array name. But if the blocks are of different sizes, how would the system know where one block begins and another one ends?

And what would then happen if one or more of the sets in the array was enlarged or made smaller by the addition or removal of some of its elements? How would the system keep track of the "boundaries" between the sets in memory?

I would really like to understand this, so thanks to anyone who can help.

Thanks again.

[R0mai]

The size of the set (or any other class) is constant. (sizeof(std::set<int>)). Set allocates it's memory from the heap (with new and delete) and the class itself only holds a pointer to this allocated space.
So if you use the sets in an array, only the pointer and some other variables are going to be in the actual array space, the data you put into the set are allocated from the heap.

[kempofighter]

So in other words, there is no problem creating an an array of sets where each set has a different number of values. Your outputSet function simply needs to use the proper interface for the set object to ensure that it is not going to accidentally add new values. In other words, don't use set's operator[] to access values when you don't know the size of each one. Use the iterators from begin() to end(). The operator[] for associative arrays can add default constructed key/value pairs outputSet needs to be coded to handle any size set by using the iterators.

[dshillady]

Thank you R0mai and kempofighter.

So it turns out that I can create a dynamic 3D array of sets, pass it to a function along with its dimensions, and use pointer arithmetic to iterate through the sets (not their elements) in the array, as is the standard way of accessing arrays as parameters? Cool, if so.

(outputSet was just a dummy-name for a function as an example.)

[R0mai]

That is correct.

[dshillady]

Great!

Problem resolved.

Thank you very, very much!