Constant Time std::vector Item Removal
Eddie
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! ]
Bo Persson
> 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
Nick Hounsome
> 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
Anders Dalvander
> 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
Jeffrey Schwab
> 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.
Pete Becker
>
> 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)
Jens Schmidt
> 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
red floyd
> 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
Stephen Howe
>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
Ike Naar
Jeffrey Schwab <je...@schwabcenter.com> wrote:
>On 7/15/10 11:52 AM, Eddie wrote:
>> vec[pos] = vec[ vec.size() -1 ];
>
>vec[pos] = vec.last();
You probably meant
vec[pos] = vec.back();
but, indeed, keeping things simple is good practice.
hak...@gmail.com
> 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.
bf
> 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
Seungbeom Kim
> 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
Mathias Gaunard
> 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.
--
Seungbeom Kim
> On Jul 16, 11:58 pm, Seungbeom Kim <musip...@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
Jeffrey Schwab
> vec[pos] = std::move(vec.back());
What's in vec.back() after that statement? (I'm still coming to terms
with move semantics.)
--
Seungbeom Kim
> On 7/20/10 10:00 AM, Seungbeom Kim wrote:
>
>> vec[pos] = std::move(vec.back());
>
> What's in vec.back() after that statement? (I'm still coming to terms
> with move semantics.)
That depends on the value_type of the vector. If it is a simple type
(such as int) or if it doesn't have a move assignment operator, std::move
has no effect, the above assignment is simply a copy, and vec.back()
remains unchanged. If it owns some resource and has a move assignment
operator (such as std::string), the assignment is a move, which takes
the resource from vec.back() and gives it to vec[pos], causing the latter
to release what it previously owned. Then vec.back() is a valid but "null"
object which probably doesn't own any resource; the exact semantics is
defined by the move constructor. For example, vec.back() could be a std::
string object with a null pointer inside, representing an empty string.
--
Seungbeom Kim
Bo Persson
> On 7/20/10 10:00 AM, Seungbeom Kim wrote:
>
>> vec[pos] = std::move(vec.back());
>
> What's in vec.back() after that statement? (I'm still coming to
> terms with move semantics.)
An object that we don't care much about, in a valid but not very
interesting state. Perhaps similar to a default constructed element.
The move assignment operator (if there is one) "steals" the internals
of the object, leaving it as an empty shell. Possibly to be destroyed
soon, or assigned a new value.
Bo Persson
Mathias Gaunard
> On 7/20/10 10:00 AM, Seungbeom Kim wrote:
>
> > vec[pos] = std::move(vec.back());
>
> What's in vec.back() after that statement? (I'm still coming to terms
> with move semantics.)
It's not clearly stated by the standard what operations must be valid
on a moved-from object.
It seems that destruction and all forms of copy construction and
assignment must remain valid, which means move semantics are not
really overhead-free, since all these primitives will need to check
for the moved-from state.
Bo Persson
> On Jul 31, 3:25 am, Jeffrey Schwab <j...@schwabcenter.com> wrote:
>> On 7/20/10 10:00 AM, Seungbeom Kim wrote:
>>
>>> vec[pos] = std::move(vec.back());
>>
>> What's in vec.back() after that statement? (I'm still coming to
>> terms with move semantics.)
>
> It's not clearly stated by the standard what operations must be
> valid on a moved-from object.
It must be in a "valid state", whatever that means for the object.
> It seems that destruction and all forms of copy construction and
> assignment must remain valid, which means move semantics are not.
> really overhead-free, since all these primitives will need to check
> for the moved-from state.
No, they will not have to check for any other states than they already
have. The move assignment and move copy construction will have to
leave the object in some valid state that is cheap to set, possibly
looking like it was just default constructed.
There will be some "overhead" in the move operations, but cheaper than
copy construction or copy assignment (otherwise you would just use
those). For example, with a std::vector the move constructor would set
the moved-from object to contains a null pointer, and have zero size
and capacity.
Bo Persson
Falk Tannhäuser
> On Jul 31, 3:25 am, Jeffrey Schwab<j...@schwabcenter.com> wrote:
>> On 7/20/10 10:00 AM, Seungbeom Kim wrote:
>>
>>> vec[pos] = std::move(vec.back());
>>
>> What's in vec.back() after that statement? (I'm still coming to terms
>> with move semantics.)
>
> It's not clearly stated by the standard what operations must be valid
> on a moved-from object.
> It seems that destruction and all forms of copy construction and
> assignment must remain valid, which means move semantics are not
> really overhead-free, since all these primitives will need to check
> for the moved-from state.
I don't think there will be a special "moved-from" state in real-world implementations. I would rather expect one of the following:
(1) the moved-from object retains its old value,
(2) the moved-from object obtains the old value of the moved-to object (i.e. move is implemented as swap), or
(3) the moved-from object becomes empty (i.e. as if it was default-constructed).
Depending on implementation details of the type in question, what actually happens may depend on the current object value. For
example, in case of std::string with short-string optimization in effect, I wouldn't be too surprised to see (1) for short
strings, (2) for long strings in case of move assignment and (3) for long strings in case of move construction.
Of course, as long as you only do things you are supposed to with the moved-from object (as destruct or re-assign it), all this
doesn't really matter.
Falk
Mathias Gaunard
> No, they will not have to check for any other states than they already
> have.
My point is that you will need to introduce an extra "empty" state in
order to make use of move semantics, and that state may require
additional branches in each of the object primitives.
nm...@cam.ac.uk
=?ISO-8859-1?Q?Falk_Tannh=E4user?= <clcppm...@this.is.invalid> wrote:
>
>I don't think there will be a special "moved-from" state in real-world
>implementations. I would rather expect one of the following:
>(1) the moved-from object retains its old value,
>(2) the moved-from object obtains the old value of the moved-to object
(i.e. move is implemented as swap), or
>(3) the moved-from object becomes empty (i.e. as if it was default-
>constructed)
Such objects certainly exist, and are unavoidable for a few requirements.
Any that contain context- or location-dependent data are likely to have
such properties - e.g. the context gets nullified on a move.
My understanding of C++ is that it implicitly assumes that objects do
NOT have such properties, but that is based primarily on reading the
actual wording and not being able to make it self-consistent if they
do. However, I can see no explicit wording one way or the other.
Regards,
Nick Maclaren.
Seungbeom Kim
>
> I don't think there will be a special "moved-from" state in real-world implementations. I would rather expect one of the following:
> (1) the moved-from object retains its old value,
> (2) the moved-from object obtains the old value of the moved-to object (i.e. move is implemented as swap), or
> (3) the moved-from object becomes empty (i.e. as if it was default-constructed).
>
> Depending on implementation details of the type in question, what actually happens may depend on the current object value. For
> example, in case of std::string with short-string optimization in effect, I wouldn't be too surprised to see (1) for short
> strings, (2) for long strings in case of move assignment and (3) for long strings in case of move construction.
> Of course, as long as you only do things you are supposed to with the moved-from object (as destruct or re-assign it), all this
> doesn't really matter.
I'm not sure if it doesn't violate anything when (2) is used, i.e. when
y = std::move(x);
doesn't (immediately) release any resource that y previously held.
I don't really know, though it looks somewhat suspicious.
(Of course, in the original context where it is used with std::remove(),
it won't make much difference eventually.)
--
Seungbeom Kim
Felipe Magno de Almeida
> On Aug 2, 1:10 am, "Bo Persson" <b...@gmb.dk> wrote:
>
>> No, they will not have to check for any other states than they already
>> have.
>
> My point is that you will need to introduce an extra "empty" state in
> order to make use of move semantics, and that state may require
> additional branches in each of the object primitives.
IIUC, You don't if you implement move as swap.
> --
Regards,
--
Felipe Magno de Almeida
Bo Persson
> On Aug 2, 1:10 am, "Bo Persson" <b...@gmb.dk> wrote:
>
>> No, they will not have to check for any other states than they
>> already have.
>
> My point is that you will need to introduce an extra "empty" state
> in order to make use of move semantics, and that state may require
> additional branches in each of the object primitives.
Many objects already have an empty state, like the one they get from a
default constructor. If it doesn't, the move operations can leave the
object in an non-empty state. The only requrement is that the object
remains in a valid state. You don't have to invent a special
moved-from state if that is expensive.
Bo Persson
Seungbeom Kim
> Mathias Gaunard wrote:
>> On Aug 2, 1:10 am, "Bo Persson" <b...@gmb.dk> wrote:
>>
>>> No, they will not have to check for any other states than they
>>> already have.
>>
>> My point is that you will need to introduce an extra "empty" state
>> in order to make use of move semantics, and that state may require
>> additional branches in each of the object primitives.
>
> Many objects already have an empty state, like the one they get from a
> default constructor. If it doesn't, the move operations can leave the
> object in an non-empty state. The only requrement is that the object
> remains in a valid state. You don't have to invent a special
> moved-from state if that is expensive.
Right. You don't even have to change the object, in which case a move is
identical to a copy. Most likely it is when the object doesn't own
a resource which you allocate and get a handle for, e.g. dynamically
allocated memory, files, sockets, etc. For example:
struct point
{
double coordinates[3];
double mass;
// ...
};
you just copy the values, and don't even have to reset the original.
However, if you don't have to change the source object, you probably
don't want to bother to define a move constructor, because the copy
constructor does the same thing and will be used in place of the move
constructor if it is not defined. And you often don't even have to define
the copy constructor operator, because the default copy constructor will
just work fine.
So, when you want to define a move constructor, it is when the object owns
a resource, and the copy constructor has to allocate another resource so
that both objects maintain ownership to their respective resources, but
the point of the move constructor is that you don't have to allocate
another resource but can just "steal" the existing one. And you have to
"reset" the source object somehow because it has lost the ownership.
# For every occurrence of "constructor" above, you can substitute
"assignment operator" and everything still holds. It is just too
tedious to write "constructor/assignment operator" each time. :(
--
Seungbeom Kim