C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  simple vector question          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Guest Posted: Sat Aug 05, 2006 6:16 am    Post subject: simple vector question I have a complex class that I am storing in a vector. I seem to have a memory leak and I think it's because I don't really know how to use vectors properly. Not only that but my code is overly complex. /***************************************************/ class BmTrack { public: BmTrack(); BmTrack(BmDetection* detection, double deltaT, double sigma1, double sigma2, int* track_total); ~BmTrack(); private: int track_num; //track number int track_class; //track classification int track_class2; CvKalman* kf; //kalman filter structure std::vector<double> x; //track locations for each frame std::vector<double> y; double v; //average track velocity double v2; int lane_num; //lane number int track_life; //count down to removal of track CvMat* W; //class membership CvMat* logW; //log for probabililty CvMat* Meas; //measurement history int flag_image; //tells if track image saved IplImage* image; //image of object CvRect bb; //bounding box }; /***************************************************/ /*Tracks*/ typedef std::vector<BmTrack*> BmTrack_vector; class BmTracks { public: BmTracks(); BmTracks(BmDetections* detections, double deltaT, double sigma1, double sigma2, int* track_total); ~BmTracks(); private: BmTrack_vector tracks; CvMat* Sigma_meas; //inverse S for var of measurements int T_frames; //number of frames to track before taking snapshot }; /***************************************************/ I create create the tracks object by a loop for (int i=0; i<num_Tracks; i+=1) { tracks.push_back(new BmTrack(d,deltaT,sigma1,sigma2,track_total)); } The size of the vector is constantly changing by removing elements from within the vector. The way I'm dong it looks something like this. BmTrack* t; for(i=num_tracks-1; i>=0; i-=1) { if(dead_track[i]) { t = tracks.at(i); delete t; tracks.erase(tracks.begin()+i); } } Am I doing something wrong here. I don't have a copy or assignment method defined for BmTrack. And is it a bad idea to create the BmTrack* t variable outside of my loop? Thanks for any help. Brendan [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Alex Guest Posted: Sat Aug 05, 2006 9:05 am    Post subject: Re: simple vector question brendan.morris (AT) gmail (DOT) com wrote: Quote: The size of the vector is constantly changing by removing elements from within the vector. The way I'm dong it looks something like this. BmTrack* t; for(i=num_tracks-1; i>=0; i-=1) { if(dead_track[i]) { t = tracks.at(i); delete t; tracks.erase(tracks.begin()+i); } } Am I doing something wrong here. I don't have a copy or assignment method defined for BmTrack. And is it a bad idea to create the BmTrack* t variable outside of my loop? Thanks for any help. Brendan Brendan, the code above does not look like you have a leak there. However, there are more elegant and efficient ways to achieve what you are trying to do. Something like this would be a better approach: int i = 0; for (std::vector<BmTrack*>::iterator it = tracks.begin(); it != tracks.end(); ++it) { if (i < num_tracks && dead_track[i]) { delete *it; it = tracks.erase(it); } ++i; } However, this can be further optimized, since you have the vector and array in parallel to keep track of "dead" entries. I don't know enough about your code, but I suggest you see if you can get rid of the dead_track array and: - encapsulate dead flag into BmTrack or - turn tracks vector into std::map, so the second pair member would keep track of an entry's "deadness". Alex [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ulrich Eckhardt Guest Posted: Sat Aug 05, 2006 11:32 pm    Post subject: Re: simple vector question brendan.morris (AT) gmail (DOT) com wrote: Quote: class BmTrack { BmTrack(); BmTrack(BmDetection* detection, double deltaT, double sigma1, double sigma2, int* track_total); ~BmTrack(); private: int track_num; //track number int track_class; //track classification int track_class2; CvKalman* kf; //kalman filter structure std::vector<double> x; //track locations for each frame std::vector<double> y; double v; //average track velocity double v2; int lane_num; //lane number int track_life; //count down to removal of track CvMat* W; //class membership CvMat* logW; //log for probabililty CvMat* Meas; //measurement history int flag_image; //tells if track image saved IplImage* image; //image of object CvRect bb; //bounding box }; typedef std::vector<BmTrack*> BmTrack_vector; I have a few problems here: you are passing around pointers in the constructor, but what does that mean? Also, you store pointers as members, what does that mean? There are typically two things that a pointer can mean: 1. ownership 2. reference When ownership is meant, you definitely need a copy constructor and assignment operator, the compiler-generated ones are not sufficient. At the very least, you should declare them as private and not implement them, so they don't get used accidentally. Quote: The size of the vector is constantly changing by removing elements from within the vector. You know that a vector is (mostly) a simple array allocated with new[], right? That means, that when you remove or insert in the middle, surrounding elements have to be moved, making this inefficient. I would normally use a std::list in such cases and, if possible, not use pointers then. Since you always remove a lot of elements in a loop (see below) you could instead copy all elements you want to keep(!) to a new vector and afterwards swap those two. Quote: The way I'm dong it looks something like this. BmTrack* t; for(i=num_tracks-1; i>=0; i-=1) { if(dead_track[i]) { t = tracks.at(i); delete t; tracks.erase(tracks.begin()+i); } } What is 'dead_track'? I guess it is a vector of booleans that marks tracks that can be removed. In that case, you have a logical error here: as soon as you remove an element from 'tracks', the index 'i' in 'dead_tracks' doesn't resemble the index 'i' in 'tracks'! BmTrack_vector tmp; tmp.reserve(tracks.size()); for(...) if(you_want_to_keep(tracks[i])) tmp.push_back(tracks[i]) else delete tracks[i]; tracks.swap(tmp); Quote: Am I doing something wrong here. I don't have a copy or assignment method defined for BmTrack. You are not copying them, as you are using pointers, so this doesn't matter. It is however good practice to have copying and assignment under control, i.e. either implement them or disable them, unless the compiler-generated ones are okay. Quote: And is it a bad idea to create the BmTrack* t variable outside of my loop? Yes, the general rule is to keep the scope of variables as small as possible. BTW: this also applies to loop-variables, which are typically declared in the loop header: for( int i=0; i!=limit; ++i) ... You did that in one loop, but not in the other. In case you need to target a buggy compiler that doesn't get the scope of such vars right, you should still be able to work around it like this: /** Inject another scope for compilers that don't properly scope variables declared in a for loop. */ #if defined(_MSC_VER) && _MSC_VER<1300 # define for if(false){}else for #endif Further, why do you use vector::at() instead of vector::operator[]()? The former does additional bounds-checking on the passed index, but if that is necessary, it means your algorithm is faulty! Uli [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Alf P. Steinbach Guest Posted: Sun Aug 06, 2006 12:04 am    Post subject: Re: simple vector question * brendan.morris (AT) gmail (DOT) com: Quote: I have a complex class that I am storing in a vector. I seem to have a memory leak and I think it's because I don't really know how to use vectors properly. Not only that but my code is overly complex. To reduce or avoid memory leaks: * Replace raw pointers + direct usage of 'delete' with smart pointers (e.g. boost::shared_ptr for objects in collections, std::auto_ptr for transferring ownership). * Replace direct usage of 'new T[n]' with std::vector. * Make sure that remaining objects that do direct memory management are not copied outside your control, by declaring a copy constructor and an assignment operator. You can disable copying by making these operations private or protected. Or you can take charge of copying. * Make sure that objects that are destroyed polymorphically have virtual destructor. * Be clear about responsibilities and object ownership. [snip] Quote: I create create the tracks object by a loop for (int i=0; i<num_Tracks; i+=1) { tracks.push_back(new BmTrack(d,deltaT,sigma1,sigma2,track_total)); } The size of the vector is constantly changing by removing elements from within the vector. The way I'm dong it looks something like this. BmTrack* t; for(i=num_tracks-1; i>=0; i-=1) { if(dead_track[i]) { t = tracks.at(i); delete t; tracks.erase(tracks.begin()+i); } } Am I doing something wrong here. Maybe. The code shown doesn't update the 'dead_track' array: that may bite you if this code is executed repeatedly, as you indicate it is, with 'dead_track' surviving between invocations. Also, the code shown doesn't update the 'num_tracks' variable, which may or may not constitute a bug. Why not use 'tracks.size()' instead? Caching is just optimization: better to achieve correctness first. ;-) Also, but only relevant for efficiency, if the number of tracks to be erased is proportional to the size of the vector, call it n, then this is an O(n2) algorithm, each erase operation being O(n); perhaps it would be better to use a std::list or std::map instead of a std::vector. Quote: I don't have a copy or assignment method defined for BmTrack. Having a copy constructor and an assignment operator can help track down inadvertent copying, or, they can help you to take charge of copying. Quote: And is it a bad idea to create the BmTrack* t variable outside of my loop? Just stylistically. To prevent variables being used in unintended harmful ways, place the declaration of a variable in the innermost scope possible (some advocate that a variable should preferentially be declared where it's first used). However, this particular variable is not needed at all for the code shown, and can simply be removed, and the loop variable 'i' should, stylistically, be declared in the loop, like 'for( std::size_t i = tracks.size()-1; i >= 0; --i )'. -- A: Because it messes up the order in which people normally read text. Q: Why is it such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail? [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Guest Posted: Sun Aug 06, 2006 9:10 am    Post subject: Re: simple vector question {Please don't quote the signature and the banner unless necessary. -mod} Alf P. Steinbach wrote: Quote: To prevent variables being used in unintended harmful ways, place the declaration of a variable in the innermost scope possible (some advocate that a variable should preferentially be declared where it's first used). However, this particular variable is not needed at all for the code shown, and can simply be removed, and the loop variable 'i' should, stylistically, be declared in the loop, like 'for( std::size_t i = tracks.size()-1; i >= 0; --i )'. If tracks is empty, i will be initialized to some huge value (because a size_t is unsigned), and your program will crash. I like to do reverse iteration through a vector by writing this as for (size_t i = tracks.size(); i--; ) { // LOOP BODY ... } The above loop (a) doesn't execute at all if tracks is empty (b) has i == tracks.size()-1 in the loop body for the first iteration (c) has i == 0 in the loop body for the last iteration. [When i reaches zero, the loop terminates; the fact that the i-- causes i to be set to a huge value (since size_t is unsigned) doesn't matter since i promptly goes out of scope. If you don't believe the above code is right, kindly try it out yourself before posting a reply that it's incorrect.] Quote: { Signature and banner stripped. -mod } [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Frederick Gotham Guest Posted: Mon Aug 07, 2006 2:43 am    Post subject: Re: simple vector question Alf P. Steinbach posted: Quote: 'for( std::size_t i = tracks.size()-1; i >= 0; --i )'. There is an actual bug in the example: the comparision i >= 0 will /always/ be true. for(size_t i = tracks.size() - 1; i != (size_t)-1; --i) The cast is unnecessary, although it supresses a compiler warning. -- Frederick Gotham [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Earl Purple Guest Posted: Mon Aug 07, 2006 2:47 am    Post subject: Re: simple vector question Alf P. Steinbach wrote: Quote: To reduce or avoid memory leaks: * Replace raw pointers + direct usage of 'delete' with smart pointers (e.g. boost::shared_ptr for objects in collections, std::auto_ptr for transferring ownership). Good advice. Can also use tr1::shared_ptr which is the same as boost::shared_ptr. If you are going to use boost though anyway there is a ptr_vector class there that you can use. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Dave Harris Guest Posted: Mon Aug 07, 2006 2:49 am    Post subject: Re: simple vector question brendan.morris (AT) gmail (DOT) com () wrote (abridged): Quote: I have a complex class that I am storing in a vector. I seem to have a memory leak and I think it's because I don't really know how to use vectors properly. Not only that but my code is overly complex. I don't think the problem lies in the code you posted. In fact, your code looks better than most of the "improvements" suggested by other posters. Do you understand how arrays work? Vectors aren't much different as far as managing the pointed-to objects are concerned. One thing which does strike me as unclear is the relationship between num_tracks and the size of the vector. You may want to decrement num_tracks whenever you delete a track, or assign tracks.size() to it at the end, or something like that. There needs to be code to update dead_track but I'm guessing you have it and just didn't post it. Quote: Am I doing something wrong here. I don't have a copy or assignment method defined for BmTrack. That's OK as long as the BmTrack objects aren't copied or assigned - and the code you show only copies and assigns pointers to them, not the objects themselves. Quote: And is it a bad idea to create the BmTrack* t variable outside of my loop? It's best to keep the scope of such variables as small as possible, but it won't affect the semantics. Strictly speaking you should remove the item from the vector before deleting it but in practice not everyone bothers. As a more general issue, the biggest problem here is efficiency. Erase inside a loop like that typically takes O(n*n) time. I usually write such code using a separate pointer, counter or iterator: assert( num_tracks == tracks.size() ); int num_alive = 0; for (int i = 0; i < num_tracks; ++i) if (dead_track[i]) { BmTrack *track = tracks[i]; tracks[i] = NULL; // Vector never sees a deleted pointer. delete track; } else tracks[num_alive++] = tracks[i]; tracks.erase( tracks.begin() + num_alive, tracks.end() ); num_tracks = num_alive; assert( num_tracks == tracks.size() ); copying the live tracks to the front of the array and then cleaning up the rear of the vector in one operation after the loop. -- Dave Harris, Nottingham, UK. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Dave Harris Guest Posted: Mon Aug 07, 2006 2:50 am    Post subject: Re: simple vector question aleskx (AT) gmail (DOT) com (Alex) wrote (abridged): Quote: Something like this would be a better approach: int i = 0; for (std::vector<BmTrack*>::iterator it = tracks.begin(); it != tracks.end(); ++it) { if (i < num_tracks && dead_track[i]) { delete *it; it = tracks.erase(it); } ++i; } Except this has two new bugs. The erase() returns an iterator to the next track, which the loop increment then skips over. And after the first erase() the tracks vector is no longer in sync with the dead_track vector. -- Dave Harris, Nottingham, UK. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Alex Guest Posted: Tue Aug 08, 2006 4:12 am    Post subject: Re: simple vector question Dave Harris wrote: Quote: aleskx (AT) gmail (DOT) com (Alex) wrote (abridged): Something like this would be a better approach: int i = 0; for (std::vector<BmTrack*>::iterator it = tracks.begin(); it != tracks.end(); ++it) { if (i < num_tracks && dead_track[i]) { delete *it; it = tracks.erase(it); } ++i; } Except this has two new bugs. The erase() returns an iterator to the next track, which the loop increment then skips over. And after the first erase() the tracks vector is no longer in sync with the dead_track vector. You are right. This would be a proper way to deal with that portion of the code: for (std::vector<BmTrack*>::iterator it = tracks.begin(); it != tracks.end() { if ((*it)->isDead()) { delete *it; it = tracks.erase(it); } else ++it; } The code above assumes implementation of isDead() member function in BmTrack instead of using dead_track array. Alex [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top red floyd Guest Posted: Tue Aug 08, 2006 5:59 am    Post subject: Re: simple vector question Quoth Alex, nevermore: Quote: You are right. This would be a proper way to deal with that portion of the code: for (std::vector<BmTrack*>::iterator it = tracks.begin(); it != tracks.end() { if ((*it)->isDead()) { delete *it; it = tracks.erase(it); } else ++it; } The code above assumes implementation of isDead() member function in BmTrack instead of using dead_track array. std::vector<BmTrack*>::iterator it = std::remove_if( tracks.begin(), tracks.end(), std::mem_fun_ptr(&BmTrack::isDead)); for (std::vector<BmTrack*>::iterator it1 = it; it != tracks.end(); ++it) delete (*it); tracks.erase(it, tracks.end()); That way, you don't have to remember the semantics. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Guest Posted: Tue Aug 08, 2006 6:01 am    Post subject: Re: simple vector question I found my problem and now have happily run my code for a full weekend. It turns out it really wasn't in the code snippets I provided. Thanks for all the suggestions. When I started writing this code I really hadn't used c++ and resorted to more basic c type programming I was more familiar with. There seemed to be quite a few different suggestions. 1 std::lists or some other structure 2 better class management with member functions or variables 3 limiting scope of variables 3 seems easy enough to do. 2 is generally a good idea and something I am moving towards given a little more c++ programming experience. I went with vectors initially because I new I just wanted some way to collect all my tracks. Vectors seemed logical because they are the same as arrays. In any case things seem to work now and the relative slowness of the vector erase is nothing compared with other video processing. Again thanks for all the help. Brendan [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Carl Barron Guest Posted: Tue Aug 08, 2006 9:10 am    Post subject: Re: simple vector question In article <yeQBg.4828$9T3.1423 (AT) newssvr25 (DOT) news.prodigy.net>, red floyd <no.spam (AT) here (DOT) dude> wrote: Quote: Quoth Alex, nevermore: You are right. This would be a proper way to deal with that portion of the code: for (std::vector<BmTrack*>::iterator it = tracks.begin(); it != tracks.end() { if ((*it)->isDead()) { delete *it; it = tracks.erase(it); } else ++it; } The code above assumes implementation of isDead() member function in BmTrack instead of using dead_track array. std::vector<BmTrack*>::iterator it = std::remove_if( tracks.begin(), tracks.end(), std::mem_fun_ptr(&BmTrack::isDead)); for (std::vector<BmTrack*>::iterator it1 = it; it != tracks.end(); ++it) delete (*it); tracks.erase(it, tracks.end()); That way, you don't have to remember the semantics. Ouch!! Most implementations of remove_if that way will cause memory leaks by overwriting pointers removed by ptrs that are wanted without deleteing the removed items. BmTrack * delete_if_dead(BmTrack *p) { if(p->isDead()) { delete p; p = 0; } return p; } std::transform(tracks.begin(),tracks.end(),tracks.begin(),delete_if_dead) ; tracks.erase ( std::remove(tracks.begin(),tracks.end(),(BmTrack *)0), tracks.end() ); is safer, if you don't like walking the same container twice, writing an output_iterator that does the work and copy the vector to 'itself' via the output_iterator, or a for loop to do it. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Dave Harris Guest Posted: Tue Aug 08, 2006 11:07 pm    Post subject: Re: simple vector question cbarron413 (AT) adelphia (DOT) net (Carl Barron) wrote (abridged): Quote: Ouch!! Most implementations of remove_if that way will cause memory leaks by overwriting pointers removed by ptrs that are wanted without deleteing the removed items. The problem is worse than that. Red floyd's code can delete tracks that we wanted to keep, leading to undefined behaviour when they are used. Suppose, for example, tracks contains two pointers and we want to delete the first and keep the second. Remove_if will typically leave both tracks[0] and tracks[1] pointing to the same object. When we delete tracks[1], we lose the object we wanted to keep and tracks[0] continues pointing to it even after the erase(). Remove_if() is very dangerous when used with plain pointers. Partition() is safer and will work here if you reverse the sense of the predicate. It's interesting that so many of the suggestions for this algorithm contained major bugs. -- Dave Harris, Nottingham, UK. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.