Deleting elements from a Vector

Deleting elements from a Vector

[Simon Wright]

I need to remove some of the elements from a vector, depending on the
element. I have the code below, which works for GNAT, but which seems
distinctly dodgy; in particular, it fails if the last Element is
negative and therefore gets deleted.

The Booch Components have

   procedure Delete_Item_At (It : in out Iterator) is abstract;

(an Iterator is very similar to a Cursor) which is defined to leave the
Iterator designating the 'next' Element (i.e., the one, is any, you
would have reached by applying Next to the original Iterator). But I
don't see any such promise for the Containers.

Is there a proper idiom for doing this job? Should I maybe go over the
Vector in reverse order and use the version of Delete that uses the
index?

with Ada.Containers.Vectors;
with Ada.Text_IO; use Ada.Text_IO;
procedure Deleting_From_Queue is
   package Vectors is new Ada.Containers.Vectors (Positive, Integer);
   V : Vectors.Vector;
begin
   V.Append (1);
   V.Append (-1);
   V.Append (2);
   V.Append (-2);
   V.Append (3);
   declare
      C : Vectors.Cursor := V.First;
      D : Vectors.Cursor;
      use type Vectors.Cursor;
   begin
      while C /= Vectors.No_Element loop
         if Vectors.Element (C) < 0 then
            Put_Line ("deleting element " & Vectors.Element (C)'Img);
            D := C;
            V.Delete (D);  -- D -> No_Element
         else
            Put_Line ("skipping element " & Vectors.Element (C)'Img);
            Vectors.Next (C);
         end if;
      end loop;
   end;
   Put_Line ("length now " & V.Length'Img);
end Deleting_From_Queue;

Re: Deleting elements from a Vector

[Jeffrey Carter]

On 04/19/2015 01:27 PM, Simon Wright wrote:
> I need to remove some of the elements from a vector, depending on the
> element. I have the code below, which works for GNAT, but which seems
> distinctly dodgy; in particular, it fails if the last Element is
> negative and therefore gets deleted.
> 
> Is there a proper idiom for doing this job? Should I maybe go over the
> Vector in reverse order and use the version of Delete that uses the
> index?
> 
> with Ada.Containers.Vectors;
> with Ada.Text_IO; use Ada.Text_IO;
> procedure Deleting_From_Queue is
>    package Vectors is new Ada.Containers.Vectors (Positive, Integer);
>    V : Vectors.Vector;
> begin
>    V.Append (1);
>    V.Append (-1);
>    V.Append (2);
>    V.Append (-2);
>    V.Append (3);
>    declare
>       C : Vectors.Cursor := V.First;
>       D : Vectors.Cursor;
>       use type Vectors.Cursor;
>    begin
>       while C /= Vectors.No_Element loop
>          if Vectors.Element (C) < 0 then
>             Put_Line ("deleting element " & Vectors.Element (C)'Img);
>             D := C;
>             V.Delete (D);  -- D -> No_Element
>          else
>             Put_Line ("skipping element " & Vectors.Element (C)'Img);
>             Vectors.Next (C);
>          end if;
>       end loop;
>    end;
>    Put_Line ("length now " & V.Length'Img);
> end Deleting_From_Queue;

Seems to me that in the general case a cursor becomes invalid after the element
it designates is deleted from the container through another cursor. For most
such containers I'd think doing Next on the cursor before the Delete would work.
However, since a Vector is an unbounded array, the cursor may just be an index,
in which case that wouldn't work. I'd advise always using a Vector as if it were
an array, and iterate over it using indices.

-- 
Jeff Carter
"He didn't get that nose from playing ping-pong."
Never Give a Sucker an Even Break
110

Re: Deleting elements from a Vector

[Niklas Holsti]

On 15-04-19 23:27 , Simon Wright wrote:
> I need to remove some of the elements from a vector, depending on the
> element. I have the code below, which works for GNAT, but which seems
> distinctly dodgy; in particular, it fails if the last Element is
> negative and therefore gets deleted.

Out of curiosity, how does it fail? Exception?

> The Booch Components have
>
>     procedure Delete_Item_At (It : in out Iterator) is abstract;
>
> (an Iterator is very similar to a Cursor) which is defined to leave the
> Iterator designating the 'next' Element (i.e., the one, is any, you
> would have reached by applying Next to the original Iterator). But I
> don't see any such promise for the Containers.

I could not find such promises. There is a promise that the cursor used 
to delete the element becomes No_Element, as the comment in your code 
(quoted below) says.

It seems that what you are doing is at least unspecified and may be 
erroneous:

- RM A.18.2(251/3) says that any other cursor that designates (or 
designated) the deleted element becomes invalid through the deletion.

- RM A.18.2(2522/2) says that any use of an invalid cursor in "=" or 
Has_Element has unspecified result, and using the cursor with any other 
subprogram from Containers.Vectors is erroneous execution.

So, after the V.Delete (D) in the code below, the cursor C is invalid, 
and on the next loop iteration the condition C /= Vectors.No_Element has 
unspecified result, and the possibly executed Vectors.Element (C) is 
erroneous execution. So don't do that :-)

> Is there a proper idiom for doing this job? Should I maybe go over the
> Vector in reverse order and use the version of Delete that uses the
> index?

Indeed that seems safer. Note also RM A.18.2(240/2..243/2) for the 
definition and properties of an "ambiguous" cursor. This also suggests 
traversing the vector in reverse index order.

> with Ada.Containers.Vectors;
> with Ada.Text_IO; use Ada.Text_IO;
> procedure Deleting_From_Queue is
>     package Vectors is new Ada.Containers.Vectors (Positive, Integer);
>     V : Vectors.Vector;
> begin
>     V.Append (1);
>     V.Append (-1);
>     V.Append (2);
>     V.Append (-2);
>     V.Append (3);
>     declare
>        C : Vectors.Cursor := V.First;
>        D : Vectors.Cursor;
>        use type Vectors.Cursor;
>     begin
>        while C /= Vectors.No_Element loop
>           if Vectors.Element (C) < 0 then
>              Put_Line ("deleting element " & Vectors.Element (C)'Img);
>              D := C;
>              V.Delete (D);  -- D -> No_Element
>           else
>              Put_Line ("skipping element " & Vectors.Element (C)'Img);
>              Vectors.Next (C);
>           end if;
>        end loop;
>     end;
>     Put_Line ("length now " & V.Length'Img);
> end Deleting_From_Queue;
>


-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Deleting elements from a Vector

[Simon Wright]

Thanks to all for your comments.

Niklas Holsti <niklas.holsti@tidorum.invalid> writes:

> On 15-04-19 23:27 , Simon Wright wrote:
>> I need to remove some of the elements from a vector, depending on the
>> element. I have the code below, which works for GNAT, but which seems
>> distinctly dodgy; in particular, it fails if the last Element is
>> negative and therefore gets deleted.
>
> Out of curiosity, how does it fail? Exception?

$ ./deleting_from_queue
skipping element  1
deleting element -1
skipping element  2
deleting element -2
skipping element  3
deleting element -3

raised CONSTRAINT_ERROR : Position cursor is out of range

> It seems that what you are doing is at least unspecified and may be
> erroneous:
>
> - RM A.18.2(251/3) says that any other cursor that designates (or
> designated) the deleted element becomes invalid through the deletion.
>
> - RM A.18.2(2522/2) says that any use of an invalid cursor in "=" or
> Has_Element has unspecified result, and using the cursor with any
> other subprogram from Containers.Vectors is erroneous execution.
>
> So, after the V.Delete (D) in the code below, the cursor C is invalid,
> and on the next loop iteration the condition C /= Vectors.No_Element
> has unspecified result, and the possibly executed Vectors.Element (C)
> is erroneous execution. So don't do that :-)

I won't!

>> Is there a proper idiom for doing this job? Should I maybe go over the
>> Vector in reverse order and use the version of Delete that uses the
>> index?
>
> Indeed that seems safer. Note also RM A.18.2(240/2..243/2) for the
> definition and properties of an "ambiguous" cursor. This also suggests
> traversing the vector in reverse index order.

Like this:

   for J in reverse 1 .. V.Last_Index loop
      if V (J) < 0 then
         Put_Line ("deleting element " & Integer'Image (V (J)));
         V.Delete (J);
      else
         Put_Line ("skipping element " & Integer'Image (V (J)));
      end if;
   end loop;

Re: Deleting elements from a Vector

[Georg Bauhaus]

On 20.04.15 09:56, Simon Wright wrote:

>>> Is there a proper idiom for doing this job? Should I maybe go over the
>>> Vector in reverse order and use the version of Delete that uses the
>>> index?
>>
>> Indeed that seems safer. Note also RM A.18.2(240/2..243/2) for the
>> definition and properties of an "ambiguous" cursor. This also suggests
>> traversing the vector in reverse index order.
>
> Like this:
>
>     for J in reverse 1 .. V.Last_Index loop
>        if V (J) < 0 then
>           Put_Line ("deleting element " & Integer'Image (V (J)));
>           V.Delete (J);
>        else
>           Put_Line ("skipping element " & Integer'Image (V (J)));
>        end if;
>     end loop;

+1; also, as this entails sliding, copying to a new vector and
dumping the old seems another option that prevents any tampering.

Re: Deleting elements from a Vector

[Simon Wright]

Georg Bauhaus <bauhaus@futureapps.invalid> writes:

> On 20.04.15 09:56, Simon Wright wrote:
>
>>>> Is there a proper idiom for doing this job? Should I maybe go over the
>>>> Vector in reverse order and use the version of Delete that uses the
>>>> index?
>>>
>>> Indeed that seems safer. Note also RM A.18.2(240/2..243/2) for the
>>> definition and properties of an "ambiguous" cursor. This also suggests
>>> traversing the vector in reverse index order.
>>
>> Like this:
>>
>>     for J in reverse 1 .. V.Last_Index loop
>>        if V (J) < 0 then
>>           Put_Line ("deleting element " & Integer'Image (V (J)));
>>           V.Delete (J);
>>        else
>>           Put_Line ("skipping element " & Integer'Image (V (J)));
>>        end if;
>>     end loop;
>
> +1; also, as this entails sliding, copying to a new vector and
> dumping the old seems another option that prevents any tampering.

Profiling needed! Thanks for the idea ...

Re: Deleting elements from a Vector

[Dmitry A. Kazakov]

On Sun, 19 Apr 2015 21:27:50 +0100, Simon Wright wrote:

> Is there a proper idiom for doing this job?

Using an indices instead of iterators. Iterators are considered harmful.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de