Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #44868 > unrolled thread

best way to remove std::vector member

Back to article view | Back to comp.lang.c++

Contents

  best way to remove std::vector member Lynn McGuire <lynnmcguire5@gmail.com> - 2016-09-05 13:56 -0500
    Re: best way to remove std::vector member Paavo Helde <myfirstname@osa.pri.ee> - 2016-09-05 22:43 +0300
    Re: best way to remove std::vector member Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-09-05 21:11 +0100
    Re: best way to remove std::vector member Vir Campestris <vir.campestris@invalid.invalid> - 2016-09-05 21:28 +0100
      Re: best way to remove std::vector member Marcel Mueller <news.5.maazl@spamgourmet.org> - 2016-09-05 23:17 +0200
        Re: best way to remove std::vector member Vir Campestris <vir.campestris@invalid.invalid> - 2016-09-07 20:55 +0100
    Re: best way to remove std::vector member Juha Nieminen <nospam@thanks.invalid> - 2016-09-06 06:14 +0000
    Re: best way to remove std::vector member Luca Risolia <luca.risolia@linux-projects.org> - 2016-09-06 11:16 +0200
      Re: best way to remove std::vector member Öö Tiib <ootiib@hot.ee> - 2016-09-06 07:16 -0700
        Re: best way to remove std::vector member Luca Risolia <luca.risolia@linux-projects.org> - 2016-09-23 14:38 +0200
      Re: best way to remove std::vector member Lynn McGuire <lynnmcguire5@gmail.com> - 2016-09-06 12:30 -0500
        Re: best way to remove std::vector member Paavo Helde <myfirstname@osa.pri.ee> - 2016-09-06 21:32 +0300
    Re: best way to remove std::vector member mark <mark@invalid.invalid> - 2016-09-08 15:58 +0200
      Re: best way to remove std::vector member Lynn McGuire <lynnmcguire5@gmail.com> - 2016-09-08 12:45 -0500
        Re: best way to remove std::vector member mark <mark@invalid.invalid> - 2016-09-08 21:59 +0200
          Re: best way to remove std::vector member Lynn McGuire <lynnmcguire5@gmail.com> - 2016-09-08 15:25 -0500
          Re: best way to remove std::vector member Victor Bazarov <v.bazarov@comcast.invalid> - 2016-09-09 08:09 -0400
            Re: best way to remove std::vector member mark <mark@invalid.invalid> - 2016-09-09 17:06 +0200
              Re: best way to remove std::vector member Victor Bazarov <v.bazarov@comcast.invalid> - 2016-09-09 11:22 -0400
                Re: best way to remove std::vector member mark <mark@invalid.invalid> - 2016-09-09 20:33 +0200
                  Re: best way to remove std::vector member Victor Bazarov <v.bazarov@comcast.invalid> - 2016-09-09 16:07 -0400
    Re: best way to remove std::vector member Kan <fcantoro@nospam.it> - 2016-09-12 18:26 +0200

Page 1 of 2  [1] 2  Next page →

#44868 — best way to remove std::vector member

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

[toc] | [next] | [standalone]

#44872

On 5.09.2016 21: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:
>
> 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;
>          }
>      }
> }

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

Cheers
Paavo

[toc] | [prev] | [next] | [standalone]

#44873

Lynn McGuire <lynnmcguire5@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.

[toc] | [prev] | [next] | [standalone]

#44876

On 05/09/2016 19: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:
>
> 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;
>         }
>     }
> }
>

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

[toc] | [prev] | [next] | [standalone]

#44881

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

[toc] | [prev] | [next] | [standalone]

#44935

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

[toc] | [prev] | [next] | [standalone]

#44895

Lynn McGuire <lynnmcguire5@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: news@netfront.net ---

[toc] | [prev] | [next] | [standalone]

#44897

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.

[toc] | [prev] | [next] | [standalone]

#44899

On Tuesday, 6 September 2016 12:16:35 UTC+3, Luca Risolia  wrote:
> 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.

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. ;-)

[toc] | [prev] | [next] | [standalone]

#45126

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

[toc] | [prev] | [next] | [standalone]

#44903

On 9/6/2016 4:16 AM, Luca Risolia wrote:
> 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.

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

[toc] | [prev] | [next] | [standalone]

#44911

On 6.09.2016 20:30, Lynn McGuire wrote:
> On 9/6/2016 4:16 AM, Luca Risolia wrote:
>> 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.
>
> 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);
>          }
>      }
> }

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

[toc] | [prev] | [next] | [standalone]

#44944

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.

[toc] | [prev] | [next] | [standalone]

#44947

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

[toc] | [prev] | [next] | [standalone]

#44950

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.

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

[toc] | [prev] | [next] | [standalone]

#44951

On 9/8/2016 2: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.
>
> ---------------------------------------
> 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.

Thanks,
Lynn

[toc] | [prev] | [next] | [standalone]

#44960

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

[toc] | [prev] | [next] | [standalone]

#44962

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

[toc] | [prev] | [next] | [standalone]

#44964

On 9/9/2016 11:06 AM, mark wrote:
> 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).

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

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

[toc] | [prev] | [next] | [standalone]

#44965

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.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c++

csiph-web