Man, I am utterly stuck on this. For reference: 1. I''m using vectors from the Standard Template Library. 2. "Task" is a class I defined. 3. "ready" is a pointer to a vector containing pointers to Task objects. I am trying to delete the first element in the vector. Shouldn''t this little bit of code do the trick? ready->erase( ready->begin() ); As far as I can tell in the debugger, it doesn''t do anything at all to the vector. the funny thing is that I have tested the code without pointers using this code: ready.erase( ready.begin() ); That works fine, but unfortunatly, I need to use pointers. Any help would be GREATLY appreciated.

Well, I am not sure because I am away from my reference docs but I think the problem may be that when you erase the object, it never actually removes is from the vector.

Maybe what you should be doing instead is swapping the element that you need to remove to the end of the vector and then call the function pop_back() on the vector. This way the element is remove from the vector.

Well, for starters, order is important in my vector, so swapping with the end would result in some bad things happening.

Since I posted this, I have tried pop_back() and even clear(), and neither seem to work. I have a feeling it may be a small bug related to what is being contained in my vectors (pointers to a class I defined).

Anyways, I think I am just going to switch to STL queues.

OK, from what I can see you have about 5 different issues here.

First and foremost: erasing from the beginning of a vector is an inefficient operation . If you need to erase from the beginning of your container, either you've got things in reverse order, or you need to use a different one.

Given that you shouldn't be using a vector anyway, I understand that you are creating a vector of Tasks, not a vector of Task pointers (i.e. Task*). Take a look at this program:

    #include <vector>#include <iostream>using std::vector;using std::cout;using std::endl;class Task{	static int m_nextInst;	int m_inst;public:	Task () : m_inst (m_nextInst++)	{		cout << m_inst << ": default ctor\n";	}	Task (const Task &org) : m_inst (m_nextInst++)	{		cout << m_inst << ": copy ctor from "			<< org.m_inst << endl;	}	Task &operator = (const Task &org)	{		cout << m_inst << ": assignment operator to "			<< org.m_inst << endl;		return *this;	}	~Task ()	{		cout << m_inst<< ": dtor\n";	}};int Task::m_nextInst = 0;int main (){	cout << "Beginning\n";	vector<Task> *ready = new vector<Task>;	ready->reserve (2);	Task t;	cout << "ready size = " << ready->size () << endl;	cout << "Pushing back t\n";	ready->push_back (t);	cout << "Pushing back t\n";	ready->push_back (t);	cout << "ready size = " << ready->size () << endl;	cout << "erasing beginning\n";	ready->erase (ready->begin ());	cout << "ready size = " << ready->size () << endl;	cout << "deleting ready\n";	delete ready;	cout << "end of program\n";	return 0;}    

This is a driver program that uses a class called "Task" that has value semantics. If you create a vector (or any STL container) of user-defined types, you should give it value semantics. This means that you should have a copy constructor and a assignment operator that "do the right things". Since my class doesn't have any important data, all the functions do is print out strings.

I also have instance counting, so you can tell which objects are being operated on. The program has this output, with the "line #)" added by me for discussion purposes.

line  1) Beginningline  2) 0: default ctorline  3) ready size = 0line  4) Pushing back tline  5) 1: copy ctor from 0line  6) Pushing back tline  7) 2: copy ctor from 0line  8) ready size = 2line  9) erasing beginningline 10) 1: assignment operator to 2line 11) 2: dtorline 12) ready size = 1line 13) deleting readyline 14) 1: dtorline 15) end of programline 16) 0: dtor  

So what's happening here?

Line 2 is the stack object "Task t;" being created--that's instance 0.

Line 5 is the vector push_back. If you use a vector of types, instead of pointers to types, push_back calls your class's copy constructor. So if you haven't written a correct copy constructor, you'll get unexpected results. Task instance 1 is created as a copy of instance 0, so 1 is the first element in the array.

Line 7 is the second push_back, which creates a new Task 2 as a copy of Task 0.

Line 10 and 11 show why it's a Bad Idea to erase from the beginning of a vector. When you erase anywhere in a vector, everything pass the point of deletion must by copied forward. So what you see is that the first element is assigned the value of the second element, copying its contents. Then the second element is deleted.

A similar thing must be done for insertions at the beginning of a vector; when you push_front on a vector, the entire contents of the vector must be copied forward, then the new element is copied onto the first element. This is why, for a vector, it's only efficient to use push_back and pop_back (or insert/erase on the iterator of the last value). Everything else requires copying all elements past the point of modification.

For the rest of the program, line 14 deletes the element that was in the vector; a vector automatically deletes all of its elements when it gets deleted. And finally, at the return 0, the stack object is deleted (line 16).

It's also interesting to note that, for a vector, if it grows past its bounds it must allocate more memory and copy the entire vector to the new location. Look at what my program output is if I delete the single line "ready->reserve (2)":

Beginning0: default ctorready size = 0Pushing back t1: copy ctor from 0Pushing back t2: copy ctor from 13: copy ctor from 01: dtorready size = 2erasing beginning2: assignment operator to 33: dtorready size = 1deleting ready2: dtorend of program0: dtor  

Now there are 3 instances and an extra dtor called. Why? Because the initial size of the vector is 1. When I push back the second element, it grows and needs to copy everything over, then delete the old vector.

This is just for a 2-element vector. If you have 10 or 20 or 200, imagine how much copying is going on!

So much for the tutorial on vectors. What's the solution to your problem? Well, one of two things, and maybe both:
1) Pick the right container. Only use a std::vector if you need to insert/delete at the end. Period. Anything else is inefficient. If you need to insert/delete at only the beginning and the end, a std::deque might be appropriate. If you need to be able to insert/delete from anywhere at any time, use a std::list. I have issues with the std::deque, but that's for another post. Personally, I only use vectors and lists for my non-sorted containers.
2) Consider an extra level of indirection. All STL containers must make at least one value-wise copy operation of an object stored in them; as you can see from above, sometimes there's a lot more than one copy operation. If your object is large, this will end up costing you a lot of cycles. A solution is to make the container hold pointers to objects instead of objects themselves. The benefit is that copying is extremely fast--just copies one pointer to another). The drawback is that there's an extra level of indirection for calls to the object. However, if you do a lot of operations at once, you can dereference once and then perform all the operations. Another drawback is that the container destructor will not destroy your objects; you must destroy them yourself.

Example:

vector&ltTask*> ready;ready.push_back (new Task);// ....vector&ltTask*>::iterator it = ready.begin ();// it acts like a Task**Task* pTask = *it; // this is the extra step added by indirectionpTask->method1 (); // so dereference once & make all the callspTask->method2 ();pTask->method3 (); // ...  

How's that for a lengthy discussion? I should really write an article on STL for gamedev. Maybe after my midterm on Tuesday.

Good luck. Oh, and as a final note: if you're using Microsoft Visual C++, be SURE to get the latest service pack; the released versions of MSVC++ 5.0 and 6.0 don't implement templates correctly, and a lot of STL functions will not work without the service packs.

Edited by - Stoffel on February 18, 2001 3:20:45 PM

quote: Original post by Washizu
I am trying to delete the first element in the vector. Shouldn't this little bit of code do the trick?

ready->erase( ready->begin() );

That will remove the first element from the vector, giving you a shorter vector and, if the element is an object, calling its destructor.

However, if you are expecting your Task destructor to be called, it won't happen. That's because the element being removed is a pointer to a Task, not a Task itself.

If you wanted the Task deleted, then you'll need to do that yourself...

    delete ready->front();ready->erase( ready->begin() );    

Oh, and don't even think about putting an auto_ptr<Task> into the vector. Putting auto_ptr's into STL containers is bad bad bad.


---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!


Edited by - mossmoss on February 18, 2001 3:45:37 PM

Thanks a ton for the education on STL containers. I''m still going over what you guys have written.

Two quick points:

1. I am using a vector of pointers to Task objects.
2. I misworded my original statement. I am not trying to delete the Task object, I am just trying to remove it from the vector. I still need that object for other reasons.

Here is a MUST READ website!
Mumit''s STL Newbie''s Guide: http://abel.hive.no/C++/STL/stlnew.html

You''re looking for the section on "Pointers and STL". Basically, you need a wrapper class, and if you''re using inheritance, you''ll need a more sophisticated wrapper...

I won''t steal his thunder, so check out his website.

Good luck!

Simon Wilson,
XEOS Digital Development

Ack, it appears I have failed you. I re-read your post and you DID say pointer-to-vector-containing-pointers-to-objects. Still, my main point was that you don''t want to be erasing from the beginning of a vector; if you have 100 elements, and you erase the first one, the vector has to perform 99 pointer copies.

So, does it work? Yeah it does:

  #include <vector>#include <iostream>using std::vector;using std::cout;using std::endl;class Task // empty class this time{};int main (){	Task* t1 = new Task;	Task* t2 = new Task;	cout << "t1 = " << t1 << ", t2 = " << t2 << endl;	vector <Task*> *ready = new vector<Task*>;	ready->push_back (t1);	ready->push_back (t2);	cout << "ready->size () = " << ready->size () << endl		<< "ready->at(0) = " << ready->at(0) << endl		<< "ready->at(1) = " << ready->at(1) << endl;	ready->erase (ready->begin ());	cout << "ready->size () = " << ready->size () << endl		<< "ready->at(0) = " << ready->at(0) << endl;	delete ready;	delete t2;	delete t1;	return 0;}  

Output:

t1 = 007D0CA0, t2 = 007D0C70ready->size () = 2ready->at(0) = 007D0CA0ready->at(1) = 007D0C70ready->size () = 1ready->at(0) = 007D0C70 

You should see something like this happen if you try it on your machine. How is it that you''re convinced that the erase is not working? In other words, what information are you getting from the debugger that leads you to believe the first element is not erased?

I just wanted to add that std::queue is built using std::vector std::queue is basically what they call an "adapter" template class.

Dire Wolf
direwolf@digitalfiends.com