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: Hakusa on 16 Jul 2010 01:20 On Jul 15, 11:52 am, Eddie <edwardlee1...(a)gmail.com> wrote: > 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? When i took my first programming class, this was exactly how i was told you delete an element of an array. Relying on the standard all the time, it can be hard to remember such things. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: bf on 16 Jul 2010 01:32 On Jul 15, 5:52 pm, Eddie <edwardlee1...(a)gmail.com> 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: > > 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? As others have said, if the order of the elements in the array is important, this is not a very good idea, but otherwise it's efficient. I usually write it slightly different: vec[pos] = vec.back(); vec.pop_back(); _ /Bjorn -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Seungbeom Kim on 16 Jul 2010 07:58 On 2010-07-16 09:18, Stephen Howe wrote: > I would be tempted to write this as > > swap(vec[pos], vec.back()); > vec.pop_back(); > > assuming the container is not empty. That swap will probably incur three assignments, but is it really necessary (compared to just one in the original post) when the last element is going to be destroyed anyway? My rough guess is that in C++0x, three moves could be more efficient than one copy in some cases, but then I hope we can just write: vec[pos] = std::move(vec.back()); vec.pop_back(); which will be just one move or one copy. -- Seungbeom Kim [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Mathias Gaunard on 18 Jul 2010 05:28 On Jul 16, 11:58 pm, Seungbeom Kim <musip...(a)bawi.org> wrote: > On 2010-07-16 09:18, Stephen Howe wrote: > >> I would be tempted to write this as > >> swap(vec[pos], vec.back()); >> vec.pop_back(); > >> assuming the container is not empty. > > That swap will probably incur three assignments, but is it really > necessary (compared to just one in the original post) when the last > element is going to be destroyed anyway? In the absence of move semantics, swap is the only primitive the user can customize for move-like behaviour. -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Seungbeom Kim on 19 Jul 2010 23:00
On 2010-07-18 13:28, Mathias Gaunard wrote: > On Jul 16, 11:58 pm, Seungbeom Kim <musip...(a)bawi.org> wrote: >> On 2010-07-16 09:18, Stephen Howe wrote: >> >>> I would be tempted to write this as >> >>> swap(vec[pos], vec.back()); >>> vec.pop_back(); >> >>> assuming the container is not empty. >> >> That swap will probably incur three assignments, but is it really >> necessary (compared to just one in the original post) when the last >> element is going to be destroyed anyway? > > In the absence of move semantics, swap is the only primitive the user > can customize for move-like behaviour. So, with the advent of the formal support for move semantics in C++0x, will the method I proposed be better than and recommended over the swap idiom? vec[pos] = std::move(vec.back()); vec.pop_back(); -- Seungbeom Kim [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |