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;

[Jeffrey Carter]

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

[Niklas Holsti]

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

Out of curiosity, how does it fail? Exception?

Post by Simon Wright
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 :-)

Post by Simon Wright
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.

Post by Simon Wright
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;

[Simon Wright]

Thanks to all for your comments.

Post by Niklas Holsti

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

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

Post by Niklas Holsti
It seems that what you are doing is at least unspecified and may be
- 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!

Post by Niklas Holsti

Post by Simon Wright
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;

[Georg Bauhaus]

Post by Simon Wright

Post by Niklas Holsti

Post by Simon Wright
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.

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.

[Simon Wright]

Post by Georg Bauhaus

Post by Simon Wright

Post by Niklas Holsti

Post by Simon Wright
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.

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

[Dmitry A. Kazakov]

Post by Simon Wright
Is there a proper idiom for doing this job?

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