Constant Time std::vector Item Removal
in [C++]
|
Prev: Distinguish between pointers created with 'new' and created with references.
Next: Distinguish between pointers created with 'new' and created with references.
From: Eddie on 15 Jul 2010 00:52 I used to call vector.remove(it+i) to remove the i-th position element in a STL vector, but this causes a O(n) shifting of objects past the deleted item: std::vector<ObjType> vec; ..... // fill with items vec.erase( vec.begin() + pos ); // remove ith pos item Recently, I've been getting good results by simply replacing the soon- to-be-deleted i-th element in the vector by the tail item in the vector, then resizing the vector to originalsize - 1: std::vector<ObjType> vec; ..... // fill with items vec[pos] = vec[ vec.size() -1 ]; vec.resize( vec.size() - 1 ); Just thought I'd share. Anyone have any thoughts on this? -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Bo Persson on 15 Jul 2010 10:43 Eddie wrote: > I used to call vector.remove(it+i) to remove the i-th position > element in a STL vector, but this causes a O(n) shifting of objects > past the deleted item: > > std::vector<ObjType> vec; > .... // fill with items > vec.erase( vec.begin() + pos ); // remove ith pos item > > > > Recently, I've been getting good results by simply replacing the > soon- to-be-deleted i-th element in the vector by the tail item in > the vector, then resizing the vector to originalsize - 1: > > std::vector<ObjType> vec; > .... // fill with items > vec[pos] = vec[ vec.size() -1 ]; > vec.resize( vec.size() - 1 ); > > > Just thought I'd share. Anyone have any thoughts on this? Yes, that would work but produces a slightly different result. If the vector is sorted, for example, the difference could be significant. Bo Persson -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Nick Hounsome on 15 Jul 2010 10:46 On 15 July, 16:52, Eddie <edwardlee1...(a)gmail.com> wrote: > I used to call vector.remove(it+i) to remove the i-th position element > in a STL vector, but this causes a O(n) shifting of objects past the > deleted item: > > std::vector<ObjType> vec; > .... // fill with items > vec.erase( vec.begin() + pos ); // remove ith pos item > > Recently, I've been getting good results by simply replacing the soon- > to-be-deleted i-th element in the vector by the tail item in the > vector, then resizing the vector to originalsize - 1: > > std::vector<ObjType> vec; > .... // fill with items > vec[pos] = vec[ vec.size() -1 ]; > vec.resize( vec.size() - 1 ); > > Just thought I'd share. Anyone have any thoughts on this? That's essentially how you work with std algorithms such as std::remove - They can't actually remove stuff from a collection bacause they don't take the collection as an argument so they just reorder it such that the dead stuff is at the end and return you an iterator to the first 'dead' element. You then use this with collection to actually erase them. e.g. std::vector<int> v; // fill it up somehow v.erase(std::remove(v.begin(), v.end(), 99), v.end()); // really remove all elements with value 99 -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Anders Dalvander on 15 Jul 2010 10:42 On Jul 15, 5:52 pm, Eddie <edwardlee1...(a)gmail.com> wrote: > Just thought I'd share. Anyone have any thoughts on this? You could use vec.back() instead of vec[vec.size() - 1], vec.pop_back() instead of vec.resize(vec.size() - 1), and use std::swap instead of copy-assignment, you'll get this shorter code: std::vector<ObjType> vec; ..... // fill with items std::swap(vec[pos], vec.back()); vec.pop_back(); Regards, Anders Dalvander -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Jeffrey Schwab on 15 Jul 2010 10:44
On 7/15/10 11:52 AM, Eddie wrote: > Recently, I've been getting good results by simply replacing the soon- > to-be-deleted i-th element in the vector by the tail item in the > vector, then resizing the vector to originalsize - 1: Somebody once asked me about this during a job interview, to see whether I would come up with the very solution you've mentioned. I did not come up with the idea (which is clever), but I did get the job. :) I'm surprised there's nothing online about this technique. I hereby propose we call it "tail-tucking." > std::vector<ObjType> vec; > .... // fill with items > vec[pos] = vec[ vec.size() -1 ]; > vec.resize( vec.size() - 1 ); I prefer: vec[pos] = vec.last(); vec.pop_back(); Hard-coded 1s and 0s are insidious. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |