best way to remove std::vector member

[Lynn McGuire]

What is the best way to loop and remove a member of a std::vector instance variable ? The current code is:

std::vector <DataGroup *> owners; is an class instance variable.

int DataItem::removeOwner (DataGroup * ownerDG)
{
int num = owners.size ();

for (int i = 0; i < num; i++)
{
if (owners [i] == ownerDG)
{
owners.erase (owners.begin () + i);
--num;
--i;
}
}
}

Sincerely,
Lynn McGuire

[Paavo Helde]

owners.erase(std::remove(owners.begin(), owners.end(), ownerDG),
owners.end());

Cheers
Paavo

[Ben Bacarisse]

Lynn McGuire <lynnmc...@gmail.com> writes:

> What is the best way to loop and remove a member of a std::vector
> instance variable ?

The loop (possibly correctly) removes all the members of the vector that
are equal to the target.

> The current code is:
>
> std::vector <DataGroup *> owners; is an class instance variable.
>
> int DataItem::removeOwner (DataGroup * ownerDG)
> {
> int num = owners.size ();
>
> for (int i = 0; i < num; i++)
> {
> if (owners [i] == ownerDG)
> {
> owners.erase (owners.begin () + i);
> --num;
> --i;
> }
> }
> }

It looks like you want the erase-remove idiom:

owners.erase(std::remove(owners.begin(), owners.end(), ownerDG),
owners.end());

but you might really want to stop at the first (something your example
does not do).

--
Ben.

[Vir Campestris]

Think carefully about whether you want to use a vector. Erase is
horribly expensive near the beginning of a big vector - it has to copy
the remaining elements down one.

Especially think about it if you're going to remove several scattered items!

OTOH most of the time it's the fastest collection. YMMV.

Andy

[Marcel Mueller]

On 05.09.16 22.28, Vir Campestris wrote:
> Especially think about it if you're going to remove several scattered
> items!

If implemented correctly the performance is not worse than O(n) where n
is the size of the vector after the removal. Assuming that you have to
check each element in the vector there is no significantly better
solution available unless the copy constructor of the elements is quite
expensive.

However, if done carelessly it performs O(n²).

The Java implementation of ArrayList.removeAll or batchRemove shows the
correct implementation of the algorithm including exception safety. (In
contrast the .NET implementation of the same algorithm is buggy.)

> OTOH most of the time it's the fastest collection. YMMV.

Sorted vectors are sometimes a good choice too. E.g. you could order the
pointers by their (arbitrary) value if removals occur quite often. This
reduces the effort to a logarithmic lookup and at most one std::copy
which should evaluate to a native machine instruction for POD types on
many platforms. BTDT.

Of course, insert operations become slower this way. And if you fill a
large vector in random order it will become O(n²) like Bubble Sort.
In this case BTrees are usually a good choice. Unfortunately none of my
preferred languages provide a reasonable BTree implementation in the
class library so I ended up by writing my own one.



Marcel

[Juha Nieminen]

Lynn McGuire <lynnmc...@gmail.com> wrote:
> int num = owners.size ();

size() doesn't return an int!

> for (int i = 0; i < num; i++)
> {
> if (owners [i] == ownerDG)
> {
> owners.erase (owners.begin () + i);
> --num;
> --i;
> }
> }
> }

That's an O(n^2) algorithm, while std::erase() uses an O(n) algorithm.

--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

[Luca Risolia]

On 05/09/2016 20:56, Lynn McGuire wrote:
> What is the best way to loop and remove a member of a std::vector
> instance variable ? The current code is:

As an alternative approach from using std::vector::erase() every time,
consider a way to mark one or more elements in the vector as "unused"
instead.

[Öö Tiib]

One may be able to use something with faster erase than vector or mark
elements "removed" instead of erasing or somehow avoid inserting the
elements (that will be later erased) into container at the first place.

Those solutions are how to think out of the box to solve some actual
problem that we know nothing of, so we can't use those approaches
for to erase elements from vector. ;-)

[Lynn McGuire]

I thought about just marking the pointers as nullptr in the vector. But then I could not use owners.push_back (newOwner) and would
have to search for any nullptr elements first.

I am thinking about reversing the search. That is my normal method and don't know why I did not do it this time. Much safer than
modifying the index variable directly.

std::vector <DataGroup *> owners; is an class instance variable.

int DataItem::removeOwner (DataGroup * ownerDG)
{
int num = owners.size ();

for (int i = num - 1; i >= 0; i--)

{
if (owners [i] == ownerDG)
{
owners.erase (owners.begin () + i);
}
}
}

Thanks,
Lynn

[Paavo Helde]

This is still algorithmically worse (O(N*M)) than std::remove +
std::vector::erase (O(N)) - where M is the typical multiplicity of values.

Cheers
Paavo

[Vir Campestris]

On 05/09/2016 22:17, Marcel Mueller wrote:
> If implemented correctly the performance is not worse than O(n) where n
> is the size of the vector after the removal. Assuming that you have to
> check each element in the vector there is no significantly better
> solution available unless the copy constructor of the elements is quite
> expensive.

In list, however, an erase takes negligible time. Find is a PITA though,
and seek to nth nearly impossible - that's why YMMV.

Andy

[mark]

It doesn't sound like you are using vector functionality. So using a
(unordered) set may be a better choice. It works perfectly fine with
pointers.

[Lynn McGuire]

On 9/8/2016 8:58 AM, mark wrote:
> It doesn't sound like you are using vector functionality. So using a (unordered) set may be a better choice. It works perfectly fine
> with pointers.

????

Thanks,
Lynn

[mark]

Your removeOwner invalidates vector indices. So I don't see you needing
indexed access.

---------------------------------------
std::unordered_set<DataGroup *> owners;

int DataItem::removeOwner (DataGroup * ownerDG) {

// average complexity O(1)
owners.erase(ownerDG);
...
}
---------------------------------------

If you need to support duplicate entries, there is multiset /
unordered_multiset. What you do loose with set / multiset is the
insertion order.

[Lynn McGuire]

Thanks,
Lynn

[Victor Bazarov]

On 9/8/2016 3:59 PM, mark wrote:
> On 2016-09-08 19:45, Lynn McGuire wrote:
>> On 9/8/2016 8:58 AM, mark wrote:
>>> It doesn't sound like you are using vector functionality. So using a
>>> (unordered) set may be a better choice. It works perfectly fine
>>> with pointers.
>>
>> ????
>
> Your removeOwner invalidates vector indices. So I don't see you needing
> indexed access.

Indices cannot be "invalidated". Iterators are invalidated, that's true,
but they are not used anyway. The code as written, functionally sound,
albeit inefficient.

>
> ---------------------------------------
> std::unordered_set<DataGroup *> owners;
>
> int DataItem::removeOwner (DataGroup * ownerDG) {
> // average complexity O(1)
> owners.erase(ownerDG);
> ...
> }
> ---------------------------------------
>
> If you need to support duplicate entries, there is multiset /
> unordered_multiset. What you do loose with set / multiset is the
> insertion order.

V
--
I do not respond to top-posted replies, please don't ask

[mark]

On 2016-09-09 14:09, Victor Bazarov wrote:
> On 9/8/2016 3:59 PM, mark wrote:
>> On 2016-09-08 19:45, Lynn McGuire wrote:
>>> On 9/8/2016 8:58 AM, mark wrote:
>>>> It doesn't sound like you are using vector functionality. So using a
>>>> (unordered) set may be a better choice. It works perfectly fine
>>>> with pointers.
>>>
>>> ????
>>
>> Your removeOwner invalidates vector indices. So I don't see you needing
>> indexed access.
>
> Indices cannot be "invalidated". Iterators are invalidated, that's true,
> but they are not used anyway. The code as written, functionally sound,
> albeit inefficient.

What I mean is that elements shift. Elements after a removed element
don't keep their index. The last index will be completely invalid (going
beyond the end).

[Victor Bazarov]

Yes, and that's why the OP used '--num' and '--i' in the loop body.
Please take another look at the code.

[mark]

On 2016-09-09 17:22, Victor Bazarov wrote:
>>> Indices cannot be "invalidated". Iterators are invalidated, that's
>>> true,
>>> but they are not used anyway. The code as written, functionally sound,
>>> albeit inefficient.
>>
>> What I mean is that elements shift. Elements after a removed element
>> don't keep their index. The last index will be completely invalid (going
>> beyond the end).
>
> Yes, and that's why the OP used '--num' and '--i' in the loop body.
> Please take another look at the code.

I never said his code was wrong. I just stated my assumption that he
probably wasn't getting much use out of vector properties (like being
contiguous, random access) and that an alternate data structure might be
better.

[Victor Bazarov]

I think I see now. You're saying that the choice of the container is
not in harmony with 'removeOwner' function's disruptive effects, i.e.
*if* some other part of the program held onto some indices (to elements
of that vector), 'removeOwner' would break the contract of their
[presumed] invariance. Yes? Thank you.

The OP didn't explain the reasoning for choosing 'std::vector', and I
usually refrain from speculating on the code I can't see. My mistake is
to assume that others do as well.

[Kan]

If you really want to use a vector and a loop, without using std::remove
as suggested, you could also loop with iterator instead of index and use
the return value of std::vector::erase:

int DataItem::removeOwner(DataGroup * ownerDG)
{
for (auto it = owners.begin(); it != owners.end(); )
{
if (*it == ownerDG)
{
it = owners.erase(it);
}
else
{
++it;
}
}
}

[Luca Risolia]

On 06/09/2016 16:16, Öö Tiib wrote:
> Those solutions are how to think out of the box to solve some actual
> problem that we know nothing of, so we can't use those approaches
> for to erase elements from vector. ;-)

The more alternatives the better ;)