2D Vector && Segfaults

[Clockowl]

Hi guys, I'm getting a segfault and I don't really understand why.. Here is the code

n, i, quadcount, quadPerVert and quadindex are all (arrays of) unsigned integers.

unsigned int *quadsPerVert = new unsigned int[quadcount * 4];
//(...)
vector<vector<unsigned int> > quadsPerVertIndex;
quadsPerVertIndex.reserve(quadcount * 4);

for (n = 0; n < quadcount * 4; n++) {
    //find vertex with >= 2 quads
    if (quadsPerVert[n] >= 2) {
        for (i = 0; i < quadcount * 4; i++) {
            if ((unsigned int)quadindex[i] == n) {
                quadsPerVertIndex[n].push_back(i/4); //it segfaults here
            }
        }
    }
}

I'm guessing that quadPerVertIndex[n] doesn't exist yet, but how can that be when I reserved it? And how would I fix this? I've looked at the vector methods, but I don't understand why this doesn't work.

TIA,
Nick

[ArkM]

Use resize(n), not reserve(n) vector member function.
The last one does not initialize vector elements, it only reserved memory for future vector grows.

[Clockowl]

Thanks, worked like a charm!

How does that work then? It allocates more memory, but the vector doesn't grow in size?

and...

quadsPerVertIndex.resize(quadcount * 4);
    quadsPerVertIndex.clear();

Is that the correct way to allocate and clear (as in, set all elements to zero) a vector then?

[ArkM]

No, it's a wrong way. The vector v is empy after v.clear() call (v.size() == 0).

There are two different properties of a std::vector class: a size and a capacity. Get them by size() and capacity() member functions. Always: v.capacity() >= v.size().

Capacity (~ from MSDN): determines how much the vector can grow before it must reallocate storage for the controlled sequence. Try to print v.capacity() in the test program. Initially an empty vector (as usually - it's not the Standard requirement) has capacity == 0. While size <= capacity you can use pointers to the vector elements. If size() == capacity() and you push_back() the next element, all previous element addresses become invalid (the vector object moves all element to a new memory block). So it's a good way to reserve the right capacity for the vector (if you can do it) as early as possible.

Size: number of elements in the vector.

Accordingly we have two pairs of member functions (setter - getter):
reserve - capacity and resize - size.

There is a good example of capacity/size correlations in VC++ help...

[Clockowl]

I don't have VC++, using GCC... But thanks for the explanation, although.. I don't really understand the underlying mechanism. I thought reserve() was like allocating some extra memory (with or without moving the whole vector), so that after that allocation I should be able to access the newly allocated elements.

But it only makes sure it doesn't need to reallocate when the vector grows to that size?

[ArkM]

Suppose you have a very, very big purse. Are you a multi-millionaire because of you have such a purse?

vector object <=> purse => capacity <- reserve()
vector element <=> coin (or banknote) => size <- resize()

May be it helps ;)...

[Clockowl]

No, because in the purse I would have "allocated" the space for "coins".

Now bear with me and change coins for ints, why is it giving me segfaults? I have allocated plenty of space for the coins by having a big purse, but I don't have access to that space because the individual places haven't been initialized by their constructor? xD

PS:
I see how I can use the vector (and other STL container classes) now, thanks for that, I'm just wondering how it all works underneath.

[ArkM]

Let's remember: in the original snippet you have a vector of vectors (of unsigned int). Well, you have a purse (so big bag) for purses. After 1st (and only) reserve() you have a big big big big bag for many purses but no purses (for unsigned int coins) in this bag!

So quadsPerVertIndex[n].push_back(i/4) expression refers to non-existing vector of unsigned (sorry, to non-existing purse) but not to an empty purse (sorry, vector of unsigned). Feel the difference...

A vector object sceleton:

1. Number of elements - size - number of initialized slots with real objects
2. Pointer to memory block -> |...| element slots |...|
3. Memory block capacity (number of slots = initialized+free)

In your case (vector of vectors) every initialized slot contains vector of unsigned (its structure see above) but uninitialized slot contains a garbage (unpredictable values). Now you want to push new unsigned value into n-th (uninitialized!) vector of unsigned. Look at the sceleton above... Right, it has senseless pointer to nowhere. You catch segmentation faults now. Tomorrow you overwrite your stack... an so on...

[Clockowl]

"but I don't have access to that space because the individual places haven't been initialized by their constructor? xD"

So that is true? I can't access the reserved vectors because they aren't initialized yet and therefore do not exist...

So it'd work with chars, ints, floats.. but not with vectors. Okay, makes sense now.

[ArkM]

Of course, you have (formal) access rights to a really allocated by reserve() call vector's memory buffer. So quadsPerVertIndex[n] returned a reference to your process memory chunk (no segmentation faults at this moment). But the next step of quadsPerVertIndex[n].push_back(i/4) expression' elaboration was:

call push_back() member function for the vector (see vector header sceleton in my post above) which was placed in this memory slot.

Alas, there is no any valid vector header info in this slot now (reserve() call does not built any vector elements in a new buffer). But push_back() code does not know about that. It takes a pointer (no valid pointer values here) and try to access memory via this "pointer" value... Crash...

Have you noticed that resize() creates empty element objects? In your case:
1. resize() calls vector<int> constructor for every new slot in the buffer.
2. push_back takes an empty vector, allocates a buffer for a pushed element - and so on...

Moral: resize() is not "better" than reserve(). These vector member functions have different functionalities - vector maintenace for resize(), vector usage optimization for reserve().

[Clockowl]

Okay, thanks. I get it now.