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
there a good reference as to when pointers to (vector<>)s go bad?  What can

{
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******************//
/**
* 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
}
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
so.  Is
> there a good reference as to when pointers to (vector<>)s go bad?
What can

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
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:

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

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
> 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 ;-)

> 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

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

 Page 1 of 1 [ 8 post ]

Relevant Pages