Removing an element and resizing a vector

[monkeycracks]

I'm holding some objects in a std::vector and I'm not quite sure how to go about removing a choice element from the vector and resizing it(if this is even necessary).

So far I've got this :

Code: Select all

for(int x = 0; x < (int)vec.size(); x++)
			{
				if(vec[x] == pointertoobject)
				{	
					delete vec[x];
				}
			}

This is great and all, but should I be removing it from the vector somehow using the erase() method and then resizing it so that there's not a blank spot?

Bleh, maybe I'm just braindead from lack of sleep. Either way, hayulp ?

[JP]

With std::vector i think you generally have to use the iterators to go through the objects if you're planning on removing anything...

If you use a core::array then you don't have to use iterators at all so that might be easier for you, you can just do array.erase(index) to remove it from the array.

Of course you may be better off using a core::list (do you know when you should use lists or arrays?) in which case you'd pretty much have to use an iterator again. Iterators are a bit different to use and can be easy to mess up if you forget to increment them but check them out as they're not too hard.

Here's some small improvements to your code snippet:

Code: Select all

for(int x = 0; x < (int)vec.size(); x++) 
         { 
            if(vec[x] == pointertoobject) 
            {    
               delete vec[x]; 
               // make sure you erase it from the vector otherwise you'll leave an invalid reference here, if anything you should definetly make it NULL!
               break; // why would you keep iterating through the rest of the array needlessly? (unless of course it's possible to have repeated entries! which would probably be bad anyway...)

            } 
         }

[monkeycracks]

Thanks JP. I never would've caught the break. I was thinking using a list might be better here, but I wasn't really sure. I've never really gone in-depth with iterators, lists, and vectors so maybe I'll do some reading then.

[BlindSide]

Btw, I would use binary_search here (In core::array) instead of looping over everything, its O(logN). And if you don't need it to be in-order, you can just copy the last element over the one you are deleting and set_used(size() - 1).

[monkeycracks]

Code: Select all

std::list<Object*>::iterator i;
				for(i = objList.begin(); i != objList.end(); i++)
				{
					if((*i) == PointerToObject)
					{
						delete (*i);
						objList.erase(i);
						break;
					}
				}

Correct?


Edit :
Blindside, I would try that, but I switched to an std::list rather than std::vector. Is there any advantage to using the Irrlicht containers over the STL ones?

[BlindSide]

Nope, I'm not sure if std::vector has binary_search however, it would probably be implemented in <algorithm> through an exterior function rather than a member function in the stl.

[monkeycracks]

Sweet, well thruogh some printfs I've found that it behaves as expected and automatically resizes, so I'm pretty happy. Thanks for the nudge towards iterators and stuff.

[JP]

But blindside... binary search requires the array to be in order

[BlindSide]

But blindside... binary search requires the array to be in order

core::array automatically does a heap sort before performing a binary search, and then flags that the array is sorted until an element is changed.

[JP]

Aye fair point, irrlicht's sensible, i don't think std::vectors are though, are they?

Oh and remembering that Irrlicht's heap sort doesn't work for pointers so if your array has pointers in it then binary search and sorting is unlikely to work!

[vitek]

Aye fair point, irrlicht's sensible, i don't think std::vectors are though, are they?

The sort flag is not part of a std::vector<>. The C++ Standard Library does not require it, and doing so would go against the design principles of the library. It is wrong to force users to pay the cost (size or space) for features that they may not use. It is trivial to write a std::vector<> wrapper that maintains a sorted ordering. You could also use a std::set<> or std::multiset<>.

Oh and remembering that Irrlicht's heap sort doesn't work for pointers so if your array has pointers in it then binary search and sorting is unlikely to work!

Yeah. It really should seperate the sorting criteria from the sorting algorithm (i.e., sort should be done using a function object or function pointer, with an appropriate default). Having to create a new type to be able to apply sorting is annoying.

Travis

[BlindSide]

Oh and remembering that Irrlicht's heap sort doesn't work for pointers so if your array has pointers in it then binary search and sorting is unlikely to work!

Well I just use it for sorting the addresses of the pointers XD

I agree with what Vitek is saying, well not entirely (I mean, "size or space", aren't they the same thing?), and most std::vector implementation are quite buggy when it comes to custom sorting overloads, but I don't want to start another Std vs Core argument.

[Lambda]

just do vector.erase( vector.begin() + elementindex );

[monkeycracks]

I'm using a std::list now, and this was a good opportunity for me to learn iterators. Thanks for the tip on how to do it with vectors though.

[vitek]

(I mean, "size or space", aren't they the same thing?)

Yeah. Obviously I meant space and time...

and most std::vector implementation are quite buggy when it comes to custom sorting overloads

I happen to work at a company that sells a C++ Standard Library implementation, so I'd be curious to know what you're talking about. Perhaps you could create a testcase or just explain? I guess you could reply via PM if you don't want to start a big argument in this thread.

Travis