Vector of Pointers
-
Hi. Ok slightly long explaination, I apologise! I am currently developing a 3d drawing system and am having a few problems with storing the vertexes of each line. Basically there are two objects that I am using to construct a drawing: points and lines. A point stores the x y z coordinate of a vertex. Each point that is drawn is stored in a global vector of points. A line consists of many points and consists of a vector that stores a reference to each pointer in the global vector. The problem I am having is that the vector of pointers in the line object start off pointing to the vertex in the global array but when another point is added to the global array it can no longer find it instead it comes back with the vertex being at some strange position, the most common coordinate being -1.5883997e38. I can see it may be something to do with how the global vector stores the point objects. Ive checked: The actual values of the pointers in the line vector do not change value The global vector containing the points stores the points ok Is this explanation enough or do I need to post code? Kevin
Hi, First of all your approach of using STL classes for 3D drawing system is not so good. 3D graphics being a expensive operation on computer, experts are using hardware accelerated methods like using graphics library like DirectX, openGL. stl::Vector is an expensive array is inefficient for such application. Then, what do you mean by reference, reference to vector item. please post some code snippet.
-
Hi, First of all your approach of using STL classes for 3D drawing system is not so good. 3D graphics being a expensive operation on computer, experts are using hardware accelerated methods like using graphics library like DirectX, openGL. stl::Vector is an expensive array is inefficient for such application. Then, what do you mean by reference, reference to vector item. please post some code snippet.
Ok thanks for replying Max: Thats basically the design I have but without the geometry class. I am never going to be able to draw a point, it is simply used to construct a line (the system is only going to be able to draw lines) Pallini, Rajkumar: Heres some code: --------------------------------- // holds all the lines std::vector lines; // holds all the points std::vector allpoints; struct Point { public: GLfloat x, y, z; bool selected; /* constructors */ Point() { } Point(const GLfloat & xval, const GLfloat & yval, const GLfloat & zval) { } Point(const Point & from) { } }; /* a class to describe a line in 3 dimensional space */ class Line { public: // each pointer in this vector should point to a Point object in allpoints std::vector points; bool selected; // Initializes variables Line() { } Line(int typein) { } // Functions void addPoint(Point & p) { points.push_back(&p); } void draw() // ive only included part of it { Point current; glLineWidth(thickness); glColor3fv(color); glBegin(GL_LINE_STRIP); for (int i = 0; i < points.size(); i++) { current = *(points[i]); glVertex3f(current.x, current.y, current.z); } glEnd(); } }; ----------------------------- the reason for storing all the points in one big data structure and then referencing them makes it easier to select the lines and points later on. the "allpoints" in the final implementation is really a vector std::vector sector[GRID_SIZE][5][GRID_SIZE]; when a point is created it is assigned to a sector based on its x, y, z coordinates (forget about that for now) when a point is selected i want it to flag "selected = true" by changing its value through the allpoints vector. then when the line is drawn it checks the value of each of its points to see if any has been selected (this is why i use pointers so it checks the actual point and not a copy of it), if so it will change to a different colour. Rajkumar: I am using opengl with sdl and im not all that bothered about how fast the system runs as its only really a proof of concept. when i wasnt using pointers the system ran fast (but not using pointers meant that things couldnt be selected) thanks kevin
-
Ok thanks for replying Max: Thats basically the design I have but without the geometry class. I am never going to be able to draw a point, it is simply used to construct a line (the system is only going to be able to draw lines) Pallini, Rajkumar: Heres some code: --------------------------------- // holds all the lines std::vector lines; // holds all the points std::vector allpoints; struct Point { public: GLfloat x, y, z; bool selected; /* constructors */ Point() { } Point(const GLfloat & xval, const GLfloat & yval, const GLfloat & zval) { } Point(const Point & from) { } }; /* a class to describe a line in 3 dimensional space */ class Line { public: // each pointer in this vector should point to a Point object in allpoints std::vector points; bool selected; // Initializes variables Line() { } Line(int typein) { } // Functions void addPoint(Point & p) { points.push_back(&p); } void draw() // ive only included part of it { Point current; glLineWidth(thickness); glColor3fv(color); glBegin(GL_LINE_STRIP); for (int i = 0; i < points.size(); i++) { current = *(points[i]); glVertex3f(current.x, current.y, current.z); } glEnd(); } }; ----------------------------- the reason for storing all the points in one big data structure and then referencing them makes it easier to select the lines and points later on. the "allpoints" in the final implementation is really a vector std::vector sector[GRID_SIZE][5][GRID_SIZE]; when a point is created it is assigned to a sector based on its x, y, z coordinates (forget about that for now) when a point is selected i want it to flag "selected = true" by changing its value through the allpoints vector. then when the line is drawn it checks the value of each of its points to see if any has been selected (this is why i use pointers so it checks the actual point and not a copy of it), if so it will change to a different colour. Rajkumar: I am using opengl with sdl and im not all that bothered about how fast the system runs as its only really a proof of concept. when i wasnt using pointers the system ran fast (but not using pointers meant that things couldnt be selected) thanks kevin
This approach won't work if you store the addresses of pointers which are in an STL structure rather than indexes into the structure. STL moves the pointers around when you add stuff because it tends to store stuff in red/black balanced trees internally. As soon as it moves things around to keep its trees balanced your pointers to pointers become pointers to garbage. In other words you have to treat STL containers as black boxes and not make assumptions about how they store stuff. Once you put something in a std::vector or std::map the std::vector or std::map owns it and can do what it wants. :)
Nothing is exactly what it seems but everything with seems can be unpicked.
-
Ok thanks for replying Max: Thats basically the design I have but without the geometry class. I am never going to be able to draw a point, it is simply used to construct a line (the system is only going to be able to draw lines) Pallini, Rajkumar: Heres some code: --------------------------------- // holds all the lines std::vector lines; // holds all the points std::vector allpoints; struct Point { public: GLfloat x, y, z; bool selected; /* constructors */ Point() { } Point(const GLfloat & xval, const GLfloat & yval, const GLfloat & zval) { } Point(const Point & from) { } }; /* a class to describe a line in 3 dimensional space */ class Line { public: // each pointer in this vector should point to a Point object in allpoints std::vector points; bool selected; // Initializes variables Line() { } Line(int typein) { } // Functions void addPoint(Point & p) { points.push_back(&p); } void draw() // ive only included part of it { Point current; glLineWidth(thickness); glColor3fv(color); glBegin(GL_LINE_STRIP); for (int i = 0; i < points.size(); i++) { current = *(points[i]); glVertex3f(current.x, current.y, current.z); } glEnd(); } }; ----------------------------- the reason for storing all the points in one big data structure and then referencing them makes it easier to select the lines and points later on. the "allpoints" in the final implementation is really a vector std::vector sector[GRID_SIZE][5][GRID_SIZE]; when a point is created it is assigned to a sector based on its x, y, z coordinates (forget about that for now) when a point is selected i want it to flag "selected = true" by changing its value through the allpoints vector. then when the line is drawn it checks the value of each of its points to see if any has been selected (this is why i use pointers so it checks the actual point and not a copy of it), if so it will change to a different colour. Rajkumar: I am using opengl with sdl and im not all that bothered about how fast the system runs as its only really a proof of concept. when i wasnt using pointers the system ran fast (but not using pointers meant that things couldnt be selected) thanks kevin
I cannot understand completely you code (maybe some
<pre>TAGs probably will help), however IMHO you may have some troubles if memory reallocation happens (and it can happen) in the global vector, beacause the pointers stored in yourLineclass loose sense. :)If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
-
This approach won't work if you store the addresses of pointers which are in an STL structure rather than indexes into the structure. STL moves the pointers around when you add stuff because it tends to store stuff in red/black balanced trees internally. As soon as it moves things around to keep its trees balanced your pointers to pointers become pointers to garbage. In other words you have to treat STL containers as black boxes and not make assumptions about how they store stuff. Once you put something in a std::vector or std::map the std::vector or std::map owns it and can do what it wants. :)
Nothing is exactly what it seems but everything with seems can be unpicked.
ah right, thanks very much. would it be sensible to create my own data structure then?
-
I cannot understand completely you code (maybe some
<pre>TAGs probably will help), however IMHO you may have some troubles if memory reallocation happens (and it can happen) in the global vector, beacause the pointers stored in yourLineclass loose sense. :)If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
yeh i think its a memory reallocation issue. im new to this whole pointers thing, ill get it eventually!
-
ah right, thanks very much. would it be sensible to create my own data structure then?
I would :) Most people will advise you to use the stl constainers because they are fast and reliable. I think for an experimental app like this you'd learn more by creating your own data structures. It's not as hard as you'd think.
Nothing is exactly what it seems but everything with seems can be unpicked.
-
I would :) Most people will advise you to use the stl constainers because they are fast and reliable. I think for an experimental app like this you'd learn more by creating your own data structures. It's not as hard as you'd think.
Nothing is exactly what it seems but everything with seems can be unpicked.
ok, thanks very much
-
Hi, First of all your approach of using STL classes for 3D drawing system is not so good. 3D graphics being a expensive operation on computer, experts are using hardware accelerated methods like using graphics library like DirectX, openGL. stl::Vector is an expensive array is inefficient for such application. Then, what do you mean by reference, reference to vector item. please post some code snippet.
Rajkumar_R wrote:
First of all your approach of using STL classes for 3D drawing system is not so good.
STL is not a graphic API, but we still need to keep our data somewhere before sending it to OpenGL or DirectX.
Maximilien Lincourt Your Head A Splode - Strong Bad
-
Rajkumar_R wrote:
First of all your approach of using STL classes for 3D drawing system is not so good.
STL is not a graphic API, but we still need to keep our data somewhere before sending it to OpenGL or DirectX.
Maximilien Lincourt Your Head A Splode - Strong Bad
Hi, sure STL is not graphic API, These data structure has tradeoffs for speed and also memory consumption is high. consider accessing a item of vector; it involves more than one indirection of reference and more than one call path vector<char> vecObj; char c = vecObj[3] is very slow compared to a simple char Array[10]; char c = Array[3]; For 3D graphics, rendering millions of triangles in fraction of second, the data structure that keeps the data should be fast, When you get time try using directX, they use their own data structure's for these purpose which is usually a buffer, and also possibly they manage to keep data in hardware cache. Best Regards Raj
-
Hi, sure STL is not graphic API, These data structure has tradeoffs for speed and also memory consumption is high. consider accessing a item of vector; it involves more than one indirection of reference and more than one call path vector<char> vecObj; char c = vecObj[3] is very slow compared to a simple char Array[10]; char c = Array[3]; For 3D graphics, rendering millions of triangles in fraction of second, the data structure that keeps the data should be fast, When you get time try using directX, they use their own data structure's for these purpose which is usually a buffer, and also possibly they manage to keep data in hardware cache. Best Regards Raj
unfortunately time is something I dont have, this is a research project so I have to finish the program off by the end of the month at the latest so I can get onto writing a report. fortunately I dont require millions of triangles to be rendered, only a few thousand. Its a simple 3d sketching package. thanks for everyone's input
-
Hi, sure STL is not graphic API, These data structure has tradeoffs for speed and also memory consumption is high. consider accessing a item of vector; it involves more than one indirection of reference and more than one call path vector<char> vecObj; char c = vecObj[3] is very slow compared to a simple char Array[10]; char c = Array[3]; For 3D graphics, rendering millions of triangles in fraction of second, the data structure that keeps the data should be fast, When you get time try using directX, they use their own data structure's for these purpose which is usually a buffer, and also possibly they manage to keep data in hardware cache. Best Regards Raj
Rajkumar_R wrote:
vector vecObj; char c = vecObj[3] is very slow compared to a simple char Array[10]; char c = Array[3];
Nonsense. All of a
std::vectors functions are smallinlinefunctions. Using avectoris, in most cases, just as efficient.Steve
-
unfortunately time is something I dont have, this is a research project so I have to finish the program off by the end of the month at the latest so I can get onto writing a report. fortunately I dont require millions of triangles to be rendered, only a few thousand. Its a simple 3d sketching package. thanks for everyone's input
There is nothing wrong with using
std::vectors. Contrary to what some people have been saying, in most cases using avectoris just as fast as using raw memory allocation functions.Steve
-
Rajkumar_R wrote:
vector vecObj; char c = vecObj[3] is very slow compared to a simple char Array[10]; char c = Array[3];
Nonsense. All of a
std::vectors functions are smallinlinefunctions. Using avectoris, in most cases, just as efficient.Steve
Hi Steve, Thanks for your comments, But I would like you to see the code in low level, This is the dissasembly of code for vector and normal array simple array
c = Array[2];
00411A2F mov al,byte ptr [ebp-0DAh]
00411A35 mov byte ptr [ebp-0A5h],alvector
c = vecObj[2];
00411A1A push 2
00411A1C lea ecx,[ebp-0D0h]
00411A22 call std::vector >::operator[] (4114ECh)
00411A27 mov al,byte ptr [eax]
00411A29 mov byte ptr [ebp-0A5h],aland the call to operator [] disassembles to
reference operator[](size_type _Pos)
{ // subscript mutable sequence
00411E40 push ebp
00411E41 mov ebp,esp
00411E43 sub esp,0CCh
00411E49 push ebx
00411E4A push esi
00411E4B push edi
00411E4C push ecx
00411E4D lea edi,[ebp-0CCh]
00411E53 mov ecx,33h
00411E58 mov eax,0CCCCCCCCh
00411E5D rep stos dword ptr es:[edi]
00411E5F pop ecx
00411E60 mov dword ptr [ebp-8],ecx#if _HAS_ITERATOR_DEBUGGING
if (size() <= _Pos)
00411E63 mov ecx,dword ptr [this]
00411E66 call std::vector >::size (41159Bh)
00411E6B cmp eax,dword ptr [_Pos]
00411E6E ja std::vector >::operator[]+0A8h (411EE8h)
{
_DEBUG_ERROR("vector subscript out of range");
00411E70 mov esi,esp
00411E72 push 2F4h
00411E77 push offset string L"c:\\program files\\mic"... (41B8B0h)
00411E7C push offset string L"vector subscript out"... (41B868h)
00411E81 call dword ptr [__imp_std::_Debug_message (41F3D0h)]
00411E87 add esp,0Ch
00411E8A cmp esi,esp
00411E8C call @ILT+835(__RTC_CheckEsp) (411348h)
_SCL_SECURE_OUT_OF_RANGE;
00411E91 xor eax,eax
00411E93 jne std::vector >::operator[]+80h (411EC0h)
00411E95 mov esi,esp
00411E97 push offset string L"("Standard C++ Libra"... (41B800h)
00411E9C push 0
00411E9E push 2F5h
00411EA3 push offset string L"c:\\program files\\mic"... (41B8B0h)
00411EA8 push 2
00411EAA call dword ptr [__imp___CrtDbgReportW (41F4D4h)]
00411EB0 add esp,14h
00411EB3 cmp esi,esp
00411EB5 call @ILT+835(__RTC_CheckEsp) (411348h)
00411EBA cmp -
Hi Steve, Thanks for your comments, But I would like you to see the code in low level, This is the dissasembly of code for vector and normal array simple array
c = Array[2];
00411A2F mov al,byte ptr [ebp-0DAh]
00411A35 mov byte ptr [ebp-0A5h],alvector
c = vecObj[2];
00411A1A push 2
00411A1C lea ecx,[ebp-0D0h]
00411A22 call std::vector >::operator[] (4114ECh)
00411A27 mov al,byte ptr [eax]
00411A29 mov byte ptr [ebp-0A5h],aland the call to operator [] disassembles to
reference operator[](size_type _Pos)
{ // subscript mutable sequence
00411E40 push ebp
00411E41 mov ebp,esp
00411E43 sub esp,0CCh
00411E49 push ebx
00411E4A push esi
00411E4B push edi
00411E4C push ecx
00411E4D lea edi,[ebp-0CCh]
00411E53 mov ecx,33h
00411E58 mov eax,0CCCCCCCCh
00411E5D rep stos dword ptr es:[edi]
00411E5F pop ecx
00411E60 mov dword ptr [ebp-8],ecx#if _HAS_ITERATOR_DEBUGGING
if (size() <= _Pos)
00411E63 mov ecx,dword ptr [this]
00411E66 call std::vector >::size (41159Bh)
00411E6B cmp eax,dword ptr [_Pos]
00411E6E ja std::vector >::operator[]+0A8h (411EE8h)
{
_DEBUG_ERROR("vector subscript out of range");
00411E70 mov esi,esp
00411E72 push 2F4h
00411E77 push offset string L"c:\\program files\\mic"... (41B8B0h)
00411E7C push offset string L"vector subscript out"... (41B868h)
00411E81 call dword ptr [__imp_std::_Debug_message (41F3D0h)]
00411E87 add esp,0Ch
00411E8A cmp esi,esp
00411E8C call @ILT+835(__RTC_CheckEsp) (411348h)
_SCL_SECURE_OUT_OF_RANGE;
00411E91 xor eax,eax
00411E93 jne std::vector >::operator[]+80h (411EC0h)
00411E95 mov esi,esp
00411E97 push offset string L"("Standard C++ Libra"... (41B800h)
00411E9C push 0
00411E9E push 2F5h
00411EA3 push offset string L"c:\\program files\\mic"... (41B8B0h)
00411EA8 push 2
00411EAA call dword ptr [__imp___CrtDbgReportW (41F4D4h)]
00411EB0 add esp,14h
00411EB3 cmp esi,esp
00411EB5 call @ILT+835(__RTC_CheckEsp) (411348h)
00411EBA cmpThat's because you're looking at the code in a debug build (which means function inlining is disabled). I can also see you've got iterator debugging and range checking enabled. In short your comparison is flawed. Here's a disassembly for a release build (using MSVC6): For the raw array:
16: int raw = IntRaw[0];
004010DC mov eax,dword ptr [esi]For the vector:
20: int vec = IntVec[0];
0040113B mov eax,dword ptr [ebp]Here's the whole program used:
// VectorTest.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <vector>
#include <iostream>
int main(int argc, char* argv[])
{
using namespace std;
int *IntRaw = new int[10];
vector<int> IntVec(10, 0);
// Raw.
int raw = IntRaw[0];
cout << raw << endl;
// Vector.
int vec = IntVec[0];
cout << vec << endl;
return 0;
}Steve
-
That's because you're looking at the code in a debug build (which means function inlining is disabled). I can also see you've got iterator debugging and range checking enabled. In short your comparison is flawed. Here's a disassembly for a release build (using MSVC6): For the raw array:
16: int raw = IntRaw[0];
004010DC mov eax,dword ptr [esi]For the vector:
20: int vec = IntVec[0];
0040113B mov eax,dword ptr [ebp]Here's the whole program used:
// VectorTest.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <vector>
#include <iostream>
int main(int argc, char* argv[])
{
using namespace std;
int *IntRaw = new int[10];
vector<int> IntVec(10, 0);
// Raw.
int raw = IntRaw[0];
cout << raw << endl;
// Vector.
int vec = IntVec[0];
cout << vec << endl;
return 0;
}Steve
Hi, I have posted already the release build disassembly. please check
-
Hi, I have posted already the release build disassembly. please check
-
Hi, if we disabled range checking it affects all STL containers we use . Yes, the comparison is not fair so i said raw array and vector are different. This is only a simply operator we have other operators/ interface that have more expensive operations. A single additional instruction will be neglegible for application which uses it less frequently. IN 3D graphics application, point(vertex) is the building block. Millions of triangle for single 3D object will have 3*Millions of vertex. a single additional instruction will have 3*Million instruction this will reduce the performance. I repeat I put simple example operator [], but for other interfaces we can't even set _SECURE_SCL like definition to 0. Yes STL is best. But I just want to ensure the above statement. Mr. kevinbrydon may use this application for thousand of triangle today, he may use it for millions of triangle tomorrow. Best Regards Raj
-
Hi, if we disabled range checking it affects all STL containers we use . Yes, the comparison is not fair so i said raw array and vector are different. This is only a simply operator we have other operators/ interface that have more expensive operations. A single additional instruction will be neglegible for application which uses it less frequently. IN 3D graphics application, point(vertex) is the building block. Millions of triangle for single 3D object will have 3*Millions of vertex. a single additional instruction will have 3*Million instruction this will reduce the performance. I repeat I put simple example operator [], but for other interfaces we can't even set _SECURE_SCL like definition to 0. Yes STL is best. But I just want to ensure the above statement. Mr. kevinbrydon may use this application for thousand of triangle today, he may use it for millions of triangle tomorrow. Best Regards Raj
Rajkumar_R wrote:
if we disabled range checking it affects all STL containers we use .
That's exactly what I want to happen in a release build. In my opinion, and that of many others, checked iterators should not be enabled in release builds by default anyway. I use code like this in my precompiled header to get it to work this way:
#ifdef NDEBUG
#define _SECURE_SCL 0
#endifI encourage you to do this and have another look at the release build's machine code. For most operations a
vector's performance will be the same as that of a raw array (as it was in the MSVC6 code I posted). All the member functions are simpleinlinefunctions.Steve
-
There is nothing wrong with using
std::vectors. Contrary to what some people have been saying, in most cases using avectoris just as fast as using raw memory allocation functions.Steve
Stephen Hewitt wrote:
Contrary to what some people have been saying, in most cases using a vector is just as fast as using raw memory allocation functions.
Hey Stephen, I just stumbled upon this old thread. In general or specifically for business apps STL is more than adequate. However I do have some minor experience in Console Gaming development and for the graphics rendering I do believe the point being made about DirectX for example might be valid. Rendering, several years back when I was involved, was a huge bottleneck and some advances have been made in that area and I seem to remember reading about what Rajkumar_R is talking about in DirectX. For production graphics I would think one would certainly want to use the current approach being supported by any particular graphics platform.
led mike
