Prev: Distinguish between pointers created with 'new' and created with references.
Next: Distinguish between pointers created with 'new' and created with references.
From: Pete Becker on 16 Jul 2010 01:19
On 2010-07-15 15:46:12 -0400, Nick Hounsome said:

>
> 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

It's even a bit more subtle than the description above. remove doesn't
reorder, it overwrites and leaves the dead stuff at the end untouched:

iterator current = first;
while (first != last)
{
if (!(*first == to_remove))
*current++ = *first;
++first;
}
return current;

(In real life, the algorithm would scan for the first non-matching
value instead of copying each of the first values on top of itself, but
that's just efficiency. <g>)

So if you were removing all the 2's from { 1, 2, 3, 2, 4, 2, 5} you'd
end up with { 1, 3, 4, 5, 4, 2, 5 } and a returned iterator pointing to
the fifth element.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Jens Schmidt on 16 Jul 2010 01:18
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:
>
> 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?

This method depends on the index where an element is stored to have
no meaning. Also the order of the elements is changed.

If you didn't choose vector for some other reason like contiguous
storage or calculation of index positions, you may want to use some
other data structure, like unordered_map.

As the choice of structure and algorithm depends on a lot more
parameters, I can't say more here. But your method is sensible in
a lot of cases.
--
Greetings,
Jens Schmidt


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: red floyd on 16 Jul 2010 01:18
On Jul 15, 8:52 am, 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 );
>

That should be fine. And your "removed" object will be destroyed per
23.2.4.2/6


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Stephen Howe on 16 Jul 2010 01:18
>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?

No problem. But the original std::remove() algorithm is stable, in that if
the erase-remove idiom is applied whatever is
deleted, the remaining elements are stable (as in stable_sort,
stable_partition).

Your algorithm is not stable, but that is no bad thing, you may not need it.
I would be tempted to write this as

swap(vec[pos], vec.back());
vec.pop_back();

assuming the container is not empty.

Stephen Howe

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Ike Naar on 16 Jul 2010 01:29
In article <HNqdnUyvzP0npqLRnZ2dnUVZ_judnZ2d(a)giganews.com>,
Jeffrey Schwab <jeff(a)schwabcenter.com> wrote:
>On 7/15/10 11:52 AM, Eddie wrote:
>> vec[pos] = vec[ vec.size() -1 ];
>
>I prefer:
>vec[pos] = vec.last();

You probably meant

vec[pos] = vec.back();

but, indeed, keeping things simple is good practice.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6
Prev: Distinguish between pointers created with 'new' and created with references.
Next: Distinguish between pointers created with 'new' and created with references.