Am I being paranoid about vector pointers? 
Author Message
 Am I being paranoid about vector pointers?

I am trying to use a lot of (vector<>)s in my code for a QuadTree type
structure.  More or less, I have one main (vector<>)[m_oNodes] which holds
all the nodes.  But I also have all sorts of nested (vector<>)s and
relations between the nodes in the main (vector<>).  It has been mentioned
to me that pointers to elements in the (vector<>)s can go bad quite often.
Now I am paranoid and not sure how long or under what conditions a pointer
(such as p_pNode or pNode in CreateQuad()) will be valid.  I am afraid to
nest too deep, or use too many pointers.  I wanted to nest
CreateLeafHeightMap inside CreateQuad, but I am worried about doing so.  Is
there a good reference as to when pointers to (vector<>)s go bad?  What can
you guys tell me about this, am I being to paranoid?  Thanks.

struct StQuadBound
{
    float fX;
    float fZ;

Quote:
};

struct StLeafHMVertex
{
    float fX;
    float fZ;
    float fY;
    float fNx;
    float fNy;
    float fNz;
    float fTu;
    float fTv;
Quote:
};

struct StNode
{
    bool bLeaf;     // This node is a leaf
    bool bRoot;     // This node is the root
    int iIndex;     // This node's index in vector
    int iLevel;     // This node's level in tree
    StQuadBound stBounds[4]; // This node's boundaries
    int iParentIndex;   // This node's parent's index
    int iSize;     // This node's width/height
    C2DVector<StLeafHMVertex, 1, 1> oHeightMap;  // This node's height map

Quote:
};

//******************Part of the Class******************//
void CreateQuad(StNode *p_pNode)
/**
 * Name: CreateQuad
 * Desc: Take a QuadTree node and make 4 child nodes
**/
{
    if (p_pNode->iLevel == m_iMaxLevel) return;
    for (int iCnt = 0; iCnt<4; iCnt++)
    {
        m_iNodeCount++;
        StNode *pNode = &m_oNodes[m_iNodeCount-1];
        pNode->iIndex = m_iNodeCount - 1;
        // Child is never the root
        pNode->bRoot = false;
        // Child is leaf if is in the last level
        pNode->iLevel = p_pNode->iLevel + 1;
        if (pNode->iLevel == m_iMaxLevel)
            pNode->bLeaf = true;
        else
            pNode->bLeaf = false;
        // Parent
        pNode->iParentIndex = p_pNode->iIndex;
        // Bounds
        pNode->iSize = p_pNode->iSize / 2;
        float iCenterX = p_pNode->stBounds[0].fX + pNode->iSize;
        float iCenterZ = p_pNode->stBounds[3].fZ + pNode->iSize;
        float fLBX = 0;
        float fLBZ = 0;
        switch (iCnt)
        {
        case 0:
            fLBX = p_pNode->stBounds[0].fX;
            fLBZ = iCenterZ;
            break;
        case 1:
            fLBX = iCenterX;
            fLBZ = iCenterZ;
            break;
        case 2:
            fLBX = iCenterX;
            fLBZ = p_pNode->stBounds[2].fZ;
            break;
        case 3:
            fLBX = p_pNode->stBounds[0].fX;
            fLBZ = p_pNode->stBounds[2].fZ;
            break;
        }
        ComputeBounds(pNode, fLBX, fLBZ);
        // Recurse children
        if (!pNode->bLeaf) CreateQuad(pNode);
    }
Quote:
}

void CreateLeafHeightMap(int p_iNode)
/**
 * Name: CreateLeafHeightMap
 * Desc: Create Height Map for a node
**/
{
    StNode *pRoot = &m_oNodes[0];
    StNode *pNode = &m_oNodes[p_iNode];
    // Get first column and row index
    int iFirstCol = (int)((pNode->stBounds[0].fX - pRoot->stBounds[0].fX) /
m_iHeightMapIntSize);
    if (iFirstCol != 0) iFirstCol++;
    int iFirstRow = (int)((pRoot->stBounds[0].fZ - pNode->stBounds[0].fZ) /
m_iHeightMapIntSize);
    if (iFirstRow != 0) iFirstRow++;
    int iColCnt = (int)(((pNode->stBounds[1].fX - pNode->stBounds[0].fX) /
m_iHeightMapIntSize) + 1);
    int iRowCnt = (int)(((pNode->stBounds[0].fZ - pNode->stBounds[3].fZ) /
m_iHeightMapIntSize) + 1);
    pNode->oHeightMap.Resize(iColCnt, iRowCnt);
    for (int iCntCol = 0; iCntCol<iColCnt; iCntCol++)
    {
        for (int iCntRow = 0; iCntRow<iRowCnt; iCntRow++)
            pNode->oHeightMap.Set(iCntCol, iCntRow) =
pRoot->oHeightMap.Get(iFirstCol+iCntCol, iFirstRow+iCntRow);
    }
Quote:
}



Fri, 08 Jul 2005 13:21:36 GMT  
 Am I being paranoid about vector pointers?


Quote:
> I am trying to use a lot of (vector<>)s in my code for a QuadTree type
> structure.  More or less, I have one main (vector<>)[m_oNodes] which
holds
> all the nodes.  But I also have all sorts of nested (vector<>)s and
> relations between the nodes in the main (vector<>).  It has been
mentioned
> to me that pointers to elements in the (vector<>)s can go bad quite
often.
> Now I am paranoid and not sure how long or under what conditions a
pointer
> (such as p_pNode or pNode in CreateQuad()) will be valid.  I am afraid
to
> nest too deep, or use too many pointers.  I wanted to nest
> CreateLeafHeightMap inside CreateQuad, but I am worried about doing
so.  Is
> there a good reference as to when pointers to (vector<>)s go bad?
What can
> you guys tell me about this, am I being to paranoid?  Thanks.

Note 5 at the bottom of http://sgi.com/tech/stl/Vector.html gives
conditions...I'm not sure if those are set in stone guarantees or just
implementation specific guarantees, but the way vector is specified,
it's probable.

Ken



Fri, 08 Jul 2005 14:47:47 GMT  
 Am I being paranoid about vector pointers?

Quote:
> I am trying to use a lot of (vector<>)s in my code for a QuadTree type
> structure.  More or less, I have one main (vector<>)[m_oNodes] which
holds
> all the nodes.  But I also have all sorts of nested (vector<>)s and
> relations between the nodes in the main (vector<>).  It has been
mentioned
> to me that pointers to elements in the (vector<>)s can go bad quite
often.
> Now I am paranoid and not sure how long or under what conditions a
pointer
> (such as p_pNode or pNode in CreateQuad()) will be valid.  I am afraid
to
> nest too deep, or use too many pointers.  I wanted to nest
> CreateLeafHeightMap inside CreateQuad, but I am worried about doing
so.  Is
> there a good reference as to when pointers to (vector<>)s go bad?

Yes, there is.  It's called ISO/IEC 14882:1998(E), or the C++ Standard,
particular section 23.2.4, in the case of std::vector<>.

Pointers into a vector "go bad" precisely (and exclusively) when:

1. The vector's internal data is reallocated.  Reallocation will occur
when 'n' items are inserted into the vector and capacity()-size() > n.
2. When an item is inserted into or removed from vector "before" (or at)
the pointer (e.g. you're pointing at the 10th entry, and you insert a
new item at index 7).

(Obviously, clearing the vector will invalidate pointers - it also fits
the description of condition #2 above).

(Note, if you swap one vector with another, all pointers/iterators
remain valid, and simply refer to elements of the other container after
the swap, as you'd expect... at least if you expect correctly ;-)

Quote:
> What can you guys tell me about this, am I being to paranoid?  Thanks.

It's more code than I want to read now :)

-cd



Fri, 08 Jul 2005 14:55:30 GMT  
 Am I being paranoid about vector pointers?



Quote:
> 1. The vector's internal data is reallocated.  Reallocation will occur
> when 'n' items are inserted into the vector and capacity()-size() > n.

You must mean capacity()-size() < n
--
With best wishes,
    Igor Tandetnik

"For every complex problem, there is a solution that is simple, neat,
and wrong." H.L. Mencken



Fri, 08 Jul 2005 22:39:31 GMT  
 Am I being paranoid about vector pointers?

Quote:


> > 1. The vector's internal data is reallocated.  Reallocation will
occur
> > when 'n' items are inserted into the vector and capacity()-size() >
n.

> You must mean capacity()-size() < n

Uh, yeah :)

-cd



Fri, 08 Jul 2005 22:54:19 GMT  
 Am I being paranoid about vector pointers?
Just for clarification...So if I resize other data structures before or
after the vector, it will not cause the vector to be reallocated and my
pointer to go bad?



Quote:


> > I am trying to use a lot of (vector<>)s in my code for a QuadTree type
> > structure.  More or less, I have one main (vector<>)[m_oNodes] which
> holds
> > all the nodes.  But I also have all sorts of nested (vector<>)s and
> > relations between the nodes in the main (vector<>).  It has been
> mentioned
> > to me that pointers to elements in the (vector<>)s can go bad quite
> often.
> > Now I am paranoid and not sure how long or under what conditions a
> pointer
> > (such as p_pNode or pNode in CreateQuad()) will be valid.  I am afraid
> to
> > nest too deep, or use too many pointers.  I wanted to nest
> > CreateLeafHeightMap inside CreateQuad, but I am worried about doing
> so.  Is
> > there a good reference as to when pointers to (vector<>)s go bad?

> Yes, there is.  It's called ISO/IEC 14882:1998(E), or the C++ Standard,
> particular section 23.2.4, in the case of std::vector<>.

> Pointers into a vector "go bad" precisely (and exclusively) when:

> 1. The vector's internal data is reallocated.  Reallocation will occur
> when 'n' items are inserted into the vector and capacity()-size() > n.
> 2. When an item is inserted into or removed from vector "before" (or at)
> the pointer (e.g. you're pointing at the 10th entry, and you insert a
> new item at index 7).

> (Obviously, clearing the vector will invalidate pointers - it also fits
> the description of condition #2 above).

> (Note, if you swap one vector with another, all pointers/iterators
> remain valid, and simply refer to elements of the other container after
> the swap, as you'd expect... at least if you expect correctly ;-)

> > What can you guys tell me about this, am I being to paranoid?  Thanks.

> It's more code than I want to read now :)

> -cd



Sat, 09 Jul 2005 04:44:01 GMT  
 Am I being paranoid about vector pointers?

Quote:
> Just for clarification...So if I resize other data structures before
or
> after the vector, it will not cause the vector to be reallocated and
my
> pointer to go bad?

Please clarify what you mean by "before" or "after".

If I understand your question correctly, then the answer is "yes", you
may make such changes without affecting pointers into your vector.

See if this helps:  a typical implementation of vector is roughly
(leaving out most of the member functions - just the data):

template<class T> class vector
{
    T* m_pFirst;    // pointer to first element
    T* m_pLast;        // pointer to one-past the last element
    T* m_pEnd;    // pointer to one-past the end of the allocation

    size_t size() { return m_pLast - m_pFirst; }
    size_t capacity() { return m_pEnd - m_pFirst; }

    T& operator[](size_t n) { return m_pFirst[n]; }

Quote:
};

Pointers into the vector will be m_pFirst + n (where 'n' is the index of
the item being referenced).

As you can see, the things that will invalidate pointers into the vector
are the things that cause m_pFirst to get a new value.

Moving the vector itself will not invalidate pointers:

vector< vector<int> > vvi;

// put data into vvi
// ...

// point at an int element in the (2-d) vector
int* pi = &vvi[n][m];

// insert something into vvi
vector<int> vi;
vvi.insert( vvi.begin(), vi );

// pi is still valid even though the vector it's pointing into has moved
// (since the data in that vector hasn't moved).

HTH

-cd

-cd



Sat, 09 Jul 2005 05:06:27 GMT  
 Am I being paranoid about vector pointers?


Quote:
> Moving the vector itself will not invalidate pointers:

> vector< vector<int> > vvi;

> // put data into vvi
> // ...

> // point at an int element in the (2-d) vector
> int* pi = &vvi[n][m];

> // insert something into vvi
> vector<int> vi;
> vvi.insert( vvi.begin(), vi );

> // pi is still valid even though the vector it's pointing into has
moved
> // (since the data in that vector hasn't moved).

Actually, I think I overstepped reality here... pi would still be valid
if the vector had been moved via memcpy, but since it's in another
vector, it will have been moved via assignment onto another vector,
which will copy the data from the old vector, thus moving it.

The library would behave as I described if C++ had the much sought "move
constructors" that's being kicked around in the committee right now (and
if std::vector was updated to use move-construction when possible).

-cd



Sat, 09 Jul 2005 07:18:33 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. Am I being too paranoid?

2. I am new to programming and am lost

3. What am I doing wrong with vector interrupts?

4. HELP, I am having problems with pointer...

5. how good am I? Am I Good Enough????

6. proper way of refering to pointer of vector to vector

7. Determine where I am running

8. System.Threading.Timer , am I doing this correctly ?

9. Am i connected?

10. Request - Opinions on Book I am considering:

11. I am puzzled: __nogc new = LNK2001

12. Am I in the wrong NG???

 

 
Powered by phpBB® Forum Software