• Advertisement
Sign in to follow this  

std::vector and operator [] ?

This topic is 4286 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

i am curious. what is the [] operator from the vector good for? i don't like the way for these sequence containers to loop through an array. i prefer a normal for( int i=0;i<Count;i++) blub.Draw(); but this doesn't work when i've defined blub std::vector<CBlub*> *blub but why? what do i need this vector for if not to use it to access the members of this element? do i really need to make it this way? std::vector<CBlub*>::iterator i; for(i = blub->begin(); i != blub->end(); i++) (*i)->Draw(); apart from that. i've got another question, what kind of speed impact do these containers have when i loop through them instead of just using a normal array CBlub *blub and loop then through every element? i'm asking because i've written a simple level loader, wich loads every object and to save these objects i use vectors. to perform the draw and movement etc.. for every object in my level, i would need to loop through these arrays several times per frame. how big is the impact on my frametime? i know i could just give the pointer from the sequence container to a standart array, but i would like to know if it is nessecary, regarding speed.

Share this post


Link to post
Share on other sites
Advertisement
The [] operator works regardless of what the vector holds. In release builds the vector operator [] should compile to about the same speed as a raw array. If you need a fixed size array, then feel free to use a fixed size array. If you need the dynamic sizing of a vector, use the vector and you get essentially the same access speed as a raw array.

Share this post


Link to post
Share on other sites
If you have a std::vector< CBlub * > * blub; then to iterate through it using operator[] you would need to do:
for (int i = 0; i < Count; ++i)
{
(*blub)->Draw();
}
blub is a pointer to a vector, so you must dereference it before you can access it. Likewise, the vector that blub points to contains pointers, so you must dereference them before you can access them. The real question is why you're using a pointer to a vector of pointers, rather than just std::vector< CBlub > blub, which would allow your first example to compile as written.

As to the difference between a std::vector< CBlub > and a dynamically allocated CBlub *, in the worst case the overhead will be insignficant (the possible construction and destruction of a few additional CBlub objects) while in the best case std::vector will be far more efficient thanks to the separation of memory allocation and initialization. This is of course with full optimisations and provided that you use vector sensibly. There will be absolutely no difference in the time it takes to loop through a vector as opposed to a dynamically allocated array.

Σnigma

Share this post


Link to post
Share on other sites
EDIT: Wow, am I slow [smile]

Quote:
Original post by SiS-Shadowman
i am curious. what is the [] operator from the vector good for?

It allows you to use the vector like you would an array, which means that your code that iterates using the index will work just fine.

Quote:
but this doesn't work when i've defined blub std::vector<CBlub*> *blub but why? what do i need this vector for if not to use it to access the members of this element?


It doesn't work because you're using pointers everywhere. You'll need to dereference them like so:

for(int i=0 ; i<Count ; i++)
(*blub)->Draw();


Now, if you had just defined blub as std::vector<CBlub> blub then you could use your first block of code as is.

Quote:
apart from that. i've got another question, what kind of speed impact do these containers have when i loop through them instead of just using a normal array CBlub *blub and loop then through every element?


When you do a release build (ie. optimisations are turned on), a std::vector should have exactly the same performance as an array when accessing elements. Inserting and removing will have a performance hit because of the dynamic memory allocation and re-shuffling of elements (unless you only insert or remove from the end of the vector), which is why you should make sure your using the right container. For example, if you were doing a lot of insertions/removes at random locations in a large dataset a std::list might be a better choice. For what your doing a vector sounds fine though.

Share this post


Link to post
Share on other sites
hm, i thanks for the quick answer.
i haven't worked much with these things yet. i only read some examples at http://cplus.about.com/od/stltutorial/l/aa110103a.htm about these sequence containers.

so basicly, what you say enigma, is that i shouldn't use any pointers with these vectors?

i think i don't fully understand how it works. just to show you how i use it.

std::vector<CMesh*> *Mesh;
CMesh *NewMesh;
while(!EOF(pfile)) // i use tinyxml, but this would be the same for now...
{
// read the file etc...
NewMesh = new Cmesh;
NewMesh->LoadMeshFile( some parameters from the file.. );

Mesh->insert(Mesh->end(), NewMesh);
}




this is because i don't know how many objects i have to load out of the file.
but will it also work if i just have a CMesh NewMesh and insert it every time? i'm very unshure about it.
does the CMesh NewMesh now have to be in the array, so that everytime a new mesh gets created?

i'll try it out, but i need some assurance, the app works now and i don't want to screw it up ^^ i have done that too often.

Share this post


Link to post
Share on other sites
I'm not saying you should never use pointers with vectors, I'm saying that if it makes sense to use a Class * array = new Class[dimension];, then it makes sense to use a std::vector< Class > array;.

I hope that example code isn't a direct copy from your project because it has undefined behaviour - you never actually allocate your vector. Assuming that just a error in your post the following would be equivalent (and potentially more efficient depending upon how heavyweight CMesh is):
std::vector< CMesh > Mesh;
while(!EOF(pfile)) // i use tinyxml, but this would be the same for now...
{
CMesh mesh;
mesh.LoadMeshFile(/*parameters*/);
Mesh.push_back(mesh);
}
Of course, what would be even better would be if you were to rewrite CMesh so that initialization occurs in the constructor, in which case you could use:
std::vector< CMesh > Mesh;
while(!EOF(pfile)) // i use tinyxml, but this would be the same for now...
{
Mesh.push_back(CMesh(/*parameters*/));
}
Σnigma

Share this post


Link to post
Share on other sites
*thinking* now i see what your point is. ofcourse i'll allocate space for Mesh, it was just to show you what pointers i am using.

one last question ( i think ):

since we aren't dealing with pointers in your loop, the mesh objects gets copied one more time, isn't it? since it will be first initiated in the loop, then it is given as an argument to the vector, wich copies this element into it's own memory. won't that consume much time? i think about later, when i've several hundreds of objects in my scene and every one has not so less vertices ( wich results in big vertex/index buffers ) textures etc...

wouldn't it be better to just use
std::vector<CMesh*> Mesh;
and then just give the pointer to the allocated new mesh from the loop to Mesh?

my understanding of c++ doesn't go that far, it just sounds logical to me, but i've been wrong very often about that, so i just ask :)

Share this post


Link to post
Share on other sites
Quote:
Original post by SiS-Shadowman
wouldn't it be better to just use
std::vector<CMesh*> Mesh;
and then just give the pointer to the allocated new mesh from the loop to Mesh?


To tell you the truth, a good optimizing compiler (and the Microsoft one isn't too bad in that respect) will use some common optimization techniques to construct the Mesh object in place in the vector, so only one Mesh ever needs to be constructed and you don;t have to worry about pointers (and their attendant risks).

You would use the Mesh objects in the vector by using references to them.

The biggest problem would be that if the vector gets resized, them Mesh objects get copied. If there's a way to determine how many Mesh objects will ultimately be added to your vector, you can avoid that problem as well with the reserve() member function.

Using a vector of pointers will also eliminate deep vector copies and resizing of the vector is mush cheaper, but then you have to worry about explicit object lifetime control, invalid pointers, and the rest of the pointer snakepit.

Share this post


Link to post
Share on other sites
Quote:
Original post by SiS-Shadowman
*thinking* now i see what your point is. ofcourse i'll allocate space for Mesh, it was just to show you what pointers i am using.

one last question ( i think ):

since we aren't dealing with pointers in your loop, the mesh objects gets copied one more time, isn't it? since it will be first initiated in the loop, then it is given as an argument to the vector, wich copies this element into it's own memory. won't that consume much time? i think about later, when i've several hundreds of objects in my scene and every one has not so less vertices ( wich results in big vertex/index buffers ) textures etc...

wouldn't it be better to just use
std::vector<CMesh*> Mesh;
and then just give the pointer to the allocated new mesh from the loop to Mesh?

my understanding of c++ doesn't go that far, it just sounds logical to me, but i've been wrong very often about that, so i just ask :)


You're correct for the wrong reasons.

Yes, if you had vector<Vertex> (as your vertex buffer) in your classes you'd spend ages copying that mesh into vector<CMesh>. However, your vertex buffers and index buffers and whatnot will generally be pointers to the data themselves, so they'll only occupy 4 bytes (whatever), which isn't much to copy. So you could store all your meshes in a vector<CMesh> without worrying, since at most they might have ~64 bytes, or more if you give your meshes names.

However: Since you're looking ahead to the future - you'd probably want your meshes to be stored in the vector as a pointer. This is because you may want many instances of the same mesh (for example, lots of the same tree) - so instead of giving each new model a new mesh with new vertices/indices, using lots and lots of memory, you could just give each model a pointer to just one mesh, and let them render that. Voila, memory saved!

You may want to look into boost::shared_ptr for that, though. If you feel it's beyond the scope of your abilities, don't worry - use regular pointers instead. You can always rewrite. Link to boost can be found in my signature.

Hope that helps.

Share this post


Link to post
Share on other sites
Quote:
Original post by Bregma
To tell you the truth, a good optimizing compiler (and the Microsoft one isn't too bad in that respect) will use some common optimization techniques to construct the Mesh object in place in the vector, so only one Mesh ever needs to be constructed and you don;t have to worry about pointers (and their attendant risks).


And if you are REALLY worried about it, just do Mesh.resize(Mesh.size()+1), which is ugly, but pretty much forces the new object to be created in place. Less, but still pretty likely to do that is Mesh.push_back(CMesh());
In both cases you would use Mesh.back() to get to the new object.

But as meshes are usually somewhat big (unless THEY use vectors for their data as well), it's not as critical to have them close to each other in memory for iterating and pointers would be a better choice. If this vector will have multiple pointers to the same mesh, it will be tricky to delete them later, so find a place where you manage a list with pointers to all mesh instances. (Somehow I prefer using a simple template manager class to derive stuff like mesh or texture classes from, especially since loading functions pretty much always follow the scheme "see if we loaded this file already and return pointer to existing data or load it".. and there's not much point in writing it again for all kinds of different ressources).

One thing that you should NOT do. NEVER even think about pulling a stunt like game_object.mesh=&Mesh[x], unless you can be absolutely sure that your vector never grows or has more than enough memory reserved. You don't want it to grow, be moved to a completely different address and invalidate pretty much every single mesh pointer in your program. Use the index instead, even if you dislike the small indirection.

Share this post


Link to post
Share on other sites
Quote:
Original post by _goat
However: Since you're looking ahead to the future - you'd probably want your meshes to be stored in the vector as a pointer. This is because you may want many instances of the same mesh (for example, lots of the same tree) - so instead of giving each new model a new mesh with new vertices/indices, using lots and lots of memory, you could just give each model a pointer to just one mesh, and let them render that. Voila, memory saved!


i've done that some hours ago. i've got an vector container wich contains each mesh, that will be used in the level.
and i've got one container for each object ( since trees will be animated in the future etc.. ) wich just holds the pointer to the right mesh in CMesh.

thanks for your help. i've now a better understanding of these vectors, lists etc..

One thing that you should NOT do. NEVER even think about pulling a stunt like game_object.mesh=&Mesh[x], unless you can be absolutely sure that your vector never grows or has more than enough memory reserved

i am not shure, if my approach is correct. what i do at a level load is:

loop through the file
{
search for the next object and check out the model name
search for the model name in Mesh, if it occurs there, get the index, if not
add one model to the end of Mesh and retrieve its index

instance the correct class for the object ( tree, wall etc.. )
give the pointer model[index] to the currently instanced class
}




will this work? i haven't tested it with different models, since i my model loader is outdated and needs to read my new model format ( for wich i don't have new models )
i hope it does. if not, what would you do?

btw: after the file is loaded, i will never modify the Mesh vector again, and i will only insert new elements at the end.

Share this post


Link to post
Share on other sites
Your description of your loading process is a little too ambiguous/general for me to be able to critique with any valid input. It sounds like you won't get any crazy error pointers if you search for the mesh by name and return its index. However:

Quote:
Original post by SiS-Shadowman
btw: after the file is loaded, i will never modify the Mesh vector again, and i will only insert new elements at the end.


Warning! The vector class allows you to push_back elements happily because when you run out of space (it works just like an array, remember) it'll allocate a whole new bunch of space that's bigger, copy the old memory to the beginning of that space, and push_back the element into some of the remainder of the new space. You can not

... wait. You said that in your post. I guess you mean you'll take then index of the mesh in the vector? That's garuanteed never to change, so that's all good then. Carry on. Have fun.

Share this post


Link to post
Share on other sites
hm, i wanted that each class of an object just holds the pointer to the wanted mesh, but that could be problematic if i understand you right.

now each object has a std::vector<CMesh*> *Mesh pointer and the index for its mesh. i would have preferred the other way, but that is ok. thanks very much :)

Share this post


Link to post
Share on other sites
I'm not sure I understand why you want a pointer to a vector of mesh pointers?

Are more than one object going to point to the same vector of mesh pointers? Are they sharing mesh lists - so that you want changing one to change all. I realize that may be what you want if you are loading dozens of objects, all of which use the same set of meshes, but just checking. Otherwise it seems you might want std::vector<CMesh*> meshes; instead

Share this post


Link to post
Share on other sites
Quote:
Original post by SiS-Shadowman
hm, i wanted that each class of an object just holds the pointer to the wanted mesh, but that could be problematic if i understand you right.


If you FIRST load all meshes and only start handing out pointers once you don't add anything to the mesh array, then nothing should happen. But if you return pointers to vector elements before it stopped growing, you might run into trouble.

Quote:
now each object has a std::vector<CMesh*> *Mesh pointer and the index for its mesh. i would have preferred the other way, but that is ok. thanks very much :)


How many Mesh vectors are there? Or is that just because of some "globals are evil and I want a squeaky clean design" approach?

However, if you only store pointers to meshes and don't put the actual instances in a vector, then they won't change either. Of course then they might end up all over the place and freeing them later on could cause some nice memory fragmentation.

A compromise might be using a deque. Never experimented with it, but if I get the description right, it's basically vector-like chunks. So when you grow a deque beyond it's current capacity, it won't copy anything, but start a new block. Drawback is the hidden indirection, because when you access it by index, it has to do a lookup in a map to find the correct block.

Because they are usually using power of two sizes for the blocks, adjusting the index is a simple index>>x (x/block_size) to find the block and index&(x-1) (x%block_size) to get the index within the block. And actually, I'm not even sure why they would use a map for block addresses, when a vector would do (so I take it, they used map in a general sense meaning "table" and not std::map). However, using direct pointers to the actual data should be safe, so the overhead for random access won't matter much anyway.

In short, a deque is a good compromise, if you want your data aligned next to each other to avoid cache misses (ie. if you intend to iterate of the data a lot), but can't forsee the eventual size and don't want lots of resizing and copying large amounts of stuff around either.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement